当前位置：文档之家 › 离散数学第2章习题解答

离散数学第2章习题解答

  • 格式：docx
  • 大小：38.01 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

离散数学课后答案(第1-2-4章)武汉大学出版社

离散数学课后答案(第1-2-4章)武汉大学出版社

离散数学课后答案(第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. 每小题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, 从而主析取范式为m0m1m3m7, 主合取范式为M2 M4 M5 M6.真值表法公式 (p q) (q r) 真值表如下:p q r(p q) (qr)00010011010001111000101011001111013724 M5 M6.。

离散数学第2章习题解答

离散数学第2章习题解答
(F(a) F(b) F(c) (G(b) G(c)).
(2)xF(x) yG(y)
xF(x) yG(y)(量词辖域收缩扩张等值式)
(F(a) F(b) F(c)) (G(a) G(b) (c)).
(3)x yH(x,y)
x(H(x,a) H (x,b) H(x,c)
(H(a,a) H (a,b) H(x,c)
“存在自然数x,x发既为奇数，又为偶数。 ”
取x2，则F(2)为假，于是F(2) G(2)为真，这表明x(F(x) G(x)为真命题。
分析本题说明
x(F(x) G(x)) x(F(x) G(x)), x(F(x) G(x)) x(F(x) G( x)),
这里，A B表示A与B不等值，以后遇到，含义相同。
“对于任意的实数x和y，如果x为有理数，y为元理数，则x y。” 这是假命题。
分析 闭式在任何解释下不是真就是假， 不可能给出解释I,使得闭式在I下真值不确定，这一点是闭式的一个重要特征。 而非封闭的公式就没有这个特征。
2.9取A1L(f(x,y),g(x,y))和A2x( f (x, y), x)，则A1和A2都是非土产的公式，在A1中，x, y都是自由出现的，在A2中，y是自出现的。
2.5(1)取解释I1为：个体域D R(实数集合)，F ( x) : x为有理数，G( x) : x能表示成分数，在I1下，x(F(x) G(x))的含义为
“对于叙何实数x而言，若x为有理数， 则x能表示成分数”，简言之为“有 理数都能表示成分数。 ”在此蕴含式中，当前件F ( x)为真时，后件G(x)也为真， 不会出现前件为真， 后件为假的情况， 所以在I1下，x(F(x) G (x))为真命题。
( H (b,a) H (b,b) H (b, c)

离散数学课后习题答案(第二章)

离散数学课后习题答案(第二章)
习题 2-1,2-2 （1） 用谓词表达式写出下列命题。 a) 小张不是工人。 解：设 W（x） ：x 是工人。c：小张。 则有 ¬W ( c )
b) 他是田径或球类运动员。 解：设 S（x） ：x 是田径运动员。B（x） ：x 是球类运动员。h：他 则有 S（h）∨B（h） c) 小莉是非常聪明和美丽的。 解：设 C（x） ：x 是聪明的。B（x） ：x 是美丽的。l：小莉。 则有 C（l）∧ B（l） d）若 m 是奇数，则 2m 不是奇数。 解：设 O（x） ：x 是奇数。 则有 O（m）→¬ O（2m） 。 e)每一个有理数是实数。 解：设 R（x） ：x 是实数。Q（x） ：x 是有理数。 则有 （∀x） （Q（x）→R（x） ） f) 某些实数是有理数。 解：设 R（x） ：x 是实数。Q（x） ：x 是有理数。 则有 （∃x） （R（x）∧Q（x） ） g) 并非每个实数都是有理数。 解：设 R（x） ：x 是实数。Q（x） ：x 是有理数。 则有 ¬（∀x） （R（x）→Q（x） ） h)直线 A 平行于直线 B，当且仅当直线 A 不相交于直线 B。 解：设 P（x，y） ：直线 x 平行于直线 y，G（x，y） ：直线 x 相交于直线 y。 则有 P（A，B）�¬G（A，B） （2） 找出以下十二个句子所对应的谓词表达式。 a) 所有的教练员是运动员。 （J(x)，L(x)） 解：设 J(x)：x 是教练员。L(x)：x 是运动员。 则有 （∀x） （J（x）→L（x） ） b) 某些运动员是大学生。 （S(x)） 解：设 S(x)：x 是大学生。L(x)：x 是运动员。 则有 （∃x） （L（x）∧S（x） ） c) 某些教练是年老的，但是健壮的。 （O(x)，V（x） ） 解：设 J(x)：x 是教练员。O(x)：x 是年老的。V（x） ：x 是健壮的。 则有 （∃x） （J（x）∧O（x）∧V（x） ） d) 金教练既不老但也不健壮的。 （j） 解：设 O(x)：x 是年老的。V（x） ：x 是健壮的。j：金教练 则有 ¬ O（j）∧¬V（j） e) 不是所有的运动员都是教练。 解：设 L(x)：x 是运动员。J(x)：x 是教练员。 则 ¬（∀x） （L（x）→J（x） ） f) 某些大学生运动员是国家选手。 （C（x） ）

