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

2024年3月1日发(作者：小学升初中数学试卷美版)

【MeiWei_81重点借鉴文档】

习题一

1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？

（1）中国有四大发明.

答：此命题是简单命题，其真值为1.

（2）5是无理数.

答：此命题是简单命题，其真值为1.

（3）3是素数或4是素数.

答：是命题，但不是简单命题，其真值为1.

（4）2x35

答：不是命题.

（5）你去图书馆吗？

答：不是命题.

（6）2与3是偶数.

答：是命题，但不是简单命题，其真值为0.

（7）刘红与魏新是同学.

答：此命题是简单命题，其真值还不知道.

（8）这朵玫瑰花多美丽呀！

答：不是命题.

（9）吸烟请到吸烟室去！

答：不是命题.

（10）圆的面积等于半径的平方乘以.

答：此命题是简单命题，其真值为1.

（11）只有6是偶数，3才能是2的倍数.

答：是命题，但不是简单命题，其真值为0.

（12）8是偶数的充分必要条件是8能被3整除.

答：是命题，但不是简单命题，其真值为0.

（13）20RR年元旦下大雪.

答：此命题是简单命题，其真值还不知道.

2.将上题中是简单命题的命题符号化.

解:（1）p：中国有四大发明.

（2）p:是无理数.

（7）p:刘红与魏新是同学.

（10）p:圆的面积等于半径的平方乘以π.

（13）p:20RR年元旦下大雪.

3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.

（1）5是有理数.

答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1.

（2）25不是无理数.

答：否定式：25是有理数.p：25不是无理数.q：25是有理数.其否定式q的真值为1.

（3）2.5是自然数.

答：否定式：2.5不是自然数.p：2.5是自然数.q：2.5不是自然数.其否定式q的真值为1.

（4）ln1是整数.

答：否定式：ln1不是整数.p：ln1是整数.q：ln1不是整数.其否定式q的真值为1.

【MeiWei_81重点借鉴文档】

4.将下列命题符号化，并指出真值.

（1）2与5都是素数

答：p：2是素数，q：5是素数，符号化为pq，其真值为1.

（2）不但是无理数，而且自然对数的底e也是无理数.

答：p：是无理数，q：自然对数的底e是无理数，符号化为pq，其真值为1.

（3）虽然2是最小的素数，但2不是最小的自然数.

答：p：2是最小的素数，q：2是最小的自然数，符号化为pq，其真值为1.

（4）3是偶素数.

答：p：3是素数，q：3是偶数，符号化为pq，其真值为0.

（5）4既不是素数，也不是偶数.

答：p：4是素数，q：4是偶数，符号化为pq，其真值为0.

5.将下列命题符号化，并指出真值.

（1）2或3是偶数.

（2）2或4是偶数.

（3）3或5是偶数.

（4）3不是偶数或4不是偶数.

（5）3不是素数或4不是偶数.

答:p：2是偶数，q：3是偶数，r:3是素数，s:4是偶数,t:5是偶数

(1) 符号化:pq，其真值为1.

(2) 符号化：pr，其真值为1.

(3) 符号化：rt，其真值为0.

(4) 符号化：qs，其真值为1.

(5) 符号化：rs，其真值为0.

6.将下列命题符号化.

（1）小丽只能从筐里拿一个苹果或一个梨.

答：p：小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨，符号化为:pq.

（2）这学期，刘晓月只能选学英语或日语中的一门外语课.

答：p：刘晓月选学英语，q：刘晓月选学日语，符号化为:(pq)(pq).

7.设p：王冬生于1971年，q：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化

答:列出两种符号化的真值表：

p q

0 0 0 0

0 1 1 1

1 0 1 1

1 1 0 1

根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式.

8.将下列命题符号化,并指出真值.

（1）只要,就有；

（2）如果,则；

（3）只有,才有；

（4）除非,才有；

（5）除非,否则；

（6）仅当.

答:设p:,则:;设q:,则:.

符号化真值

【MeiWei_81重点借鉴文档】

（1）

（2）

（3）

（4）

（5）

（6）

9.设p：俄罗斯位于南半球,q：亚洲人口最多,将下面命题用自然语言表述,并指出其真值：

（1）（2）（3）（4）；

；；

；

（5）；

（6）；

（7）.

答:根据题意,p为假命题,q为真命题.

自然语言真值

（1）只要俄罗斯位于南半球,亚洲人口就最多 1

（2）只要亚洲人口最多,俄罗斯就位于南半球 0

（3）只要俄罗斯不位于南半球,亚洲人口就最多 1

（4）只要俄罗斯位于南半球，亚洲人口就不是最多 1

（5）只要亚洲人口不是最多，俄罗斯就位于南半球 1

（6）只要俄罗斯不位于南半球，亚洲人口就不是最多 0

（7）只要亚洲人口不是最多，俄罗斯就不位于南半球 1

10．设p：9是3的倍数,q：英国与土耳其相邻,将下面命题用自然语言表述,并指出真值：

（1）；

（2）；

（3）；

（4）.

答:根据题意,p为真命题,q为假命题.

自然语言

（1） 9是3的倍数当且仅当英语与土耳其相邻

（2） 9是3的倍数当且仅当英语与土耳其不相邻

（3） 9不是3的倍数当且仅当英语与土耳其相邻

（4） 9不是3的倍数当且仅当英语与土耳其不相邻

11．将下列命题符号化,并给出各命题的真值：

（1）若2+2=4,则地球是静止不动的；

（2）若2+2=4,则地球是运动不止的；

（3）若地球上没有树木,则人类不能生存；

（4）若地球上没有水,则答:

（1）

命题1

p:2+2=4

命题2

q:地球是静止不动的

符号化

真值

是无理数.

真值

【MeiWei_81重点借鉴文档】

（2）

（3）

（4）

p:2+2=4

p:地球上有树木

q:地球是静止不动的

q:人类能生存

12.将下列命题符号化,并给出各命题的真值：

（1）2+2=4当且仅当3+3=6；

（2）2+2=4的充要条件是3+36；

（3）2+24与3+3=6互为充要条件；

（4）若2+24,则3+36,反之亦然.

答:设p:2+2=4,q:3+3=6.

符号化

(1)

(2)

(3)

(4)

真值

13.将下列命题符号化,并讨论各命题的真值：

（1）若今天是星期一,则明天是星期二；

（2）只有今天是星期一,明天才是星期二；

（3）今天是星期一当且仅当明天是星期二；

（4）若今天是星期一,则明天是星期三.

答:设p:今天是星期一,q:明天是星期二,r:明天是星期三.

符号化真值讨论

(1) 不会出现前句为真,后句为假的情况

(2)

(3)

(4)

不会出现前句为真,后句为假的情况

必然为1

若p为真,则真值为0;若p为假,则真值为1

14.将下列命题符号化：

（1）刘晓月跑得快,跳得高；

（2）老王是山东人或者河北人；

（3）因为天气冷,所以我穿了羽绒服；

（4）王欢与李乐组成一个小组；

（5）李欣与李末是兄弟；

（6）王强与刘威都学过法语；

（7）他一面吃饭,一面听音乐；

（8）如果天下大雨,他就乘班车上班；

（9）只有天下大雨,他才乘班车上班；

（10）除非天下大雨,否则他不乘班车上班；

（11）下雪路滑,他迟到了；

（12）2与4都是素数,这是不对的；

（13）“2或4是素数,这是不对的”是不对的.

答:

命题1 命题2

(1) p:刘晓月跑得快 q:刘晓月跳得高

(2)

(3)

p:老王是山东人

p:天气冷

q:老王是河北人

q:我穿羽绒服

命题3

符号化

