离散数学课后答案第二版曲婉玲主编.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.87M 资料格式：doc 举报版权申诉

u010088405-5252317-1_11201207222209442815117.doc.pdf-第1页.png

第1页 / 共19页

u010088405-5252317-1_11201207222209442815117.doc.pdf-第2页.png

第2页 / 共19页

u010088405-5252317-1_11201207222209442815117.doc.pdf-第3页.png

第3页 / 共19页

u010088405-5252317-1_11201207222209442815117.doc.pdf-第4页.png

第4页 / 共19页

u010088405-5252317-1_11201207222209442815117.doc.pdf-第5页.png

第5页 / 共19页

u010088405-5252317-1_11201207222209442815117.doc.pdf-第6页.png

第6页 / 共19页

u010088405-5252317-1_11201207222209442815117.doc.pdf-第7页.png

第7页 / 共19页

u010088405-5252317-1_11201207222209442815117.doc.pdf-第8页.png

第8页 / 共19页

文本预览

第一章命题逻辑基本概念课后练习题答案 1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2 是素数，q:5 是素数,真值为 1；（2）p∧q,其中，p: 是无理数，q:自然对数的底 e 是无理数,真值为 1；（3）p∧┐q,其中，p:2 是最小的素数，q:2 是最小的自然数,真值为 1；（4）p∧q,其中，p:3 是素数，q:3 是偶数,真值为 0；（5）┐p∧┐q,其中，p:4 是素数，q:4 是偶数,真值为 0. 2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2 是偶数，q:3 是偶数,真值为 1；（2）p∨q,其中，p:2 是偶数，q:4 是偶数,真值为 1；（3）p∨┐q,其中，p:3 是偶数，q:4 是偶数,真值为 0；（4）p∨q,其中，p:3 是偶数，q:4 是偶数,真值为 1；（5）┐p∨┐q,其中，p:3 是偶数，q:4 是偶数,真值为 0； 3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；. 4.因为 p 与 q 不能同时为真. 5.设 p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为 1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为 1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为 1；（4）p→r，若 p 为真，则 p→r 真值为 0，否则，p→r 真值为 1. 本章自测答案 5.(1)： ∨ ∨ ,成真赋值为 00、10、11； (2)：0，矛盾式，无成真赋值；第二章命题逻辑等值演算 (3)： ∨ ∨ ∨ ∨ ∨ ∨ ∨ ,重言式，000、001、010、011、100、101、110、111 全部为成真赋值；返回 7.(1)： ∨ ∨ ∨ ∨ ⇔ ∧ ∧ ； (2)： ∨ ∨ ∨ ⇔ ∧ ∧ ∧ ； 8.(1)：1⇔ ∨ ∨ ∨ ,重言式； (2)： ∨ ⇔ ∨ ∨ ∨ ∨ ∨ ∨ ； (3)： ∧ ∧ ∧ ∧ ∧ ∧ ∧ ⇔0，矛盾式. 11.(1)： ∨ ∨ ⇔ ∧ ∧ ∧ ∧ ； (2)： ∨ ∨ ∨ ∨ ∨ ∨ ∨ ⇔1；

