离散数学习题解答(耿素云屈婉玲)北京大学出版社

去找 QQ头像 http://www.7zhao.net

(2)如果小王是理科学生,则他的数学成绩一定很好。如果小王不是文科生,则他一定是理科生。小王的数学成绩不好,所以小王是文科学生。 (1)设

p:今天是星期六 q:我们到颐和园玩 r:我们到圆明园玩 s:颐和园游人太多

前提:p?(q?r),s??q,p,s 结论:r 证明:

(1) s??q (2) (3) (4) (5) (6)

s ?q

前提引入

前提引入 (1)(2)假言推理 前提引入 前提引入 (4)(5)假言推理 (3)(6)析取三段论

p

p?(q?r)

q?r

(7) r

(2)设

p:小王是理科学生 q:小王数学成绩好 r:小王是文科学生

前提:p?q,?r?p,?q 结论:r 证明:

(1)p?q (2)?q (3)?p (4)?r?p

(5)r

前提引入 前提引入 (1)(2)拒取式 前提引入

(3)(4)拒取式

习题四

1.将下列命题0元谓词符号化: (1) 小王学习过英语和法语。

(2) 除非李建是东北人,否则他一定怕冷。 (3) 2大于3仅当2大于4. (4) 3不是偶数。 (5) 2或3是素数。

解(1)设一元谓词F(x):小王学习过x。a:英语,b:法语。(1)中命题符号化为0元谓词的蕴含式:F(a)?F(b)。

文章来源:http://www.7zhao.net

去找 QQ头像 http://www.7zhao.net

(2)设一元谓词F(x):x是东北人。G(x):x怕冷。a:李建。符号化为

?F(a)?G(a)。

(3)设二元谓词G(x,y):x大于y;a:2,b:3,c:4.符号化为:

G(a,b)?G(a,c).

(4)设一元谓词F(x): x不是偶数。a:3。命题符号化为0元谓词的蕴含式:

F(a)。

(5) 设一元谓词F(x): x是素数。a:2,b:3. 符号化为

F(a)?F(b)。

2.在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1)凡有理数都能被2整除。 (2)有的有理数都能被2整除。 其中(a)个体域为有理数集合。 (b)个体域为实数集合。

解:F(x):x能被2整除;G(x):x是整数。 (a)(1)?xF(x),真值为0,(2)?xF(x)真值为1.

(b)(1)?x(G(x)?F(x))真值为0,(2)?x(G(x)?F(x)),真值为1.

3.在一阶逻辑中将下列命题符号化,并分别讨论个体域限制为(a)(b)条件时的命题的真值: (1)对任意的x,均有x2?2?(x?2)(x?2)。 (2)存在x,使得x?5?9。 (a)个体域为自然数集合。 (b)个体域为实数集合。

解:设F(x):x?2?(x?2)(x?2),G(x):x?5?9

(a)(1)?xF(x),真值为0,(2)?xG(x)真值为1. (b)(1)?xF(x),真值为1,(2)?xG(x)真值为1. 4.在一阶逻辑中将下列命题符号化: (1)没有不能表示成分数的有理数。 (2)在北京卖菜的人不全是外地人。 (3)乌鸦都是黑色的。

文章来源:http://www.7zhao.net

2 去找 QQ头像 http://www.7zhao.net

(4)有的人天天锻炼身体。 解:

(1)??x(F(x)??G(x))或者?x(F(x)?G(x)),其中F(x):x是有理数,G(x):x能表示成分数

(2)??x(F(x)?G(x))或?x(F(x)??G(x)),其中F(x):x在北京卖菜,G(x):x是外地人 (3)?x(F(x)?G(x)),其中F(x):x是乌鸦,G(x):x是黑色的; (4)?x(F(x)?G(x)),其中F(x):x是人,G(x):x天天锻炼身体。 5.在一阶逻辑中将下列命题符号化: (1)所有的火车都比轮船跑得快。 (2)有的火车比有的汽车快。

(3)不存在比所有火车都快的汽车。 (4)说凡是汽车就比火车慢是不对的。 解:

G(y):y是轮船,H(x,y):x(1)?x?y(F(x)?G(y)?H(x,y)),其中F(x):x是火车,

比y快;

(2)?x?y(F(x)?G(y)?H(x,y)),其中F(x):x是火车,G(y):y是汽车,H(x,y):x比y快;

(3)??x(G(x)??y(F(y)?H(x,y)),其中F(x):x是火车,G(y):y是汽车,

H(x,y):x比y快;

(4)??x(G(x)??y(F(y)?H(x,y)),其中F(x):x是火车,G(y):y是汽车,

H(x,y):x比y慢;

6.在下列命题符号化,个体域为实数集合R,并指出各命题的真值: (1)对所有的x,都存在y,使得x*y?0。 (2)存在着x,对所有y都有x*y?0。 (3)对所有的x,都存在y,使得y?x?1。 (4)对所有的x和y,都有y*x?x*y。 (5)对任意的x和y,都有y*x?x?y。 (6)对任意的x,存在y,使得x?y?0。

22文章来源:http://www.7zhao.net

去找 QQ头像 http://www.7zhao.net

解:各命题符号化如下: (1)?x?y(x*y?0), (2)?x?y(x*y?0), (3)?x?y(y?x?1), (4)?x?y(y*x?x*y), (5)?x?y(y*x?x?y), (6)?x?y(x2?y2?0)。

7.将下列各公式翻译成自然语言,个体域为整数集Z, 并判断各命题的真假: (1)?x?y?z(x?y?z) (2)?x?y(x*y?1) (3)?x?y?z(x?y?z)

解:

(1)对所有整数x和y,存在整数z,使得x?y?z,为真命题。 (2)对任意整数x,存在整数y,使得x*y?1,为假命题。 (3),存在整数x,使得对任意整数y与z,均有x?y?z,为假命题。

8.指出下列公式中的指导变元,量词的辖域,各个体变项的自由出现和约束出现: (1)?x(F(x)?G(x,y)) (2)?xF(x,y)??yG(x,y)

(3)?x?y(F(x,y)?G(y,z))??xH(x,y,z) 解:

(1)指导变元为x,全称量词?的辖域为F(x)?G(x,y)。其中x是约束出现的,y是自由出现的。

(2)蕴含式前件?xF(x,y)中,指导变元为x,全称量词?的辖域为F(x,y),其中x是约束出现的,y是自由出现的。

(3)在?x?y(F(x,y)?G(y,z)),指导变元为x和y,辖域为(F(x,y)?G(y,z)),其中x和y约束出现的,而z是自由出现的。在?zH(x,y,z)中,指导变元为z,辖域为H(x,y,z),

文章来源:http://www.7zhao.net

联系客服:779662525#qq.com(#替换为@)