【MeiWei_81重点借鉴文档】

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

p:王欢与李乐组成一个小组

p:李辛与李末是兄弟

p:王强学过法语

p:他吃饭

p:天下大雨

p:下雪

p:2是素数

q:刘威学过法语

q:他听音乐

q:他乘车上班

q:路滑

q:4是素数

r:他迟到了

p:王欢与李乐组成一个小组

p:李辛与李末是兄弟

(13) p:2是素数 q:4是素数

15.设p：2+3=5.

q：大熊猫产在中国.

r:太阳从西方升起.

求下列符合命题的真值：

（1）

（2）

（3）

（4）

解：p真值为1，q真值为1，r真值为0.

（1）0，（2）0，（3）0，（4）1

16.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值：

（1）

（2）

（3）（4）

解：（1）0，（2）0，（3）0，（4）1

17.判断下面一段论述是否为真：“是无理数.并且,如果3是无理数,则外,只有6能被2整除,6才能被4整除.”

解：p:是无理数q:3是无理数r:也是无理数.另是无理数s:6能被2整除t：6能被4整除

符号化为:，该式为重言式，所以论述为真。

18.在什么情况下,下面一段论述是真的:“说小王不会唱歌或小李不会跳舞是正确的,而说如果小王会唱歌,小李就会跳舞是不正确的.”

解：p:小王会唱歌。q:小李会跳舞。

真值为1.真值为0.可得，p真值为1，q真值为0.

所以，小王会唱歌，小李不会跳舞。

19.用真值表判断下列公式的类型:

（1）

（2）p

（3）

（4）

（5）

【MeiWei_81重点借鉴文档】

（6）（7）解：

（1）

此式为重言式

（2）

此式为可满足式

（3）

此式为矛盾式

（4）

此式为重言式

（5）

此式为可满足式

（6）

p q

（p1

【MeiWei_81重点借鉴文档】

此式为重言式

（7）

q r

0 0

0 1

1 0

1 1

此式为可满足式

20.求下列公式的成真赋值：

（1）

（2）

（3）

（4）解：

0 0 0 1 1 0

0 1 1 0 1 1

1 0 1 1 1 1

1 1 1 1 0 1

由真值表得：（1）的成真赋值是01，10,11（2）的成真赋值是00，10,11

（3）的成真赋值是00，01,10（4）的成真赋值是01，10,11

21.求下列各公式的成假赋值：

（1）

（2）

（3）

解：

p q r

0 0 0 1 1 1

【MeiWei_81重点借鉴文档】

由真值表得：（1）的成假赋值是011（2）的成假赋值是010,110

（3）的成假赋值是100,101

22.已知公式是矛盾式，求公式成真和成假赋值.

解：∵是矛盾式∴也是矛盾式。

由此可得：该式无成真赋值。而成假赋值为：000,001,010,011,100,101,110,111

23.已知公式是重言式,求公式的成真和成假赋值.

解：∵是重言式，∴也是重言式。

由此可得：该式无成假赋值。而成真赋值为：000,001,010,011,100,101,110,111

24.已知是重言式，试判断公式的类型.

解：∵11，∴25.已知的类型.

解：∵只有00，∴26.已知解：是重言式，及是矛盾式，而要使该式为矛盾式，其成假赋值都是重言式。

是矛盾式，试判断的类型.

是重言式，而要使该式为重言式，其成真赋值只有都是重言式。

是矛盾式，试判断公式及及是矛盾式。

是重言式。

27.设A、B都是含命题变量项p1,p2,…,pn的公式,证明:重言式.

解：

A B

是重言式当且仅当A和B都是

由真值表可得，当且仅当A和B都是重言式时，是重言式。

28.设A、B都是含命题变量项p1,p2,…,pn的公式,已知是矛盾式,能得出A和B都是矛盾式的结论吗?为什么?

解：

A B

【MeiWei_81重点借鉴文档】

1 1 1

同样由真值表可得，的成假赋值有00,01,10.所以无法得到A和B都是矛盾式。

29.设A、B都是含命题变量项p1,p2,…,pn的公式,证明:是矛盾式当且仅当A和B都是矛盾式.

解：

A B

由真值表可得，当且仅当A和B都是矛盾式时，是矛盾式。

30.设A、B都是含命题变量项p1,p2,…,pn的公式,已知是重言式,能得出A和B都是重言式的结论吗?

解：

A B

由真值表可得0

的成真赋值有01,10，11.所以无法得到A和B都是重言式。

习题二

1.设公式Apq,Bpq，用真值表验证公式A和B适合德摩根律：

(AB)AB

(AB)

AB

00 1 0 1 1

01 1 0 0 0

10 0 1 0 0

11 1 0 0 0

2.公式A和B同题（1），用真值表验证公式A和B适合蕴涵等值式.

ABAB

AB

AB

00 1 0 0 0

01 1 0 0 0

10 0 1 1 1

11 1 0 0 0

3．用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.

（1）(pqq)

答：原式=((pq)q)

=(pqq)

是矛盾式.

4.用等值演算法证明下面等值式.

（pq）（pq）（1）p

（qq）答：右式=p=p1=p

（2）((pq)(pr))(p(qr))

答：右式=p(qr)=(pq)(pr)=(pq)(pr))=左式

【MeiWei_81重点借鉴文档】

（3）(pq)(pq)(pq)

答：左式=(pq)(pq)

=(p(pq))(q(pq))

=(pq)(pq)

（4）(pq)(pq)(pq)(pq)

答：左式=(p(pq))(q(pq))

=(pq)(pq)

5.求下列公式的主析取范式，并求成真赋值：

（1）(pq)(qp)

答：