离散数学(微课版) 第2章习题答案

离散数学(微课版) 第2章习题答案

离散数学（微课版）第2章习题答案习题 2.11. 给出以下相关数集的定义：•人类：所有人类的集合。

•学生：具有在某所学校注册学籍的人的集合。

•男学生：具有在某所学校注册学籍且性别为男性的学生的集合。

2. 判断以下命题是否为真：•男学生集合是人类集合的子集。

•学生集合是男学生集合的子集。

答案：1.人类集合和学生集合的关系可以表示为：学生集合是人类集合的子集。

因为学生是人类的一个子集，但并不是全部人类都是学生。

2.男学生集合是人类集合的子集，因为男学生是学生的一个子集，而学生又是人类的一个子集。

所以男学生集合也是人类集合的一个子集。

3.学生集合是男学生集合的超集，因为男学生是学生的一个子集，但并不是所有学生都是男学生。

所以学生集合包含了男学生集合。

习题 2.21. 给出以下关系的定义：•R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}。

2. 判断以下命题是否为真：•R 是对称关系。

•R 是自反关系。

答案：1.该关系 R 中的元素可以表示为有序对的形式，如 (1, 1) 表示元素 1 和元素 1 之间存在关系。

根据 R 的定义，可以发现所有的对称元素都存在于 R 中。

所以 R 是一个对称关系。

2.该关系 R 中包括了所有元素对 (x, x)，表示每个元素和它自己之间都存在关系。

所以 R 是一个自反关系。

习题 2.31. 给出以下集合的定义：• A = {1, 2, 3, 4}• B = {2, 4, 6, 8}• C = {1, 3, 5, 7}2. 判断以下命题是否为真：• A ∩ B = {2, 4}• A ∪ C = {1, 2, 3, 4, 5, 7}答案：1. A ∩ B表示 A 和 B 的交集，即包含了同时属于 A 和B 的元素。

根据 A 和 B 的定义，可以发现共同元素为 {2, 4}。

所以命题A ∩ B = {2, 4} 是真的。

2. A ∪ C 表示 A 和 C 的并集，即包含了属于 A 或 C 的所有元素。

离散数学习题解答-第2章命题逻辑

离散数学习题解答-第2章命题逻辑

(2) 有 4 个不同的命题变元，使公式的真值为 0 的赋值有 p 0, q 0, r 1, w 0 ；
p 0, q 1, r 0, w 1 ； p 0, q 1, r 1, w 0 ； p 1, q 1, r 0, w 1 ；
3
p 1, q 1, r 1, w 1 ； 使 公 式 的 真 值 为 1 有 赋 值 有 p 0 , q 0 ,r 0 ,w ； 0 p 0, q 0, r 0, w 1 ； p 0, q 0, r 1, w 1 ； p 0, q 1, r 0, w 0 ； p 0, q 1, r 1, w 1 ； p 1, q 0, r 0, w 0 ； p 1, q 0, r 0, w 1 ； p 1, q 0, r 1, w 0 ； p 1, q 0, r 1, w 1 ； p 1, q 1, r 0, w 0 ； p 1, q 1, r 1, w 0 ；
((p q) s) (r t )
3. 列出下列各公式的所有赋值， 并指出哪些赋值使公式的真值为 1， 哪些赋值使公式的真值 为 0。 (1) ( p q) r r (2) (w q) ( p r ) w (3) (( p q) ( p q)) p (4) ((u q) (t r )) (r u) (5) (m q) ((q r ) s) (6) (m q) (t r ) q 解 ： (1) 有 3 个 不 同 的 命 题 变 元 ， 使 公 式 的 真 值 为 0 的 赋 值 有 p 0, q 0, r 0 ；
p 0, q 0, r 1 ； p 0, q 1, r 0 ； p 0, q 1, r 1 ； p 1, q 0, r 1 ； p 1, q 1, r 0 ； p 1, q 1, r 1 . 使公式的真值为 1 有赋值有 p 1, q 0, r 0 .

