离散数学习题答案.docx

1、离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5） 李辛与李末是兄弟解：设 p：李辛与李末是兄弟，则命题符号化的结果是 p（6） 王强与刘威都学过法语解：设 p：王强学过法语；q：刘威学过法语；则命题符号化的结果是（9）只有天下大雨，他才乘班车上班p q解：设 p：天下大雨；q：他乘班车上班；则命题符号化的结果是 q p（11）下雪路滑，他迟到了解：设 p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是 ( p q) r15、设 p：2+3=5.q：大熊猫产在中国. r：太阳从西方升起.求下列复合命题的真值：（4） (p q r) (p q) r) 解：p=1，q

2、=1，r=0，(p q r) (11 0) 1，(p q) r) (1 1) 0) (0 0) 1(p q r) (p q) r) 1 1 119、用真值表判断下列公式的类型：（2） ( p p) qpqpq( p p)( p p) q解：列出公式的真值表，如下所示：001111011010100101110001由真值表可以看出公式有 3 个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：（4） ( p q) q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：( p q) 1 p 0 q 0q 0所以公式的成真赋值有：01，10，11。习题二及答案：

3、（P38）5、求下列公式的主析取范式，并求成真赋值：（2） (p q) (q r)解：原式 ( p q) q r q r (p p) q r (p q r) ( p q r) m3 m ，此即公式的主析取范式，7所以成真赋值为 011，111。*6、求下列公式的主合取范式，并求成假赋值：（2） ( p q) (p r)解：原式 ( p p r) (p q r) (p q r) M4所以成假赋值为 100。，此即公式的主合取范式，7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1） ( p q) r解：原式 p q (r r) (p p) (q q) r) ( p q r) ( p q

4、 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 m m m1356 m ，此即主析取范式。7主析取范式中没出现的极小项为 m0，m ，m24，所以主合取范式中含有三个极大项 M0，M ，2M ，故原式的主合取范式 M40 M M 。249、用真值表法求下面公式的主析取范式：（1） ( p q) (p r)pqrpp qp r( p q) (p r)解：公式的真值表如下：0001000001101101011010111111100010110101011100101111010

5、1由真值表可以看出成真赋值的情况有 7 种，此 7 种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 m m12 m m34 m m m567习题三及答案：（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)前提引入 r s

6、假言推理 s化简 s t附加 (s t) u前提引入 u假言推理故推理正确。16、在自然推理系统 P 中用归谬法证明下面推理：（1）前提： p q ， r q ， r s结论： p 证明：用归谬法 p结论的否定引入 p q前提引入 q假言推理 r q前提引入 r析取三段论 r s前提引入 r化简 r r合取由于r r 0 ，所以推理正确。17、在自然推理系统 P 中构造下面推理的证明：只要 A 曾到过受害者房间并且 11 点以前没离开，A 就是谋杀嫌犯。A 曾到过受害者房间。如果 A 在 11 点以前离开，看门人会看见他。看门人没有看见他。所以， A 是谋杀嫌犯。解：设 p：A 到过受害者房间