(pq)(qp)(pq)(qp)(pq)(qp)(pq)(q(pp))(p(qq)

(pq)(pp)(pq)m0m2m3成真赋值为00,10,11.

（2）(pq)qr

答：(pq)qr(pq)qrpqq0

所以为矛盾式。

（3）(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)(pr)(pqr)(pq(rr)(p(qq)r)(p(qq)(rr))((p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)m0m1m2m3m4m5m6m7所以是重言式，真值为000,001,010,011,100,101,110,111.

6.求下列公式的主析取范式，并求成真赋值：

（1）(qp)p

答：(qp)p(qp)pqpp0，是矛盾式，所有赋值均为成真赋值。

（2）(pq)(pr)

答：(pq)(pr)(ppr)(qpr)(pqr)M4，成假赋值为100.

（3）(p(pq))r

答：(p(pq))r(p(pq))r(ppqr1，所以为重言式。所有赋值均为成真赋值。

7.求下列公式的主析取范式，再用主析取范式求主合取范式：

（1）(pq)r

答：(pq)r(pq(rr))((pp)(qq)r)

【MeiWei_81重点借鉴文档】

(pq(rr))((pp)(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)

m1m3m5m6m7M0M2M4（2）(pq)(qr)

答：(pq)(qr)(pq)(qr)(pq)(pr)(qq)(qr)(pq(rr))(p(qq)r)((pp)qr)(pqr)(pqr)(pqr)(pqr)m0m1m3m7M2M4M5M68.求下列公式的主合取范式，再用主合取范式求主析取范式：

（1）(pq)q

答：(pq)q(pq)qpqq1m0m1m2m3

为重言式。

（2）(pq)r

答：(pq)r((pq)(pq))r((pq)(pq))r

((pq)(pq))r(pqr)(pqr)M0M6

m1m2m3m4m5m7（3）(rp)pq

答：(rp)pqrppq

M0M1M2M3M4M5M6M7

0

因此为矛盾式.

9.用真值表求下面的公式的主析取范式.

（1）(pq)(pr)

答：公式的真值表如下：

p

pq

0 0 0 1 0

0 0 1 1 0

0 1 0 1 1

0 1 1 1 1

1 0 0 0 1

1 0 1 0 1

1 1 0 0 1

1 1 1 0 1

其成真赋值为001,010,011,100,101,110,111，所以其主析取范式为

m1m2m3m4m5m6m7

（2）(pq)(pq)

答：公式的真值表如下：

q

0 0 1

pr

(pq)(pr)

pq

pq

(pq)(pq)

【MeiWei_81重点借鉴文档】

(pq)(pq)(pq)((pq)(pq))

(pq)(pq)

故其成真赋值为001，010.所以其主析取范式为m1m2.

10.用真值表求下面公式的主合取范式.

（1）(pq)r

答：(pq)r(pr)(qr)

M0M2M4

（2）(pq)(qr)

答：(pq)(qr)(pq)(qr)

M2M4M5M6

11.用真值表求下面公式的主析取范式和主合取范式.

（1）(pq)r

（2）p(pqr)

（3）(qp)p

pqr

(pq)r

p(pqr)

(qp)p

000 0 1 0

001 0 1 0

010 0 1 0

011 1 1 0

100 0 1 0

101 1 1 0

110 0 1 0

111 1 1 0

答：（1）由真值表可得成真赋值为011,101,111，故主析取范式为m3m5m7，主合取范式为M0M1M2M4M6

（2）由真值表可得无成假赋值，故主析取范式为

m0m1m2m3m4m5m6m7，主合取范式为1.

（3）由真值表可得无成真赋值，故主析取范式为0，主合取范式为

M0M1M2M3.

12.已知公式A含3个命题变项p,q,r，并且它的成真赋值为000，011，110，求A的主合取范式和主析取范式.

答：由题意得，A的主主合取范式为M1M2M4M5M7，主析取范式

m0m3m6.

13.已知公式A含3个命题变项p,q,r，并且它的成真赋值为000，011，110，求A的主合取范式和主析取范式.

答：由题意得，A的主主合取范式为M2M3M6M7，主析取范式

m0m1m5m7.

14.已知公式A含n个命题变相p1,p2,......,pn，并且无成假赋值，求A的主合取范式.

答：A的主合取范式为1..

15.用主析取范式判断下列公式是否等值：

（1）(pq)r与q(pr)

答：(pq)r(pq)r

【MeiWei_81重点借鉴文档】

m1m3m4m5m7

q(pr)pqr

m0m1m2m3m4m5m7

所以上述公式不等值.

（2）(pq)与(pq)

答：(pq)pq

m0m1m2

(pq)pq

m0

16.用主合取范式判断下列公式是否等值.

（1）p(qr)与(pq)r

答：p(qr)M6

(pq)r=M6

（2）p(qr)与(pq)r

答：p(qr)M6

(pq)r=M0M2M6

17.将下列公式化成与之等值且仅含,,中联结词的公式：

（1）(p(q(qr)))

答：(p(q(qr)))(p(q(qr)))

p((qr))

p((q(qr))(q(qr)))

（2）(pq)r

答：(pq)r，原式已满足题目要求.

（3）p(qr)

答：p(qr)(p(qr))((r)p)

(p((qr)(qr)))(((qr)(qr))p)

18.将下列公式化成与之等值且仅含{,}中联结词的公式：

（1）pqr

答：此公式已经符合题目要求.

（2）(pr)q

答：(pr)q((pr)(rp))q

((pr)(rp))q

((pr)(rp))q

（3）(p(qr))q

答：(p(qr))q(p(qr))p

(p(qr))p

((p(qr))p)

19.将下列公式化成与之等值且仅含,中联结词的公式.

（1）(pq)r

答：(pq)r((pq)r)

（2）(p(qp))qr

答：(p(qp))qr((p(qp))qr)

【MeiWei_81重点借鉴文档】

（3）pqr

答：pqr(pqr)

20．将下列公式化成与之等值且仅含{，}中联结词的公式：

（1）(pq)r（2）(pq)r（3）(pq)r

答：(pq)r(pq)r(pq)r(pq)r

(2)(pq)r

答：(pq)r((pq)r)((pq)r)

(3)(pq)r

答：(pq)r((pq)r)(r(pq))

(((pq)r)(r(pq)))

(((pq)r)(r(pq)))

21．证明：

（1）(pq)(qp)，(pq)(qp).

（2）(p(qr))((pq)r)，(p(qr))((pq)r).

证明：(1)pq(pq)(qp)qp；

pq(pq)(qp)qp

(2)令p0,q0,r1则p(qr)1,(pq)r0，p(qr)1,(pq)r0.，可知(p(qr))((pq)r)，(p(qr))((pq)r).

22.从表2.6中，找出与下列公式等值的真值函数：

（1）pq （2）pq （3）(pq)(pq)（4）(pq)

(2)(2)(2)(2)答：(1)F14;(2)F8;(3)F6;(4)F2

23．设A、B、C为任意的命题公式，证明：

（1）等值关系有自反性：AA

（2）等值关系有对称性：若AB,则BA

（3）等值关系有传递性：若AB且BC，则AC

答：(1)AA(AA)(AA)AAAA1

(2)BA(BA)(AB)(AB)(BA)AB

(3)

若AB且BC(AB)(BA)(BC)(CB)(AB)(BC)(CB)(BA)(AC)(CA)

AC即AC24．设A、B为任意的命题公式，证明：AB当且仅当AB

答：AB(AB)(BA)(AB)(BA)AB.

因此AB当且仅当AB。

【MeiWei_81重点借鉴文档】

25．设A、B、C为任意的命题公式，（1）若ACBC，举例说明AB不一定成立。（2）若ACBC，举例说明AB不一定成立。由（1）、（2）可知，联结词与不满足消去率。

答：(1)设Ap1,Bq0,Cr1，则AC1BC1 ，但A1,B0，二者不等价。

（2）设Ap1,Bq0,Cr0，则AC0BC0，但A1,B0，二者不等价。

26．在上题（25）中，若已知ACBC，在什么条件下，AB一定成立？又若已知ACBC，在什么条件下，AB一定成立？

解：若C0;则ACBC，AB一定成立。

若C1；则ACBC，AB一定成立。

27．某电路中有一个灯泡和三个开关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。

答：（a）由题意知，灯亮的情况如下：

F(pqr)(pqr)(pqr)(pqr)

m1m3m4m6

（b）F(pqr)(pqr)(pqr)(pqr)

((pr)(pr))

（c）Fpqr

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

答：p：A输入，q：B输入，r：C输入.有题意可得：

FA(pqr)(pqr)(pqr)(pqr)

(pq)(pq)p

FB(pqr)(pqr)pq

FCpqr

29.在某班班委成员的选举中，已知王小红、李强、丁金生3位同学被选进了班委会.该班的甲、乙、丙三名学生预言：

甲说：王小红为班长，李强为生活委员.

乙说：丁金生为班长，王小红为生活委员.

丙说：李强为班长，王小红为学习委员.

班委会分工名单公布后发现，甲、乙、丙三人都恰好猜对了一半.问王小红、李强、丁金生各任何职（用等值等演求解）？

答：设p：王小红为班长，q：李强为生活委员

r：丁金生为班长，s：王小红为生活委员

t：李强为班长，w：王小红为学习委员

【MeiWei_81重点借鉴文档】

由题意得，p、q有且只有一个为真，r、s有且只有一个为真，t、w有且只有一个为真.

若p为真，则q为假，那么r为假，则s为真，这样p与s矛盾，因此这种假设行不通.

若p为假，则q为真，那么t为假，则w为真，则s为假，所以r为真，因此王小红、李强、丁金生的职位分别是：学习委员、生活委员、班长.

30.某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：

（1）若赵去，钱也去.

（2）李、周两人中必有一人去.

（3）钱、孙两人中去且仅去一人.

（4）孙、李两人同去或同不去.

（5）若周去，则赵、钱也同去.

用等值演算法分析该公司如何选派他们出国？

答：设p：派赵去，q：派钱去，r：派李去，s：派孙去，t：派周去

首先以条件（2）为基础，有三种情况：

① 若周去，李不去，由条件（5）得则赵、钱同去，由条件（3）得那么孙不去，符合5个条件，即pqrst.

② 若李去，周不去，由条件（4）得则孙去，从而由条件（3）得钱不去，而由条件（1）得赵也不去，即pqrst.

③ 若周、李都去，那么由条件（4）得则孙去，由条件（5）得赵、钱都去，这样孙和钱都去，与条件（3）矛盾，因此这种情况不存在.

习题三

1.从日常生活或数学中的各种推理中，构造两个满足附加律的推理定律，并将它们符号化。例如：“若2是偶数，则2是偶数或3是奇数”。令p:2是偶数，q:3是奇数，则该附加律符号为ppq。

解：（1）“若3是素数，则3是素数或5是奇数”。令p：3是素数，q：5是奇数，则该附加律符号化为ppq

（2）“若明天不下雨，则明天不下雨或明天下雪”。令p：明天下雨，q：明天下雪，则该附加律符号化为ppq。

2.从日常生活或数学的各种推理中，构造两个满足化简律的推理定律，并将它们符号化。例如：“我去过海南岛和新疆，所以我去过海南岛”。令p：我去过海南岛，q:我去过新疆，则该化简律符号化为pqp。

解：（1）“6能被2和3整除，所以6能被2整除”。令p：6能被2整除，p：6能被2整除，q：6能被3整除，则该化简律符号化为pqp。

（2）“小明会弹琴和跳舞，所以小明会弹琴”。令p：小明会弹琴，q：小明会跳舞，则该化简律符号化为pqp。

3.随意构造三个满足假言推理定律的推理，并将它们符号化。例如：“如果2是素数，则雪是黑色的，2是素数，所以雪是黑色的”。令p:2是素数，q：雪是黑色的，该假言推理定律符号化为(pq)pq。

解：（1）“如果小明会跳舞，则他会弹琴，小明会跳舞，所以他会弹琴”。令p：小明会弹琴，q：小明会跳舞，该假言推理定律符号化为(pq)pq。

（2）“如果3是奇数，则明天下雨，3是奇数，所以明天下雨”。令p：3是奇数，q：明天下雨，该假言推理定律符号化为(pq)pq。

（3）“如果明天晴天，则小明去游泳，明天晴天，所以小明去游泳”。令p：明天晴天，q：小明去游泳，该假言推理定律符号化为(pq)pq。

4.参照1,2,3题，请构造满足拒取式、析取三段论、假言三段论、等价三段论、构造性二难等推理定律的实例各一个，并将它们符号化。

【MeiWei_81重点借鉴文档】

解：（1）拒取式：“明天是周末，小明就休息，小明没有休息，所以明天不是周末”。令p：明天周末，q：小明休息。该拒取式定律符号化为pqqp。

（2）析取三段论：“小明会弹琴或跳舞，小明不会跳舞，所以小明会弹琴”。令p：小明会弹琴，q：小明会跳舞，该析取三段式定律符号化为pqqp。

（3）假言三段论：“明天要是周末，小明明天休息，小明要是明天休息，他就会去游泳，所以，明天要是周末，小明就去游泳”。令p：明天是周末，q：小明明天休息，t：小明去游泳，该假言三段论定律符号化为pqqtpt。

（4）等价三段论：“2是素数当且仅当3是奇数，3是奇数当且仅当4是偶数，所以2是素数当且仅当4是偶数”。令p：2是素数，q：3是奇数，t：4是偶数，该等价三段论定律符号化为pqqtpt。

（5）构造性二难：“明天是周一，小明就要上学，明天是周末，小明就要去游泳，明天是周末或者周一，所以小明去上学或者去游泳”。令p：明天是周一，q小明要上学，s：明天是周末，t：小明要去游泳，该构造性二难定律符号化为pqstpsqt。

（6）破坏性二难：“明天是周一，小明就要上学，明天是周末，小明就要去游泳，小明没有去上学或者小明没有去游泳，所以明天不是周一或者明天不是周末”。令p：明天是周一，q小明要上学，s：明天是周末，t：小明要去游泳，该构造性二难定律符号化为pqstqtps。

5.分别写出德摩定律、吸收律所产生的推理定律（每个等值式产生两条推理定律）。

解：的摩定律1：ABAB

产生的推理定律：（1）ABAB（2）ABAB

的摩定律2：ABAB

产生的推理定律：（1）ABAB（2）ABAB

吸收律1：AABA

产生的推理定律：（1）AABA（2）AAAB

吸收律2：AABA

产生的推理定律：（1）AABA（2）AAAB

6.判断下列推理是否正确。先将简单命题符号化，再写出前提、结论、推理的形式结构（以蕴涵式的形式给出）和判断过程（至少给出两种判断方法）：

（1）若今天是星期一，则明天是星期三。今天是星期一，所以明天是星期三。

（2）若今天是星期一，则明天是星期二。明天是星期二，所以今天是星期一。

（3）若今天是星期一，则明天是星期三。明天不是星期三，所以今天不是星期一。

（4）若今天是星期一，则明天是星期二。今天不是星期一，所以明天不是星期二。

（5）若今天是星期一，则明天是星期二或星期三。

（6）今天是星期一当且仅当明天是星期三。今天不是星期一，所以明天不是星期三。

解：（1）设p：今天是星期一，q：明天是星期三，推理的形式结构为pqpq，判断该推理是否正确，即判断pqpq是否为重言式，不难看出，该式满足假言推理定律，所以推理正确。

（2）设p：今天是星期一，q：明天是星期二，推理的形式结构为pqqp。

等值演算法：pqqppqqpqppq，可见该式不是重言式，所以推理不正确。

【MeiWei_81重点借鉴文档】

pqqppqqp主析取范式法：qp，从而可知不是重言式，故推理不正确。

pqM1m0m2m3（3）设p：今天是星期一，q：明天是星期三，推理的形式结构为pqqp，判断该推理是否正确，即判断pqqp是否为重言式，不难看出，该式满足拒取式定律，所以推理正确。

（4）设p：今天是星期一，q：明天是星期二，推理的形式结构为pqpq。

pqpqpqpq等值演算法：(ppqp)q，可见该式不是重言式，所以推理不pqpq正确。

主析取范式法：pqpqpqpq(ppqp)qpqpqM1m0m2m3，从而可知不是重言式，故推理不正确。

（5）设p：今天是星期一，q：明天是星期二，r：明天是星期三。推理的形式结构为pqr。

p(qr)pqrM4m0m1m2m3m4m5m6m7，由此可知p(qs)不为重言式，故推理不正确。

显然该式不是重言式，所以推理不正确。

（6）设p：今天是星期一，r：明天是星期三，推理的形式结构为(pr)pr。

(pr)pr((pr)(rp)p)r(pr)(rp)pr(pr)(pr)prp(pr)rpm4m5m6m77.在下面各推理中没给出结论。请对于每个推理前提给出两个结论，使其中之一是有效的，而另一个不是有效的：

（1）前提：pq，qr

（2）前提：(pq)r，r，q

（3）前提：p(qr)，p，q

解：（1）结论1：pr为有效的（假言三段论）

结论2：p为无效的。

（2）结论1：pq是有效的（拒取式）

，由此可知不为重言式，故推理不正确。

【MeiWei_81重点借鉴文档】

结论2：p是无效的

（3）结论1：(qr)是有效的（假言三段论）

结论2：r是无效的

8.在下面各推理中没给出结论，请对于每个推理前提给出两个结论，使其中之一是有效的，而另一个不是有效的。

（1）只有天气热，我才去游泳。我正在游泳，所以……

（2）只有天气热，我就去游泳。我没去游泳，所以……

（3）除非天气热并且我有时间，我才去游泳。天气不热或我没时间，所以……

解：

（1）设p：天气热，q：我去游泳

前提：qp,q

结论1：p，有效结论（假言推理）

结论2：p，无效结论

（2）设p：天气热，q：我去游泳。

前提：pq,q

结论1：p，有效结论（拒取式）

结论2：p，无效结论

（3）设p：天气热，q：我有时间，r：我去游泳。

前提：rpq,pq

结论1：r，有效结论（拒取式）

结论2：r，无效结论。

9.用三种方法（真值表法，等值演算法，主析取范式法）证明下面推理是正确的：

若a是奇数，则a不能被2整除。若a是偶数，则a能被2整除。因此，如果a是偶数，则a不是奇数。

解：设p：a是奇数，q：a能被2整除，r：a是偶数。

推理的形式结构为pqrqrp（R）。下面用三种方法证明该式为重言式：

（1）真值表法：

(pq)(rq)

(rp)

pqr R

000 0 1 1

001 1 1 1

010 0 1 1

011 0 1 1

100 0 1 1

101 1 0 1

110 1 1 1

111 1 0 1

由真值表可知（R）为重言式，故推理是正确的。

（2）等值演算法：

pqrqrppqrqrppqqrprpqpqrr(交换律，结合律)

pqqrpqqr1【MeiWei_81重点借鉴文档】

【MeiWei_81重点借鉴文档】

（3）构造证明法：

前提：pq,rq

结论：rp

证明：

①pq前提引入

②qp①置换

③rq前提引入

④rp③②假言三段论

主析取范式法

由方法2可以得知推理的形式结构（R）的主析取范式为

(*)m0m1m2m3m4m5m6m7，则（R）为重言式，推理正确。

10.用两种方法（真值表法，主析取范式法）证明下面推理不正确：

如果a,b两数之积是负数，则a,b之中恰有一个是负数。a,b两数之积不是负数，所以a,b中无负数。

真值表法：

(qr)(qr)

p(qr)(qr)

qr

pqr A

000 0 1 1 1

001 1 1 0 0

010 1 1 0 0

011 0 1 0 0

100 0 0 1 1

101 1 1 0 1

110 1 1 0 1

111 0 0 0 1

推理不正确

主析取范式法：

(p((qr)(qr))(qr))p)(qr)(p(qr)(qr)p(qr))p(qr)p(qr)m0m4m5m6m7

由于主析取范式只含有5个极小项，所以（3.8）不是重言式，推理不正确。

11.填充下面推理证明中没有写出的推理规则。

前提：pq，qr，rs，p

结论：s

证明:

①p前提引入

②pq前提引入

③q析取三段论

④qr前提引入

⑤r析取三段论

⑥rs前提引入

⑦s假言推理

12.填充下面推理证明中没有写出的推理规则。

前提：p(qr)，q(rs)

结论：(pq)s

证明：

①pq附加前提引入

【MeiWei_81重点借鉴文档】

②p化简规则

③q化简规则

④p(qr)前提引入

⑤qr前提引入

⑥r③⑤假言推理

⑦q(rs)前提引入

⑧rs③⑦假言推理

⑨s⑥⑧假言推理

13.前提：(pq)q，pq，rs

结论1：r

结论2：s

结论3：rs

（1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。

（2）证明从此前提出发，推任何结论的推理都是正确的。

（1）证明：

结论1：

((pq)q)(pq)(rs)rpqqpqrsr0pqrsr0r1结论2：

((pq)q)(pq)(rs)spqqpqrss0pqrss0s1结论3：

((pq)q)(pq)(rs)rspqqpqrsrs0pqrsrs0rs1（2）证明：

设任何可能的结论为R,则：

((pq)q)(pq)(rs)*pqqpqrs*0pqrs*0*114.在自然系统p中构造下面推理的证明：

（1）前提：p(qr)，p，q

结论：rs

【MeiWei_81重点借鉴文档】

（2）前提：pq，(qr)，r

结论：p

（3）前提：pq

结论：p(pq)

（4）前提：pq，qs，st，tr

结论：pq

（5）前提：pr，qs，sttr

结论：rs

（6）前提：pr，qspq

结论：t(rs)

（1）证明

（1）

p(qr) 前提引入

（2）

p 前提引入

（3）（1）（2）假言推理

qr

（4）前提引入

（5） (3)(4)假言推理

（6）（5）附加

rs

（2）证明

(qr) （1）前提引入

（2）（1）置换

qr

（3）前提引入

（4）（2）（3）析取三段论

q

（5）

pq 前提引入

（6）（4）（5）拒取式

p

（3）证明

（1）

pq 前提引入

（2）（1）置换

pq

(pq)(pp) （3）（2）置换

p(qp) （4）（3）置换

（5）

p(pq) （4）置换

（4）证明

(st)(ts) 前提引入（1）

（2）（1）置换

ts

（3）（2）换件

tr

（4）前提引入

tr

（5）（4）化简

（6）（3）（5）假言推理

（7）前提引入

qs

(qs)(sq) （7）置换（8）

（9）（8）化简

sq

（10）

q （6）（9）假言推理

（11）

qp 前提引入

（12）

p （10）（11）假言推理

（13）

pq （10）（12）合取

（5）证明

（1）

pq 前提引入

【MeiWei_81重点借鉴文档】

（2）

p （1）化简

（3）（1）化简

（4）

pr 前提引入

（5）（2）（4）假言推理

（6）前提引入

qs

（7）（3）（6）假言推理

（8）（5）（7）合取

rs

（6）证明

（1）

pq 前提引入

（2）

p （1）化简

（3）（1）化简

（4）前提引入

pr

（5）（2）（4）析取三段论

（6）前提引入

qs

（7）（3）（6）析取三段论

（8）（5）（7）合取

rs

t(rs) （9）（8）附加

（10）

t(rs) （9）置换

15.在自然推里系统p中用附加前提法证明下面各推理：

（1）前提：p(qr)，sp，q

结论：sr

（2）前提：(pq)(rs)，(st)u

结论：pu

（1）证明

（1）附加前提引入

（2）前提引入

sp

（3）

p （1）（2）假言推理

（4）

p(qr) 前提引入

（5）（3）（4）假言推理

qr

（6）前提引入

（7）（5）（6）假言推理

（2）证明

（1）

p 附加前提引入

（2）

pq （1）附加

(pq)(rs) （3）前提引入

（4）（2）（3）假言推理

rs

（5）（4）化简

（6）（5）附加

st

(st)u （7）前提引入

（8）（6）（7）假言推理

16.在自然推理系统p中用归谬法证明下面推理：

（1）前提：pq，rqrs

结论：p

（2）前提：pq，pr，qs

结论：rs

（1）证明

（1）

p 结论否定引入

【MeiWei_81重点借鉴文档】

（2）

pq 前提引入

（3）（2）（1）假言推理

q

（4）前提引入

rq

（5）（3）（4）析取三段论

r

（6）前提引入

rs

（7）（6）化简

（8）（5）（7）合取

rr

（2）证明

(rs) （1）结论否定引入

（2） (1)置换

rs

（3）（2）化简

r

（4）（2）化简

s

（5）

pr 前提引入

（6）（3）（5）拒取式

p

（7）前提引入

qs

（8）（4）（7）拒取式

q

（9）（9）置换

pq

（10）

qp 前提引入

（11）

(pq)(pq) （10）（11）合取

17.在自然系统p中构造下面推理的证明：

只要A曾到过受害者房间并且11点前没离开，A就犯了谋杀罪。A曾到过受害者房间，

如果A在11点以前离开，看门人会看见他。看门人没有看见他，所以A犯了谋杀罪。

设

p:A到过受害者房间

q:A在11点前离开

r:A是谋杀嫌疑犯

s:看门人看见A

前提：(pq)r,p,qs,s

结论：r

证明

（1）

qs 前提引入

（2）

s 前提引入

（3）

q （2）（1）拒取式

（4）

p 前提引入

（5）

pq （3）（4）合取

（6）

(pq)r 前提引入

（7）

r （5）（6）假言推理

18.在自然系统p中构造下面各推理的证明：

(1)如果今天是星期六，我们就要去颐和园或圆明园玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。

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

(1)设

p:今天是星期六

q:我们到颐和园玩

r:我们到圆明园玩

s:颐和园游人太多

前提：p(qr),sq,p,s

【MeiWei_81重点借鉴文档】

结论：r

证明：

（1）

sq

（2）

（3）

q

（4）

（5）

p(qr)

（6）

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）假言推理

前提引入

（4）（5）假言推理

（3）（6）析取三段论

前提引入

（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)。

（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）条件时的命题的真值：

【MeiWei_81重点借鉴文档】

(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）乌鸦都是黑色的。

（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是汽车，2H(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。

解：各命题符号化如下：

（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)，

22【MeiWei_81重点借鉴文档】

【MeiWei_81重点借鉴文档】

（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)，其中z约束出现的，而x,y是自由出现的。

9.给定解释I如下：

（a）个体域DI为实数集合R.

（b）DI中特定元素a0

（c）特定函数f(x,y)xy,x,yDI

（d）特定谓词F(x,y):xy,G(x,y):xy,x,yDI.

说明下列公式在I下的含义，并指出各公式的真值：

(1).xy(G(x,y)F(x,y))

(2)xy(F(f(x,y),a)G(x,y))

(3)xy(G(x,y)F(f(x,y),a))

(4)xy(G(f(x,y),a)F(x,y))

解：

（1）xy((xy)(xy)),即对任意的实数x和y，若xy，则xy。

（2）xy((xy0)(xy)),即对任意的实数x和y，若xy0，则xy。

（3）xy((xy)(xy0)),即对任意的实数x和y，若xy，则xy0。

（4）xy((xy0)(xy)),即对任意的实数x和y，若xy0，则xy。

其中（1）（3）真值为1，（2）（4）真值为0。

10.给定解释I如下：

（a）个体域DN（N为自然数集合）

（b）D中特定元素a=2.

（c）D上函数f(x,y)xy,g(x,y)x*y.

（d）D上谓词F(x,y):xy.

说明下列各式在I的含义，并讨论其真值：

(1).xF(g(x,a),x)

【MeiWei_81重点借鉴文档】

(2)xy(F(f(x,a),y)F(f(y,a),x)).

(3)xyzF(f(x,y),z).

(4)xF(f(x,x),g(x,x)).

解：各式在I下的解释为：

（1）x(x2x)，即对任意的自然数x，有x2x；

（2）xy((x2y)(y2x))，即对任意的自然数x和y，如果有x2y，则有y2x。

（3）xyz(xyz)，即对任意的自然数x和y，存在z，使xyz；

（4）x(2xx2)，即存在的自然数x，使2xx。

其中（1）（2）真值为0，（3）（4）真值为1。

11.判断下列各式的类型：

(1).F(x,y)(G(x,y)F(x,y))

(2)x(F(x)F(x))y(G(y)G(y)).

(3)xyF(x,y)xyF(x,y).

(4)xyF(x,y)xyF(x,y).

(5)xy(F(x,y)F(y,z)).

(6)(xF(x)yG(y))yG(y).

解：

其中（1）（4）为永真式，（2）（6）为矛盾式，（3）（5）为可满足式，但不是永真式。

12.设I为一个任意的解释，在解释I下，下面哪些公式一定是命题？

(1).xF(x,y)yG(x,y).

(2)x(F(x)G(x))y(F(y)H(y))..

(3)x(yF(x,y)yG(x,y)).

(4)x(F(x)G(x)H(y))

（2）（3）一定是命题，因为他们是闭式。

13.给出下列各公式一个成真的解释，一个成假的解释。

(1).x(F(x)G(x))

(2)x(F(x)G(x)H(x))

(3)x(F(x)y(G(y)H(x,y)))

解：(1).令x是全体正整数。

成真的情况是：F(x)：x是偶数，G(x):x是奇数。

成假的情况是：F(x)：x是偶数，G(x):x是素数。

(2).令x是全体正整数，。

成真的情况是：F(x)：x能被2整除，G(x):x能被3整除，H(x):x能被5整除。则存在30能被，2，3，5整除。

成假的情况是：F(x)：x是偶数，G(x):x是素数，H(x):x能被5整除。不存在一个数既是偶数又是素数同时还能被5整除。

(1).令x是全体正整数，y是全体偶数。

成真的情况是：F(x)：x是奇数，G(y):y能被2整除，H(x,y):x比y大。则对任意偶数y，都存在一个大于y的奇数。

成假的情况是：F(x)：x是偶数，G(y):y能被2整除，H(x,y):x比y小。则对偶数2，不存在一个小于2的偶数。

14.证明下面的公式既不是永真式也不是矛盾式：

(1).x(F(x)y(G(y)H(x,y)))

(2)xy(F(x)G(y)H(x,y)))

2【MeiWei_81重点借鉴文档】

【MeiWei_81重点借鉴文档】

解：(1),成真的情况是：F(x)：x是正偶数，G(y):y是非1的正整数，H(x,y):x能被y整除且xy。则对任意一个正偶数x，都存在2，整除x。

矛盾的情况：F(x)：x是偶数，G(y):y是非1的正整数，H(x,y):x能被y整除且xy。则对任意一个正数x（比如3），不一定存在不等于x的整数，整除x。

(2).成真的情况：F(x)：x能被2整除，G(y):y能被3整除，H(x,y):x*y能被6整除.成假的情况是：F(x)：x能被2整除，G(y):y能被4整除，H(x,y):x*y能被6整除.

15.（1）给出一个非闭式的永真式。

（2）给出一个非闭式的永假式。

（3）给出一个非闭式的可满足式，但不是永真式。

解：

（1）(F(x)G(x))F(x)G(x)，它是重言式(AB)AB的代换实例。

（2）(F(x)F(x))，它是矛盾式(AA)的代换实例。

（3）x(F(x,y)F(y,x))

习题五

1. 设个体域D={a，b，c}，在D中消去公式x(F(x)yG(y))的量词。甲、乙用了不同的演算过程：

甲的演算过程如下:

x(F(x)yG(y))x(F(x)(G(a)G(b)G(c)))(F(a)(G(a)G(b)G(c)))(F(b)(G(a)G(b)G(c)))(F(c)(G(a)G(b)G(c)))(F(a)F(b)F(c))(G(a)G(b)G(c))乙的演算过程如下：

x(F(x)yG(y))

xF(x)yG(y)(F(a)F(b)F(c))(G(a)G(b)G(c))显然，乙的演算过程简单，试指出乙在推演过程中的关键步骤。

答：乙在演算中的关键步骤是，开始利用量词辖域收缩与扩张等值式，将量词的辖域缩小，从而简化了演算。

2. 设个体域D={a，b，c}，消去下列各式的量词：

（1）xy(F(x)G(y))

（2）xy(F(x)G(y))

（3）xF(x)yG(y)

（4）x(F(x,y)yG(y))

答：1)(F(a)F(b)F(c))(G(a)G(b)G(c))

2)(F(a)F(b)F(c))(G(a)G(b)G(c))

