离散数学复习要点第一章命题逻辑
一、典型考查点
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、求偏序关系的特殊元:设为偏序集,B?A,b∈B,①若(?x)(x∈B→b≤x)为真,则称b为B的最小元。 ②若(?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、求上界下界上确界和下确界:设为偏序集,B?A,b∈A,①若(?x)(x∈B→b≤x)为真,则称b为B的下界。 ②若(?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 上的包含关系,试给出 的哈斯图,并给出子集{{a,b},{a,c},{c}}的极大元、极小元、最大元、最小元。 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, 中的特殊元(么元或零元)与中相同。详见P82 5、特殊代数系统判定:(G, )封闭→广群结合→半群么元→独异点可逆→群,根据定义,满足条件即可。详见P86 6、群的证明:方法:根据群的四个条件,逐一验证即可,注意:对于么元和逆元,先根据运算特点解出么元和逆元,再验证。详见P86 7、群的性质:1、 8、子群及判定:三个判定定理根据已知条件选择,给定群 9、特殊群的判断:1、阿贝尔群即满足交换律的群2、循环群即群中每个元都由某一个元的n次幂生成,这个元就是生成元。3、同余类整数加法,乘法, 11、格、子格、分配格、有补格的判定:1、格:即偏序集中,任意两个元素都有最小上界和最大下界。2、子格:子集,运算∨,∧封闭即可。3、分配格:含有五角格和钻石格为子图的都不是分配格,但链是分配格。4、有补格:每个元素都至少有一个补元素的有界格。求补元时,满足:a∨b=1(即全上界),和a∧b=0(即全下界) 详见P97 二、强化练习 1.在整数集上,不是二元运算( )A.加法 B.减法 C.乘法D.除法 2.设A是奇数集合,×为乘法运算,则是( )A.半群B.群 C.循环群D.交换群 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是非空有限集,代数系统 中,其中P(S)为集合S的幂集,则P(S)对∪运算的单位元是________,零元是________。 11.在 12.设是格,其中A={1,2,3,4,6,8,12,24},≤为整除关系,则3的补元是________。 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、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b 二、选择 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年春季学期电大《离散数学》形成性考核三