7、，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假言推理习题四及答案：（P65-67）5、在一阶逻辑中将下列命题符号化：（2） 有的火车比有的汽车快。解：设 F(x)：x 是火车，G(y)：y 是汽车，H(x,y)：x 比 y 快；则命题符号化的结果是：$x$y(F (x) G( y) H (x, y)（3） 不存在比所有火车都快的汽车。解：方法一：设 F(x)：x 是汽车，G(y)：y 是火车，H(x

8、,y)：x 比 y 快；则命题符号化的结果是：$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 快；则命题符号化的结果是：$x(G(x) y(F ( y) H (x, y) 或 $xy(G(x) (F ( y) H (x, y)9、给定解释 I 如下：(a) 个体域为实数集合 R。-(b) 特定元素 a = 0 。-(c) 函数 f (x, y) = x - y, x, y R 。(d) 谓词。F- (x, y) : x = y, G- (x, y) : x

9、y, x, y R给出以下公式在 I 下的解释，并指出它们的真值：（2） xy(F ( f (x, y), a) G(x, y)解：解释是： xy(x - y = 0 x y) ，含义是：对于任意的实数 x，y，若 x-y=0 则 x=2 ；（2） r(R)=R U IA= 1,5 , 2,5 , 3,1 , 3,3 , 4,5 , 1,1 , 2,2 , 4,4 , 5,5 , 6,6 ，s(R) = R U R-1 = 1,5 , 5,1 , 2,5 , 5,2 ,3,1 , 1,3 , 3,3 ,4,5 , 5,4t(R) = R U R2 U R3 U . = R U R2 = 1,5

10、 ,2,5 , 3,1 , 3,3 ,3,5 , 4,541 、 设 A=1 ， 2 ， 3 ， 4 ， R 为 A A 上 的 二 元 关 系 ， , A A ， R a + b = c + d（1） 证明R 为等价关系；（2） 求R 导出的划分。（1） 只需证明 R 具有自反性、对称性和传递性即可，证明过程如下：（a） 任取 A A ，有a + b = a + b ， R ，所以R 具有自反性；（b）任取 , A A ，若 R ，则有a + b = c + d ，c + d = a + b ， R ，所以R 具有对称性；（c）任取 , , A A ，若 R 且 R ，则有a + b = c

11、 + d 且c + d = e + f ， a + b = e + f ， R ，所以R 具有传递性， 综合（a）（b）（c）可知：R 为集合 A A 上的等价关系；（2） 先求出集合 A A 的结果：A A = , , , , , , , , , , , , , 再分别求集合 A A 各元素的等价类，结果如下：R= ,R= R= , ,R= R= R= , , ,R= R= R= R= , , , ,R= R= R= , , ,R= R= , , = 。R等价关系 R 导出的划分就是集合A 关于 R 的商集 A / R ，而集合 A 关于 R 的商集 A / R 是由 R 的所有等价类作为元

12、素构成的集合，所以等价关系R 导出的划分是：, , , , , , , , , ,46、分别画出下列各偏序集 A, R的哈斯图，并找出 A 的极大元、极小元、最大元和最小元。（1） R= a, d , a, c , a, b , a, e , b, e , c, e , d , e U IAebcdaf解：哈斯图如下：A 的极大元为 e、f，极小元为 a、f； A 的最大元和最小元都不存在。*22、给定 A = 1,2,3,4 ，A 上的关系 R = 1,3 , 1,4 , 2,3 , 2,4 , 3,4 ，试（1） 画出 R 的关系图；12（2） 说明 R 的性质。解：（1）34（2）R 的

13、关系图中每个顶点都没有自环，所以 R 是反自反的，不是自反的；R 的关系图中任意两个顶点如果有边的都是单向边，故 R 是反对称的，不是对称的；R 的关系图中没有发生顶点 x 到顶点 y 有边、顶点 y 到顶点 z 有边，但顶点 x到顶点 z 没有边的情况，故 R 是传递的。*48、设 A, R 和 B,S 为偏序集，在集合 A B 上定义关系 T 如下： a , b, a , b A B,1 122a , bT a , b a Ra b Sb1 1221212证明 T 为A B 上的偏序关系。证明：（1）自反性：任取 a ,b A B，则：1 1Q R为偏序关系，具有自反性， a Ra11Q

14、S为偏序关系，具有自反性， b Sb a Ra11 b Sb1111又 a ,b T a ,b a Ra b Sb ，1 1221212 a ,bT a ,b，故T具有自反性1 11 1（2） 反对称性：任取 a ,b, a ,b A B，若 a ,bT a ,b且 a ,bT a ,b，则有：1 1221 122221 1a Ra b Sb（1）1212a Ra b Sb（2）2121 a Ra a Ra ，又R为偏序关系，具有反对称性，所以a = a122112b Sb b Sb，又S为偏序关系，具有反对称性，所以b = b122112 a ,b = a ,b ，故T具有反对称性1 122

15、（3） 传递性：任取 a ,b, a ,b，a ,b A B，若 a ,bT a ,b且 a ,bT a ,b，则有：1 1223 31 122223 3a ,bT a ,b a Ra b Sb1 1221212a ,bT a ,b a Ra b Sb223 32323 a Ra a Ra ,又R为偏序关系，具有传递性，所以a Ra122313b Sb b Sb ,又S为偏序关系，具有传递性，所以b Sb122313 a Ra b Sb a ,bT a ,b，故T具有传递性。13131 13 3综合（1）（2）（3）知 T 具有自反性、反对称性和传递性，故 T 为A B 上的偏序关系。习题九及

16、答案：（P179-180）8、S=Q Q,Q 为有理数集，为*S上的二元运算， a,b , x,y S 有a,b * x,y = ax,ay+b （1） *运算在S上是否可交换、可结合？是否为幂等的？（2） *运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元 。解：（1）x, y* a,b = xa,xb+y = ax,bx+y a,b * x, y *运算不具有交换律( x, y * a,b )* c,d= ax,bx+y * c,d = acx,adx+bx+y而 x, y *( a,b * c,d )= x, y * ac,ad+b= xac,xad+xb+y = a

17、cx,adx+bx+y = ( x, y * a,b )* c,d*运算有结合律任取 a,b s，则有：a,b * a,b = a2, ab + b a,b *运算无幂等律（2）令 a,b * x, y = a,b 对 a,b s均成立则有：ax,ay+b = a,b 对 a,b s均成立 ax = a a (x -1)= 0 对(a,b)成立ay + b = bay = 0必定有x -1 = 0 x = 1 y = 0y = 0*运算的右单位元为1，0，可验证1，0也为*运算的左单位元，*运算的单位元为 1，0令 a,b * x, y = x, y ，若存在 x, y 使得对 a,b s上述

18、等式均成立， 则存在零元，否则不存在零元。由 a,b * x, y = x, y ax,ay+b = x, y ax = x (a -1)x = 0ay + b = y(a -1)y+b = 0由于(a -1)y+b = 0不可能对 a,b s均成立，故 a,b * x, y = x, y 不可能对 a,b s均成立，故不存在零元；设元素a,b的逆元为x, y ，则令a,b* x, y = e = 1，0 x = 1 ax = 1 a（当a 0）ay + b = 0y = - ba当a = 0时，a,b的逆元不存在；ba当a 0时，a,b 的逆元是 1 , -a11、设S = 1，2，.,10

19、，问下面的运算能否与S构成代数系统 S，* ?如果能构成代数系统则说明*运算是否满足交换律、结合律，并求*运算的单位元和零元。（3） x * y=大于等于x和y的最小整数；解：（3）由*运算的定义可知： x * y=max(x,y)，x,y S,有x * y S，故*运算在S上满足封闭性，所以*运算与非空集合S能构成代数系统； 任取x,y S,有x * y=max(x,y)=max(y,x)=y* x, 所以*运算满足交换律；任取x,y,zS,有(x * y) *z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z)=x*(y * z), 所以*运算满足结合律；

20、任取x S，有x *1=max(x,1)=x=max(1,x)=1* x,所以*运算的单位元是1；任取x S，有x *10=max(x,10)=10=max(10,x)=10 * x,所以*运算的零元是10；16、设V1= 1,2,3, ,1 , 其中x y表示取x和y之中较大的数。V2= 5,6, *,6 ，其中x * y表示取x和y之中较小的数。求出V 和V 的所有的子代数。12指出哪些是平凡的子代数，哪些是真子代数。解：（1）V中运算的单位元是1，1V的所有的子代数是：1,2,31, ,1 ,1 , ,1 ,1,2, ,1 ,1,3, ,1 ；1V的平凡的子代数是：1,2,3, ,1 ,

21、 1, ,1 ；V的真子代数是：1, ,1 , 1,2, ,1 , 1,3, ,1 ；1（2）V 中*运算的单位元是6，2 V 的所有的子代数是： 5,62,*,6 ， 6, *,6 ；2V 的平凡的子代数是：5,6,*,6 ，6,*,6 ；V 的真子代数是：6,*,6 。2习题十一及答案：（P218-219）1、图 11.11 给出了 6 个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由解：（a）、（c）、（f）是格；因为任意两个元素构成的集合都有最小上界和最大下界；（b） 不是格，因为d,e的最大下界不存在；（d） 不是格，因为b,c的最小上界不存在；（e） 不是格，因为a,b的最

22、大下界不存在。2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。（1）L=1，2，3，4，5；（2）L=1，2，3，6，12；解：画出哈斯图即可判断出：（1）不是格，（2）是格。4、设 L 是格，求以下公式的对偶式：（2） a (b c) (a b) (a c)解：对偶式为： a (b c) (a b) (a c) ，参见 P208 页定义 11.2。6、设 L 为格， a, b, c L ，且a b c ，证明a b = b c 。证明：Q a b, a b = b,Q b c,b c = b,a b = b c9、针对图 11.11 中的每个格，如果格中的元素存在补元，则求出这些

23、补元。解：（a）图：a,d 互为补元，其中 a 为全下界，d 为全上界，b 和 c 都没有补元；（c）图：a,f 互为补元，其中 a 为全下界，f 为全上界，c 和 d 的补元都是 b 和 e，b 和 e 的补元都是 c 和d；（f）图：a,f 互为补元，其中 a 为全下界，f 为全上界，b 和 e 互为补元，c 和 d 都没有补元。10、说明图 11.11 中每个格是否为分配格、有补格和布尔格，并说明理由。解：（a）图：是一条链，所以是分配格，b 和 c 都没有补元，所以不是有补格，所以不是布尔格；（c）图：a,f 互为补元，c 和 d 的补元都是 b 和 e，b 和 e 的补元都是 c 和 d，所以任何元素皆有补元，是有补格；Q c (b d ) = c a = c, (c b) (c d ) = f d = d c (b d ) (c b) (c d ) ，所以 对 运算不满足分配律，所以不是分配格，所以不是布尔格；（f）图：经过分析知图（f）对应的格只有 2 个五元子格：L1=a,c,d,e,f, L2=a,b,c,d,f。画出 L1 和 L2 的哈斯图可知 L1 和 L2 均不同构于钻石格和五角格，根据分配格的充分必要条件（见 P213 页的定理 11.5） 得图（f）对应的格是分配格；c 和 d 都没有补元，所以不是有补格，所以不是布尔格。