离散数学(刘任任版)第2章答案

(4) 反对称关系矩阵 M R (rij )nn 的元素满足： 当i≠j 时 ， rij rji 0 。
而关系图中任何两个结点之间的有向弧是单向的。 （即若关系R是反对称的，当且仅当关系矩阵中 以对角线对称的元素不能同时为1，在关系图上 任两个结点的定向弧线不可能成对出现）
5.
R·S={<1,4>,<1,3>},S·R={<3,4>}; R 2={<1,1>,<1,2>,<1,4>}; S 2={<2,2>,<3,4>,<3,3>}.
β(A×A-{<x,x>})=2n2-n
(4)共有2n 2n(n1)/ 2 2n(n1)/ 2 种定义在A上
的不同的对称关系; 说明: ∵A上的对称关系必须满足：如果<x,y>在
这个关系中，则<y,x>也必须在这个关系中。 ∴在构造A上的对称关系的时候可以先将所有 的<x,y>和<y,x>（其中x≠y）看成是一个整体。 ∴要考虑的序偶的个数有：
s(R1) s(R2 ) (R1 R11) (R2 R21)任取 x, y s(R1 R2 ) (R1 R2 ) (R1 R2 )1 (i)若 x,y (R1 R2 ),
则 x, y R1 R1 R11,且 x, y R2 R2 R21,从而 x,y (R1 R11) (R2 R21)
14.
证明 S {Ai Bj | Ai Bj } (1)由S定义知, Ai Bj (2)任取Ai Bi S和Al Bm S, 1 i, j r,1 j, m s ( Ai Bj ) ( Al Bm ) ( Ai Am ) (Bj Bm )

离散数学 第2章 习题解答

习题 2.11．将下列命题符号化。

(1) 4不是奇数。

解：设A(x)：x是奇数。

a：4。

“4不是奇数。

”符号化为：¬A(a)(2) 2是偶数且是质数。

解：设A(x)：x是偶数。

B(x)：x是质数。

a：2。

“2是偶数且是质数。

”符号化为：A(a)∧B(a)(3) 老王是山东人或河北人。

解：设A(x)：x是山东人。

B(x)：x是河北人。

a：老王。

“老王是山东人或河北人。

”符号化为：A(a)∨B(a)(4) 2与3都是偶数。

解：设A(x)：x是偶数。

a：2，b：3。

“2与3都是偶数。

”符号化为：A(a)∧A(b)(5) 5大于3。

解：设G(x,y)：x大于y。

a：5。

b：3。

“5大于3。

”符号化为：G(a,b)(6) 若m是奇数，则2m不是奇数。

解：设A(x)：x是奇数。

a：m。

b：2m。

“若m是奇数，则2m不是奇数。

”符号化为：A(a)→A(b)(7) 直线A平行于直线B当且仅当直线A不相交于直线B。

解：设C(x,y)：直线x平行于直线y。

设D(x,y)：直线x相交于直线y。

a：直线A。

b：直线B。

“直线A平行于直线B当且仅当直线A不相交于直线B。

”符号化为：C(a,b)↔¬D(x,y)(8) 小王既聪明又用功，但身体不好。

解：设A(x)：x聪明。

B(x)：x用功。

C(x)：x身体好。

a：小王。

“小王既聪明又用功，但身体不好。

”符号化为：A(a)∧B(a)∧¬C(a)(9) 秦岭隔开了渭水和汉水。

解：设A(x,y,z)：x隔开了y和z。

a：秦岭。

b：渭水。

c：汉水。

“秦岭隔开了渭水和汉水。

