离散数学习题 - 下载本文

第一章习题

1. 1判断下列语句是否为命题,若是命题请指出是简单命题还是复合命题。

(1)2是无理数。

(2)5能被2整除。 (3)现在开会吗? (4)x+5>0

(5)这朵花真是好看!

(6)2是素数当且仅当三角形有三条边。

(7)雪是黑色的当且仅当太阳是从东方升起。 (8)2000年10月1日天气晴好。 (9)太阳系以外的星球上有生物。 (10)小李在宿舍里。 (11)全体起立。

(12)4是2的倍数或是3的倍数。 (13)4是偶数且是奇数。 (14)李明和王华是同学。

(15)蓝色和黄色可以调配成绿色。

1..2 将上题中的命题符号化,并讨论他们的真值。 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;

1. 4将下列命题符号化,并讨论其真值。

(1) 如果今天是1号,则明天是2号; (2) 如果今天是1号,则明天是3号; 1. 5将下列命题符号化。 (1) 2是偶数不是素数;

(2) 小王不但聪明而且用功; (3) 虽然天气冷。老王还是来了; (4) 他一边吃饭,一边看电视;

(5) 如果天下大雨,他就乘公交汽车来; (6) 只有天下大雨,他才乘公交汽车来;

(7) 除非天下大雨,否则他不乘公交汽车来; (8) 不经一事,不长一智;

1. 5设p,q的真值为0 ,r,s的真值为1,求下列命题公式的真值。

(1) p?(q?r);

(2) (p?r)?(?p?s); (3)(p?(q?r)?((p?q)?(r?s); (4)?(p?(q?r??p)))?(r??s); 1.6设p:2+3=5。

q:大熊猫产在中国。 r:复旦大学在广州。

求下列复合命题的真值: (1)(pq)→r

(2)(r→(p∧q))┐p (3)┐r→(┐p∨┐q∨r)

(4)(p∧q∧┐r)((┐p∨┐q)→r)

1.7.用真值表判断下列公式的类型:方法不限。 (1)p→(p∨q∨r) (2)(p→┐q)→┐q (3)┐(q→r)∧r

(4)(p→q)→(┐q→┐p) (5)(p∧r)(┐p∧┐q)

(6)((p→q)∧(q→r))→(p→r) (7)(p→q)(rs)

1. 8用等值演算法证明下列等值式。

(1) (p?q)?(p??q)?p;

(2) ((p?q)?(p?r))?(p?(q?r)); (3) ?(p?q)?(q?p)??(p?q)) 1. 9设 A,B,C 为任意的命题公式。

(1) 已知A?C?B?C,问A?B吗? (2) 已知A?C?B?C,问A?B吗? (3) 已知?A??B, 问A?B吗?

1.10求下列命题公式的主析取范式,主合取范式,成真赋值,成假赋值。