3)(F(a)F(b)F(c))(G(a)G(b)G(c))

4）(F(a,y)F(b,y)F(c,y))(G(a)G(b)G(c))

3．设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。

（1）x(F(x)G(x))

（2）x(F(x)G(x))

答：解释为I1：F（R），R是偶数，G（R）R是素数

解释为I2：F（R），R是奇数，G（R）R是素数

4．给定公式AxF(x)xF(x)

【MeiWei_81重点借鉴文档】

a) 在解释I1中，个体域D1={a}，证明公式A在I1下的真值为1。

b) 在解释I2中，个体域D2={a1，a2，…，an}，n2，A在I2下的真值还一定是1吗？为什么？

答：1.在I1下，xF(x)xF(x)F(a)F(a)F(a)F(a)1

在I2下，xF(x)xF(x)(F(a1)F(a2)....F(an))(F(a1)F(a2).....F(an))为可满足式，但不是永真式。设F（R）:R为奇数，此时蕴含式前件为真，后件为假，故蕴含式真值为0。若将F（R）改为令F（R），R为整数，则蕴含式的前件后件均为真，则真值为1。问题的关键是n2，n项的析取为真，只需要其中的一项为真，而不能保证所有的项为真。

5．给定解释I如下：

（a）个体域D={3，4}；