(3)：0⇔ ∧ ∧ ∧ . 12.A⇔ ∧ ∧ ∧ ∧ ⇔ ∨ ∨ . 本章自测答案第三章命题逻辑的推理理论 6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系 (1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确 (1)设 p:今天是星期一，q:明天是星期三，推理的形式结构为 (p→q)∧p→q(记作*1) 在本推理中，从 p 与 q 的内在联系可以知道，p 与 q 的内在联系可以知道，p 与 q 不可能同时为真，但在证明时，不考虑这一点，而只考虑*1 是否为重言式. 可以用多种方法（如真值法、等值演算法、主析取式）证明*1 为重言式，特别是，不难看出，当取 A 为 p,B 为 q 时，*1 为假言推理定律，即 (p→q)∧p→q ⇒ q (2)设 p:今天是星期一，q:明天是星期三，推理的形式结构为 (p→q)∧p→q(记作*2) 可以用多种方法证明*2 不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等 (p→q)∧q→p ⇔(┐p∨q) ∧q →p ⇔q →p ⇔┐p∨┐q ⇔ ⇔ ∨ ∨ 从而可知，*2 不是重言式，故推理不正确，注意，虽然这里的 p 与 q 同时为真或同时为假，但不考虑内在联系时，*2 不是重言式，就认为推理不正确. 9.设 p:a 是奇数，q:a 能被 2 整除，r:a：是偶数推理的形式结构为 (p→q┐)∧(r→q)→(r→┐p) (记为*) 可以用多种方法证明*为重言式，下面用等值演算法证明： (p→┐q)∧(r→q)→(r→┐p) ⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律) ⇔(p∨q)∨(┐p∧r)∨┐q∨┐r ⇔(┐p∨q)∨(┐q∧┐r) ⇔┐p∨(q∨┐q)∧┐r ⇔1 10.设 p:a,b 两数之积为负数，q:a,b 两数种恰有一个负数，r：a，b 都是负数. 推理的形式结构为 (p→q)∧┐p→(┐q∧┐r) ⇔(┐p∨q) ∧┐p→(┐q∧┐r) ⇔┐p→(┐q∧┐r) (使用了吸收律) ⇔p∨(┐q∧┐r)