()1(p?(q?v)?(p?q?r);(2)(?p?q)?(?q?p); (3)?(p?q)?q?r;1.11通过求主析取范式判断下列各组命题公式是不是等值。

(1)1,p?(q?r);2,q?(p?r);(2)1,p?q;2,p?q;

1.12有一探测队有3名队员,有一天取得一块矿样,3人的判断如下: 甲说:这不是铁,也不是铜; 已说:这不是铁,是锡; 丙说:这不是锡,是铁;

经实验鉴定后发现,其中一人两个判断是正确的,一个人判断对一半,一个人的判断全错了,根据以上的情况判断矿样的种类。

1.13判断下列的推理是不是正确,先将命题符号化,在写出前提和结论,然后在进行判断。

(1)如果今天是1号,则明天是5号,今天是1号,所以明天是5号。 (1)如果今天是1号,则明天是5号,明天是5号,所以今天是1号。 (1)如果今天是1号,则明天是5号,明天不是5号,所以今天不是1号。 (1)如果今天是1号,则明天是5号,今天不是1号,所以明天不是5号。 1.14构造下面的推理的证明。

(1)前提:?p(p??q),?q?r,?r.结论:?p.(2)前提:p?(q?s),q,p??r;结论:r?s.(3)前提:p?q.结论:p?(p?q)(4)前提:q?p,q?s,s?t,t?r.结论:p?q?r?s.

1.15如果他是理科学生,他必学好数学,如果他不是文科学生,他必是理科学生,他没有学好数学,所以他不是文科学生。 判断上面的推理是不是正确,并且证明你的结论。 1.16给定命题公式如下;

上述公式的成真赋值A,成假赋值为B,公式的类型为C。

供选择的答案

:① 无 ② 全体赋值 ③ 010,100,101,111 ④010,100,101,110,111 B: ① 无 ② 全体赋值 ③000,001,011, ④000,010,110 C: ①重言式 ②矛盾式 ③ 可满足式 1.17给定命题公式如下;

上述公式的主析取范式中含的极小项的个数为A,主合取范式含的极大项的个数为B,成真值的赋值为C 供选择的答案

A① 2 ② 3 ③ 5 ④ 0 ⑤ 8 B① 0 ② 8 ③ 5 ④ 3

C① 000,001,110; ②001,011,101,110,111; ③全体赋值 ④ 无 1.18给定下列三组前提。

(1)?(p??q),?q?r,?r(2)(p?q)?r,?r?s,?s

(3)?p?q,?q?r,r?s上述前提中,(1)的逻辑结论(有效结论)为A,(2)的逻辑结论为B,(3)的逻辑结论C。 供选择的答案

A,B,C:① r ② q ③?p ④ s ⑤?p??q ⑥p?s ⑦p?q

1.19设计一个符合下列要求的室类照明控制的线路,在房间的门外、门类及其床头分别装一个可以控制同一个电灯F的3个开关A,B,C, 当且仅当一个开关的搬键向上或3 个开关的搬键都向上时候电灯亮,则F的逻辑关系式可以化简为A

供选择的答案

A:① A?B?C ②A?B?C?(A?B?C)

1.20.某电路中有一个灯泡和三个开关A,B,C。已知在且仅在下述四种情况下灯亮:

(1)C的扳键向上,A,B的扳键向下。 (2)A的扳键向上,B,C的扳键向下。 (3)B,C的扳键向上,A的扳键向下。 (4)A,B的扳键向上,C的扳键向下。

设F为1表示灯亮,p,q,r分别表示A,B,C的扳键向上。 (a)求F的主析取范式。

(b)在联结词完备集{┐,∧}上构造F. (c)在联结词完备集{┐,→,}上构造F.

1.21.一个排队线路,输入为A,B,C,其输出分别为FA,FB,FC。本线路中,在同一时间内只能有一个信号通过,若同时有两个和两个以上信号申请输出时,则按A,B,C的顺序输出。写出FA,FB,FC在联结词完备集{┐,∨}中的表达式。

第二章习题

2.1在一阶逻辑中将下列命题符号化.

(1)鸟都会飞翔.

(2)并不是所有人都爱吃糖. (3)有人爱看小说.

(4)没有不爱看电影的人.

2.2 在一阶逻辑中将下列命题符号化,并指出个命题的真值.个体域分别为 (a)自然数集合N(N中含O). (b)整数集合Z. (c)实数集合R.

2 (1)对于任意的x,均由?x?1??x?2x?1

2 (2 )存在x,使得x+2=0. (3 ) 存在x,使得5x=1.

2.3 在一阶逻辑中将下列命题符号化.

(1)每个大学生不是文科生就是理科生. (2)有些人喜欢所有的花. (3)没有不犯错误的人.

(4)在北京工作的人未必就是北京人. (5)任何金属都可以溶解在某种液体中. (6)凡对顶角都相等.

2.4在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)时命题的真值:

(1)对于任意的x,均有x2-2=(x+

)(x-)。