（b）

f(x)为f(3)4,f(x)3;

（c）

F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1

试求下列公式在I下的真值。

（1）xyF(x,y)

（2）xyF(x,y)

（3）xy(F(x,y)F(f(x),f(y)))

答：（1）

xyF(x,y)x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4))111(2).xyF(x,y)x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4))000(3).xy(F(x,y)F(f(x),f(y)))x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4))))(F(3,3)F(f(3),f(3)))(F(3,4)F(f(3),f(4)))(F(4,3)F(f(4),f(3)))(F(4,4)F(f(4),f(4)))(00)(11)(11)(00)111116．甲使用量词辖域收缩与扩张等值式进行如下演算：

x(F(x)G(x,y))xF(x)G(x,y)

乙说甲错了，乙说的对吗？为什么？

答：乙说的对，甲错了。本题中，全称量词的指导变元为R，辖域为F(x)G(x,y)，其中F(R)与G（R，R）中的R都是约束变元，因而不能将量词的辖域缩小。

7．请指出下面等值演算中的两处错误。

xy(F(x)(G(y)H(x,y)))xy(F(x)(G(y)H(x,y)))

xy((F(x)G(y))H(x,y))答：演算的第一步，应用量词否定等值式时丢掉了否定连接词“”，演算的第二步，在原错的基础上又用错了等值式即，(F(x)(G(y)H(x,y)))((F(x)G(y))H(x,y))

