离散数学复习要点第一章命题逻辑
一、典型考查点
1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1
2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5
3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5
4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9
5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。
6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15
7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B)
8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。
9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。
注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16
11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。
重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论
文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21
二、强化练习
1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗?
2.下列式子为重言式的是( )
A.P→P∨Q
B.(┐P∧Q)∧(P∨┐Q)
C.┐ (P Q)
D.(P∨Q) (P→Q)
3．下列为两个命题变元P，Q的小项是（）
A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q
4．下列语句中是真命题的是（）
A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的
5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）
A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q）
6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式
7．命题公式?（P∧Q）→R的成真指派是（）
A．000，001，110，B．001，011，101，110，111 C．全体指派D．无
8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
A ．? P ∧Q
B ．P ∧? Q
C ．P →? Q
D ．P ∨? Q
9．下面联结词运算不可交换的是（ ）A ．∧ B ．→ C ．∨ D ．
10下列命题公式不是重言式的是（ ）
A ．Q →（P ∨Q ）
B ．（P ∧Q ）→P
C ．?（P ∧? Q ）∧（? P ∨Q ）
D ．（P →Q ）（? P ∨Q ）
11.设命题变元为P ，Q ，R ，则小项m100=________，大项M010=________。
12.置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以________，记为________规则。
13.请用联结词┐，∧表示联结词∨和联结词 ：________，________。
14．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是________式。
15．命题公式（P ∧Q ）→? P 的成真指派为__________，成假指派为__________。
16.用等值演算求(P →Q)→R 的主合取范式。17.列出(P →(Q ∨R)) (P →Q)的真值表。
19．构造命题公式（（P ∧Q ）→P ）∨R 的真值表。
20．求下列公式的主合取范式和主析取范式：P ∨（? P →（Q ∨（? Q →R ）））
21．构造命题公式（R Q Q P ∧→∨）→P ∧? R 的真值表。
22．求下列公式的主析取范式和主合取范式：（P →（Q ∧R ））∧（? P →（? Q →R ））。
23.用推理方法证明：P ∨Q ，P →R ，Q →S├R ∨S 。
24．构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。
25．构造下面推理的证明。只要A 曾到过受害者房间并且11点以前没离开，A 就犯了谋杀罪。A 曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。所以A 犯了谋杀罪。
离散数学复习要点 第二章谓词逻辑
一、典型考查点
1、基本概念：个体词、个体域、谓词、特性谓词、辖域，详见P27；前束范式详见P36
2、谓词符号化 步骤：①正确理解给定命题。必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。②把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。③找出恰当量词。应注意全称量词(?x)后跟条件式，存在量词(?x)后跟合取式。④用恰当的联结词把给定命题表示出来。详见P30
3、谓词公式类型的判定（永真式、永假式、可满足式） 方法：利用论域翻译成自然语言后进行判断。详见P34
4、自由变元与约束变元的判定 方法：按定义，关键是要看它在A 中是约束出现，还是自由出现，若与量词的指导变元相同，就是约束出现，不同就是自由出现。详见P31。
5、等价式 (1)量词否定等价式：(a)?(?x)A ?(?x)?A(b)?(?x)A ?(?x)?A
(2) 量词辖域缩小或扩大等价式
(a) (?x)(A(x)∧B)?(?x)A(x)∧B (b) (?x)(A(x)∨B)?(?x)A(x)∨B
(c) (?x)(A(x)→B)?(?x)A(x)→B (d) (?x)(B →A(x))?B →(?x)A(x)
(e) (?x)(A(x)∧B)?(?x)A(x)∧B (f) (?x)(A(x)∨B)?(?x)A(x)∨B
(g) (?x)(A(x)→B)?(?x)A(x)→B (h) (?x)(B →A(x))?B →(?x)A(x)。
(3) 量词分配律等价式：
(a) (?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) (b)(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)其中，A(x)，B(x)为有x 自由出现的任何公式。详见P3435
6、蕴含式(a)(?x)A(x)∨(?x)B(x)?(?x)(A(x)∨B(x))
(b) (?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)
(c) (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)
(d) (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)
其中，A(x)和B(x)为含有x 自由出现的任意公式。详见P35
6、前束范式 方法：①把量词全部通过等值演算化到整个谓词公式的前面②把量词前面的┐全部通过德摩根定律化到谓词公式的内部。详见P36
7、推理：方法：演绎（常用格式）、反证法、CP 规则即附加前提等。对于命题逻辑中的所有规则都可用。
特殊规则：(1)量词消去 (简称UI 或US 规则) (?x)A(x)?A(c) (?x)A(x)?A(y) (?x)A(x)?A(c)
量词产生规则(简称EG 或UG 规则) A(c)?(?y)A(y) A(x)?(?y)A(y) 详见P38
二、强化练习
1.下列式子不是谓词合式公式的是( )
A.(?x)(P(x)→(?x)(Q(x) ∧A(x ，y)))
B.(?x)∧(?y)∨P(x ，y)
C.(?x)P(x)→R(y)
D.(?x)P(x)∧Q(y ，z)
2.设个体域为实数集，特定元素a=0，函数f(x ，y)=x-y ，特定谓词F(x ，y)为x A.(?x)(?y)F(x ，f(f(x ，y)，y)) B.(?x)(?y)(┐F(f(x ，y)，x)) C.(?x)(?y)(?z)(F(x ，y)→F(f(x ，z)，f(y ，z))) D.(?x)F(f(a ，x)，a) 3.对于公式(?x)(?y)P(x ，y)∨Q(x ，z)∧(?x)P(x ，y)，下列说法正确的是( ) A.x 是自由变元 B.x 是约束变元 C.( ?x)的辖域是P(x ，y)∨Q(x ，z) D.(?x)的辖域是P(x ，y) 4.设论域为{1，2}，与公式(?x)┐A(X)等价的是( ) A. ┐A(1) ∨┐A(2) B . ┐A(1)→┐(A2) C. ┐A(1) ∧┐A(2) D. A(1) →A(2) 5．在公式（x ?）F （x ，y ）→（? y ）G （x ，y ）中变元x 是（ ） A ．自由变元 B ．约束变元 C ．既是自由变元，又是约束变元 D ．既不是自由变元，又不是约束变元 6．下列等价式不正确的是（ ） A ．)(Q )(P ))(Q )(P (x x x x x x x ?∨??∨? B ．)(Q )(P ))(Q )(P (x x x x x x x ?∧??∧? C ．)(Q )(P ))(Q )(P (x x x x x x x ?∨??∨? D ．Q )(P )Q )(P (∧??∧?x x x x 7．设A （x ）:x 是人，B （x ）：x 犯错误，命题“没有不犯错误的人”符号化为（ ） A ．))( B )(A (x x x ∧? B ．?→?)(A (x x ? B （x ）） C ．?))(B )(A (x x x ∧? D ．?∧?)(A (x x ? B(x)) 二、填空题 8.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。 9．（?x ）（?y ）（P （x ，y ）Q （y ，z ））∧?xP （x ，y ）中?x 的辖域为________，?x 的辖域为________。 10．公式（x ?）（F （x ）→G(y)）→(y ?)(H(x)),,(L z y x ∧)中的自由变元为_________，约束变元为__________。 三、综合应用题 11．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。 离散数学复习第三章集合与函数 一、典型考查点 1、基本概念判断：函数的入射、满射、双射及定理、复合运算，详见P72，73，75。幂集、差集、对称差、笛卡尔积，详见P46，47，43，49。全序关系，详见P68.。方法：理解概念即可，按定义的步骤计算。 2、关系的相关概念判断：①特殊关系：若R=?，为空关系；若R=A ?B ，为全域关系。R={ 逆运算，交换每个元的第一、二位元素的位置即 5、等价关系和划分的判断及证明：①等价关系的证明：自反、对称、传递三个性质逐一验证。要注意给出的等价关系的条件的变通。②等价关系与划分一一对应，等价关系的等价类即为确定的划分的分块，即有关系的，划在同一块。划分中凡在同一个分块中的元，都写成满足关系的元，这样写出的关系R就是一个等价关系。 6、相容关系和覆盖的判断：相容关系两个性质：自反和对称，注意：相容关系图的画法省略了自反和对称。覆盖按定义判断即可。详见P61 7、偏序关系与哈斯图：①基本概念：三个性质：自反、反对称和传递；可比，就是有关系，a≤b∨b≤a；盖住，就是直接关系，中间没有第三个元，即若a 8、求偏序关系的特殊元：设 ②若(?x)(x∈B→x≤b)为真，则称b为B的最大元。③若?(?x)(b≠x∧x≤b)为真，则称b为B的极小元。 ④若?(?x)(b≠x∧b≤x)为真，则称b为B的极大元。 根据定义判断时，最小（大）元与极小（大）元是有区别的，最小（大）元是B中最小（大）的元素，它与B中其他元素都可比；而极小（大）元不一定与B中元素都可比，只要没有比它小（大）的元素，它就是极小（大）元。对于有穷集B，极小（大）元一定存在，且可能有多个，但最小（大）元不一定存在，若存在则必唯一。若B中只有一个极小（大）元，则它一定是B的最小（大）元。详见P68 9、求上界下界上确界和下确界：设 ②若(?x)(x∈B→x≤b)为真，则称b为B的上界。③若b是一下界且对每一个B的下界b’有b’≤b，则称b为B的最大下界或下确界，记为glb。④若b是一上界且对每一个B的上界b’有b≤b’，则称b为B的最小上界或上确界，记为lub。 判断时注意，上界下界上确界和下确界是A集合上来找的，B的上界，下界，最小上界，最大下界都可能不存在。若存在，最小上界和最大下界是唯一的。详见P69 二、强化练习 1.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f( ) A.仅是入射B.仅是满射C.是双射D.不是函数 ]2.关系矩阵所对应的关系具有自反性( ) A. ? ? ? ? ? ? ? ? ? ? 1 1 1 1 1 1 B. ? ? ? ? ? ? ? ? ? ? 1 1 1 1 1 C. ? ? ? ? ? ? ? ? ? ? 1 1 1 D. ? ? ? ? ? ? ? ? ? ? 1 1 1 1 3.设R1和R2是集合A上的相容关系，不是相容关系( ) A.R1?R2 B.Rl?R2 C.R1-1 D.Rl R2 4．集合A={1，2，…，10}上的关系R={ 5．若R和S是集合A上的两个关系，则下述结论正确的是（） A．若R和S是自反的，则R∩S是自反的B．若R和S是对称的，则R S是对称的 C．若R和S是反对称的，则R S是反对称的D．若R和S是传递的，则R∪S是传递的 6．R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是t（R）中元素的是（） A．<1，1>B．<1，2>C．<1，3>D．<1，4> 7．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（） A．1∈A B．{1，2，3}?A C．{{4，5}}?A D．?∈A 8．设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（） A．M∩N B．M∪NC．M⊕N D．M-N 9．设A-B=?，则有（）A．B=? B．B≠?C．A?B D．A?B 10．A ，B 是集合，P （A ），P （B ）为其幂集，且A ∩B=?，则P(A)∩P(B)为（ ） A ．? B ．{?} C ．{{?}} D ．{?，{?}} 11．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A 到B 的入射函数的是 A ．f ={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B ．f ={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C ．f ={<1,6>,<2,7>,<4,9>,<3,8>} D ．f ={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} 12．下面关于关系R 的传递闭包t(R)的描述最确切的是（ ） A ．t(R)是包含R 的二元关系 B ．t(R)是包含R 的最小传递关系 C ．t(R)是包含R 的一个传递关系 D ．t(R)是任何包含R 的传递关系 13.设A={l ，2，3，4}，A 上的二元关系R={<1，2>，<3，4>，<4，3>}，S={ 14．设N 是自然数集合，f 和g 是N 到N 的函数，且f （n ）=2n+1，g （n ）=n2，那么复合函数（f f ）（n ）=________（g f ）（n ）=________。 15．设复合函数g f 是从A 到C 的函数，如果g f 是满射，那么________必是满射，如果g f 是入射，那么________必是入射。 16．设A={1，2}，B={2，3}，则A-A=________，A-B=________。 17．设A={1，2}，B={2，3}，则A ⊕A=__________，A ⊕B=__________。 18．设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R 的自反闭包r(R)= _________，对称闭包S （R ）=__________。 19．设f :R →R,f (x)=x2-2,g :R →R,g(x)=x-1,那么复合函数))((x g f =__________，))((x f g =__________。 20．设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A ∪B)=_______,ran(A ∩B)= __________。 18．已知A={{?}，{?，1}}，B={{?，1}，{1}}，计算A ∪B ，A ○+B ，A 的幂集P （A ）。 21．设A={a,b,c,d}，R={，，， 22.设A={2，3，6，12，24，36}，请画出A 上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大元、最大元。 23．设A={1，2，3，4，6，8，12，24}，R 为A 上的整除关系，试画的哈斯图，并求A 中的最大元、最小元、极大元、极小元。 24．若集合A={1，{2，3}}的幂集为P （A ），集合B={{?，2}，{2}}的幂集为P （B ），求 P(A)∩P(B)。 25． X={1 2 3 4}，R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。 （1）画出R 的关系图；（2）写出R 的关系矩阵；（3）说明R 是否具有自反、反自反、对称、传递性质。 26．设A={a,b,c},P(A)是A 的幂集，R 为A 上的包含关系，试给出 27．设R 为N ×N 上的二元关系，对任意, 28.设A={|a ，b ∈Z+，Z+为整数集}，A 上的关系R={<, 29．R 是集合A 上自反和传递的关系，试证明：R R=R 。 离散数学复习第四章代数系统 一、典型考查要点： 1、运算的判断：方法：运算满足封闭性，即运算后产生的象仍在同一个集合中。详见P77 2、运算性质的判断：运算性质：封闭、结合、交换、分配、幂等、吸收、消去 方法：根据定义，在所讨论的集中任取元素，符合定义即可。在运算表中可以判断：1）运算*具有封闭性，当且仅当运算表中的每个元素都属于A 。2）运算*具有可交换性，当且仅当运算表关于主对角线是对称的。3）运算*具有等幂性，当且仅当运算表的主对角线上的每一元素与它所在行（列）的表头元素相同。详见P79 3、代数系统中特殊元：么元（单位元）、零元、逆元 判断方法：根据定义，在所讨论的集中找到特殊元，符合定义即可。在运算表中可以判断：1）A 中关于运算*具有零元，当且仅当该元素所对应的行和列中的元素都与该元素相同。2）A 中关于运算*具有幺元，当且仅当该元素所对应的行和列依次与运算表的行和列相一致。3）设A 中关于运算*具有幺元，a 和b 互逆，当且仅当位于a 所在行和b 所在列的元素及b 所在行和a 所在列的元素都是幺元。详见P80 4、子代数的判定：关键两个条件:B?A, 5、特殊代数系统判定：（G， ）封闭→广群结合→半群么元→独异点可逆→群，根据定义，满足条件即可。详见P86 6、群的证明：方法：根据群的四个条件，逐一验证即可，注意：对于么元和逆元，先根据运算特点解出么元和逆元，再验证。详见P86 7、群的性质：1、 8、子群及判定：三个判定定理根据已知条件选择，给定群 9、特殊群的判断：1、阿贝尔群即满足交换律的群2、循环群即群中每个元都由某一个元的n次幂生成，这个元就是生成元。3、同余类整数加法，乘法， 11、格、子格、分配格、有补格的判定：1、格：即 二、强化练习 1.在整数集上，不是二元运算( )A.加法 B.减法 C.乘法D.除法 2.设A是奇数集合，×为乘法运算，则 3.不满足结合律是( )A.a*b=min(a，b) B.a*b=max(a，b)C.a*b=2(a+b) D.a*b=2ab 4．在N上，可结合的是（）A．a*b=a-2b B．a*b=min{a，b} C．a*b=-a-b D．a*b=|a-b| 5．整环和域是（）A整环一定是域B域不一定是整环C域一定是整环D域一定不是整环 6．设集合A={1，2，3，……，10}，A上是不封闭的是（）A．x*y=max{x,y} B．x*y=min{x,y}C．x*y=GCD{x,y},即x,y的最大公约数D．x*y=LCM{x,y},即x,y的最小公倍数 7．设H，K是群（G， ）的子群，下面代数系统是（G， ）的子群的是（） A．（H∩K， ）B．（H∪K， ）C．（K-H， ）D．（H-K， ） 4．下列所示的哈斯图所对应的偏序集中能构成格的是（） A．B．C．D． 8.代数系统 9.在实数集R上定义运算a b=a+b+ab，则幺元为________，元素2的逆元为________。 10．设S是非空有限集，代数系统 11．在 12．设 13．有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是__________，设a有逆元，则其逆元a-1=__________。 14． 15．设H 是形如??? ??101x 的2×2阶矩阵的集合，H 中定义通常的矩阵乘法运算。验证H 是群，1 101-??? ??x =??? ??-101x 。 16．在整数集Z 上定义：Z ,,2∈?-+=b a b a b a ，证明： 17．设H 是G 的有限子集，则 离散数学复习第五章图论 一、典型考查要点 1、图的基本概念：方法：度：点连接的边的条数，自环算2度；生成子图：点不减少，边减少；完全图：每个点都与余下的点有边；同构：两个图总可以画成相同的。详见P110 2、握手定理：结点度数总和等于边数的两倍，即∑deg(v)=2|E|，用于边点度之间的计算。 3、路的两个定理及证明： 1、在一个具有n 个结点的图中，如果从结点vj 到vk 存在一条路，则从结点vj 到vk 存在一条不多于n-1条边的路。推论：在一个具有n 个结点的图中，若从结点vj 到vk 存在一条路，则必存在一条从vj 到vk 而边数小于n 的通路。详见P115 4、连通图的判定及证明：1、无向连通图：任意两点都有路，即都走得通，只有一个连通分支。2、有向图中：强连通，任意两点都有路，即都走得通；弱连通，去掉方向后才连通；单侧连通， 每对点，只要一个点可达另一点。3、强连通的充要条件证明：一个有向图是强连通的充分必要条件是G 有一个回路，它至少包含每个结点一次。详见P116-117 5、边割集、点割集的判定及证明：点割集：图中去掉这些点及关联的边后，恰好不连通。定理：一个连通无向图G 中的结点v 是割点的充分必要条件是存在两个结点u 和w ，使得结点u 和w 的每一条路都通过v 。 边割集：图中去掉这些边后，恰好不连通，连通分支变为2。定理：G 的一条边e 不包含在G 的回路中当且仅当e 是G 的割边。详见P116-117 6、邻接矩阵、可达矩阵的表示：邻接矩阵：10i j ij i j v adj v a v nadj v ori j ?=?=?，表示图中点与点的关系，可以利用它的Ak 来求长度为k 的路的条数，即定理：设A 为简单图G 的邻接矩阵，则Ak 中的i 行j 列元素akij 等于G 中联结vi 到vj 的 长度为k 的链(或路)的数目。可达矩阵：1v 0v i j ij i j v P v ??=???从到至少存在一条路从到不存在路可以利用它来判定连通性，全为1，就是连通的。 详见P117-118 7、欧拉图及应用：欧拉路：边遍行且只能一次的路，点可以重复。欧拉回路：边遍行且只能一次的回路。判定：欧拉路存在当且仅当G 连通，且有零个或两个奇数度结点。欧拉回路存在当且仅当G 连通，并且所有点度数都为偶数。应用到一笔画问题，即有没有欧拉路。 8、汉密尔顿图及应用：汉密尔顿路：点遍行且只能一次的路。汉密尔顿回路：点遍行且只能一次的回路。判定：1、必要条件：若图有汉密尔顿回路，则V 的每个非空子集S 均有W(G-S)≤|S|，其中W(G-S)是G-S 的连通分支数。可以利用这个必要条件来判定有些图不是汉密尔顿图。2、充分条件：图G 有n 个点的简单图,如果每一对结点度数之和大于等于n-1,则G 中存在一条汉密尔顿路。若每一对结点度数之和大于等于n,则存在汉密尔顿回路。3、应用到网路连通、朋友开会排座位等，就是先利用题目中的联系，有关系就确定一条边，构造一个图，找一条汉密尔顿路或汉密尔顿回路即可。详见P121 9、平面图的判定：1、平面图：画在平面上，边不相交叉。判定：平面图不含与K3,3,或K5同胚的子图。K3,3,K5及彼得森图都不是平面图。2、欧拉公式：n-m+r=2,计算边点面之间的关系问题。面的次数即围着这个面的边的条数，单独的边要算2次。必要条件：给定连通简单平面图G= 10、树的6个等价定义：(1)无回路的连通图(2)无回路且e=v-1 (3)连通且e=v-1(4)无回路，但增加一边后得到且仅得一个回路(5)连通，但删去任一边后就不连通(6)每一对结点间有且仅有一条通路。利用e=v-1和握手定理计算边点的数目。详见P128 11、最小生成树：连通图中权之各最小的生成树，利用避圈法：边的权由小到大依次画入生成树中，但不能形成回路，若有回路就不画入，这样直到形成生成树为止，最小生成树不唯一。应用在网络连通上，造价最少的问题中。详见P129 12、M 叉树详见P120，根树表示算式：根据算式运算的顺序，由内向外形成根树。详见P131 二、强化练习 13.13图的最小入度是( )A.0 B.1 C.2 D.3 2.下面既是汉密尔顿图又是欧拉图的图形是( ) ??????????1001001111011010 3.树有3个5度点、1个4度点、3个2度点，其它的都是1度，边是( ) A.17 B.18 C.19 D.20 5．G 是 n 个结点的简单图，有（ ）A ．Δ(G)＜nB ．Δ(G)≤nC ．Δ(G)＞nD ．Δ(G)≥n 6．具有4个结点的非同构的无向树的数目是（ ）A ．2 B ．3 C ．4 D ．5 7．简单图G 所有结点的度数之和为12，则G 边一定有（ ）A ．3 B4 C ．5 D ．6 8．下列不一定是树的是（ ）A ．无回路的连通图 B ．有n 个结点，n-1条边的连通图 C ．每对结点之间都有通路的图 D ．连通但删去一条边则不连通的图 9．欧拉回路是（ ）A ．路径 B ．迹C ．既是初级回路也是迹 D ．既非初级回路也非迹 10.若回路中，除________外________各不相同，则此回路称为圈(或初级回路)。 11.偶图记为Kn,m 那么当________时，Kn,m 是平面图，当________时，Kn,m 是非平面图。 12.若图中存在________，它经过图中所有的边恰好________次，则称该图为欧拉图。 13．在24图中，结点v2的度数是________。25．设图D= 14．如14图的有补格中，c 的补元是____，b 的补元是_____。 15．在根树中，若每一个结点的出度___m,则称这棵树为m 叉树。如果每一个结点的出度_____m 或0，则称这棵树为完全m 叉树。 16．简单图G 有n 个结点，m 条边，设m>21 (n-1)(n-2)，证明：G 是连通的。 17.求30图所示格的所有5元子格。18.用矩阵的方法求31图中结点u2，u5之间长为2的路径的数目。19．28给出了一个有向图。（1）求出它的邻接矩阵A ；（2）求出A2，A3，A4及可达矩阵P 。 20．证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点一次。 21．证明：边e 是图G 的一条割边，当且仅当图G 中不存在包含边e 的简单回路。 22．今有n 个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明： （1）当n ≥3时，这n 个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边（或右边）的人的朋友。 （2）当n ≥4时，这n 个人能排成一圆圈，使得每个人是其两旁的人的朋友。 23．在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。 华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x 2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5 离散数学形成性考核作业( 一) 集合论部分 分校_________ 学号____________________ 姓名__________________ 分数 本课程形成性考核作业共 4 次, 内容由中央电大确定、统一布置。本次形考作业是第一次作业, 大家要认真及时地完成集合论部分的形考作业, 字迹工整, 抄写题目, 解答题有解答过程。 第 1 章集合及其运算 1．用列举法表示”大于2而小于等于9 的整数” 集合． 2．用描述法表示”小于5 的非负整数集合” 集合． 3 ．写出集合B={1, {2, 3 }} 的全部子集． 4 ．求集合A={ ,{ } } 的幂集． 5 ．设集合A={{ a }, a }, 命题: { a } P(A) 是否正确, 说明理由． 6 ．设 A {1,2,3}, B { 1,3,5}, C { 2,4,6}, 求 (1) A B (2) A B C (3) C - A (4) A B 7 ．化简集合表示式: (( A B ) B) - A B． 试证：A - ( B C ) = ( A - B ) - C. 9 .填写集合{4, 9 } {9, 10, 4} 之间的关系. 10 .设集合A = {2, a , {3}, 4}, 那么下列命题中错误的是（） A .{a } A B . { a , 4, {3}} A C . {a } A D . A 11 .设B = { {a }, 3, 4, 2}, 那么下列命题中错误的是（） 第2章关系与函数 并验证 A (B C ) = ( A B ) (A C ). 4 .写出从集合A = { a , b , c }到集合B = {1}的所有二元关系. 8 .设A B C 是三个任意集合 A . {a } B B .{2, { a }, 3, 4} B C . {a } B D .设集合A = {a , b }, B = {1, 2, 3}, C = {3, 4}, 求 A (B C ), (A B) (A C ) .对任意三个集合 B 和 C 若ABA C 是否一定有B C ?为什么？ .对任意三个集合 B 和 C 试证若A B = AC 」A 离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧()) 下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨Q ）→R ． 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) ． 4．设P (x )：x 是人，Q (x )：x 去上课，则命题“有人去上课．” 可符号化为 ?x(P(x) ∧Q(x)) ． 5．设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名： 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f 2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={ 一、单项选择题（每小题2分，共38分） 题目1 正确 获得2.00分中的2.00分 未标记标记题目 题干 假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。 选择一项： A. 16 B. 47 C. 15 D. 17 题目2 正确 获得2.00分中的2.00分 未标记标记题目 题干 二叉树第k层上最多有（）个结点。 选择一项： A. 2k-1 B. 2k-1 C. 21 k D. 2k 题目3 正确 获得2.00分中的2.00分 未标记标记题目 题干 将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。 选择一项： A. 34 B. 35 C. 33 D. 36 题目4 正确 获得2.00分中的2.00分 未标记标记题目 如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。 选择一项： A. 二叉树 B. 哈夫曼树 C. 完全二叉树 D. 平衡二叉树 题目5 正确 获得2.00分中的2.00分 未标记标记题目 题干 在一棵度具有5层的满二叉树中结点总数为（）。 选择一项： A. 33 B. 32 C. 31 D. 16 题目6 正确 获得2.00分中的2.00分 未标记标记题目 题干 一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。 选择一项： A. 37 B. 72 C. 38 D. 31 题目7 正确 获得2.00分中的2.00分 未标记标记题目 题干 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。 选择一项： A. 18 B. 30华南农业大学 离散数学 期末考试2013试卷及答案
电大离散数学形成性考核作业集合
(完整版)离散数学试卷及答案
离散数学模拟题一套及答案
中国石油大学大学《离散数学》期末复习题及答案
电大 离散数学作业7答案
离散数学试题与答案
离散数学模拟试题讲解
大学离散数学期末重点知识点总结(考试专用)
国家开放大学2020年春季学期电大《离散数学》形成性考核三
相关主题
文本预览