”符号化为：A(a,b,c)(10) 除非小李是东北人，否则她一定怕冷。

解：设A(x)：x是东北人。

B(x)：x怕冷。

a：小李。

“除非小李是东北人，否则她一定怕冷。

”符号化为：B(a)→¬A(a)2．将下列命题符号化。

并讨论它们的真值。

(1) 有些实数是有理数。

解：设R(x)：x是实数。

离散数学(屈婉玲版)第二章习题答案

2.13 设解释I为：个体域D I ={-2,3,6},一元谓词F（X）：X≤3，G（X）：X>5,R(X):X≤7。

在I下求下列各式的真值。

（1）∀x(F(x)∧G(x))解：∀x(F(x)∧G(x))⇔(F(-2) ∧G(-2)) ∧(F(3) ∧G(3)) ∧(F(6) ∧G(6))⇔((-2≤3) ∧(-2>5)) ∧((3≤3) ∧(3>5)) ∧((6≤3) ∧(6<5))⇔((1 ∧0))∧((1 ∧0)) ∧((0 ∧0))⇔0∧0∧0⇔0(2) ∀x(R(x)→F(x))∨G(5)解：∀x(R(x)→F(x))∨G(5)⇔(R(-2)→F(-2))∧ (R(3)→F(3))∧ (R(6)→F(6))∨ G(5)⇔((-2≤7) →(-2≤3))∧ (( 3≤7) →(3≤3))∧ (( 6≤7) →(6≤3)) ∨ (5>5)⇔(1 →1)∧ (1 →1)∧ (1→0) ∨ 0⇔1∧ 1∧ 0 ∨ 0⇔0(3)∃x(F(x)∨G(x))解：∃x(F(x)∨G(x))⇔(F(-2) ∨ G(-2)) ∨ (F(3) ∨G(3)) ∨ (F(6) ∨G(6))⇔((-2≤3) ∨ (-2>5)) ∨ ((3≤3) ∨ (3>5)) ∨ ((6≤3) ∨ (6>5))⇔(1 ∨ 0) ∨ (1 ∨ 0) ∨ (0 ∨ 1)⇔1 ∨ 1 ∨ 1⇔12.14 求下列各式的前束范式，要求使用约束变项换名规则。