8.在一阶逻辑中将下面命题符号化，要求用两种不同的等值形式。

（1）没有小于负数的正数

（2）相等的两个角未必都是对顶角

答：

(1).x(F(x)G(x))x(G(x)F(x)),(1)

【MeiWei_81重点借鉴文档】

其中F(x):x小于负数，G(x):x是正数。

(2).

x(F(x)G(x)x(F(x)G(x)),

其中F(x):两个角相等，G(x):两个角是对顶角

9. 设个体域D为实数集合，命题“有的实数既是有理数，又是无理数”。这显然是个假命题。可是某人却说这是真命题，其理由如下：设F（R）：R是有理数，G（R）：R是无理数。xF(x)与xG(x)都是真命题，于是，xF(x)xG(x)x(F(x)G(x))，由于xF(x)xG(x)是真命题，故x(F(x)G(x))也是真命题，即有的实数是有理数，也是无理数，问此人的结论对吗？为什么？

答：不对，因为存在量词对于无分配率。

10. 在求前束范式时，有人说x(F(x)G(x,y))已是前束范式，理由是量词已在公式的前面。他说的对吗？为什么？

答：前束范式中，否定连联接词不能在量词前面出现。

11. 有人说无法求公式

因为公式中的两个量词的指导变元相同。x(F(x)G(x))xG(x,y)的前束范式，他的理由正确吗？为什么？

答：用换名规则可使两个指导规则不同。

12.求下列各式的前束范式：

(1)xF(x)yG(x,y)

(2)x(F(x,y)yG(x,y,z))

(3)xF(x,y)xG(x,y)

(4)x1(F(x1)G(x1,x2))(x2H(x2)x3L(x2,x3))

(5)x1F(x1,x2)(F(x1)x2G(x1,x2))

答：(1)xy(F(x)G(z,y))

(2)xt(F(x,y)G(x,t,z))

(3)x1x2x3x4((F(x1,y)G(x2,y))(G(x3,y)F(x4,y)))

(4)y1y2y3((F(y1)G(y1,x2))(H(y2)L(x2,y3)))

(5)y1y2(F(y1,x2)(F(x1)G(x1,y2)))

13.将下列命题符号化，要求符号化的公式全为前束范式：

(1)有的汽车比有的火车跑得快

(2)有的火车比所有汽车跑得快

(3)说所有的火车比所有的汽车跑得快是不对的

(4)说有的飞机比有的汽车慢也是不对的

答：(1)F(R):R是汽车，G(R):R是火车，H(R,R):R比R跑得快

xy(F(x)G(y)H(x,y))

(2))F(R):R是火车，G(R):R是汽车，H(R,R):R比R跑得快

