下载文档原格式
第二章习题一1、指出下列公式∀x∃y(F(x,y)∧G(y,z)) ∨∃xH(x,y,z)中的指导变元，量词的辖域，各个体变项的自由出现和约束出现。
解：全称量词的指导变元为x，第一个存在量词的指导变元为y，第2个存在量词的指导变元为x。
在∀x∃y(F(x,y) ∧G(y,z))中约束变元为x与y，自由变元为z。
在∃xH(x,y,z)中的约束变元为x，自由变元为y,z。
2、给定解释I如下：(a)个体域为实数集R；(b)特定元素a=0；(c)函数f(x,y)=x-y，x与y为实数。
(d)谓词F(x,y)为x=y，G(x,y)为x<y，x与y为实数。
给出下列公式在解释I下的真值。
(1) ∀x ∀y(F(f(x,y),a) →G(x,y))(2) ∀x ∀y(G(f(x,y),a) →F(x,y))(1) ∀x ∀y(F(f(x,y),a) →G(x,y))解：原式=∀x ∀y(F(x-y,0) → G(x,y))=∀x∀y(x-y=0 → x<y)当x-y=0为1时，x<y为0，故此式的值为0。
(1) ∀x ∀y(G(f(x,y),a) →F(x,y))=∀x ∀y(G(x-y,0) →F(x,y))=∀x ∀y((x-y<0) →x=y)当x-y<0即x<y时即前件成立时，后件x=y不可能成立即为0，故此式的值为0。
3、给定解释I如下：(a)个体域D=自然数N；(b)特定元素a=2；(c)函数f(x,y)=x+y，g(x,y)=x*y；(d)谓词F(x,y)为x=y；给出下列各式在I下的解释，并讨论它们的真值：(1) ∀x∀y(F(f(x,a),y) →F(f(y,a),x))(2) ∃x(F(f(x,x),g(x,x)))(1) ∀x∀y(F(f(x,a),y) →F(f(y,a),x))=∀x∀y(F(f(x,2),y) →F(f(y,2),x))=∀x∀y(F(x+2,y) →F(y+2,x))=∀x∀y((x+2=y) →(y+2=x))当x+2=y时即x-y=-2即前件为1时，后件y+2=x即x-y=2是不可能的，也即后件为0，故此式的值为0。
离散数学课后答案(第1-2-4章)武汉大学出版社习题1.11、（1）否（2）否（3）是，真值为0（4）否（5）是，真值为12、（1）P：天下雨Q：我去教室┐P →Q（2）P：你去教室Q：我去图书馆P →Q （3）P，Q同（2）Q →P（4）P：2是质数Q：2是偶数P∧Q3、（1）0（2）0（3）14、（1）如果明天是晴天，那么我去教室或图书馆。
（2）如果我去教室，那么明天不是晴天，我也不去图书馆。
（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。
习题1.21、（1）是（2）是（3）否（4）是（5）是（6）否2、（1）(P →Q) →R，P →Q，R，P，Q （2）(┐P∨Q) ∨（R∧P），┐P ∨Q，R∧P，┐P，Q，R，P（3）((P →Q) ∧(Q →P)) ∨┐(P →Q))，(P →Q) ∧(Q →P)，┐(P →Q)，P →Q，(Q →P)，P →Q，P，Q，Q，P，P，Q3、（1）((P →Q) →(Q →P)) →(P →Q) （2）((P →Q) ∨((P →Q) →R))→((P →Q) ∧((P →Q) →R))（3）(Q →P∧┐P) →(P∧┐P →Q)4、(P →Q) ∨((P∧Q) ∨(┐P∧┐Q)) ∧(┐P∨Q)习题1.31、（1）I(P∨(Q∧R)) = I(P)∨(I(Q)∧I(R)) = 1∨(1∧0) = 1（2）I((P∧Q∧R)∨(┐(P∨Q)∧┐(R∨S))) = (1∧1∧0)∨(┐(1∨1)∧┐(0∨1)) = 0∨(0∧0) = 0 （3）I((P←→R)∧(┐Q→S)) = (1←→0)∧(┐1→1) = 0∧1 = 0（4）I((P∨(Q→R∧┐P))←→(Q∨┐S)) = (1∨(1→(0∧┐1)))←→(1∨┐1) = 1←→1 = 1（5）I(┐(P∧Q)∨┐R∨((Q←→┐P)→R∨┐S)) = ┐(1∧1)∨┐0∨((1←→┐1)→(0∨┐1)) = 0∨1∨1 = 12、（1）P Q P→Q Q∧(P→Q) Q∧(P→Q)→P0 0 1 0 10 1 1 1 01 0 0 0 11 1 1 1 1（2）P Q R Q∧R ┐(P∨(Q∧R)) P∨Q P∨R（2）原式<=> ┐T∨(┐(┐P∨Q)∨(┐┐Q∨┐P)) <=> (P∧┐Q)∨(Q∨┐P)<=> (P∧┐Q)∨┐(P∧┐Q) <=> T 原式为永真式（3）原式<=> ┐(P∧Q) ←→┐(P∧Q) <=> T 原式为永真式（4）原式<=> P∧(Q∨R) ←→P∧(Q∨R) <=> T 原式为永真式（5）原式<=> ┐(P∨┐Q)∨Q <=> (┐P∧Q)∨Q <=> Q 原式为可满足式（6）原式<=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> T 原式为永真式（7）原式<=> (┐P∨P∨Q)∧┐P <=> (T∨Q)∧┐P<=> T∧┐P <=> ┐P 原式为可满足式（8）原式<=> ┐((P∨Q) ∧(┐Q∨R))∨(┐P ∨R) <=> (P∧┐Q)∨(Q∧┐R)∨(┐P∨R)<=> ((P∧┐Q)∨┐P)∨((Q∧┐R)∨R)<=>(( P∨┐P)∧(┐Q∨┐P))∨(( Q∨R)∧(┐R ∨R))<=> (┐Q∧┐P)∨( Q∨R) <=> T 原式为永真式4、（1）左<=> ┐P∨┐Q∨P <=> ┐┐P∨(┐P ∨┐Q) <=> 右（2）左<=> ┐(┐P∨Q) <=> 右（3）左<=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> 右（4）左<=> ┐(P→Q)∨┐(Q→P) <=> (P∧┐Q)∨(Q∧┐P) <=> 中<=> ((P∧┐Q)∨Q)∧((P∧┐Q)∨┐P)<=> (P∨Q)∧(┐Q∨Q)∧(P∨┐P)∧(┐Q∨┐P)<=> (P∨Q)∧┐(P∧Q) <=> 右(5)左( P Q) ( R Q) (P Q) Q 右5.(1)左Q P Q 右(2)(P (Q R)) ((P Q) (P R))( P Q R) ( P Q) ( P R)(P Q R) (P Q) P R(P Q R) ((P P) ( Q P)) R(P Q R) ( Q P R)(P Q R) (P Q R)T故P (Q R) (P Q) (P R)(3).(P Q) (P P Q)( P Q) P (P Q)( P Q) ( P P) ( P Q)( P Q) ( P Q)T故P Q P P Q(4).((P Q) Q) P Q( ( P Q) Q) P Q(( P Q) Q) P Q( P Q) (Q Q) P Q(P Q) (P Q)T故(P Q) Q P Q(5).((P P) Q) ((P P) R) (Q R) (( T Q) ( T R)) Q R(Q R) Q RQ R Q RQ TT故((P P) Q) ((P P) R) Q R(6)左(Q F) (R F)( Q F) ( R F)Q RRR Q 右6.(1)原式( P Q R)(2)原式P Q P (P Q P)(3)原式P (Q R P) P Q R ( P Q R)7.(1)原式( P Q P)(2)原式( P Q R) P Q ( ( P Q R) P Q)(3)原式P Q (R P) (P Q (R P))8. (1) (P Q) (( P ( P Q)) R) P(2)(P Q R) ( P R)(3)(P F) (Q T)习题1.41.(1)原式( P Q) (( P Q) (Q P))( P Q) (Q P)(P Q) Q PQ P,既是析取范式又是合取范式(2)原式(( P Q) ( P Q)) ( ( P Q) ( P Q))(P Q) (P Q) 析取范式P (Q Q)合取范式(3)原式P Q S ( P Q)析取范式( P ( P Q)) Q SP Q S合取范式(4)原式P P Q Q R既是析取范式又是合取范式2.(1)原式P Q R为真的解释是：000，001，011，100，101，110，111故原式的主析取范式为:( P Q R) ( P Q R) ( P Q R) (P Q R) (P QR) (P Q R) (P Q R)(2)原式(P Q) R(P Q (R R)) ((P P) R)(P Q R) (P Q R) (P Q) ( P R)(P Q R) (P Q R) (P (Q Q) R) ( P (Q Q) R)(P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)(P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)为真的解释是101，100，111，011，001(3)原式( P (Q R)) (P ( Q R))(( P (Q R)) P) (( P (Q R)) ( Q R))( P P) (Q P R) ( P Q R) (Q R Q R)(P Q R) ( P Q R)为真的解释是：000,111(4)原式P P Q Q R P Q R为真的解释是：001，010，011，100，101，110，111故原式的主析取范式为：( P Q R) ( P Q R) ( P Q R) (P Q R) (P QR) (P Q R) (P Q R)3.(1)原式P Q P Q T主合取范式，无为假的解释。
离散数学（第⼆版）最全课后习题答案详解习题⼀1.下列句⼦中,哪些是命题？在是命题的句⼦中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四⼤发明.答：此命题是简单命题，其真值为 1.（2）5是⽆理数.答：此命题是简单命题，其真值为 1.（3）3是素数或4是素数.答：是命题，但不是简单命题，其真值为 1.（4）2x+ <3 5答：不是命题.（5）你去图书馆吗？答：不是命题.（6）2与3是偶数.答：是命题，但不是简单命题，其真值为0.（7）刘红与魏新是同学.答：此命题是简单命题，其真值还不知道.（8）这朵玫瑰花多美丽呀！答：不是命题.（9）吸烟请到吸烟室去！答：不是命题.（10）圆的⾯积等于半径的平⽅乘以π .答：此命题是简单命题，其真值为 1.（11）只有6是偶数，3才能是2的倍数.答：是命题，但不是简单命题，其真值为0.（12）8是偶数的充分必要条件是8能被3整除.答：是命题，但不是简单命题，其真值为0.（13）2008年元旦下⼤雪.答：此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解:（1）p：中国有四⼤发明.（2）p:是⽆理数.（7）p:刘红与魏新是同学.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.（1）5是有理数.答：否定式：5是⽆理数. p：5是有理数.q：5是⽆理数.其否定式q的真值为 1.（2）25不是⽆理数.答：否定式：25是有理数. p：25不是⽆理数. q：25是有理数.其否定式q的真值为1.（3）2.5是⾃然数.答：否定式：2.5不是⾃然数. p：2.5是⾃然数. q：2.5不是⾃然数.其否定式q的真值为1.（4）ln1是整数.答：否定式：ln1不是整数. p：ln1是整数. q：ln1不是整数.其否定式q的真值为1.4.将下列命题符号化，并指出真值.（1）2与5都是素数答：p：2是素数，q：5是素数，符号化为p q∧，其真值为1.（2）不但π是⽆理数，⽽且⾃然对数的底e也是⽆理数.答：p：π是⽆理数，q：⾃然对数的底e是⽆理数，符号化为p q∧，其真值为 1.（3）虽然2是最⼩的素数，但2不是最⼩的⾃然数.答：p：2是最⼩的素数，q：2是最⼩的⾃然数，符号化为p q∧?，其真值为1.（4）3是偶素数.答：p：3是素数，q：3是偶数，符号化为p q∧，其真值为0.（5）4既不是素数，也不是偶数.答：p：4是素数，q：4是偶数，符号化为? ∧?p q，其真值为0.5.将下列命题符号化，并指出真值.（1）2或3（3）3或5是偶数.（4）3不是偶数或4不是偶数.（5）3不是素数或4不是答: p：2是偶数，q：3是偶数，r:3是素数，s:4是偶数, t:5是偶数偶数.(1)符号化: p q∨，其真值为 1.(2)符号化：p r∨，其真值为1. (3)符号化：r t∨，其真值为0.(4)符号化：? ∨?q s，其真值为 1.(5)符号化：? ∨?r s，其真值为0.6.将下列命题符号化.（1）⼩丽只能从筐⾥拿⼀个苹果或⼀个梨.答：p：⼩丽从筐⾥拿⼀个苹果，q：⼩丽从筐⾥拿⼀个梨，符号化为: p q∨ .（2）这学期，刘晓⽉只能选学英语或⽇语中的⼀门外语课.答：p ：刘晓⽉选学英语，q ：刘晓⽉选学⽇语，符号化为: (? ∧∨∧?p q )(p q ) . 7.设 p ：王冬⽣于 1971年，q ：王冬⽣于1972年，说明命题“王冬⽣于1971年或 1972年”既可以化答:列出两种符号化的真值表： p q 0 0 1 10 1 0 10 1 1 00 1 1 1根据真值表,可以判断出,只有当 p 与 q 同时为真时两种符号化的表⽰才会有不同的真值,但结合命题可以发现,p 与 q 不可能同时为真,故上述命题有两种符号化⽅式.8.将下列命题符号化,并指出真值.,就有（1）只要（2）如果（3）只有（4）除⾮（5）除⾮（6）,则:;设 q:,则:答:设 p: .符号化真值（1）（2）（3）（4）（5）1 1 0 0 0（6） 19.设p：俄罗斯位于南半球,q：亚洲⼈⼝最多,将下⾯命题⽤⾃然语⾔表述,并指出其真值：（1）（2）；；；（3）（4）；；（5）（6）（7）；；.答:根据题意,p为假命题,q为真命题.⾃然语⾔真值（1）（2）（3）（4）（5）（6）（7）只要俄罗斯位于南半球,亚洲⼈⼝就最多只要亚洲⼈⼝最多,俄罗斯就位于南半球11111 只要俄罗斯不位于南半球,亚洲⼈⼝就最多只要俄罗斯位于南半球，亚洲⼈⼝就不是最多只要亚洲⼈⼝不是最多，俄罗斯就位于南半球只要俄罗斯不位于南半球，亚洲⼈⼝就不是最多只要亚洲⼈⼝不是最多，俄罗斯就不位于南半球10．设p：9是3的倍数,q：英国与⼟⽿其相邻,将下⾯命题⽤⾃然语⾔表述,并指出真值：.答:根据题意,p为真命题,q为假命题.⾃然语⾔真值（1）（2）（3）9是3的倍数当且仅当英语与⼟⽿其相邻9是3的倍数当且仅当英语与⼟⽿其不相邻9不是3的倍数当且仅当英语与⼟⽿其相邻11（4）9不是 3的倍数当且仅当英语与⼟⽿其不相邻 011．将下列命题符号化,并给出各命题的真值：（1）若 2+2=4,则地球是静⽌不动的；（2）若 2+2=4,则地球是运动不⽌的；（3）若地球上没有树⽊,则⼈类不能⽣存；（4）若地球上没有⽔,则是⽆理数. 答:命题 1命题 2符号化真值（1）（2）（3）（4）p:2+2=4 q:地球是静⽌不动的 q:地球是静⽌不动的 q:⼈类能⽣存0 p:2+2=4 1 1 1p:地球上有树⽊ p:地球上有树⽊q:⼈类能⽣存12.将下列命题符号化,并给出各命题的真值：（1）2+2=4当且仅当 3+3=6；（2）2+2=4的充要条件是 3+36；（3）2+2 4与 3+3=6互为充要条件；（4）若 2+2 4,则 3+3 6,反之亦然. 答:设p:2+2=4,q:3+3=6. 符号化真值 (1) (2) (3) (4)（3）今天是星期⼀当且仅当明天是星期⼆；（4）若今天是星期⼀,则明天是星期三.答:设p:今天是星期⼀,q:明天是星期⼆,r:明天是星期三.符号化真值讨论(1)(2)(3)(4)不会出现前句为真,后句为假的情况不会出现前句为真,后句为假的情况必然为1若p为真,则真值为0;若p为假,则真值为114.将下列命题符号化：（1）刘晓⽉跑得快,跳得⾼；（2）⽼王是⼭东⼈或者河北⼈；（3）因为天⽓冷,所以我穿了⽻绒服；（4）王欢与李乐组成⼀个⼩组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他⼀⾯吃饭,⼀⾯听⾳乐；（8）如果天下⼤⾬,他就乘班车上班；（9）只有天下⼤⾬,他才乘班车上班；（10）除⾮天下⼤⾬,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2与4都是素数,这是不对的；（13）“2或4是素数,这是不对的”是不对的.答: 命题1 命题2命题3符号化(1)(2)p:刘晓⽉跑得快q:刘晓⽉跳得⾼-p:⽼王是⼭东⼈p:天⽓冷q:⽼王是河北⼈----q:我穿⽻绒服p:王欢与李乐组成p:王欢与李乐组成⼀个--⼀个⼩组⼩组p:李⾟与李末是兄p:李⾟与李末是兄弟弟(6)(7) p:王强学过法语p:他吃饭q:刘威学过法语q:他听⾳乐q:他乘车上班q:他乘车上班q:他乘车上班q:路滑--(8) p:天下⼤⾬p:天下⼤⾬p:天下⼤⾬p:下雪-(9) -(10)(11)r:他迟到了p:2是素数p:2是素数q:4是素数--q:4是素数15.设p：2+3=5.q：⼤熊猫产在中国.r:太阳从西⽅升起.求下列符合命题的真值：（1）（2）（3）（4）解：p真值为1，q真值为1，r真值为0.（1）0，（2）0，（3）0，（4）116.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值：（1）（2）（3）（4）解：（1）0，（2）0，（3）0，（4）117.判断下⾯⼀段论述是否为真：“是⽆理数.并且,如果3是⽆理数,则外,只有6能被2整除,6才能被4整除.”也是⽆理数.另解：p:是⽆理数q: 3是⽆理数r:是⽆理数s: 6能被2整除18.在什么情况下,下⾯⼀段论述是真的:“说⼩王不会唱歌或⼩李不会跳舞是正确的,⽽说如果⼩王会唱歌,⼩李就会跳舞是不正确的.”解：p:⼩王会唱歌。
习题2.1答案(从本章起，习题答案由jhju提供，晓津补充。
如有问题或不同意见，欢迎到分课论坛发表)1、用谓词表达式写出下列命题a)小张不是研究生；解：设A(x)：x是研究生；a:小张；|A(a)。
b)他是跳高或篮球运动员；解：设A(x):x是跳高运动员；B(x):x是篮球运动员；a: 他；A(a)∨B(a) 。
c)晓莉非常聪明和能干；解：设 A(x):x非常聪明；B(x):x能干；l: 晓莉；A(l)∧B(l)d)若m是奇数则2m是偶数解：设 A(x): x是奇数B(y):y是偶数m:某数A(m)→ B(2m)2、将下列命题符号化并要分析到个体词及谓词a)长江流经四川省；解：B(x,y):x流经y；a:长江 b:四川省B(a,b)。
个体词：长江、四川省谓词：流经b)这架新式歼击机击沉了那艘老式快艇解：设A(x,y):x击沉了ya:新式歼击机 b:老式快艇A(a,b).个体词：歼击机、快艇谓词：击沉3、用谓词表达式符号化下列命题。
那位戴眼镜穿西服的大学生在看一本英文杂志。
解：设：A(x): x戴眼镜；B(x): x穿西服；C(x): x在看英文杂志；a: 那位大学生A(a)∧B(a)∧C(a)这个表达式的含义就是一个陈述句：那位大学生戴眼镜且那位大学生穿西服且那位大学生在看英文杂志。
个体词是：那位大学生。
谓词有：戴眼镜、穿西服、在看英文杂志。
2.2习题答案(从本章起，习题答案由jhju提供，晓津补充。
如有问题或不同意见，欢迎到分课论坛发表) 题号：1234561、对下列公式指出约束变元和自由变元，并指明量词的辖域。
a,(x)(P(x)—→Q(x))∧(x)R(x,y)；(x)的指导变元是x,其辖域是(P(x)—→Q(x))(x)的指导变元是x,其辖域是R(x,y)对于(x)来说，x是约束出现，y则是自由出现。
b,(x)(y)(P(x)∨Q(y))—→(x)(R(x)∧S(z))；(x)和(y)的指导变元是x,y,其辖域是(P(x)∨Q(y))(x)的指导变元是x,其辖域是(R(x)∧S(z))x,y在辖域是约束出现，z则是自由出现(注，教材中本题原来是多一个括号的(或者说少一个)，现在jhju将它改成这个样子，请大家仔细在书中找BUG)c,(x)(y)(P(x,y)∧Q(z))(x)(y)的指导变元是x,y,自由变元是z,其辖域是P(x,y)∧Q(z)2、在下列公式中，对约束变元进行换名，对自由变量进行代入。
练习二3解：（1）﹁(p⋀q→q)⇔﹁p⋀q→q⇔﹁﹁p⋀q⋁q⇔﹁(﹁p⋁﹁q⋁q)⇔p⋀q⋀﹁q ⇔p⋀0⇔0原式为矛盾式。
（2）（p→(p⋁q))⋁(p→r)）⇔(﹁p⋁p⋁q)⋁(﹁p⋁r)⇔﹁p⋁p⋁q⋁﹁p⋁r⇔1⋁q⋁r⇔1原式为重言式（3）p⋁q→(p⋀r)⇔﹁p⋁q⋁p⋀r⇔(﹁p⋀﹁q)⋁(p⋀r)成真赋值为000,101,111.所以原式为可满足式，但不是重言式。
4.（1）p⇔(p⋀q)⋁(p⋀﹁q)证明：(p⋀q)⋁(p⋀﹁q)⇔p⋀(q⋁﹁q)⇔p⋀1⇔p⇔左边（2）((p→q)⋀(p→r))⇔(p→(p⋀r))证明：((p→q)⋀(p→r))⇔((﹁p⋁q)⋀(﹁p⋁r))⇔﹁p⋁(q⋀r)⇔(p→(q⋀r))⇔右边（3）﹁p↔q⇔p⋁q⋀﹁(p⋀q)证明：﹁p↔q⇔﹁p→q⋀q→p⇔﹁p⋁q⋀ ﹁q⋁p⇔p⋁﹁q ⋀ ﹁p⋁q⇔(p⋁q)⋀(p⋀﹁p)⋀ (﹁q⋁q)⋀(﹁p⋁﹁q)⇔(p⋁q)⋀﹁(p⋀q)(4) (p⋀﹁q)⋁(﹁p⋀q)⇔(p⋁q)⋀﹁(p⋀q)证明：(p⋀﹁q)⋁(﹁p⋀q)⇔(p⋁﹁q)⋀(p⋁q)⋀(﹁p⋁﹁q)⋀﹁(p⋀q))⇔(p⋁q)⋀﹁(p⋀q)5.解：(1)(﹁p→q)→(﹁q⋁p)⇔﹁﹁p⋁q→﹁q⋁p⇔﹁p⋁q⋁ ﹁q⋁p⇔(﹁p⋀﹁q)⋁﹁(q⋀﹁p)⇔(﹁p⋀﹁q)⋁﹁q⋁p成真赋值为：00,01,10,115.(1)(﹁p→q)→(﹁q⋁p)解：⇔﹁(p⋁q)⋁(﹁q⋁p)⇔(﹁p⋀﹁q)⋁﹁q⋁p⇔(﹁p⋀﹁q)⋁﹁q⋀(p⋁﹁p)⋁p⋀(q⋁﹁q)⇔(﹁p⋀﹁q)⋁(p⋀﹁q)⋁(﹁p⋀﹁q)⋁(p⋀q)⋁(p⋀﹁q)⇔∑m(0,2,3)成真赋值为：00,10,116（2）p⋀q⋁ ﹁p⋁r解：⇔[p⋁(﹁p⋁r) ]⋀[q⋁(﹁p⋁r) ]⇔(p⋁﹁p⋁r)⋀(q⋁﹁p⋁r)⇔1⋀(q⋁﹁p⋁r)⇔q⋁﹁p⋁r⇔∏M(4)成假赋值为：1007(1)p⋀q⋁r解：⇔(p⋀q)⋁(﹁r⋁r)⋁(﹁p⋁p)⋁(﹁q⋁q)⋀r⇔(p⋀q⋀r)⋁(p⋀q⋀﹁r)⋁[((p⋀q)⋁(p⋀﹁q)⋁(﹁p⋀q)⋁(﹁p⋀﹁q)]⋀r⇔(p⋀q⋀r)⋁(p⋀q⋀﹁r)⋁(p⋀q⋀r)⋁(p⋀﹁q⋀r)⋁(﹁p⋀q⋀r)⋁(﹁p⋀﹁q⋀r)⇔(p⋀q⋀r)⋁(p⋀q⋀﹁r)⋁(p⋀﹁q⋀r)⋁(﹁p⋀q⋀r)⋁(﹁p⋀﹁q⋀r)⇔∑m(1,3,5,6,7)由主析取范式得出主合取范式为∏M0,2,48(1)p⋀q→q解：⇔﹁p⋀q⋁q⇔﹁p⋁﹁q⋁q⇔﹁q⋁1⇔1由公式的主合取范式得主析取范式为∑m(0,1,2,3)9.(1) (p⋁q)⋀(﹁p⋁r)解:由真值表知主析取范式为：∑m(1,2,3,4,5,6,7) 10.(1)p⋀q⋁r解：由真值表可知：主合取范式为：∏M(0,2,4) (2)(p→q)⋀(q→r)解：由真值表知主合取范式为∏M(2,4,5,6)11(2)p→(p⋁q⋁r)解：由真值表知：主析取范式为∑m(0,1,2,3,4,5,6,7,)主析取范式为：117(1)﹁(p→q↔q⋀r)⇔p⋀q⋀﹁r18(2)p↔r⋀q⇔﹁(p⋀﹁r)⋀﹁(r⋀﹁p)⋀q19(1)﹁p⋁﹁q ⋀r⇔﹁(﹁(﹁p⋁﹁q)⋁r)20(1)p⋀q⋁r⇔(p→﹁q)→r21(1)p↑q⇔q↑p,p↓q⇔(q↓p)证明：因为p↑q⇔﹁(p⋀q)又因为合取的交换律可知：(p⋀q)⇔(q⋀p)所以p↑q⇔﹁(p⋀q)⇔﹁(q⋀p)⇔(q⋀p)⇔q↑p同理可知：p↓q⇔﹁p⋁q⇔﹁(q⋁p)⇔(q↓p)22.解：(2)⇔﹁(p⋀q)⇔ p↑q(1)F(14)(2)F(8)(2)⇔﹁p⋁q⇔(q↓p)(3)F6(2)⇔(p⋀﹁q)⋁(﹁p⋀q)(4)F2(2)⇔p⋀﹁q⇔﹁﹁p⋁q﹁(p→q)27(a)F⇔(﹁p⋀﹁q⋀r)⋁(p⋀﹁q⋀﹁r)⋁(﹁p⋀q⋀r)⋁(p⋀q⋀﹁r)⇔m1⋁m3⋁m4⋁m6(b) F⇔(﹁p⋀﹁q⋀r)⋁(p⋀﹁q⋀﹁r)⋁(﹁p⋀q⋀r)⋁(p⋀q⋀﹁r)⇔﹁(﹁m1⋀﹁m3⋀﹁m4⋀﹁m6)(c) F⇔(﹁p⋀r)⋁(p⋀﹁r)⇔﹁(p↔r)28.解：F A⇔(A⋀B⋀C)⋁(A⋀B⋀﹁C)⋁(A⋀﹁B⋀C)⋁(A⋀﹁B⋀﹁C)⇔﹁(﹁(A⋀B⋀C)⋀﹁(A⋀B⋀﹁C)⋀﹁(A⋀﹁B⋀C)⋀﹁(A⋀﹁B⋀﹁C))F B⇔(﹁A⋀B⋀C)⋁(﹁A⋀B⋀﹁C)⇔﹁(﹁(﹁(A⋀B⋀C)⋀﹁(﹁A⋀B⋀﹁C))F C⇔﹁A⋀﹁B⋀C有信号为1，无信号为0F A=m(4,5,6,7)⇔pF B=m(2,3)⇔﹁p⋀qF C=m(1)⇔﹁p⋀﹁q⋀r。
离散数学课后习题答案1. 第一章习题答案1.1 习题一答案1.1.1 习题一.1 答案根据题意，设集合A和B如下：Set A and BSet A and B在此情况下，我们可以得出以下结论：•A的幂集为{ {}, {a}, {b}, {a, b} }；•B的幂集为{ {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }；•A和B的笛卡尔积为{ (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }。
因此，习题一.1的答案为：•A的幂集为{ {}, {a}, {b}, {a, b} }；•B的幂集为{ {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }；•A和B的笛卡尔积为{ (a, 1), (a, 2), (a, 3), (b, 1), (b,2), (b, 3) }。
1.1.2 习题一.2 答案根据题意，集合A和B如下所示：Set A and BSet A and B根据集合的定义，习题一.2要求我们判断以下命题的真假性：a)$A \\cap B = \\{ 2, 3 \\}$b)$\\emptyset \\in B$c)$A \\times B = \\{ (a, 2), (b, 1), (b, 3) \\}$d)$B \\subseteq A$接下来，我们来逐个判断这些命题的真假性。
a)首先计算集合A和B的交集：$A \\cap B = \\{ x\\,|\\, x \\in A \\, \\text{且} \\, x \\in B \\} = \\{ 2, 3 \\}$。
因此，命题a)为真。
b)大家都知道，空集合是任意集合的子集，因此空集合一定属于任意集合的幂集。
根据题意，$\\emptyset \\in B$，因此命题b)为真。
c)计算集合A和B的笛卡尔积：$A \\times B = \\{ (x, y) \\,|\\, x \\in A \\, \\text{且} \\, y \\in B \\} = \\{ (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) \\}$。
离散数学答案第二章习题解答第二章谓词逻辑习题与解答1、将下列命题符号化:(1) 所有的火车都比某些汽车快。
(2) 任何金属都可以溶解在某种液体中。
(3) 至少有一种金属可以溶解在所有液体中。
(4) 每个人都有自己喜欢的职业。
(5) 有些职业就是所有的人都喜欢的。
解 (1) 取论域为所有交通工具的集合。
令x x T :)(就是火车, x x C :)(就是汽车, x y x F :),(比y 跑得快。
“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。
(2) 取论域为所有物质的集合。
令x x M :)(就是金属, x x L :)(就是液体, x y x D :),(可以溶解在y 中。
“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y xD y L y x M x ∧?→?。
(3) 论域与谓词与(2)同。
“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。
(4) 取论域为所有事物的集合。
令x x M :)(就是人, x x J :)(就是职业, x y x L :),(喜欢y 。
“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→?(5)论域与谓词与(4)同。
“有些职业就是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。
2、取论域为正整数集,用函数+(加法),?(乘法)与谓词<,=将下列命题符号化:(1) 没有既就是奇数,又就是偶数的正整数。
(2) 任何两个正整数都有最小公倍数。
(3) 没有最大的素数。
(4) 并非所有的素数都不就是偶数。
解先引进一些谓词如下:x y x D :),(能被y 整除,),(y x D 可表示为)(x y v v =??。
离散数学2一、填空题（每小题2分，共30分）1 设():M x x 偶数， ():F x x 素数。
将命题“存在偶素数”符号化为： ))()((x F x M x ∧∃ 。
2 集合A={2,2,2,3}的幂集合P(A)={}3,2{},3{},2{,φ }。
3 设A={1,2,3}，B={a,b}，则=⨯B A 6 。
4 已知命题公式A 含有2个命题变项，其成真赋值为00、10、11，则其主合取范式为 1M 。
5 设p ：北京比大连人口多，q ：2+2=4，r ：乌鸦是白色的。
则命题公式)()(r p r p ⌝∧↔∨⌝的真值为 0 。
6 无向图G 具有欧拉通路，当且仅当G 是 连通 图且无奇度顶点或有两个奇度顶点。
7 6阶无向树的总度数为 10 。
8设A={1,2,3}，B={a, b}，A 1={2}，f={<1,a>,<2,a>,<3,b>}，则=-))((11A f f { 1，2 }。
9 设B A f →:，若ran B f )(=，则称B A f →:是满射的。
10 设群>⊕=<}),.({b a P G ，其中⊕为对称差。
群方程φ=⊕}{b Y 的解=Y {b} 。
11 设p：我去自习，q：我去看电影，r：我有课。
则命题“如果我去自习或看电影，我就没有课”的符号化形式为r qp⌝→∨)(。
12 画出3阶有向完全图的2条边的2个非同构的生成子图。
13 下面运算表中的=-1a c 。
14 写出模4乘法<Z4,⊗ >的运算表⊗0 1 2 31230 0 0 00 1 2 30 2 0 20 3 2 115 设A（x）是任意的含自由出现个体变项x的公式，则⇔⌝∀)(xxA )(xAx⌝∃。
二、试解下列各题（每小题5分，共25分）1. 设A = {a , b , c , d }, R = {<a ,b >,<b ,a >,<b ,c >,<c ,d >}, 求3R 的的矩阵表示和关系图表示。
离散数学第2章习题解答第2章习题解答2.1 本题没有给出个体域,因而使用全总个体域.(1) 令x(是鸟xF:)(会飞翔.G:)xx命题符号化为xF.Gx→)())((x(2)令xx(为人.F:)(爱吃糖G:)x命题符号化为xFx→G))()((x或者Fx?x∧)))(((xG(3)令xx(为人. F:)G:)(爱看小说.x命题符号化为xF.Gx∧(x())()(4) x(为人.xF:)(爱看电视. G:)xx命题符号化为Fx?∧.xG()))(x分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。
（1）-（4）中的) F都是特性谓词。
(x2°初学者经常犯的错误是，将类似于（1）中的命题符号化为FxGx∧())()(x即用合取联结词取代蕴含联结词，这是万万不可的。
将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。
”因而符号化应该使用联结词→而不能使用∧。
若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。
”这显然改变了原命题的意义。
3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。
2.2 (1)d (a),(b),(c)中均符号化为)(x xF ?其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。
（2）在)(),(),(c b a 中均符号化为)(x xG ?其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。
（3）在)(),(),(c b a 中均符号化为)(x xH ?其中.15:)(=x x H 此命题在)(),(b a 中均为假命题，在(c)中为真命题。
分析1°命题的真值与个体域有关。
2° 有的命题在不同个体域中，符号化的形式不同，考虑命题“人都呼吸”。
第二章习题二1、求证∀x∀y(P(x)→Q(y))⇔∃xP(x)→∀yQ(y)∀x∀y(P(x)→Q(y))⇔∀x∀y(¬P(x)∨Q(y)) 条件式的等值式⇔∀x(¬P(x)∨∀yQ(y)) 辖域的扩充与收缩规律⇔∀x¬P(x)∨∀yQ(y) 辖域的扩充与收缩规律⇔¬∃xP(x)∨∀yQ(y) 量词的德摩律⇔∃xP(x)→∀yQ(y) 条件式的等值式2、把下列各式转换为前束范式(1) ∃x(¬(∃yP(x,y)→(∃zQ(z)→R(x))))⇔∃x(¬(∃yP(x,y)→(¬∃zQ(z)∨R(x)))) 条件式的等值式⇔∃x(¬(¬∃yP(x,y)∨(¬∃zQ(z)∨R(x)))) 条件式的等值式⇔∃x((¬¬∃yP(x,y)∧(¬¬∃zQ(z)∧¬R(x)))) 德摩律⇔∃x((∃yP(x,y)∧(∃zQ(z)∧¬R(x)))) 否定的否定⇔∃x∃y∃z ((P(x,y)∧(Q(z)∧¬R(x)))) 量词辖域的扩张与收缩⇔∃x∃y∃z (P(x,y)∧Q(z)∧¬R(x)) 量词辖域的扩张与收缩(2) ∀x∀y((∃zP(x,y,z)∧∃uQ(x,u))→∃vQ(y,v))⇔∀x∀y(¬ (∃zP(x,y,z)∧∃uQ(x,u)) ∨∃vQ(y,v)) 条件式的等值式⇔∀x∀y( (¬∃zP(x,y,z) ∨¬∃uQ(x,u)) ∨∃vQ(y,v)) 德摩律⇔∀x∀y( (∀z¬P(x,y,z) ∨∀u¬Q(x,u)) ∨∃vQ(y,v)) 德摩律⇔∀x∀y∀z∀u∃v ( (¬P(x,y,z) ∨¬Q(x,u)) ∨Q(y,v)) 德摩律⇔∀x∀y∀z∀u∃v ( ¬P(x,y,z) ∨¬Q(x,u)∨Q(y,v)) 德摩律(3) ∀xF(x) →∀yP(x,y)⇔∀zF(z) →∀yP(x,y) 约束变元与自由变元同名，故约束变元改名⇔¬∀zF(z)∨∀yP(x,y) 条件式的等值式⇔∃z¬F(z)∨∀yP(x,y) 德摩律⇔∃z∀y(¬F(z)∨P(x,y)) 德摩律(4) ∀x(P(x,y)→∃yQ(x,y,z))⇔∀x(P(x,y)→∃sQ(x,s,z)) 约束变元y与自由变元y同名，故约束变元改名⇔∀x(¬P(x,y) ∨∃sQ(x,s,z)) 条件式的等值式⇔∀x∃s(¬P(x,y)∨Q(x,s,z)) 辖域的扩充与收缩(5) ∀x(P(x,y)↔∃yQ(x,y,z))⇔∀x(P(x,y)↔∃sQ(x,s,z)) 约束变元y与自由变元y同名，故约束变元改名⇔∀x((P(x,y)→∃sQ(x,s,z)) ∧(∃sQ(x,s,z)→P(x,y))) 双条件的等值式⇔∀x((P(x,y)→∃sQ(x,s,z)) ∧(∃tQ(x,t,z)→P(x,y))) 后面约束变元与前面同则后面换名⇔∀x((¬P(x,y)∨∃sQ(x,s,z))∧(¬∃tQ(x,t,z)∨P(x,y))) 条件式的等值式⇔∀x((¬P(x,y)∨∃sQ(x,s,z))∧(∀t¬Q(x,t,z)∨P(x,y))) 德摩律⇔∀x∃s∀t((¬P(x,y)∨Q(x,s,z))∧(¬Q(x,t,z)∨P(x,y))) 辖域的扩充与收缩(6) ∀x(F(x) →G(x,y)) →(∃yH(y) →∃zL(y,z))⇔∀x(F(x) →G(x,y)) →(∃sH(s) →∃zL(y,z)) 约束变元改名⇔¬∀x(F(x) →G(x,y)) ∨(∃sH(s) →∃zL(y,z)) 条件式的等值式⇔¬∀x(¬F(x) ∨G(x,y)) ∨(¬∃sH(s) ∨∃zL(y,z)) 条件式的等值式⇔∃x¬ (¬F(x) ∨G(x,y)) ∨(¬∃sH(s) ∨∃zL(y,z)) 德摩律⇔∃x¬(¬F(x) ∨G(x,y)) ∨(∀s¬H(s) ∨∃zL(y,z)) 德摩律⇔∃x(¬¬F(x)∧¬G(x,y))∨(∀s¬H(s)∨∃zL(y,z)) 德摩律⇔∃x(F(x)∧¬G(x,y))∨(∀s¬H(s)∨∃zL(y,z)) 否定的否定⇔∃x∀s∃z(F(x)∧¬G(x,y))∨(¬H(s)∨L(y,z)) 辖域的扩充与收缩(7) ∃xF(x,y) →(F(x) →¬∀yG(x,y))⇔∃sF(s,y) →(F(x) →¬∀yG(x,y)) 约束变元改名⇔∃sF(s,y)→(F(x)→¬∀tG(x,t)) 约束变元改名⇔¬∃sF(s,y)∨(¬F(x)∨¬∀tG(x,t)) 条件式的等值式⇔∀s¬F(s,y)∨(¬F(x)∨∃t¬G(x,t)) 德摩律⇔∀s∃t¬F(s,y)∨(¬F(x)∨¬G(x,t)) 辖域的扩充与收缩⇔∀s∃t¬F(s,y)∨¬F(x)∨¬G(x,t) 结合律。
离散数学课后习题答案二习题3.71. 列出关系}6|{=∈><+d c b a d c b a d c b a 且，，，，，，Z 中所有有序4元组。
解}6|{=∈><+d c b a d c b a d c b a 且，，，，，，Z,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><=><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3, 1,1,3,2,1,2,3,1,1,3,2,12. 列出二维表3.18所表示的多元关系中所有5元组。
假设不增加新的5元组，找出二维表3.18所有的主键码。
表3.18 航班信息航空公司航班登机口目的地起飞时间Nadir 112 34 底特律08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛09:10 Nadir 32234底特律09:44解略3. 当施用投影运算5,3,2π到有序5元组><="">解略4. 哪个投影运算用于除去一个6元组的第一、第二和第四个分量？解略5. 给出分别施用投影运算4,2,1π和选择运算Nadir 航空公司＝σ到二维表3.18以后得到的表。
解对航班信息二维表进行投影运算5,3,2π后得到的二维表航班登机口起飞时间 112 34 08:10 221 22 08:17 122 33 08:22 323 34 08:30 199 13 08:47 222 22 09:10 3223409:44对航班信息二维表进行选择运算Nadir 航空公司＝后得到的二维表航空公司航班登机口目的地起飞时间Nadir 112 34 底特律08:10 Nadir 199 13 底特律 08:47 Nadir 32234底特律09:446. 把连接运算3J 用到5元组二维表和8元组二维表后所得二维表中有序多元组有多少个分量？解略7. 构造把连接运算2J 用到二维表3.19和二维表3.20所得到的二维表。
第二版高等教育出版社课后答案第一章部分课后习题参考答案16 设p、q 的真值为0；r、s 的真值为1，求下列各命题公式的真值。
( 1)p∨ (q∧ r) 0∨ (0∧ 1) 0( 2)( p? r)∧(﹁q∨ s) ( 0? 1)∧(1 ∨ 1) 0∧ 1 0.( 3)(p∧q∧r ) ? (p∧q∧﹁r) ( 1∧ 1∧1) ? (0 ∧0∧0) 0( 4)( r ∧ s)→ (p ∧ q) ( 0∧ 1)→ (1 ∧ 0) 0→0 117．判断下面一段论述是否为真：“ 是无理数。
并且，如果 3 是无理数，则 2 也是无理数。
另外6 能被2 整除，6 才能被4 整除。
答：p: 是无理数1q: 3 是无理数0r:2是无理数1s: 6 能被 2 整除1t: 6 能被 4 整除0命题符号化为：p∧(q→ r)∧(t→ s)的真值为1，所以这一段的论述为真19．用真值表判断下列公式的类型：4)(p→ q) →( q→p)5)(p∧ r) ( p∧q)6)((p→ q) ∧ (q→ r)) →(p→r)答： ( 4)p q p→q q p0 0 1 1 10 1 1 0 11 0 0 1 01 1 1 0 0所以公式类型为永真式( 5)公式类型为可满足式(方法如上例) q→ p111(p→q)→( q→ p)1111( 6)公式类型为永真式(方法如上例)第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1)](pAq-q)(2)(p^(pVq))V (p^r)⑶(pVq) 一(pAr)答：(2) (p一(pVq)) V(p-r)= (一pV(pVq))V(「pVr)=「pVpVqVru 1 所以公式类型为永真式⑶p q r PV q p A r (pV q) f (p/\「)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可涉足式4,用等值演算法证明下面等值式：⑵(p 一q)A(p—r) u (p 一(qAij)⑷(p A「q) V「pAq)u (p Vq) A」(p A q)证明(2) (p -q) A (p->r)u (」pVq) A(「pVr)u「P V (q A ij)u p一(q A r)(4) (pA「q) V(「pAq)u (p V(^pAq)) A(「qV(「pAq). (p V「p) A (p Vq) A (「qV「p) A(「qVq)u 1 A (p V q) A - (p A q) A 1u (p V q) A (p A q)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(「p-q)-(「qVp)(2)](p - q) AqAr(3)(p V(q Ar)) 一(p VqVr)解：( 1)主析取范式( p→q)→( q p)(p q) ( q p)( p q) ( q p)( p q) ( q p) ( q p) (p q) (p q)( p q) (p q) (p q)m0 m2 m3∑ (0,2,3) 主合取范式：( p→q) →( q p)(p q) ( q p)( p q) ( q p)( p ( q p)) ( q ( q p))1 (p q)(p q) M1∏ (1)(2)主合取范式为：(p →q) q r ( p q) q r(p q) q r 0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为0(3)主合取范式为：(p (q r)) →(p q r)(p (q r)) →(p q r)( p ( q r)) (p q r)( p (p q r)) (( q r)) (p q r))11所以该式为永真式.永真式的主合取范式为1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P 中构造下面推理的证明：(2)前提：p q, (q r),r结论：p(4)前提：q p,q s,s t,t r结论：p q证明： ( 2)①(q r) 前提引入②q r ①置换③q r ②蕴含等值式④r 前提引入⑤q ③④拒取式⑥p q 前提引入⑦￢p( 3) ⑤⑥拒取式证明( 4) ：①t r 前提引入②t ①化简律③q s 前提引入④s t 前提引入⑤q t ③④等价三段论⑥( q t ) (t q) ⑤ 置换⑦( q t ) ⑥化简⑧q ②⑥ 假言推理⑨q p 前提引入15在自然推理系统 P 中用附加前提法证明下面各推理：(1) 前提：p(q r),s p,q结论：s r证明① s 附加前提引入 ② s p 前提引入 ③ p ①②假言推理 ④ p (q r)前提引入 ⑤ q r ③④假言推理 ⑥ q 前提引入 ⑦ r ⑤⑥假言推理16 在自然推理系统 P 中用归谬法证明下面各推理：(1) 前提： p q, r q,r s 结论： p证明：① p 结论的否定引入 ② p ﹁ q 前提引入 ③﹁q ①②假言推理 ④￢r q 前提引入 ⑤￢r ④化简律 ⑥ r ￢s 前提引入⑦ r ⑥化简律 ⑧ r ﹁r⑤⑦ 合取由于最后一步 r ﹁ r 是矛盾式 , 所以推理正确 .⑩p (11)p q ⑧⑨假言推第四章部分课后习题参考答案3.在一阶逻辑中将下面将下面命题符号化, 并分别讨论个体域限制为(a),(b) 条件时命题的真值:(1)对于任意x, 均有2=(x+ )(x ).(2)存在x, 使得x+5=9.其中(a) 个体域为自然数集合.(b) 个体域为实数集合.解：F(x): 2=(x+ )(x ).G(x): x+5=9.(1)在两个个体域中都解释为xF(x)，在( a)中为假命题，在(b) 中为真命题。
离散数学-第二章命题逻辑等值演算习题及答案本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March第二章作业评分要求：1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分2. 给出每小题得分(注意: 写出扣分理由)3. 总得分在采分点1处正确设置.一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次): 说明证1. p ⇔(p ∧q)∨(p ∧¬q)解逻辑方程法设 p ↔((p ∧q)∨(p ∧¬q)) =0, 分两种情况讨论:⎩⎨⎧=⌝∧∨∧=0)()(1)1(q p q p p 或者 ⎩⎨⎧=⌝∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ↔(p ∧q)∨(p ∧¬q)无成假赋值, 为永真式.等值演算法(p ∧q)∨(p ∧¬q)⇔ p ∧(q ∨¬q)∧对∨的分配率⇔ p ∧1 排中律⇔ p 同一律真值表法2. (p→q)∧(p→r)⇔p→(q∧r)等值演算法(p→q)∧(p→r)⇔ (¬p∨q)∧(¬p∨r)蕴含等值式⇔ ¬p∨(q∧r)析取对合取的分配律⇔ p→(q∧r)蕴含等值式3. ¬(p↔q)⇔(p∨q)∧¬(p∧q)等值演算法¬(p↔q)⇔ ¬( (p→q)∧(q→p) )等价等值式⇔ ¬( (¬p∨q)∧(¬q∨p) )蕴含等值式⇔ ¬( (¬p∧¬q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律⇔ (p∨q)∧¬(p∧q)德摩根律4. (p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)等值演算法(p∧¬q)∨(¬p∧q)⇔ (p∨q)∧¬(p∧q)析取对合取分配律, 排中律, 同一律说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):1.2.3.4.1. (¬p→q)→(¬q∨p)解(¬p→q)→(¬q∨p)⇔ (p∨q)→(¬q∨p)蕴含等值式⇔ (¬p∧¬q)∨(¬q∨p)蕴含等值式, 德摩根律⇔ (¬p∧¬q)∨¬q ∨ p结合律⇔ p∨¬q吸收律, 交换律⇔ M1因此, 该式的主析取范式为m0∨m2∨m32. (¬p→q)∧(q∧r)解逻辑方程法设 (¬p→q)∧(q∧r) =1, 则 ¬p→q=1且 q∧r=1,解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m3∨m7, 主合取范式为M0∧M1∧M2∧M4∧M5∧M6等值演算法(¬p→q)∧(q∧r)(p q)(q r) 蕴含等值式(p q r)(q r) 对分配律, 幂等律(p q r) (p q r)(p q r) 同一律, 矛盾律, 对分配律m7 m3主合取范式为M0∧M1∧M2∧M4∧M5∧M63. (p↔q)→r解逻辑方程法设 (p↔q)→r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析取范式为m1∨m2∨m3∨m4∨m5∨m7等值演算法(p↔q)→r((p q)(q p))r 等价等值式((p q)(q p))r 蕴含等值式(p q)(q p)r 德摩根律, 蕴含等值式的否定(参见PPT)(p q r)(q p r) 对分配律, 矛盾律, 同一律M0 M6主析取范式为m1∨m2∨m3∨m4∨m5∨m74. (p→q)∧(q→r)解等值演算法(p→q)∧(q→r)(p q)(q r) 蕴含等值式(p q)(p r)(q r) 对分配律, 矛盾律, 同一律(p q r)(p q r) (p q r)(p q r)(p q r)(p q r)m1 m0 m3 m7主合取范式为M2 M4 M5 M6.解逻辑方程法设 (p q) (q r) = 1, 则p q =1 且 q r =1.前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1.后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m0 m1 m3 m7, 主合取范式为M2 M4 M5 M6.真值表法公式 (p q)p q r(p q) (q r)00010011010001111000101011001111013724 M5 M6.。
第二章习题二
1、求证∀x∀y(P(x)→Q(y))⇔∃xP(x)→∀yQ(y)
∀x∀y(P(x)→Q(y))
⇔∀x∀y(¬P(x)∨Q(y)) 条件式的等值式
⇔∀x(¬P(x)∨∀yQ(y)) 辖域的扩充与收缩规律
⇔∀x¬P(x)∨∀yQ(y) 辖域的扩充与收缩规律
⇔¬∃xP(x)∨∀yQ(y) 量词的德摩律
⇔∃xP(x)→∀yQ(y) 条件式的等值式
2、把下列各式转换为前束范式
(1) ∃x(¬(∃yP(x,y)→(∃zQ(z)→R(x))))
⇔∃x(¬(∃yP(x,y)→(¬∃zQ(z)∨R(x)))) 条件式的等值式
⇔∃x(¬(¬∃yP(x,y)∨(¬∃zQ(z)∨R(x)))) 条件式的等值式
⇔∃x((¬¬∃yP(x,y)∧(¬¬∃zQ(z)∧¬R(x)))) 德摩律
⇔∃x((∃yP(x,y)∧(∃zQ(z)∧¬R(x)))) 否定的否定
⇔∃x∃y∃z ((P(x,y)∧(Q(z)∧¬R(x)))) 量词辖域的扩张与收缩
⇔∃x∃y∃z (P(x,y)∧Q(z)∧¬R(x)) 量词辖域的扩张与收缩
(2) ∀x∀y((∃zP(x,y,z)∧∃uQ(x,u))→∃vQ(y,v))
⇔∀x∀y(¬ (∃zP(x,y,z)∧∃uQ(x,u)) ∨∃vQ(y,v)) 条件式的等值式
⇔∀x∀y( (¬∃zP(x,y,z) ∨¬∃uQ(x,u)) ∨∃vQ(y,v)) 德摩律
⇔∀x∀y( (∀z¬P(x,y,z) ∨∀u¬Q(x,u)) ∨∃vQ(y,v)) 德摩律
⇔∀x∀y∀z∀u∃v ( (¬P(x,y,z) ∨¬Q(x,u)) ∨Q(y,v)) 德摩律
⇔∀x∀y∀z∀u∃v ( ¬P(x,y,z) ∨¬Q(x,u)∨Q(y,v)) 德摩律
(3) ∀xF(x) →∀yP(x,y)
⇔∀zF(z) →∀yP(x,y) 约束变元与自由变元同名，故约束变元改名
⇔¬∀zF(z)∨∀yP(x,y) 条件式的等值式
⇔∃z¬F(z)∨∀yP(x,y) 德摩律
⇔∃z∀y(¬F(z)∨P(x,y)) 德摩律
(4) ∀x(P(x,y)→∃yQ(x,y,z))
⇔∀x(P(x,y)→∃sQ(x,s,z)) 约束变元y与自由变元y同名，故约束变元改名
⇔∀x(¬P(x,y) ∨∃sQ(x,s,z)) 条件式的等值式
⇔∀x∃s(¬P(x,y)∨Q(x,s,z)) 辖域的扩充与收缩
(5) ∀x(P(x,y)↔∃yQ(x,y,z))
⇔∀x(P(x,y)↔∃sQ(x,s,z)) 约束变元y与自由变元y同名，故约束变元改名
⇔∀x((P(x,y)→∃sQ(x,s,z)) ∧(∃sQ(x,s,z)→P(x,y))) 双条件的等值式
⇔∀x((P(x,y)→∃sQ(x,s,z)) ∧(∃tQ(x,t,z)→P(x,y))) 后面约束变元与前面同则后面换名⇔∀x((¬P(x,y)∨∃sQ(x,s,z))∧(¬∃tQ(x,t,z)∨P(x,y))) 条件式的等值式
⇔∀x((¬P(x,y)∨∃sQ(x,s,z))∧(∀t¬Q(x,t,z)∨P(x,y))) 德摩律
⇔∀x∃s∀t((¬P(x,y)∨Q(x,s,z))∧(¬Q(x,t,z)∨P(x,y))) 辖域的扩充与收缩
(6) ∀x(F(x) →G(x,y)) →(∃yH(y) →∃zL(y,z))
⇔∀x(F(x) →G(x,y)) →(∃sH(s) →∃zL(y,z)) 约束变元改名
⇔¬∀x(F(x) →G(x,y)) ∨(∃sH(s) →∃zL(y,z)) 条件式的等值式
⇔¬∀x(¬F(x) ∨G(x,y)) ∨(¬∃sH(s) ∨∃zL(y,z)) 条件式的等值式
⇔∃x¬ (¬F(x) ∨G(x,y)) ∨(¬∃sH(s) ∨∃zL(y,z)) 德摩律
⇔∃x¬(¬F(x) ∨G(x,y)) ∨(∀s¬H(s) ∨∃zL(y,z)) 德摩律
⇔∃x(¬¬F(x)∧¬G(x,y))∨(∀s¬H(s)∨∃zL(y,z)) 德摩律
⇔∃x(F(x)∧¬G(x,y))∨(∀s¬H(s)∨∃zL(y,z)) 否定的否定
⇔∃x∀s∃z(F(x)∧¬G(x,y))∨(¬H(s)∨L(y,z)) 辖域的扩充与收缩
(7) ∃xF(x,y) →(F(x) →¬∀yG(x,y))
⇔∃sF(s,y) →(F(x) →¬∀yG(x,y)) 约束变元改名
⇔∃sF(s,y)→(F(x)→¬∀tG(x,t)) 约束变元改名
⇔¬∃sF(s,y)∨(¬F(x)∨¬∀tG(x,t)) 条件式的等值式
⇔∀s¬F(s,y)∨(¬F(x)∨∃t¬G(x,t)) 德摩律
⇔∀s∃t¬F(s,y)∨(¬F(x)∨¬G(x,t)) 辖域的扩充与收缩
⇔∀s∃t¬F(s,y)∨¬F(x)∨¬G(x,t) 结合律。
