离散数学第二版 屈婉玲 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)
? (?x)((F(x) ∨G(x)) ∨ (?x) ?F(x)
? (?x)((F(x) ∨G(x)) ∨ (?y) ?F(y)
? (?x) (?y) (F(x) ∨G(x) ∨?F(y))
（集合论部分）
1、答：(4)
2.答：32
3.答：（3）
4. 答：（4）
5.答：（2），（4）
6、设Ａ，Ｂ，Ｃ是三个集合，证明：
a、A? (B－C)＝(A?B)－(A?C)
证明：
(A?B)－(A?C)= (A?B)?~（A?C）=(A?B) ?（~A?~C）
=(A?B?~A)?(A?B?~C)= A?B?~C=A?（B?~C）
=A?（B-C）
b、(A－B)?(A－C)=A－(B?C)
证明：
(A-B)?(A-C)=(A?~B)?(A??~C) =A? (~B ?~C)
=A?~（B?C）= A-(B?C)
（二元关系部分）
1、答：（1）R={<1,1>,<4,2>} (2) R1-={<1,1>,<2,4>}
2.答：R R ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}
R-1 =｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝
3.答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,
<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}
4.
答：R 的关系矩阵=????
??
?
?
?
?????????0000000010000
00001 R 1
-的关系矩阵=????
??????000000010000000001
5、解：
（1）R={<2,1>,<3,1>,<2,3>};M R =???
?
? ??001101000;它是反自反的、反对称的、
传递的；
（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};M R =???
?
?
??011101110;它是反
自反的、对称的；
（3）R={<1,2>,<2,1>,<1,3>,<3,3>};M R =???
?
?
??100001110;它既不是自反的、也
不是反自反的、也不是对称的、也不是反对称的、也不是传递的。 6、解：
R 诱导的划分为{{1,5},{2,4},{3,6}}。 7．画出下列集合关于整除关系的哈斯图.
(1){1, 2, 3, 4, 6, 8, 12, 24}. (2){1,2,…..,9}.
并指出它的极小元，最小元，极大元，最大元。
在图（2）中极小元，最小元是1，极大元是5，6，7，8，9，没有最大元。
第5章函数
1.解
(1){<1，a>，<2，a>，<3，c>}的定义域为A，值域为{a，c}。又由于它满足单值性，所以它是函数，但因为1和2都对应a，它不是单射，{a，c}≠B，它不是满射。
(2){<1，c>，<2，a>，<3，b>}的定义域为A，值域是B。又由于它满足单值性，所以它是函数，且是单射。满射和双射。
(3){<1，a>，<1，b>，<3，c>}的定义域为A，值域是B。由于它不满足单值性，所以它不是函数，更不是单射、满射和双射。
(4){<1，b>，<2，b>，<3，b>}的定义域为A，值域是{b}。由于它满足单值性，所以它是函数，因为1、2和3都对应b，所以它不是单射，由于{b}≠B，所以它不是满射。
2.解
(1)不同的函数共n m个。
(2)显然当|m|≤|n|时，存在单射。
(3)显然当|n|≤|m|时，存在满射。
(4)显然当|m|＝|n|时，才存在双射。
3.解
因为g f(x)＝f(g(x))＝f(3x＋1)＝3(3x＋1)＝9x＋3，h g(x)＝g(h(x))＝g(3x＋2)＝3(3x＋2)＋1＝9x＋7，所以g f＝{
离散数学答案屈婉玲版第二版 高等教育出版社课后答案
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（pr）∧(﹁q∨s) ?（01）∧(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】
第四章部分课后习题参考答案 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)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快
命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x 第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数. 是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1)若 2+2=4,则 3+3=6. (2)若 2+2=4,则 3+3≠6. (3)若 2+2≠4,则 3+3=6. (4)若 2+2≠4,则 3+3≠6. (5)2+2=4当且仅当3+3=6. (6)2+2=4当且仅当3+3≠6. (7)2+2≠4当且仅当3+3=6. (8)2+2≠4当且仅当3+3≠6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。 第一章部分课后习题参考答案 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 离散数学(屈婉玲版)第四章部分答案 4.1 （1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如 果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。 （2）设有序对 第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。 封闭,不满足交换律和结合律，无零元和单位元 （2） 非零整数集合 普通的除法运算。不封闭 （3） 全体n n ?实矩阵集合 （R ）和矩阵加法及乘法运算，其中n 2。 封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）全体n n ?实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭 （5）正实数集合 和运算，其中运算定义为： 不封闭 因为 +?-=--?=R 1111111ο （6）n 关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（1>n ），零元是0；1=n 单位元是1 （7）A = {},,,21n a a a Λ n 运算定义如下： 封闭 不满足交换律，满足结合律， （8）S = 关于普通的加法和乘法运算。 封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S 是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = ,S 关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律 5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题 7．设 * 为+Z 上的二元运算+∈?Z y x ,， X * Y = min ( x ，y ),即x 和y 之中较小的数. (1)求4 * 6，7 * 3。 4, 3 《离散数学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) 4.1 （1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如 果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。 （2）设有序对 第一章习题 1.1 &1.2 判断下列语句是否为命题,若是命题请指出是简单命题还是复合命 题?并将命题符号化，并讨论它们的真值. (1) V 2是无理数. 是命题,简单命题.p:V2是无理数?真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除?真值:0 (3) 现在在开会吗？ 不是命题. ⑷ x+5>0. 不是命题. (5) 这朵花真好看呀！ 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.旷q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p q真值:0 (8) 2008 年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立！ 不是命题. (12) 4 是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p V q 真值:1 (13) 4 是偶数且是奇数. 是命题,复合命题P:4是偶数.q:4是奇数.p A q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p:李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1) 若2+2=4,则3+3=6. ⑵若2+2=4,则3+3工6. (3)若2+2 工4,则3+3=6. ⑷若2+2工4,则3+3工6. ⑸2+2=4当且仅当3+3=6. ⑹2+2=4当且仅当3+3工6. (7) 2+2工4当且仅当3+3=6. (8) 2+2工4当且仅当3+3工6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1) p -q,真值为1. (2) p q,真值为0. ⑶门p-q,真值为1. ⑷门p-n q,真值为1. (5) p「q,真值为1. (6) p?门q,真值为0. ⑺门p q,真值为0. (8) n p n q,真值为1. 1. 4将下列命题符号化，并讨论其真值。 (1)如果今天是1号，贝V明天是2号。 p：今天是1号。 q:明天是2号。 符号化为：旷q 真值为：1 (2)如果今天是1号，则明天是3号。 离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： | （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p 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 ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 ； 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 解：公式的真值表如下： , 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 — ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论：p u → 证明：用附加前提证明法。 ' ① p 附加前提引入 ② p q ∨ ①附加 ③ ()()p q r s ∨→∧ 前提引入 ４.１ (1）设Ｓ={１,２｝,R 是S 上的二元关系，且ｘR ｙ。如果Ｒ=Is ，则(A)； 如果R 是数的小于等于关系,则（Ｂ),如果Ｒ=Es ，则（C)。 （2）设有序对<ｘ+2，４>与有序对<５,2x+y>相等，则 ｘ=(D),y=(E). 供选择的答案 Ａ、B 、C ：① x ，y 可任意选择１或2;② ｘ＝1,ｙ=1；③ x=１,y=1 或 ２；x=y=2; ④ ｘ＝2,y=2;⑤ x=y=１或 x ＝y=２;⑥ x=1,ｙ＝2；⑦x=2,y ＝１。 D 、E:⑧ 3；⑨ 2;⑩－2。 答案: Ａ: ⑤ B: ③ Ｃ： ① D: ⑧ Ｅ: ⑩ 4.2设S ＝<1,2，３，４>,R 为S 上的关系，其关系矩阵是 ????? ???????0001100000011001 则（1）R 的关系表达式是（A ）。 (2)dom Ｒ＝(Ｂ),ranR=(C). (3）R ?Ｒ中有(Ｄ)个有序对。 (4）R ˉ1的关系图中有(E)个环。 供选择的答案 A ：①{<1,1>,<1,２>，<1，4>，<4，１>,＜4，3>}; ②{<１,１＞,<1,４＞,<2,1>,<４,1>,＜３,４>}; Ｂ、C ：③{１，2，3,4}；④{１,2，４};⑤{1,４}⑥{1，３,４}。 Ｄ、E ⑦1;⑧３；⑨6；⑩7。 答案： A ：② B:③ Ｃ：⑤ Ｄ:⑩ E:⑦ 4.3设R 是由方程ｘ+３ｙ=１2定义的正整数集Z+上的关系,即 { ………………………………………………最新资料推 荐……………………………………… 1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列命题符号化,并给出各命题的真值: (1)2+2＝4当且仅当3+3＝6.(2)2+2＝ 4的充要条件是3+3≠6.(3)2+2≠4与 3+3＝6互为充要条件.(4)若2+2≠4, 则 3+3≠6,反之亦然. (1)p?q,其中,p: 2+2＝4,q: 3+3＝6, 真值为 1.(2)p??q,其中,p:2+2＝4,q:3+3＝6,真值为0. (3)?p?q,其中,p:2+2＝4,q:3+3＝6,真值为 0.(4)?p??q,其中,p:2+2＝4,q:3+3＝6,真值为1. 1.13．将下列命题符号化, 并给出各命题的真值:(1) 若今天是星期一,则明天是星期二.(2)只有今天 是星期一,明天才是星期二.(3)今天是星期一当 且仅当明天是星期二. (4)若今天是星期一,则明 天是星期三. 令p: 今天是星期一;q:明天是星期二;r:明天是星期三.(1) p→q ? 1. (2) q→p ? 1. (3) p?q? 1. (4)p→r当p ? 0时为真; p ? 1时为假. 1.14．将下列命题符号化. (1) 刘晓月跑得快,跳得高.(2) 老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小 组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃 饭, 一面听音乐. (8)如果天下大雨,他就乘 班车上班.(9)只有天下大雨,他才乘班车上 班.(10)除非天下大雨,他才乘班车上班.(11) 下雪路滑, 他迟到了. (12)2与4都是素数,这是不对的. (13)“2或4是素数,这是不对的”是不对的. 6.1(5) 5S =n M (R),+为矩阵加法，则S 是（群） 答：满足封闭性，因为矩阵加法可结合所以为半群，且幺元为e ＝0的矩阵,故为独异点。又因为以任一n 阶矩阵的逆元存在是它的负矩阵，所以是群。 评语：答案太简单 6.2 （1）因为可结合，交换，幺元为1，但不存在逆元 所以是半群 （2）因为可交换，结合，幺元为0，是有限阶群并且是循环群，G 中的2阶元是2，4阶元是1和3 6.4 设Z 为正数集合，在Z 上定义二元运算 ° ，? x,y ∈Z 有 x ° y=x+y-2, 那么Z 与运算 ° 能否构成群？为什么？ 解： 设 ? a,b,c ∈Z （a ° b ）° c = (a+b-2) ° c = a+b- 2+ c-2 =a+b+c-4 a ° ( b ° c) = a ° (b+c-2) =a + b+c-2-2 =a+b+c-4 对2∈Z ，? x ∈Z 有 x ° 2=x+2-2=x=2° x, 可见 , 存在幺元，幺元为2。 对? x ∈Z 有4-x ∈Z,使x ° （4-x ）= (4-x) ° x=2 所以 x-1 = 4-x 所以Z 与运算 ° 能构成群 。 6.7 下列各集合对于整除关系都构成偏序集，判断哪些偏序集是格？ （1）L={1,2,3,4,5}. （2）L={1,2,3,6,12}. （3）L={1,2,3,4,6,9,12,18,36}. （4）L={1,2,2(2),…,2(n)}. （1）L={1,2,3,4,5}. 解：由它的哈斯图可以知道，该偏序集不是格，因为3和4、5和4 、3和5有最大下届是1，但是没有最小上届。 （2）L={1,2,3,6,12}. 解：由它的哈斯图可以知道，该偏序集是格。因为L 中的任意俩个元素都有最大下结和最小上届。 （3）L={1,2,3,4,6,9,12,18,36}. 解：由它的哈斯图可以知道，该偏序集是格。因为L 中的任意俩个元素都有最大下结和最小上届。 （4）L={1,2,2(2),…,2(n)}. 第一章 命题逻辑基本概念 课后练习题答案 4.将下列命题符号化，并指出真值： （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. 5.将下列命题符号化，并指出真值： （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； 6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨； （2）(p∧┐q)∨(┐p∧q),其中，p ：刘晓月选学英语，q ：刘晓月选学日语；. 7.因为p 与q 不能同时为真. 13.设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. 16 设p 、q 的真值为0；r 、s 的真值为1，求下列各命题公式的真值。 （1）p ∨(q ∧r)? 0∨(0∧1) ? （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是无理数 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 所以公式类型为永真式 //最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （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 设解释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 求下列各式的前束范式，要求使用约束变项换名规则。 （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）② ??x（?y (F(x)∧G(x,y,t))→?zH(s,r,z)）定理（2）③ ??x?y（(F(x)∧G(x,y,t))→?zH(s,r,z)）定理（1）③ ??x?y?z（(F(x)∧G(x,y,t))→H(s,r,z)）定理（2）④ 构造下面推理的证明。 【最新整理，下载后即可编辑】 第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p q 真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯 一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q真 值:1 (13) 4是偶数且是奇数. 是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1)若2+2=4,则3+3=6. (2)若2+2=4,则3+3≠6. (3)若2+2≠4,则3+3=6. (4)若2+2≠4,则3+3≠6. (5)2+2=4当且仅当3+3=6. (6)2+2=4当且仅当3+3≠6. (7)2+2≠4当且仅当3+3=6. (8)2+2≠4当且仅当3+3≠6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p q,真值为1. (6)p┐q,真值为0. (7)┐p q,真值为0. (8)┐p┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 习题一 1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列命题符号化, 并给出各命题的真值: (1) 2+2 ＝ 4 当且仅当3+3 ＝ 6. (2)2+2 ＝4 的充要条件是3+3 6. (3)2+2 4 与3+3 ＝ 6 互为充要条 件. (4) 若2+2 4, 则3+3 6, 反之亦然. (1) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 1. (2) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (3) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (4) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 1. 1.13．将下列命题符号化, 并给出各命题的真值 (1) 若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一 当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令p: 今天是星期一; q: 明天是星期二; r: 明天是星期三 (1) p q 1. (2) q p 1. (3) p q 1. (4) p r 当p 0 时为真; p 1 时为假 1.14．将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2) 老王是山东人或河北人. (3) 因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5) 李辛与李末是兄弟. (6) 王强与刘威都学过法语. (7) 他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9) 只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2 与4 都是素数, 这是不对的. (13) “或24 是素数, 这是不对的”是不对的. (1) p q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2) p q, 其中, p: 老王是山东人, q: 老王是河北人. (3) p q, 其中, p: 天气冷, q: 我穿了羽绒服. (4) p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5) p, 其中, p: 李辛与李末是兄弟. (6) p q, 其中, p: 王强学过法语, q: 刘威学过法语. (7) p q, 其中, p: 他吃饭, q: 他听音乐. (8) p q, 其中, p: 天下大雨, q: 他乘班车上班. 离散数学第2版答案 【篇一：离散数学课后习题答案_屈婉玲(高等教育出版 社)】 txt>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 01 111 1 0 11 011 1 1 00 100 1 1 11 001 1所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式， 再用真值表法求出成真赋值. (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 qr p∨q p∧r （p∨q）→(p∧r) 0 0000 1 0 0100 1 0 1010 0 0 1110 0 10 010 0 10 111 1 11 010 0 11 111 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) ??(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) 主合取范式：离散数学屈婉玲版第一章部分习题汇总
离散数学屈婉玲版课后习题
离散数学(屈婉玲版)第四章部分答案
离散数学课后习题答案第四章
离散数学版屈婉玲(答案)
离散数学(屈婉玲版)第四章部分答案
离散数学(屈婉玲版)第一章部分习题分解
离散数学习题答案(耿素云屈婉玲)
离散数学(屈婉玲版)第四章部分标准答案
离散数学最全课后答案(屈婉玲版)
离散数学(屈婉玲版)第六章部分答案
离散数学最全最新答案 屈婉玲
离散数学屈婉玲版第二章习题答案
离散数学(屈婉玲版)第一章部分习题汇总(完整资料).doc
离散数学最全课后答案(屈婉玲版)
离散数学第2版答案
- 离散数学(屈婉玲)答案_1-5章
- 离散数学屈婉玲版课后习题
- 离散数学(屈婉玲)答案
- 离散数学第二版 屈婉玲 1-5章(答案)
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案
- 离散数学屈婉玲版课后答案
- 离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案
- 离散数学(屈婉玲)答案解析
- 离散数学最全最新答案 屈婉玲
- 离散数学屈婉玲版第二章习题答案
- 屈婉玲版离散数学课后习题答案【2】
- 离散数学最全课后答案(屈婉玲版)
- 离散数学习题答案(耿素云屈婉玲)
- 离散数学(屈婉玲)答案
- 离散数学最全课后答案(屈婉玲版)_0
- 离散数学屈婉玲答案
- 离散数学第二版屈婉玲 答案
- 离散数学最全课后答案(屈婉玲版)
- 屈婉玲版离散数学课后习题答案
- 最新离散数学(屈婉玲版)第一章部分习题