xy(F(x)(G(y)H(x,y)))

(3)F(R):R是火车，G(R):R是汽车，H(R,R):R比R跑得快

xy(F(x)G(y)H(x,y))

(4)F(R):R是飞机，G(R):R是汽车，H(R,R):R比R慢

xy(F(x)G(y)H(x,y))、

14.在自然推理系统F中，指出下面各证明序列中的错误：

1F(x)xG(x)前提引入 (1)○【MeiWei_81重点借鉴文档】

【MeiWei_81重点借鉴文档】

2F(c)G(c)○1EI规则 ○1xF(x)yG(y)前提引入 (2)○2F(a)F(b)○1EI规则 ○1F(y)G(y)前提引入 (3)○2x(F(x)G(x))○1EG规则 ○1F(a)G(b)前提引入 (4)○2x(F(x)G(x))○1EG规则 ○1F(c)G(c)前提引入 (5)○2x(F(x)G(x))○1UG规则 ○答：(1)对F(x)xG(x)不能使用EI规则。它不是前束范式，化为前束范式得

F(x)xG(x)x(F(y)G(x))，因为量词辖域(F(y)G(x))中，除了R外还有自由出现的R，所以不能使用EI规则。

(2)对F(c)G(c)也应先化成前束范式才能消去量词，其前束范式为xy(F(x)G(y))，要消去量词，既要使用UI规则又要使用EI规则。

A(c)(3)在自然推理系统F中，EG规则为，其中c为特定的个体常项，这里xA(x)A(y)F(y)G(y)不满足要求。

(4)这里使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如F(R):R为奇数，G(R):R为偶数，显然F(3)G(4)为真，但不存在使F(x)G(x)为真的个体。