⇔ ∨ ∨ ∨ 由于主析取范式中只含有 5 个 W 极小项，故推理不正确. 11.略 14.证明的命题序列可不惟一，下面对每一小题各给出一个证明 ① p→(q→r) ② P ③ q→r ④ q ⑤ r ⑥ r∨s （2）证明： ① ┐(p∧r) ② ┐q∨┐r ③ r ④ ┐q ⑤ p→q ⑥ ┐p （3）证明： ① p→q ② ┐q∨q 前提引入前提引入 ①②假言推理前提引入 ③④假言推理前提引入前提引入 ①置换前提引入 ②③析取三段论前提引入 ④⑤拒取式前提引入 ①置换 ③ (┐p∨q)∧(┐p∨p) ②置换 ④ ┐p∨(q∧p ⑤ p→(p∨q) ③置换 ④置换 15.(1)证明： ① S ② S→P ③ P 结论否定引入前提引入 ①②假言推理 ④ P→(q→r) 前提引入 ⑤ q→r ③④假言推论 ⑥ q ⑦ r （2）证明： ① p ② p∨q 前提引入 ⑤⑥假言推理附加前提引入 ①附加 ③ (p∨q)→(r∧s) 前提引入 ④ r∧s ⑤ s ⑥ s∨t ②③假言推理 ④化简 ⑤附加 ⑦ (s∨t)→u 前提引入 ⑧ u ⑥⑦拒取式

16.(1)证明： ① p 结论否定引入 ② p→ ┐q ③ ┐q ①② ④ ┐r∨q ⑤ ┐r ⑥ r∧┐s ⑦ r ⑧ ┐r∧r （2）证明：前提引入假言推理前提引入 ③④析取三段论前提引入 ⑥化简 ⑤⑦合取 ① ┐(r∨s) 结论否定引入 ② ┐r∨┐s ③ ┐r ④ ┐s ⑤ p→r ⑥ ┐p ⑦ q→s ⑧ ┐q ①置换 ②化简 ②化简前提引入 ③⑤拒取式前提引入 ④⑦拒取式 ⑨ ┐p∧┐q ⑥⑧合取 ⑩ ┐(p∨q) ⑨置换口 p∨q 前提引入 ⑾①口 ┐(p∨q) ∧(p∨q) ⑩口合取 17．设 p：A 到过受害者房间，q: A 在 11 点以前离开，r：A 犯谋杀罪，s：看门人看见过 A。前提：(p∧┐q) →r , p ,q →s , ┐s 结论：r 证明： ① q→s 前提引入 ② ┐s 前提引入 ③ ┐q ①②拒取式 ④ p 前提引入 ⑤ p∧┐q ③④合取 ⑥（p∧┐q）→r 前提引入 ⑦ r ⑤⑥假言推理 18．（1）设 p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。前提：p→(p∨r) , s→┐q , p , s 结论：r 证明： ① s→┐q 前提引入 ② s ③ ┐q ④ p 前提引入 ①②假言推理前提引入 ⑤ p→(q∨r) 前提引入 ⑥ q∨r ④⑤假言推理

⑦r ③⑥析取三段论（2）设 p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。前提：p→q ,┐r→p ,┐q 结论：r 证明： ① p→q ② ┐q ③ ┐p 前提引入前提引入 ①②拒取式 ④ ┐r→p 前提引入 ⑤ r ③④拒取式返回第四章 (一阶)谓词逻辑基本概念本章自测答案 4.(1)┐ x(F(x)∧ ┐G(x))⇔ x( F (x) →G (x) ),其中,F(x)：x 是有理数,G(x) ：x 能表示成分数； (2)┐ x( F (x) →G (x) ) ⇔ x(F(x)∧ ┐G(x)),其中,F (x)：x 在北京卖菜,G (x) ：x 是外地人； (3) x( F (x) →G (x) ),其中,F (x)：x 是乌鸦,G (x) ：x 是黑色的； (4) xF(x)∧ G(x)),其中,F (x)：x 是人,G (x) ：x 天天锻炼身体。因为本题中没有指明个体域,因而使用全总个体域。 5.(1) x y (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x 是火车,G(y) ：y 是轮船,H(x,y)：x 比 y 快； (2) x y (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x 是火车,G(y) ：y 是汽车, H(x,y)：x 比 y 快； (3)┐ x(F(x)∧ y(G (y) → H (x,y)))⇔ x(F(x) → y(G(y) ∧ ┐H(x,y))),其中,F(x)：x 是汽车,G (y) ：y 是火车,H(x,y)：x 比 y 快； (4)┐ x(F(x)→ y(G(y) → H(x,y)))⇔ x y(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x 是汽车,G(y) ：y 是火车,H(x,y)：x 比 y 慢。 6.各命题符号化形式如下： (1) x y (x ．y = 0)； (2) x y (x ．y = 0)； (3) x y (y =x+1) (4) x y(x ．y = y．x) (5) x y(x ．y =x+ y) (6) x y (x + y ＜0 ) 9.(1)对任意数的实数 x 和 y,若 x ＜y,则 x ≠ y； (2)对任意数的实数 x 和 y,若 x–y = 0,则 x＜y； (3)对任意数的实数 x 和 y,若 x＜y,则 x–y≠0； (4)对任意数的实数 x 和 y,若 x–y ＜0,则 x=y. 其中,(1)(3)真值为 1(2)与(4)真值为 0. 11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。这里仅对(3)、(4)、(5)给出证明。 (3)取解释 I 为：个体域为自然数集合 N,F(x,y)：x ≤ y,在下, x y F(x,y)为真,而 x y F(x,y)也为真(只需取 x =0 即可),于是(3)中公式为真,取解释为：个体域仍为自然数集合 N,而 F(x,y)：x = y。此时, x yF(x,y)为真(取 y 为 x 即可),可是 x yF(x,y)为假,于是(3)中公式在下为假,这说明(3)中公式为可满足式。 (4)设 I 为任意一个解释,若在 I 下,蕴涵式前件 xy F(x,y)为假,则 x yF(x,y)→ y xF(x,y)为真,若前件 x yF(x,y)为真,必存在 I 的个体域 D1 中的个体常项 x0,使 yF(x0,y)为真,并且对于任意

y∈ ,F(x0,y)为真,由于有 x0∈ ,F(x0,y)为真,所以 xF(x,y)为真,又其中 y 是任意个体变项,所以 y xF(x,y )为真,由于 I 的任意性,所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。 (5)取解释为：个体域为自然数集合,F(x,y)：x = y 在下,(5)中公式为真,而将 F(x,y)改为 F(x,y)：x ＜ y,(5)中公式就为假了,所以它为可满足式。 13．（1）取解释为：个体域为自然数集合 N，F（x）：x 为奇数，G（x）：x 为偶数，在下， x（F（x）∨G（x））为真命题。取解释为：个体域为整数集合 Z，F（x）：x 为正整数，G（x）：x 为为负整数，在下， x（F（x）∨G（x））为假命题。（2）与（3）可类似解答。 14．提示：对每个公式分别找个成真的解释，一个成假的解释。返回第五章谓词逻辑等值演算与推理本章自测答案 2.(1) (F(a)∧ F(b)∧ F (c)) ∧ (G (a )∨G (b)∨G (c)) (2) (F(a)∧ F(b)∧ F (c)) ∨ (G (a)∧G (b)∧G (c)) (3) (F(a)∧ F(b)∧ F (c)) → (G (a)∧G (b)∧G (c)) (4) (F(a ,y) ∨ F(b,y)∨ F (c,y)) → (G (a)∨G (b)∨G (c)) 5.提示：先消去量词，后求真值，注意，本题 3 个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1 . (1) 的演算如下： x yF(x,y) ⇔x (F(x,3)∨F(x,4)) ⇔(F(3,3)∨F(3,4))∧(F(4,3)∨F(4 ,4)) ⇔1∧1⇔1 6.乙说得对，甲错了。本题中，全称量词的指导变元为 x ，辖域为(F (x)→G(x,y)),其中 F(x )与 G(x,y)中的 x 都是约束变元，因而不能将量词的辖域缩小。 7.演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“ ┐”。演算的第二步，在原错的基础上又用错了等值式，即 (F(x)∧(G(y)→ H(x,y))) ≠(F(x) ∧G(y)→H (x,y)) 12.公式的前束范式不唯一，下面每题各给出一个答案。 (1) (2) (3) (4) (5) x y (F(x)→ G(z,y)); x t (x,y) → G(x,t,z)); x4 ((F( ,y) →G( ,y))∧(G( ,y) →F(x4,y))); ((F( )→G( , )) → (H ( ) → L( , ))); (F( , )→(F( ) → ┐G ( , ))). 13.(1) x y(F(x) ∧G(y) ∧H(x ,y)),其中，F(x):x 是汽车，G(y)：y 是火车，H(x，y)：x 比 y 跑的快； (2) x y(F(x) ∧G(y)→H(x ,y)),其中，F(x):x 是火车，G(y)：y 是汽车，H(x，y)：x 比 y 跑的快； (3) x y(F(x) ∧G(y) ∧┐H(x ,y)),其中，F(x):x 是火车，G(y)：y 是汽车，H(x，y)：x 比 y 跑的快； (4) x y(F(x) ∧G(y) → ┐H(x ,y)),其中，F(x):x 是飞机，G(y)：y 是汽车，H(x，y)：x 比 y 慢； 14.(1)对 F(x) → xG(x)不能使用 EI 规则，它不是前束范式，首先化成前束范式。 F(x) → xG(x) <=> x(F(y)→G(x)) 因为量词辖域(F(y)→G(x))中，除 x 外还有自由出现的 y，所以不能使用 EI 规则。

(2)对 x F(x) → y G(y)也应先化成前束范式才能消去量词，其前束范式为 x y(F(x) →G(y)),要消去量词，既要使用 UI 规则，又要使用 EI 规则。 (3)在自然推理系统 F 中 EG 规则为 A(c)/∴ x (x) 其中 c 为特定的个体常项，这里 A(y) = F(y) →G(y)不满足要求。 (4)这里，使 F(a)为真的 a 不一定使 G(a)为真，同样地使 G(b)为真的 b 不一定使 F(b)为真，如，F(x):x 为奇数，G(x):x 为偶数，显然 F(3)∧G(4) 为真，但不存在使 F(x)∧G(x)为真的个体。 (5)这里 c 为个体常项，不能对 F(c)→G(c)引入全称量词。 15.(1)证明：① xF(x) 前提引入 ② xF(x)→ y((F(y)∨G(y)) →R(y)) 前提引入 ③ y((F(y)∨G(y)) →R(y) ①②假言推理 ①EI ③UI ④附加 ⑤⑥假言推理 ⑦EG 前提引入前提引入 ①EI ②UI ③④假言推理 ⑤化简 ③⑥合取 ⑦EG 前提引入 ①置换 ②UI 前提引入 ④UI ③⑤析取三段论 ⑥EG 前提引入 ①UI 前提引入 ③UI 前提引入 ⑤UI ④⑥析取三段论 ②⑦析取三段论 ⑧UG ④F(c) ⑤(F(c)∨G(c))→R(c) ⑥F(c)∨G(c) ⑦R(c) ⑧ xR(x) (2)证明① xF(x) ② x((F(x)→G(a)∧R(x))) ③F(c) ④F(c)→G(a)∧R(a) ⑤G(a)∧R(c) ⑥R(c) ⑦F(c)∧R(c) ⑧ x(F(x)∧R(x)) (3)证明：①┐ xF(x) ② x┐F(x) ③┐F(c) ④ x(F(x)∨G(x)) ⑤F(c)∨G(c) ⑥F(c) ⑦ xF(x) (4)证明① x(F(x)∨G(x)) ②F(y)∨G(y) ③ x(┐G(x)∨┐R(x)) ④┐G(y)┐R(y) ⑤ x R(x) ⑥R(y) ⑦┐G(y) ⑧F（y） ⑨ xF(x) 17．本题不能用附加前提证明法. 20.(1)与(2)均可用附加前提证明法。

22.(1)设 F(x)：x 为偶数，G(x):x 能被 2 整除。前提: x(F(x)→G(x))，F(6) 结论：G(6) (2)设 F(x)：x 是大学生，G(x):x 是勤奋的，a：王晓山。前提: x(F(x)→G(x))，┐G(a) 结论：┐F(a) 23.(1)设 F(x)：x 是有理数，G(x):x 是实数，H(x)：x 是整数。前提: x( F(x)→G(x))， x(F(x)∧H(x)) 结论: x(G(x)∧H(x)) 证明提示：先消存在量词。 (2)设 F(x)：x 是有理数，G(x):x 是无理数，H(x)：x 是实数，I(x)：x 是虚数。前提: x((F(x)∨G(x)) →H(x))， x( I(x)→┐H(x)) 结论: x(I(x)→(┐F(x)∧┐G(x))) 证明① x(I(x)→(┐H(x)) ②I(y)→H(y) ③ x((F(x)∨G(x))→H(x)) ④(F(y)∨G(y))→H(y) ⑤┐H(y)→(┐F(y)∧┐G(y)) 前提引入 ①UI 前提引入 ③UI ④置换 ⑥I(y)→(┐F(y)∧┐G(y)) ②⑤假言三段论 ⑦ x(I(x)→(┐F(x)∧┐G(x)) ⑧UG 24.设 F(x)：x 喜欢步行，G(x)：x 喜欢骑自行车，H(x)：x 喜欢乘汽车。前提: x(┐F(x)→┐G(x))， x(G(x)∨H(x))， x┐H(x) 结论: x┐F(x) 证明① x┐H(x) ②┐H(c) ③ x(G(x)∨H(x)) ④G(c)∨H(c) ⑤G(c) ⑥ x(F(x) →G(x)) ⑦F(c)→┐G(c) ⑧┐F(c) ⑨ x┐F(x) 前提引入 ①UI 前提引入 ③UI ②④析取三段论前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 25.设 F(x)：x 是科学工作者，G(x)：x 是刻苦钻研的，H(x)：x 是聪明的，I(x)：x 在事业中获得成功。前提: x(F(x)→G(x))， x(G(x)∧H(x)→I(x))，a：王大海，F(a)，H(a) 结论：I(a) 证明①F(a) ② x(F(x)→G(x)) ③F(a)→G(a) ④G(a) ⑤H(a) ⑥ x(G(x)∧H(x)→I(x)) ⑦G(a)∧H(a)→I(a) ⑧G(a)∧H(a) 前提引入前提引入 ②UI ①③假言推理前提引入前提引入 ⑥UI ④⑤合取

分享到：

赞收藏

资料库

离散数学课后答案第二版曲婉玲主编.doc

相关推荐

课程资源

热门标签

最新资料