离散数学第二章
2.1 等值式
一、等值式的概念
两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。
设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式A B应为重言式。
定义2.1设A,B式两个命题公式，若A,B构成的等价式A B为重言式，则称A与
B是等值的，记作A B.
定义中给出的符号不是联结词符，它是用来说明A与B等值（A B是重言式）的一种记法，因而是元语言符号。此记号在下文中频繁出现，千万不要将它与混为一谈，同时也要注意它与一般等号=的区别。
判断等值式有如下方法：
1.真值表
2.等值演算
3.范式
二、用真值表判断公式的等值
例2.1判断下面两个公式是否等值：
┐(p∨q)与┐p∧┐q
解用真值表法判断┐(p∨q)(┐p∧┐q)是否为重言式。此等价式的真值表如表2.1所示，从表中可知它是重言式，因而┐(p∨q)与┐p∧┐q等值，即┐(p∨q)(┐p∧┐q)。
其实，在用真值表法判断A B是否为重言式时，真值表的最后一列（即A B的真值表的最后结果）可以省略。若A与B的真值表相同，则A B，否则，A B（用来表示A与B不等值，也是常用的元语言符号）。
表2.1 (p∨q)(┐p∧┐q)的真值表
例2.2判断下列各组公式是否等值：
（1）p→(q→r)与(p∧q)→r
（2）(p→q)→r与(p∧q)→r
解表2.2中列出了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
表2.2 3个公式的真值表
三、等值演算
虽然用真值法可以判断任何两个命题公式是否等值，但当命题变项较多时，工作量是很大的。可以先用真值表验证一组基本的又是重要的重言式，以它们为基础进行公式之间的演算，来判断公式之间的是否等值。本书给出16组重要的等值式，希望读者牢牢记住它们。在下面公式中出现的A,B,C仍然是元语言符号，它们代表任意的命题公式。
1. 双重否定律
A┐┐A （2.1）
2. 幂等律
A A∨A,A A∧A （2.2）
3. 交换律
A∨B B∨A，A∧B B∧A （2.3）
4. 结合律
(A∨B)∨C A∨(B∨C)
(A∧B)∧C A∧(B∧C) （2.4）
5. 分配律
A∨(B∧C)(A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C)(A∧B)∨(A∧C) （∧对∨的分配律）（2.5）
6. 德摩根律
┐(A∨B)┐A∧┐B，┐(A∧B)┐A∨┐B （2.6）
7. 吸收律
A∨(A∧B)A，A∧(A∨B) A （2.7）
8. 零律
A∨11,A∧00 （2.8）
9. 同一律
A∨0A，A∧1 A （2.9）
10. 排中律
A∨┐A 1 （2.10）
11. 矛盾律
A∧┐A0 （2.11）
12. 蕴涵等值式
A→B┐A∨B （2.12）
13. 等价等值式
(A B)(A→B)∧(B→A) （2.13）
14. 假言易位
A→B┐B→┐A （2.14）
15. 等价否定等值式
A B┐A┐
B （2.15）
16. 归谬论
(A→B)∧(A→┐B)┐A （2.16）
以上16组等值式包含了24个重要等值式。由于A,B,C可以代表任意的公式，因而以上各等值式都是用元语言符号书写的，称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式（2.12）中，取A=p，B=q时，得等值式
p→q┐ p∨q
当取A=p∨q∨r，B=p∧q时，得等值式
(p∨q∨r)→(p∧q) ┐(p∨q∨r)∨(p∧q)
这些具体的等值式都被称为原来的等值式模式的代入实例。每个具体的代入实例的正确性都可以用真值表证明之，而每个等值式模式可用归纳法证明之。
由已知的等值式可以推演出更多的等值式，简单快速推理，还需要一些保持等值性的规则。
置换规则设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，若B A，则Φ(B)Φ(A).
此置换规则的正确性，可用归纳法证明之。
例如，在公式(p→q)→r中，可用┐p∨q置换其中的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∨r)∧(┐q∨r)
将以上过程连在一起，得到
公式之间的等值关系具有自反性、对称性和传递性，所以上述演算中得到的5个公式彼此之间都是等值的。在演算的每一步都用到了置换规则，因而在以下的演算中，置换规则均不标出。
上述用等值式及等值规则进行推演的过程称为等值演算，这是数理逻辑的主要内容。例2.3用等值演算法验证等值式：
(p∨q)→r(p→r)∧(q→r)
证可以从左边开始演算，也可以从右边开始演算。现在从右边开始演算。
所以，原等值式成立。读者亦可从左边开始演算验证之。
例2.3说明，用等值演算法可以验证两个公式等值。但一般情况下，不能用等值演算法直接验证两个公式不等值。
例2.4证明：(p→q)→r p→(q→r)
证方法一：真值表法。读者自己证明
方法二：观察法。易知，010是(p→q)→r的成假赋值，而010是p→(q→r)的成真赋值，所以原不等值式成立。
方法三：设A=(p→q)→r,B=p→(q→r)
先将A,B通过等值演算化成容易观察真值的情况，再进行判断。
A=(p→q)→r
(┐p∨q)→r （蕴涵等值式）
┐(┐p∨q)∨r （蕴涵等值式）
(p∧┐q)∨r （德摩根律）
B=p→(q→r)
┐p∨(┐q∨r) （蕴涵等值式）
┐p∨┐q∨r （结合律）
容易观察到，000，010是A的成假赋值，而它们是B的成真赋值。等值演算还能帮助人们解决工作和生活中的判断问题。
例2.5用等值演算判断下列公式的类型：
（1）(p→q)∧p→q
（2）(p→(p∨q))∧r
（3）p∧(((p∨q)∧┐p)→q)
解在以下的演算中没有写出所用的基本等值式，请读者自己填上。（1）(p→q)∧p→q
(┐p∨q)∧p→q
┐((┐p∨q)∧p)∨q
(┐(┐p∨q)∨┐p)∨q
((p∧┐q)∨┐p)∨q
((p∨┐p)∧(┐q∨┐p))∨q
(1∧(┐q∨┐p))∨q
(┐q∨q)∨┐p
1∨┐p
1
最后结果说明（1）中公式是重言式。
（2）┐(p→(p∨q))∧r
┐(┐p∨p∨q)∧r
(p∧┐p∧┐q)∧r
0∧r
最后结果说明（2）中公式是矛盾式。
（3）p∧(((p∨q)∧┐p)→q)
p∧(┐((p∨q)∧┐p)∨q)
p∧(┐((p∧┐p)∨(q∧┐q))∨q)
p∧(┐(0∨(q∧┐p))∨q)
p∧(┐q∨p∨q)
p∧1
p
最后结果说明（3）中公式不是重言式，00，01都是成假赋值。并且也不是矛盾式，因为10，11都是成真赋值。
等值演算中各步得出的等值式所含命题变项可能不一样多，如（3）中最后一步不含q，此时将q看成它的哑元，考虑赋值时将哑元也算在内，因而赋值的长度为2，这样，可将（3）中各步的公式都看成含命题变项p,q的公式，在写真值表时已经讨论过类似的问题的。
从例2.5可知，用等值演算判断公式的类型式是不太方便的，特别是判断非重言式的可满足式就更不方便了。在下节中将给出更简单的方法。
例2.6在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：
甲说王教授不是苏州人，是上海人。
乙说王教授不是上海人，是苏州人。
丙说王教授既不是上海人，也不是杭州人。
听完以上3人的判断后，王教授笑着说，他们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人？
解设命题
p：王教授是苏州人。
q：王教授是上海人。
r：王教授是杭州人。
p,q,r中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。设
甲的判断为A1=┐p∧q
乙的判断为A2=p∧┐q
丙的判断为A3=┐q∧┐r
则
甲的判断全对B1=A1=┐p∧q
甲的判断对一半B2=((┐p∧┐q)∨(p∧q))
甲的判断全错B3=p∧┐q
乙的判断全对C1=A2=p∧┐q
乙的判断对一半C2=((p∧q)∨(┐p∧┐q))
乙的判断全错C3=┐p∧q
丙的判断全对D1=A3=┐q∧┐r
丙的判断对一半D2=(q∧┐r)∨(┐q∧r))
丙甲的判断全错D3=q∧r
由王教授所说
E=(B1∧C2∧D3)∨(B1∧C3∧D2)∨(B2∧C1∧D3)∨(B2∧C3∧D1)∨(B2∨C1∧D2)∨(B3∧C2∧D1)
为真命题。而
B1∧C2∧D3=(┐p∧q)∧((┐p∧┐q)∨(p∧q))∧(q∧r)
(┐p∧q∧┐q∧r)∨(┐p∧q∧p∧r)
B1∧C3∧D2=(┐p∧q)∧(┐p∧q)∧((q∧┐r)∨(┐q∧r))
(┐p∧q∨r)∨(┐p∧q∧┐q∧r)
┐p∧q∧┐r
B2∧C1∧D3=((┐p∧q)∨(p∧q))∧(p∧┐q)∧(q∧r)
(┐p∧q∧p∧┐q∧q∧r)∨(p∧q∧┐q∧r)
类似可得
B2∧C3∧D10
B3∧C1∧D2p∧┐q∧r
B3∧C2∧D10
于是，有同一律可知
E(┐p∧q∧┐r)∨(p∧┐q∧r)
但因为王教授不能既是上海人，又是杭州人，因而p,r必有一个假命题，即p∧┐q∧r 0，于是
E┐p∧q∧┐r
为真命题，因而必有p,r为假命题，q为真命题，即王教授是上海人。甲说的全对，丙说对了一半，而乙全说错了。
读者应可以模仿该例判断引言中问题的正确性。
离散数学答案屈婉玲版第二版高等教育出版社课后答案
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 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?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数1 q: 3是无理数0 r: 2是无理数 1 s: 6能被2整除1 t: 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 ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式
（5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ?(?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q)
离散数学 第2章 习题解答
第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x (是鸟 x F:) (会飞翔. G:) x x 命题符号化为 x F ?. G x→ ) ( )) ( (x (2)令x x (为人. F:) (爱吃糖 G:) x x 命题符号化为 x F x→ G ?? )) ( ) ( (x 或者 F x? x ∧ ? ) )) ( ( (x G (3)令x x (为人. F:) G:) (爱看小说. x x 命题符号化为 x F ?. G x∧ (x ( )) ( ) (4) x (为人. x F:) (爱看电视. G:) x x 命题符号化为 F x? ∧ ??. x G ( ) ( )) (x 分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的) F都是特性谓词。 (x 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 F x ? G x∧ ( )) ( ) (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° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 )(x xF ? 这里，x x F :)(呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ))()((x G x F x →? 这里，x x F :)(为人，且)(x F 为特性谓词。x x G :)(呼吸。 2．3 因题目中未给出个体域，因而应采用全总个体域。
离散数学课后习题答案_屈婉玲(高等教育出版社)
第一章部分课后习题参考答案 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?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 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 ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
(1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p)
离散数学 第2章 习题解答
习题 2.1 1．将下列命题符号化。 (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是实数。Q(x)：x是有理数。 “有些实数是有理数。”符号化为：(?x)(R(x)∧Q(x))
离散数学答案第二章习题解答
习题与解答 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 x D 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 =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。
离散数学答案(尹宝林版)第二章习题解答
第二章 谓词逻辑 习题与解答 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 x D 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 =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。
离散数学课后习题答案第二章
第四章部分课后习题参考答案 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)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?，在（a）(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R.
离散数学第二章一阶逻辑知识点总结
数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词: 表示任意的, 所有的, 一切的等 如x 表示对个体域中所有的x 存在量词: 表示存在, 有的, 至少有一个等 如x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化 (1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a)
例2 在一阶逻辑中将下面命题符号化 (1) 人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域. 解：(a) (1) 设G(x)：x爱美, 符号化为x G(x) (2) 设G(x)：x用左手写字, 符号化为x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 (1) x (F(x)G(x)) (2) x (F(x)G(x)) 这是两个基本公式, 注意这两个基本公式的使用. 例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 解注意: 题目中没给个体域, 一律用全总个体域 (1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y x(F(x)y(G(y)L(x,y))) 或 x y(F(x)G(y)L(x,y)) 两者等值 (2) 令F(x): x是无理数, G(y): y是有理数, L(x,y)：x>y x(F(x)y(G(y)L(x,y))) 或x y(F(x)G(y)L(x,y)) 两者等值 几点注意： 1元谓词与多元谓词的区分 无特别要求，用全总个体域 量词顺序一般不能随便颠倒 否定式的使用 思考： ①没有不呼吸的人 ②不是所有的人都喜欢吃糖 ③不是所有的火车都比所有的汽车快 以上命题应如何符号化？ 2.2 一阶逻辑合式公式及解释字母表 定义字母表包含下述符号： (1) 个体常项：a, b, c, …, a i, b i, c i, …, i1 (2) 个体变项：x, y, z, …, x i, y i, z i, …, i 1 (3) 函数符号：f, g, h, …, f i, g i, h i, …, i1 (4) 谓词符号：F, G, H, …, F i, G i, H i, …, i1 (5) 量词符号：, (6) 联结词符号：, , , , (7) 括号与逗号：(, ), ， 定义项的定义如下： (1) 个体常项和个体变项是项. (2) 若(x1, x2, …, x n)是任意的n元函数，t1,t2,…,t n
离散数学 杨圣洪等著 第二章习题二解答
第二章习题二 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))) 德摩律
离散数学第二章
离散数学第二章 1. 有序二元组也称序偶,设 A , B 为任意集合，A 和 B 的笛卡尔积用 A × B 表示，定义为 A × B = {(a , b ) | a ∈ A , b ∈ B }。 2. 推广 n 个集合的笛卡儿积为A 1 × A 2 × … × A n = {(x 1, x 2, …, x n ) | x i ∈ A i , i = 1, 2, …, n }。 3. 笛卡尔乘与交并集符号之间满足分配率： A × (B ? C ) = (A × B ) ? (A × C ) 4. 笛卡尔积 A × B 的任意一个子集 ρ 称为由 A 到 B 的一个二元关系，当 A = B 时，称 ρ 是 A 上 的二元关系。 5. 几种特殊的关系：空关系，全关系（普遍关系）记为U A ，恒等关系I A = {(a , a ) | a ∈ A }。 6. 关系的表示方法：集合表示法，矩阵表示法，关系图表示法（结点，单边）自环 7. A,B 上的关系的交，并，补，运算结果都是A 到B 的关系。 8. ，称为关系p 的逆运算也记为p-1 9. 关系的复合运算：当且仅当存在元素 b ∈ B ，使得 a ρ1 b ，b ρ2 c 时，有 a (ρ1 ? ρ2) c 。 10. I A ? ρ = ρ ? I B =p ，关系的复合满足结合律：(ρ1 ? ρ2) ? ρ3 = ρ1 ? (ρ2 ? ρ3)。 11. 规定：ρ 0 = {(a , a ) | a ∈ A }，即 ρ 0 = I A 12. 复合关系的求法：定义，关系图，矩阵 13. 设 A 、B 均是有限集，ρ1、ρ2 都是由 A 到 B 的关系，它们的关系矩阵分别为和 ，则下列关系的关 系矩阵如何？ ρ1 ? ρ2，ρ1 ? ρ2，ρ1'，ρ1 - ρ2 ，ρ1-1。 14. 设 ρ1, ρ2 是集合 A 上的任意的关系，则 (ρ1 ? ρ2)-1 = ρ2-1 ? ρ1-1 15. 关系的性质：自反，非自反，反自反；对称，非对称，反对称；可传递，不可传递； 16. 反自反的关系一定是非自反的关系；若ρ是 A 上的反对称关系，则由定义知，在ρ中，(a , b ) 与 (b , a ) 至多有一个出现，其中 a ≠ b 。 17. {(1, 2), (3, 0), (3, 2)}这个关系可传递 18. 设 ρ 为 A 上的关系，（1） ρ 在 A 上自反当且仅当 I A ? ρ （2） ρ 在 A 上反自反当且仅当 ρ ∩I A = Φ （3） ρ 在 A 上对称当且仅当 ρ = ρ -1 （4） ρ 在 A 上反对称当且仅当 ρ ∩ ρ -1 ? I A （5） ρ 在 A 上传递当且仅当 ρ ? ρ ? ρ 。（自证，ppt 中有过程） 19.利用关系矩阵判断： }),(|),{(~ρρ ∈=b a a b
离散数学第二版邓辉文编著第一章第二节习题答案
离散数学第二版邓辉文编著第一章第二节习题答案 1.2 映射的有关概念 习题1.2 1. 分别计算?1. 5?，?-1?，?-1. 5?，? 1. 5?，?-1?，?-1. 5?. 解?1. 5?=2，?-1?=-1，?-1. 5?=-1，?1. 5?=1，?-1?=-1，?-1. 5?=-2. 2. 下列映射中，那些是双射? 说明理由. (1)f :Z →Z , f (x ) =3x . (2)f :Z →N , f (x ) =|x |+1. (3)f :R →R , f (x ) =x 3+1. (4)f :N ?N →N , f (x 1, x 2) =x 1+x 2+1. (5)f :N →N ?N , f (x ) =(x , x +1). 解 (1)对于任意对x 1, x 2∈Z ，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x ∈Z ，f (x ) ≠2∈Z ，因此f 不是满射，进而f 不是双射. (2)由于2, -2∈Z 且f (2) =f (-2) =3，因此f 不是单射. 又由于0∈N ，而任意x ∈Z 均有f (x ) =|x |+1≠0，于是f 不是满射. 显然，f 不是双射. (3)对于任意对x 1, x 2∈R ，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y ∈R ，取x =(y -1) ，这时 1??3f (x ) =x +1=?(y -1) 3?+1=(y -1) +1=y ， ??33313 所以f 是满射. 进而f 是双射.
新版离散数学答案(尹宝林版)第二章习题解答课件.doc
第二章谓词逻辑 习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解(1) 取论域为所有交通工具的集合。令 T(x):x是火车，C(x):x是汽车，F(x,y):x比y跑得快。 “所有的火车都比某些汽车快”可以符号化为x(T(x)y(C(y)F(x,y)))。 (2) 取论域为所有物质的集合。令 M(x):x是金属，L(x):x是液体，D(x,y):x可以溶解在y中。 “任何金属都可以溶解在某种液体中”可以符号化为x(M(x)y(L(y)D(x,y)))。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中”可以符号化为 x(M(x)y(L(y)D(x,y)))。 (4) 取论域为所有事物的集合。令 M(x):x是人，J(x):x是职业，L(x,y):x喜欢y。 “每个人都有自己喜欢的职业”可以符号化为x(M(x)y(J(y)L(x,y))) (5) 论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为x(J(x)y(M(y)L(y,x)))。 2. 取论域为正整数集，用函数（加法），（乘法）和谓词，将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解先引进一些谓词如下： D(x,y):x能被y整除，D(x,y)可表示为v(v y x)。 J(x):x是奇数，J(x)可表示为v(v2x)。 E(x):x是偶数，E(x)可表示为v(v2x)。
离散数学第二章习题答案
设解释I为：个体域D I ={-2,3,6},一元谓词F（X）：X3，G（X）：X>5,R(X):X7。在I下求下列各式的真值。 （1）x(F(x)G(x)) 解：x(F(x)G(x)) (F(-2) G(-2)) (F(3) G(3)) (F(6) G(6)) ((-23) (-2>5)) ((33) (3>5)) ((63) (6<5)) ((1 0))((1 0)) ((0 0)) 000 (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) ((-27) (-23)) (( 37) (33)) (( 67) (63)) (5>5) (1 1) (1 1) (10) 0 1 1 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)) ((-23) (-2>5)) ((33) (3>5)) ((63) (6>5))
(1 0) (1 0) (0 1) 1 1 1 1 求下列各式的前束范式，要求使用约束变项换名规则。 （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 ） ??x(?F(x) →?yG(z,y) 定理（2）③ ??x?y(?F(x) →G(z,y)) 定理（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)) 求下列各式的前束范式，要求使用自由变项换名规则。（代替规则）（1）xF(x)∨yG(x,y) xF(x) ∨yG(z,y) 代替规则 x（F(x) ∨yG(z,y)）定理（1）① x y（F(x) ∨G(z,y)）定理（2）① （2）x(F(x)∧yG(x,y,z))→zH(x,y,z) x(F(x)∧yG(x,y,t))→zH(s,r,z) 代替规则 x y (F(x)∧G(x,y,t))→zH(s,r,z) 定理（1）②
最新离散数学-第二章命题逻辑等值演算习题及答案
第二章作业 1 评分要求： 2 1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48 3 分 4 2. 给出每小题得分(注意: 写出扣分理由) 5 3. 总得分在采分点1处正确设置. 6 一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方 7 法每种方法至少使用一次): 8 说明 9 证 10 1. p ?(p ∧q)∨(p ∧?q) 11 解逻辑方程法 12 设 p ?((p ∧q)∨(p ∧?q)) =0, 分两种情况讨论: 13 ?? ?=?∧∨∧=0)()(1 )1(q p q p p 或者 14 ?? ?=?∧∨∧=1 )()(0 )2(q p q p p 15 (1)(2)两种情况均无解, 从而, p ?(p ∧q)∨(p ∧?q)无成假赋值, 为永真式. 16 等值演算法 17 (p ∧q)∨(p ∧?q) 18 ? p ∧(q ∨?q) ∧对∨的分配率 19 ? p ∧1 排中律 20
? p 同一律 21 真值表法 22 即 p? ((p∧q)∨(p∧?q))为永真式, 得证23 2. (p→q)∧(p→r)?p→(q∧r) 24 等值演算法 25 (p→q)∧(p→r) 26 ? (?p∨q)∧(?p∨r)蕴含等值式 27 ??p∨(q∧r)析取对合取的分配律 28 ? p→(q∧r)蕴含等值式 29 3. ?(p?q)?(p∨q)∧?(p∧q) 30 等值演算法 31 ?(p?q) 32 ??( (p→q)∧(q→p) )等价等值式 33 ??( (?p∨q)∧(?q∨p) )蕴含等值式 34
离散数学(屈婉玲版)第二章习题答案
For personal use only in study and research; not for commercial use For personal use only in study and research; not for commercial use 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 ?1 2.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）?xF(x)∨?yG(x,y) ??xF(x)∨?yG(z,y) 代替规则 ??x（F(x)∨?yG(z,y)）定理2.2（1）① ??x?y（F(x)∨G(z,y)）定理2.2（2）① （2）?x(F(x)∧?yG(x,y,z))→?zH(x,y,z) ??x(F(x)∧?yG(x,y,t))→?zH(s,r,z) 代替规则
离散数学第二版邓辉文编著第一章第二节习题答案
1.2 映射的有关概念 习题1.2 1. 分别计算??5.1，??1-，??5.1-，??5.1，??1-，??5.1-. 解 ??25.1=，??11-=-，??15.1-=-，??15.1=，??11-=-，??25.1-=-. 2.下列映射中，那些是双射? 说明理由. (1).3)(,Z Z :x x f f =→ (2).1||)(,N Z :+=→x x f f (3).1)(,R R :3+=→x x f f (4).1),(,N N N :2121++=→?x x x x f f (5)).1,()(,N N N :+=?→x x x f f 解 (1)对于任意对∈21,x x Z ，若)()(21x f x f =，则2133x x =，于是21x x =，所以f 是单射. 由于对任意∈x Z ，∈≠2)(x f Z ，因此f 不是满射，进而f 不是双射. (2)由于∈-2,2Z 且3)2()2(=-=f f ，因此f 不是单射. 又由于∈0N ，而任意∈x Z 均有01||)(≠+=x x f ，于是f 不是满射. 显然，f 不是双射. (3)对于任意对∈21,x x R ，若)()(21x f x f =，则113231+=+x x ，于是21x x =，所以f 是单射. 对于任意∈y R ，取3 1)1(-=y x ，这时 y y y x x f =+-=+??????-=+=1)1(1)1(1)(3313， 所以f 是满射. 进而f 是双射. (4)由于∈)1,2(),2,1(N ?N 且)1,2()2,1(≠，而4)1,2()2,1(==f f ，因此f 不是单射. 又由于∈0N ，而任意∈),(21x x N ?N 均有01),(2121≠++=x x x x f ，于是f 不是满射. 显然，f 就不是双射. (5)由于∈21,x x N ，若)()(21x f x f =，则)1,()1,(2211+=+x x x x ，于是21x x =，因此f 是单射. 又由于∈)0,0(N ?N ，而任意∈x N 均有)0,0()1,()(≠+=x x x f ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.
离散数学章练习题及答案
离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真 p→ ) ( (s r q 值为 0 3.公式) ∨ ? q ?与共同的成真赋值为 01；10 p ? ∧ p∧ ) ( ( ) p (q q 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ?，其中p: 7是无理数；或p，其中p: 7是无理数。 ? (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p q? →，其中p: 怕困难，q: 战胜困难 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解p r→ (q 决了
或：q (，其中p:别人有困难，q: 老王帮助别人，r: 困难解∧ ?) p r→ 决了 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ p ( r ) ( ) ((q 2.r ?) → (( → ) ∨ (( ( )) ? r p ∨ p p q ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ r ( p ) ( ) ((q 2. r → ∨ → ?) ((的真值为1 ) ( )) (( ∧ p p ∨ r q ? p ? q∧ 四、判断推理是否正确 设x =为实数，推理如下： y2 若y在x=0可导，则y在x=0连续。y 在x=0连续，所以y在x=0可导。解：x =，x为实数，令p: ｙ在ｘ=0可导，q: y在x=0连续。P为y2 假命题，q为真命题，推理符号化为：p →) (，由p，q得真值可 q ∧ p→ q 知，推理的真值为0，所以推理不正确。 五、判断公式的类型 1，r ?))) → ? ( ) ( ) (( ( ? q ∧ q p p ∨ ∧ q∨ p 2. ) p∧ ∧ → ? ∧ q )) p ( ( r (q 3. ) → ? ? p? ) ( r (r q 解：设三个公式为A,B,C则真值表如下：
离散数学第二版 屈婉玲 1-5章(答案)
《离散数学1-5章》练习题答案第2，3章(数理逻辑) 1.答：（2），（3），（4） 2.答：（2），（3），（4），（5），（6） 3.答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 4.答：（4） 5.答：?P ，Q→P 6.答：P(x)∨?yR(y) 7.答：??x(R(x)→Q(x)) 8、 c、P→(P∧(Q→P)) 解：P→(P∧(Q→P)) ??P∨(P∧(?Q∨P)) ??P∨P ? 1 (主合取范式) ? m0∨ m1∨m2∨ m3 （主析取范式） d、P∨(?P→(Q∨(?Q→R))) 解：P∨(?P→(Q∨(?Q→R))) ? P∨(P∨(Q∨(Q∨R))) ? P∨Q∨R ? M0 (主合取范式) ? m1∨ m2∨m3∨ m4∨ m5∨m6 ∨m7 (主析取范式) 9、
b、P→(Q→R)，R→(Q→S) => P→(Q→S) 证明： （1） P 附加前提 （2） Q 附加前提 （3） P→(Q→R) 前提 （4） Q→R （1），（3）假言推理 （5） R （2），（4）假言推理 （6） R→(Q→S) 前提 （7） Q→S （5），（6）假言推理 （8） S （2），（7）假言推理 d、P→?Q，Q∨?R，R∧?S??P 证明、 (1) P 附加前提 （2） P→?Q 前提 （3）?Q （1），（2）假言推理 （4） Q∨?R 前提 (5) ?R （3），（4）析取三段论 (6 ) R∧?S 前提 （7） R （6）化简 （8） R∧?R 矛盾（5），（7）合取 所以该推理正确 10.写出?x(F(x)→G(x))→(?xF(x) →?xG(x))的前束范式。 解：原式??x(?F(x)∨G(x))→(?(?x)F(x) ∨ (?x)G(x)) ??(?x)(?F(x)∨G(x)) ∨(?(?x)F(x) ∨ (?x)G(x)) ? (?x)((F(x)∧? G(x)) ∨G(x)) ∨ (?x) ?F(x)