（1）⌝∃xF(x)→∀yG(x,y)(2) ⌝（∀xF(x,y) ∨∃yG(x,y) ）解：（1）⌝∃xF(x)→∀yG(x,y)⇔⌝∃xF(x)→∀yG(z,y) 代替规则⇔∀x⌝F(x)→∀yG(z,y) 定理2.1（2 ）⇔∃x(⌝F(x)→∀yG(z,y) 定理2.2（2）③⇔∃x∀y(⌝F(x)→G(z,y)) 定理2.2（1）④（2）⌝（∀xF(x,y) ∨∃yG(x,y) ）⇔⌝(∀zF(z,y) ∨∃tG(x,t)) 换名规则⇔⌝(∀zF(z,y) )∧⌝(∃tG(x,t) )⇔∃z⌝F(z,y) ∧∀t⌝G(x,z)⇔∃z (⌝F(z,y) ∧∀t⌝G(x,z))⇔∃z ∀t(⌝F(z,y) ∧⌝G(x,t))2.15 求下列各式的前束范式，要求使用自由变项换名规则。

离散数学答案第二章习题解答

离散数学答案第二章习题解答第二章谓词逻辑习题与解答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 =??。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
当然非闭式也可以是逻辑有效式(如F(x) F(x))，也可能为矛盾式(如
F(x) F(x))，也可能不存在其值不确定的解释。
2．10(1)
xA(x)
(A(a)
A(b)
A(c))
(消去量词等值式)
A(a)
A(b)
A(c)
(德·摩根律)
x A(x)
(消去量词等值式)
2)
xA(x)
(A(a)
A(b)
A(c))
( H (b,a) H (b,b) H (b, c)
(H(c,a) H(c,b) H (c,c)
分析 在有穷个体域内消去量词时， 应将量词的辖域尽量缩小， 例如，在(2) 中，首先将量词辖域缩小了(因为yG(y)中不含x，所以，可以缩小)。否则，演算是相当麻烦的。见下面的演算：
x(F(x) yG(y)
x(F(x) (G(x) H (x))
(2)令F(x):x是人，G(y):y是化，H (x) : x喜欢，命题符号化为x(F(x) y(G(y) H ( x, y)))
(3)令F(x):x是人，G(x) : x犯错误，命题符号化为
x(F(x) G(x)),
或另一种等值的形式为
x(F(x) G(x)
(4)令F(x): x在北京工作，G( x) : x是北京人，命题符号化为
在一阶逻辑中，将命题符号化时，当引入特性谓词(如题中的F(x))之后，
全称量词后往往使用联结词→而不使用，而存在量词 后往往使用 ，而不使用→，如果用错了，会将真命题变成假命题，或者将假命题变成真命题。
2．6在解释R下各式分别化为
(1)x( x 0);
(2)x y(x y x);
(3)x y z(x y) (x z y z));
“对于任意的实数x和y，如果x为有理数，y为元理数，则x y。” 这是假命题。
分析 闭式在任何解释下不是真就是假， 不可能给出解释I,使得闭式在I下真值不确定，这一点是闭式的一个重要特征。 而非封闭的公式就没有这个特征。
2.9取A1L(f(x,y),g(x,y))和A2x( f (x, y), x)，则A1和A2都是非土产的公式，在A1中，x, y都是自由出现的，在A2中，y是自出现的。
第
2.1本题没有给出个体域,因而使用全总个体域.
(1)令F(x) :x是鸟
G(x): x会飞翔.
命题符号化为
x(F(x) G(x)).
(2)令F(x) : x为人.
G(x): x爱吃糖
命题符号化为
x(F(x) G(x))
或者
x(F(x) G(x))
(3)令F(x) : x为人.
G(x): x爱看小说.
3° (2)与(4)中两种符号化公式是等值的，请读者正确的使用量词否定 等值式，证明(2)，(4)中两公式各为等值的。
2.2(1)d (a),(b),(c)中均符号化为
xF(x)
其中F(x):(x1)2x22x1,此命题在(a),(b),(c)中均为真命题。
(2)在(a),(b),(c)中均符号化为
x(F(x) G(x))
即用合取联结词取代蕴含联结词，这是万万不可的。将(1)中命题叙述得 更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。 ”因而符号化应该使用联结词→而不能使用。若使用 ，使(1)中命题变成了 “宇 宙间的一切事物都是鸟并且都会飞翔。 ”这显然改变了原命题的意义。
取解释I为，个体域D=N(N为自然数集合)，f(x,y,) x y,g(x,y) x y L(x,y)为x y。在I下，A1为x y x y为假，所以在I下，A1真值不确定，即在I下A2的真值也是命题。
在I下，A2为x(x y x),当y0时，它为真；y 0时为假，在I下A2的真值也不确定。
分析 非闭式与 闭式的显著区别是， 前者可能在某些解释下， 真值不确定， 而后者对于任何解释真值都确定，即不是真就是假。
(4)x y(x x 2y).
易知，在解释R下，(1)，(2)为假；，(3)(4)为真。
2．7给定解释I为：个体域D=N(自然数集合)，F (x) : x为奇数，G(x):x为偶数。
(数就是偶数， 则所有自然数全为奇数， 或所有自 然数全为偶数。”因为蕴含式的前件为真，后件为假，所以真值为假。
141yxygxxf????yxygxfx?????量词否定等值式yxygzfz?????约束变项换名规则yxgzfyz?????量词辖域收缩扩张等值式yxgzfyz????2yxygyxxf????yxgyyxfx??????2211zxgzyzfz??????2121zxgyzfzz??????在以上演算中分别使用了德摩根律量词否定等值式约束变项换名规则等
(F(a) yG(y)) (F(b) yG(y)) F(c) yG(y))
(F(a) (G(a) G(b) G(c)
(F(b) (G(a) G(c))
(F(c) (G(a) G(b) G(c))
(F(a) (F(b) (G(a) G(b) (c)).
显然这个演算比原来的演算麻烦多了
2.13在I下
(F( 2) G( 2)) (F(3) G(3)) F(6) G(6))
(4)存在着x，对所有的y，都有x y1，在(a),(b)(c)(d)中都是假命题。
(5)对所有的x，存在着y，使得x y x在(a),(b)(c)(d)中都是真命题。
(6)存在x，对所有的y，都有x y x，在(a),(b)中为真命题，在(c)(d)中 为假命题。
(7)对于所有的x和y，存在着z，使得x y z，在(a), (b)中为真命题，在(c)(d)中为假命题。
(1 0) (1 0) (0 1) 0,
y(F(z) G(x,y)
( xF(x,y) yG(x, y))
x F(x,y) y G(x,y)
“存在自然数x,x发既为奇数，又为偶数。 ”
取x2，则F(2)为假，于是F(2) G(2)为真，这表明x(F(x) G(x)为真命题。
分析本题说明
x(F(x) G(x)) x(F(x) G(x)), x(F(x) G(x)) x(F(x) G( x)),
这里，A B表示A与B不等值，以后遇到，含义相同。
xG(x)
其中G(x) :x 2 0，此命题在(a)中为假命题，在(b)(c)中均为真命题。
(3)在(a),(b), (c)中均符号化为
xH (x)
其中H(x):5x1.此命题在(a),(b)中均为假命题，在(c)中为真命题。
分析1°命题的真值与个体域有关。
2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。
G(x))
(理词否定等值式)
x( F(x)
G(x))
(德·摩根律)
x(F(x)
G(x))
(蕴含等值式)
最后得到的公式满足要求(只含全称量词) ，将它翻译成自然语言，即为
并不是北京人都去过香山
可见，“有的北京人没过过香山。 ”与“并不是北京人都去过香山。 ”是同一 命题不同的叙述方法。
2.12(1)xF(x) yG(y)
在个体域为人类集合时，应符号化为
xF(x)
这里，F(x):x呼吸，没有引入特性谓词。
在个体域为全总个体域时，应符号化为
x(F(x) G(x))
这里，F(x):x为人，且F (x)为特性谓词。G(x): x呼吸。
2．3因题目中未给出个体域，因而应采用全总个体域。
(1) 令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题 符号化为
命题符号化为
x(F(x) G(x)).
(4)F(x) :x为人.
G(x): x爱看电视.
命题符号化为
x(F(x) G(x)).
分析1°如果没指出要求什么样的个体域， 就使用全总个休域， 使用全总个 体域时，往往要使用特性谓词。 (1)-(4)中的F ( x)都是特性谓词。
2° 初学者经常犯的错误是，将类似于(1)中的命题符号化为
x(F(x) G( x)),
或
x(F(x) G(x)),
(5)令F ( x) : x是金属，G( y) : y是液体，H(x,y):x溶解在y中，命题符号化为
x(F(x) y(G(y) H(x, y))).
(6)令F(x):x与y是对顶角，H(x,y):x与y相等，命题符号化为
x y(F (x, y) H(x,y)).
给定解释I1：个体域D=N(整数集合)，F ( x) : x为正数，G(x):x为负数，L(x,y):x y，在I1下，A的含义为
“对于任意的整数x和y，如果x为正整数，y为负整数，则x y。”
这是真命题。
设解释I2：个体域D=R(R整数集合)，F (x) : x为有理数，G( y) : y为无理数，L(x,y):x y，在I2下，A的含义为
分析 (2)，(5)，(6)中要使用2无谓词，用它们来描述事物之间的关系。
2.4(1)对所有的x，存在着y，使得x y 0，在(a), (b)中为真命题，在(c),(d)中为假命题。
(2)存在着x,对所有的y，都有x y 0，在(a),(b)中为真命题，在(c),(d)中为假命题。
3)对所有x，存在着y，使得x y 1，在(a),(b)(c)中均为假命题，而在(d)中为真命题。
在在I1下，x(F(x) G(x))的含义为
“对于任何实数x,x既为有理数，又能表示成分数。 ”
取x 2，则F( 2) g( 2)显然为假，所以，在I1下，x(F(x) G(x))为假命题.
(2)取解释I2为:个体域D=N(自然数集合),F(x):x为奇数,G(x):x为偶数,在I2下,x(F(x) G(x))的含义为
(消去量词等值式)
2．11(1) 令F(x) : x为人。