(5)这里c为个体常项，不能对x(H(x)F(x)引入全称量词。

15.在自然推理系统F中，构造下面推理的证明：

(1)前提：xF(x)y((F(y)G(y))R(y)),xF(x)

结论：xR(x)

(2)前提：x(F(x)(G(a)R(x))),xF(x)

结论：x(F(x)R(x))

(3)前提：x(F(x)G(x)),xG(x)

结论：xF(x)

(4)前提：x(F(x)G(x)),x(G(x)R(x)),xR(x)

结论：xF(x)

1xF(x)前提引入证明：(1)○2xF(x)y((F(y)G(y))R(y))前提引入 ○3y((F(y)G(y))R(y))○1○2假言推理 ○4F(c)○1EI ○5(F(c)G(c))R(c)○3UI ○6F(c)G(c)○4附加 ○7R(c)○5○6假言推理 ○8xR(x)○7EG ○1xF(x)前提引入 (2)○【MeiWei_81重点借鉴文档】

【MeiWei_81重点借鉴文档】

2x(F(x)(G(a)R(x)))前提引入 ○3F(c)○1EI ○4F(c)(G(a)R(c))○2UI ○5G(a)R(c)○3○4假言推理 ○6R(c)○5化简 ○7F(c)R(c)○3○6合取 ○8x(F(x)R(x))○7EG ○1xF(x)前提引入 (3)○2xF(x)○1置换 ○3F(c)○2UI ○4x(F(x)G(x))前提引入 ○5F(c)G(c)○4UI ○6F(c)○3○5析取三段论 ○7xF(x)○6EG ○1x(F(x)G(x))前提引入 (4)○2F(y)G(y)○1UI ○3x(G(x)R(x))前提引入 ○4G(y)R(y)○3UI ○5xR(x)前提引入 ○6R(R)○5UI ○7G(y)○4○6析取三段论 ○8F(R)○2○7析取三段论 ○9xF(x)○8UG ○16.找一个解释I,在I下，使得xF(x)xG(x)为真，而使得x(F(x)G(x))为假，从而说明xF(x)xG(x)x(F(x)G(x))。

答：取个体域为自然数集合N，F(R):R为奇数，G(R):R为偶数，则在以上解释下，xF(x)xG(x)为真而x(F(x)G(x))为假。

17.给定推理如下：前提：x(F(x)G(x)),x(H(x)G(x))；结论：x(H(x)F(x))。有些人证明如下：

1xH(x)附加前提引入 ○2H(R)○1UI ○3x(H(x)G(x))前提引入 ○4H(y)G(y)○3UI ○5G(R)○2○5假言推理 ○6x(F(x)G(x))前提引入 ○7F(y)G(y)○6UI ○8F(y)○5○7拒取式 ○9xF(x)○8UG ○并且说由附加前提证明法可知，推理正确，请指出以上证明的错误。

答：由第16题可知，本题不能用附加前提证明法。

18.给出上题的正确推理证明。

【MeiWei_81重点借鉴文档】

1x(F(x)G(x))前提引入证明：○2x(H(x)G(x))前提引入 ○3F(y)G(y)○1UI ○4H(y)G(y)○2UI ○5G(y)F(y)○3置换 ○6H(y)F(y)○4○5假言三段论 ○7x(H(x)F(x)○6UG

○19在自然推理系统F中，构造下面的推理证明;

前提：xF(x)xG(x)

结论：x(F(x)G(x))

证明：1xF(x)xG(x)

2F(c)yG(y)

3x(F(x)G(x))

20在自然推理系统F中，构造下面的推理证明;

(1)前提：x(F(x)G(x))

结论：xF(x)xG(x)

证明：1x(F(x)G(x))

2F(x)G(x)

3xF(x)附加前提

4xG(x)

（2）前提：x(F(x)G(x))

结论：xF(x)xG(x)

证明：1x(F(x)G(x))

2F(x)G(x)

3xF(x)附加前提

4xF(x)

5F(c)

6G(c)

7xG(x)

21在自然推理系统F中，构造下面推理的证明：

没有白色的乌鸦，北京鸭都是白色的，因此北京鸭不是乌鸦。

答：设F(x)：R是白色的

G(x)：R是乌鸦

H(x)：R是北京鸭

前提：x(G(x)F(x))

x(H(x)F(x))

结论：x(H(x)G(x))

证明：1x(G(x)F(x))

2G(x)F(x)

3F(x)G(x)

4x(H(x)F(x))

5H(x)F(x)

6H(x)G(x)

【MeiWei_81重点借鉴文档】

7x(H(x)G(x))

22在自然推理系统F中，构造下面推理的证明：

(1)偶数都能被2整除。6是偶数，所以6能被2整除。

答：设F(x)：R是偶数

G(x)：R能被2整除

前提：x(F(x)G(x))

F(6)

结论：G(6)

证明：1x(F(x)G(x))

2F(6)G(6)

3F(6)

4G(6)

（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。

答：设F(x)：R是大学生

G(x)：R是勤奋的

C：王晓山

前提：x(F(x)G(x))

G(c)

结论：F(c)

证明：1x(F(x)G(x))

2F(c)G(c)

3G(c)F(c)

4G(c)

5F(c)

23在自然推理系统F中，构造下面推理的证明：

（1）每个有理数都是实数。有的有理数是整数。因此有的实数是整数。

答：设F(x)：R是有理数

G(x)：R是实数

H(x)：R是整数

前提：x(F(x)G(x))

x(F(x)H(x))

结论：x(G(x)H(x))

证明：1x(F(x)H(x))

2F(c)H(c)

3x(F(x)G(x))

4F(c)G(c)

5G(c)

6G(c)H(c)

7x(G(x)H(x))

（2）有理数，无理数都是实数。虚数不是实数，因此虚数既不是有理数也不是无理数。

答：设F(x)：R是有理数

G(x)：R是实数

H(x)：R是无理数数

P(x)：R是虚数

前提：x(F(x)G(x))

【MeiWei_81重点借鉴文档】

x(H(x)G(x))

x(P(x)G(x))

结论：x(P(x)(F(x)H(x))

证明：1x(F(x)G(x))

2F(x)G(x)

3G(x)F(x)

4x(H(x)G(x))

5H(x)G(x)

6G(x)H(x)

7P(x)(F(x)H(x))

8x(P(x)(F(x)H(x))

24在自然推理系统F中，构造下面推理的证明：

每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢喜欢乘自行车。有的人不喜欢乘汽车，所以有的人不喜欢步行。

答：设G(x)：R喜欢步行

H(x)：R喜欢骑自行车

P(x)：R喜欢乘汽车

前提：x(G(x)H(x))

x(H(x)P(x))

xP(x)

结论：xG(x)

证明：1xP(x)

2P(c)

3x(H(x)P(x))

4H(c)P(c)

5H(c)

6x(G(x)H(x))

7G(c)H(c)

8H(c)G(c)

9G(c)

25在自然推理系统F中，构造下面推理的证明（个体域为人类集合）

每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的，所以王大海在他的事业中将获得成功。

答：设F(x)：R是科学工作者

G(x)：R是刻苦学习的

H(x)：R是聪明的

P(x)：R将在他的事业中获得成功

C：王大海

前提：x(F(x)G(x))，F(c)H(c)

x(G(x)H(x)P(x))

结论：P(c)

证明：1x(F(x)G(x))前提

2F(c)G(c)

3F(c)前提

4G(c)

【MeiWei_81重点借鉴文档】

5H(c)前提

6H(c)G(c)

7x(G(x)H(x)P(x))

8G(c)H(c)P(c)

9P(c)

【MeiWei_81重点借鉴文档】

更多推荐

推理,命题,公式,符号化,下列,等值

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

发布评论取消回复

最近发表

热门文章

标签列表

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

相关文章

发布评论取消回复

最近发表

热门文章

标签列表