离散数学复习知识点

复习知识点： 第1章1． 命题、真命题、假命题 2． 命题符号化（连接词）设P ：天下大雨，Q ：他在室内运动，命题“除非天下大雨，否则他不在室内运动”可符合化为（ D ）A ．Q P ∧⌝B ．Q P →⌝C ．Q P ⌝→⌝D ．Q P ⌝→设P ：只有你通过了大学英语六级考试，Q ：你是英语专业的学生，R ：你可以选修这门课程。

命题“只有你通过了大学英语六级考试而且不是英语专业的学生，才可以选修这门课程”( B )A ．R Q)(P →∧B ．R Q)(P →⌝∧C ．R Q)(P ↔⌝∧D ．R Q)(P ↔∧3． 什么是命题公式 4． 命题公式的等价式5． 利用逻辑等价关系证明下面的等价关系 Q P Q)(P P))(Q Q)((P ∨⇔∧→→∧→证明：6． 用真值表法求命题公式的主析取范式和主合取范式 7． 符号化以下语句，并推证结论的有效性。

有些学生相信所有的老师，任何一个学生都不相信骗子，所以老师都不是骗子。

解：设论述域为全总个体域，S(x)：x 是学生，T(x)：x 是老师，P(x)：x 是骗子，L(x,y)：x 相信y 。

将前提和结论符号化为P(x))x(T(x)y)))L(x,y(P(y)x(S (x)y))),L(x,y(T(y)x(S (x)⌝→∀⇒⌝→∀→∀→∀∧∃（1）y)))L(x,y(T(y)x(S (x)→∀∧∃ P （2）y))L(a,y(T(y)S (a)→∀∧T1，ESQ)(P TQ)(P Q)Q (Q)(P Q Q)(P T)(Q Q)(P P))P ((Q Q)(P Q)(P P)(Q Q)(P Q)(P P)Q (Q)P (Q)(P P))Q (Q)P ((Q)(P P)Q (Q)P (Q)(P P))(Q Q)((P ∨⇔∧∨⇔∨⌝∧∨⇔∨⌝∧⇔∧∨⌝∧⇔∨⌝∧∨⌝∧⇔∧∨⌝∧∨⌝∧⇔∧∨∨⌝⌝∨∨⌝⌝⇔∧∨∨⌝∧∨⌝⌝⇔∧→∨⌝∧∨⌝⇔∧→→∧→（3）S(a) T2，I （4）y))L(a,y(T(y)→∀ T2，I （5）b)L(a,T(b)→T4，US （6）y)))L(x,y(P(y)x(S (x)⌝→∀→∀ P （7）y))L(a,y(P(y)S (a)⌝→∀→ T6，US （8）y))L(a,y(P(y)⌝→∀ T3,7，I （9）b)L(a,P(b)⌝→ T8，US （10）P(b)b)L(a,⌝→ T9，E （11）P(b)T(b)⌝→T5,10，I （12）P(x))x(T(x)⌝→∀T11，UG侦查员在调查了某珠宝店的珠宝失窃案现场以及询问了认证之后，得到以下事实： （1） 是营业员甲或营业员乙作案。

（2） 如果是甲作案，则案发在非营业时间。

（3） 如果乙提供的证词可信，则案发时货柜未上锁。

（4） 如果乙提供的证词不可信，则案发在营业时间。

（5） 货柜在案发时上锁了。

侦查员推断是营业员乙作案，请用命题逻辑判断该推断是否正确。

解：设P ：甲作案；Q ：乙作案；R ：发在营业时间；S 乙的证词可信； T ：案发时货柜未上锁。

由题意可知，前提为：Q P ∨，R P ⌝→，T S →，R S →⌝，T ⌝ 推理过程： （1）T ⌝P （2）T S → P （3）S ⌝T1，2，I （4）R S →⌝ P （5）RT3，4，I （6）R P ⌝→ P （7）P ⌝T5，6，I（8）Q P ∨P（9）Q P →⌝ T8，E （10）QT7，9，I所以Q P ∨，R P ⌝→，T S →，R S →⌝，T ⌝Q ⇒第2章8． 谓词的定义、量词包括： 9． 什么是谓词公式 10． 谓词公式的自由变元、约束变元、辖域 11． 自然语句的符号化：比如：所有的狼都吃人，设T(x)表示为x 是狼，C(x)表示为x 吃人。

C(x))x(T(x)→∀ 12． 判断什么是前束范式，y)H(x,y)yG (x,→∃⌝∀x 是前束范式，Q(x))y)y(P(x,→∀∀x 是前束范式 13．证明xB(x)xA(x)B(x))x(A(x)∃→∀⇔→∃证明：第3章1.集合的元素、集合的基数、集合的子集、集合的运算空集的问题（空集的基数、空集与集合的子集、真子集的关系） 幂集的问题（集合幂集的求法，幂集的基数） 下面那个命题是不正确的是（ A ） A ．∅∈∅B ．∅∈{∅}C ．∅⊆∅D ．∅⊆{∅}下面那个命题是不正确的是（ A ） A ．{∅}⊆∅B ．{∅}⊆{∅}C ．∅⊆{{∅}}D ．∅∈{∅}下列命题中不正确的是（ ） A.x ∈{x}-{{x}}B.{x}⊆{x}-{{x}}C.A={x}∪x,则x ∈A 且x ⊆AD.A-B=∅⇔A=B设P={x|(x+1)2≤4}，Q={x|x 2+16≥5x},则下列选项正确的是（ ） A.P ⊃Q B.P ⊇Q C.Q ⊃PD.Q=P设A={a,{a}}，下列命题错误的是（ B ）)()()()()()())()((B(x))x(A(x)x xB x xA x xB x xA x xB x A x x B x A x ∃→∀⇔∃∨⌝∀⇔∃∨⌝∃⇔∨⌝∃⇔→∃A．{a}∈ρ(A) B．{a}⊆ρ(A) C．{{a}}∈ρ(A) D．{{a}}⊆ρ(A) 在0（D ）∅之间写上正确的符号。

A．= B．⊆C．∈D．∉判断下列命题哪个为真?（C）A．空集只是非空集合的子集B．空集是任何集合的真子集C．A-B=B-A⇒A=B D．若A的一个元素属于B，则A=B判断下列命题哪几个正确？（B ）A．若A∪B＝A∪C，则B＝C B．{a, b}={b, a}C．ρ（A∩B）≠ρ（A）∩ρ（B），（ρ(S)表示S的幂集）D．若A为非空集，则A≠A∪A成立设A={a, b}，B={c}。

求下列集合：（1）A⨯{0, 1}⨯B；（2）B2⨯；（3）(A⨯B)2；（4）ρ (A)⨯A。

解：（1）A⨯{0, 1}⨯B={<a, 0, c>, <a, 1, c>, <b, 0, c>, <b, 1, c>}；（2）B2⨯A={<c, c, a>, <c, c, b>}；（3）(A⨯B)2={<a, c, a, c>, <a, c, b, c>, <b, c, a, c>, <b, c, b, c>}；（4）ρ (A)⨯A={<Ф, a>, <Ф, b>, <{a}, a>, <{a}, b>, <{b}, a>, <{b}, b>, <a, a>, <a, b>}。

关系1. 设A={a,b,c}，则A上的二元关系有23*3或512 个。

2. 集合A={1, 2, …, 10}上的关系R={<x, y>：x+y=10, x, y∈A}，则R 的性质为（B）A．自反的B．对称的C．传递的，对称的D．传递的设A={Ф, {1}, {1, 3}, {1, 2, 3}}，则A上包含关系“⊆”的哈斯图为（C）A．{1,2,3}{1,3}{1}∅B．{1,2,3}{1,3}{1}∅C．{1,2,3}{1,3}{1}∅D．{1,2,3}{1,3}{1}∅集合A上的等价关系的三个性质是自反性、对称性和传递性。

集合A上的偏序关系的三个性质是自反性、反对称性和传递性。

A上的偏序关系≤的Hasse图如下。

（1）下列哪些关系式成立：a≤b，b≤a，c≤e，e≤f，d≤f，c≤f；（2）分别求出下列集合关于≤的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：（a）A；（b）{b, d}；（c）{b, e}；（d）{b, d, e}。

abc def解：（1）b≤a，c≤e，d≤f，c≤f成立；（2）（a）的极大元为a, e, f，极小元为c；无最大元，c是最小元；无上界，下界是c；无上确界，下确界是c。

（b）的极大元为b, d，极小元为b, d；无最大元和最小元；上界是e，下界是c；上确界是e，下确界是c。

（c）的极大元为e，极小元为b；最大元是e，b是最小元；上界是e，下界是b；上确界是e，下确界是b。

（d）的极大元为e，极小元为b,d；最大元是e，无最小元；上界是e，下界是c；上确界是e，下确界是c。

设A={2，3，4}，B={2，4，7，10，12}从A到B的关系},,,{baBbAabaR整除且∈∈><=，试给出R的关系图和关系矩阵，并说明此关系R及其逆关系1R-是否为函数？为什么？解：}12,4,4,4,12,3,12,2,10,2,4,2,2,2{><><><><><><><=R ，则R 的关系图为：R 的关系矩阵为110110*********R M ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦关系R 不是A 到B 的函数， 因为元素2，4的象不唯一 逆关系1R -也不是B 到A 的函数 因为元素7的象不存在． 下列函数是双射的为（A ）。

A ．f : Z →E , f (x) = 2xB ．f : N →N ⨯N, f (n) =<nC ．f : R →Z , f (x) = [x]D ．f : Z →N, f (x) = | x |（注：Z —整数集，E —偶数集， N —自然数集，R —实数集）设Z N E 、、分别为整数集，自然数集，偶数集，则下列函数是双射的为（ A ） A ．f : Z E → , ()2f x x = B ．f : Z E → , ()8f x x =C ．f : Z Z →, ()8f x =D ．f : N N N →⨯, (),1f n n n =<+> 设{,,},{1,2,3}A a b c B ==，则下列关系中能构成A 到B 函数的是（ C ） A ．1{,1,,2,,3}f a a a =<><><> B ．2{,1,,1,,2}f a b b =<><><> C ．4{,1,,1,,1}f a b c =<><><> D ．1{,1,,2,,2,,3}f a a b c =<><><><> 设函数:f B C →，:g A B →都是单射，则:fg A C →（ A ）A ．是单射B ．是满射C ．是双射D ．既非单射又非满射 设函数:f B C →，:g A B →都是满射，则:fg A C →（ B ）A ．是单射B ．是满射C ．是双射D ．既非单射又非满射 设,f g 是自然数集N 上的函数,x x g x x f N x 2)(,1)(,=+=∈∀，则()fg x =21x +，()g f x =2(1)x +．关系F={<x 1,y 1>,<x 2,y 2>,<x 3,y 2>}是函数 （ 对 ） 关系F={<x 1,y 1>,<x 1,y 2>}是函数 （ 错 ） 设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110则G 的边数为( B )．A ．6B ．5C ．4D ．3 已知图G 的邻接矩阵为，则G 有（ D ）．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点，7边设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( D )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的 在自然数集N 上，运算 C 是不可结合的。