本文格式為Word版，下載可任意編輯——離散數學課后習題合集

第一章命題演算基礎

1.1判斷以下語句是否為命題，若是請翻譯為符號公式；若不是說明由。

（1）請給我一支筆！（2）火星上有生物。（3）X?Y?8

（4）只有努力工作，方能把事情做好。

（5）假使嫦娥是虛構的，而圣誕老人也是虛構的，那么大量孩子受騙了。解

（1）不為命題，由于它不是陳述句。

（2）是命題，用命題變元P表示該命題。

（3）不為命題，雖為陳述句，但不能判斷其真假性。

（4）是命題。設P表示努力工作，則原句翻譯為命題公式Q?P。Q表示把事情做好，（5）是命題。設P表示嫦娥是虛構的，Q表示圣誕老人也是虛構的，R表示大量孩子受騙了，則原句翻譯為(P?Q)?R。1.2試判定以下公式的永真性和可滿足性。

（1）(P?Q)?(?P??(Q??R))解

（1）當P?T時，

原式=(T?Q)?(?T??(Q??R))=Q?(F??(Q??R))

=Q?F=?Q

當Q=T時，上式=F；當Q?F時，上式=T，因此公式存在成真解釋

(P,Q,R)?(T,F,?)，存在成假解釋(P,Q,R)?(T,T,?)，故公式可滿足，但非永真。

（2）?(P?Q)?((Q??R)??P)解

當P?T時

原式=?(T?Q)?((Q??R)??T)

1

=?Q?((Q??R)?F)

=?Q?((Q??R)當Q=T時

上式=?T?(T??R)=F??R=F

當Q=F時

上式=?F?(F??R)=T???R=??R=R

當R?T時，上式=T，因此公式存在成真解釋(P,Q,R)?(T,F,T)，存在成假解釋

(P,Q,R)?(T,T,?)，故公式可滿足，但非永真。

（3）(??P?Q)?((Q??R)?P)解

當P?T時

原式=(??T?Q)?((Q??R)?T)=(T?Q)?(Q??R)=(Q?(Q??R)當Q?T時

上式=(T?(T??R)

=?R

當R?T時，上式=F，當R?F時，上式=T，因此，公式存在成真解釋

(P,Q,R)?(T,T,F)，存在成假解釋(P,Q,R)?(T,T,T)，故公式可滿足，但非永真。

（4）(??P?Q)?((Q?R)??P)解

當P?T時

原式=(??T?Q)?((Q?R)??T)

2

=(T?Q)?((Q?R)?F)=Q??(Q?R)=Q?(?Q??R)當Q?T時

上式=T?(?T??R)

=F??R=?R

當R?T時，上式=F，當R?F時，上式=T，因此，公式存在成真解釋

(P,Q,R)?(T,T,F)，存在成假解釋(P,Q,R)?(T,T,T)，故公式可滿足，但非永真。

1.3試求以下公式的成真解釋和成假解釋

（1）?((P?Q)?R)?(Q?R)解

（1）當Q?T時

原式=?((P?T)?R)?(T?R)=?(T?R)?T

=?R

當R?T時，上式=F，當R?F時，上式=T。

當Q?F時

原式=?((P?F)?R)?(F?R)=?(?P?R)?R當R?T時

上式=?(?P?T)?T=?T?T=F當R?F時

上式=?(?P?F)?F

=?P?F=P

當P?T時，上式=T，當P?F時，上式=F，

3

因此，公式的成真解釋為(P,Q,R)?(T,F,F),(?,T,F)；成假解釋為

(P,Q,R)?(F,F,F),(?,T,T),(?,F,T)。

（2）?(P?Q)?((Q?R)?P)解

當P?T時

原式=?(T?Q)?((Q?R)?T)=?(T?Q)?T=?Q?T=?Q

當Q?T時，上式=F；當Q?F時，上式=T。

當P?F時

原式=?(F?Q)?((Q?R)?F)=?T?(Q?R)=F?(Q?R)=F

因此，公式的成真解釋為(P,Q,R)?(T,F,?)(P,Q,R)?(T,T,?),(F,?,?)。

（3）(??P?Q)?((Q?R)??P)解

當P?T時

原式=(??T?Q)?((Q?R)??T)=Q?((Q?R)?F)=Q??(Q?R)當Q?T時

上式=T??(T?R)

成假解釋為

4

；

=?(T?R)

=?R

當R?T時，上式=F；當R?F時，上式=T。當Q?F時

上式=F??(F?R)=T當P?F時

原式=(??F?Q)?((Q?R)??F)=(F?Q)?((Q?R)?T)=F?(Q?R)=T

因此，公式的成真解釋為(P,Q,R)?(T,T,F),(T,F,?),(F,?,?)；(P,Q,R)?(T,T,T)。

（4）(??P??Q)?(Q?(?R?P))解

當P?T時

原式=(??T??Q)?(Q?(?R?T))=(T??Q)?(Q??R)=?Q?(Q??R)當Q?T時

上式=?T?(T??R)=F?T=F當Q?F時

上式=?F?(F??R)

=T??R=?R

當R?T時，上式=F；當R?F時，上式=T。

成假解釋為

5

當P?F時

原式=(??F??Q)?(Q?(?R?F))=(F??Q)?(Q?F)=T?(Q?F)=Q

當Q?T時，上式=T；當Q?F時，上式=F。

因此，公式的成真解釋為(P,Q,R)?(T,F,F),(F,T,?)；(P,Q,R)?(T,T,?),(T,F,T),(F,F,?)。

1.4試寫出以下公式的對偶式和內否式

（1）(?P?Q)?((Q??R)?P)（2）(P??Q)?((Q?R)??P)（3）?(P?Q)?((Q??R)??P)（4）(?P?Q)?((Q??R)??P)解

（1）內否式為(P??Q)?((?Q?R)??P)消去“?〞得式子?(?P?Q)?((Q??R)?P)對偶式=?(?P?Q)?((Q??R)?P)

（2）內否式為(?P?Q)?((?Q??R)?P)消去“?〞得式子(?P??Q)?((Q?R)??P)對偶式為(?P??Q)?((Q?R)??P)

（3）內否式為?(?P??Q)?((?Q?R)?P)

消去“?〞得式子?(?P?Q)?(((?Q??R)?(Q?R))??P)對偶式為?(?P?Q)?(((?Q??R)?(Q?R))??P)

（4）內否式為(P??Q)?((?Q?R)?P)

成假解釋為

6

消去“?〞得式子(P?Q)?((?Q??R)??P)對偶式為(P?Q)?((?Q??R)??P)1.5試證明聯(lián)結詞集合{?,?}是完備的。

證明

由于，P?Q??P?QP?Q??(P??Q)

所以，聯(lián)結詞集合??,??可以表示集合??,?,??。

又由于，聯(lián)結詞集合??,?,??是完備的，即??,?,??可以表示任何一個命題演算公式，所以??,??可以表示任何一個命題演算公式，故聯(lián)結詞集合??,??是完備的。1.6試證明聯(lián)結詞集合???,???不是完備的。

證明設集合

???是完備的，則由聯(lián)結詞集合的完備性定義知

?P?f(P,Q,R,?)?P?Q?R??。當P,Q,R,?全取為真時，上式左邊=F，右邊

=T，矛盾。

因此???不是完備的。

設集合???是完備的，則由聯(lián)結詞集合的完備性定義知?P?f(P,Q,R,?)，其中f表示“?〞。當P,Q,R,?全取為真時，上式左邊=F，右邊=T，矛盾。因此???不是完備的。

1.7試求以下公式的析取范式和合取范式

（1）(?P?Q)?(P??Q)解

原式=?(?P?Q)?((P??Q)?(?P???Q))=(P??Q)?(P??Q)?(?P?Q)=(P??Q)?(?P?Q)（析取范式）=((P??Q)??P)?((P??Q)?Q)

7

=(P??P)?(?P??Q)?(P?Q)?(?Q?Q)=(?P??Q)?(P?Q)（合取范式）

（2）(P?(Q??R))?(R?(Q?P))解

原式=?(?P?(?Q??R))?(?R?(?Q?P))=(P?Q?R)?(P??Q??R)

=(P?P??Q??R)?(Q?P??Q??R)?(R?P??Q??R)=P??Q??R（合取范式和析取范式）

（3）?(P?Q)?((Q??R)??P)解

原式=?(?P?Q)?((?Q??R)??P)=P??Q?(?P??Q??R)（合取范式）=(P??Q)?(?P??Q??R)

=((P??Q)??P)?((P??Q)??Q)?((P??Q)??R)=(P??Q)?(P??Q??R)（析取范式）

（4）(P?Q)?(?P??(Q??R))解

原式=?(P?Q)?(?P??(?Q??R))=(?P?Q)?(?P?Q?R)

=(?P?Q)?(P??Q)?(?P?Q?R)（析取范式）=((?P?Q)?(P??Q))?(?P?Q?R)

=((?P?Q)?P)?((?P?Q)??Q))?(?P?Q?R)

=((?P?P)?(P?Q)?(?P??Q)?(Q??Q))?(?P?Q?R)=((P?Q)?(?P??Q))?(?P?Q?R)

8

=((P?Q)?(?P?Q?R))?((?P??Q)?(?P?Q?R))=(P?Q??P)?(P?Q?Q)?(P?Q?R)?(?P??Q??P)?(?P??Q?Q)?(?P??Q?R)

=(P?Q)?(P?Q?R)?(?P??Q)?(?P??Q?R)（合取范式）1.8試求以下公式的主析取范式和主合取范式

（1）(?P?R)?(?P?(?Q?R))解

原式=?(??P?R)?((?P?(?Q?R))?(P??(?Q?R)))=(?P??R)?(?P??Q?R)?(P?(Q??R))=(?P??R)?(?P??Q?R)?(P?Q)?(P??R)

=((?P??R)?(Q??Q))?(?P??Q?R)?((P?Q)?(R??R))?((P??R)?(Q??Q))

=(?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)?(P?Q??R)?(P??Q??R)=?(0,1,2,4,6,7)=

?(3,5)

=(P??Q??R)?(?P?Q??R)

（2）(??P?Q)?((Q?R)??P)解

原式=?(??P?Q)?((?Q?R)??P)

=(?P??Q)?((?Q?R)??P)?(?(?Q?R)?P)=(?P??Q)?(?P??Q)?(?P?R)?(P?Q??R)

9

=(?P?(Q??Q)?(R??R))?(?Q?(P??P)?(R??R))?((?P??Q)?(R??R))?((?P?R)?(Q??Q))?(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)?(?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)=?(0,1,2,3,4,5,6)=

?(7)

=?P??Q??R

（3）(P??Q)?R解

原式=?P??Q?R=?(6)

=

?(0,1,2,3,4,5,7)

=(?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(?P?Q?R)?(P??Q??R)?(P??Q?R)?(P?Q?R)

（4）P?(P?(Q?P))解

原式=?P?(P?(?Q?P))=(?P?P)?(?P??Q?P)=T?T=T

10

=?(?)=

?(0,1,2,3)

=(?P??Q)?(?P?Q)?(P??Q)?(P?Q)1.9用把公式化為主范式的方法判斷以下各題中兩式是否等價

（1）(P?Q)?(P?Q),(?P?Q)?(Q?P)解

（1）(P?Q)?(P?Q)

=?(?P?Q)?(P?Q)

=(P??Q)?(P?Q)=

?(2,3)

(?P?Q)?(Q?P)

=(?P?Q)?(?Q?P)

=(?P?Q??Q)?(?P?Q?P)=F?F=F=

?(?)

由此可見兩公式的主析取范式不相等，因此，兩公式不等價。（2）(P?R)?(Q?R),(P?Q)?R解

(P?R)?(Q?R)

=(?P?R)?(?Q?R)

=((?P?R)?(Q??Q))?((?Q?R)?(P??P))

=(?P?Q?R)?(?P??Q?R)?(P??Q?R)?(?P??Q?R)=(P??Q?R)?(?P?Q?R)?(?P??Q?R)=

?(2,4,6)

11

(P?Q)?R

=?(P?Q)?R=(?P??Q)?R=(?P?R)?(?Q?R)

=((?P?R)?(Q??Q))?((?Q?R)?(P??P))

=(?P?Q?R)?(?P??Q?R)?(P??Q?R)?(?P??Q?R)=(P??Q?R)?(?P?Q?R)?(?P??Q?R)=

?(2,4,6)

由此可見兩公式的主合取范式相等，因此，兩公式等價。12

其次章命題演算的推理理論

2.1用永真公理系統(tǒng)證明以下公式

（1）P?(P?P)

證明

（1）P?P公理1（2）(P?R)?((Q?R)?((P?Q)?R))公理13（3）(P?P)?((P?P)?((P?P)?P))Q,R用P代入（4）（3）（1）(P?P)?((P?P)?P)分（5）（4）（1）(P?P)?P分（6）P?(P?Q)公理11（7）P?(P?P)Q用P代入（8）(P?Q)?((Q?P)?(P?Q))公理7（9）(P?(P?P))?(((P?P)?P)?(P?(P?P)))Q用P?P代入（10）((P?P)?P)?(P?(P?P))分（9）（7）（11）P?(P?P)分（10）（5）（2）(?P?Q)?(?Q?P)證明

（1）(P??Q)?(Q??P)公理14（2）(?P???Q)?(?Q???P)P用?P代入，Q用?Q代入（3）??P?P公理15（4）(P?Q)?((R?P)?(R?Q))定理（5）(??P?P)?((?Q???P)?(?Q?P))

P用??P代入，Q用P代入，R用?Q代入

13

（6）(?Q???P)?(?Q?P)分（5）（3）（7）(P?Q)?((Q?R)?(P?R))公理3（8）((?P???Q)?(?Q???P))?(((?Q???P)?(?Q?P))?((?P???Q)?(?Q?P)))

P用?P???Q代入，Q用?Q???P代入，R用?Q?P代入

（9）（8）（2）((?Q???P)?(?Q?P))?((?P???Q)?(?Q?P))分（10）(?P???Q)?(?Q?P)分（9）（6）（11）Q???Q定理（12）(Q???Q)?((?P?Q)?(?P???Q))

（4）式中P用Q代入，Q用??Q代入，R用?P代入

（13）（12）（11）(?P?Q)?(?P???Q)分（14）((?P?Q)?(?P???Q))?(((?P???Q)?(?Q?P))?((?P?Q)?(?Q?P)))

（7）式中P用?P?Q代入，Q用?P???Q代入，R用?Q?P代入

((?P???Q)?(?Q?P))?((?P?Q)?(?Q?P))分（15）（14）（13）(?P?Q)?(?Q?P)分（16）（15）（10）

（3）P??P證明

P?(P?Q)公理11（1）

（2）P?(P??P)Q用?P代入（3）(P?Q)?(?Q??P)定理

(P?(P??P))?(?(P??P)??P)Q用P??P代入（4）

（5）?(P??P)??P分（4）（3）

14

（6）Q?(P?Q)公理12（7）?P?(P??P)Q用?P代入（8）(P?Q)?((Q?R)?(P?R))公理3（9）(?(P??P)??P)?((?P?(P??P))?(?(P??P)?(P??P)))

P用?(P??P)代入，Q用?P代入，R用P??P代入

（10）(?P?(P??P))?(?(P??P)?(P??P))分（9）（5）（11）（10）（7）?(P??P)?(P??P)分（12）(?P?P)?P定理（13）(?(P??P)?(P??P))?(P??P)P用P??P代入（14）（13）（11）P??P分（4）((P?Q)??R)?((P???Q)??R)

證明

（1）??P?P公理1（2）??Q?QP用Q代入（3）(P?Q)?((R?P)?(R?Q))定理（4）(??Q?Q)?((P???Q)?(P?Q))P用??Q代入，R用P代入（5）(P???Q)?(P?Q)分（4）（2）（6）(P?Q)?((Q?R)?(P?R))公理3（7）((P???Q)?(P?Q))?(((P?Q)??R)?((P???Q)??R))

P用P???Q代入，Q用P?Q，R用?R代入

（8）((P?Q)??R)?((P???Q)??R)分（7）（5）2.2已知公理：A:P?(Q?P)

B:(Q?R)?((P?Q)?(P?R))C:(P?P)?P

15

D:Q?(P?Q)E:(P?Q)?(Q?P)及分開規(guī)則和代入規(guī)則。

試證明（1）P?P為定理

（2）(P?P)?(R??R)為定理。證明

（1）(P?P)?P公理C（2）Q?(P?Q)公理D（3）P?(P?P)Q用P代入（4）(Q?R)?((P?Q)?(P?R))公理B（5）((P?P)?P)?((P?(P?P))?(P?P))Q用P?P代入，R用P代入（6）（5）（1）(P?(P?P))?(P?P)分（7）P?P分（6）（3）（8）(P?P)?((R??R)?(P?P))

（2）式中Q用P?P代入，P用R??R代入

(R??R)?(P?P)分（9）（8）（7）

（10）(P?Q)?(Q?P)公理E（11）((R??R)?(P?P))?((P?P)?(R??R))

P用R??R代入，Q用P?P代入

（12）(P?P)?(R??R)分（11）（9）2.3用假設推理系統(tǒng)證明以下公式

（1）(P?Q)?((P??Q)??P)證明

P?Q假設（1）

（2）P??Q假設

16

（3）??P后件的否定（4）??P?P公理15（5）P分（4）（3）（6）（1）（5）Q分（7）?Q分（2）（5）（6）（7）矛盾

由反證法推理定理知

P?Q，P??Q├?P

由推理定理知

(P?Q)?((P??Q)??P)

（2）(P?(Q?R))?((P?Q)?(P?R))證明

（1）P?(Q?R)（2）P?Q（3）P（4）Q?R（5）Q（6）R由假設推理過程的定義知

P?(Q?R)，P?Q，P├R

由推理定理知

(P?(Q?R))?((P?Q)?(P?R))

（3）((P?Q)?R))?(P?(Q?R))證明

（1）(P?Q)?R（2）P（3）Q（4）P?(Q?(P?Q))（5）Q?(P?Q)假設假設假設分（1）（3）分（2）（3）分（4）（5）假設

假設假設公理10分（4）（2）

17

（6）P?Q分（5）（3）（7）R分（1）（6）由假設推理過程的定義知

(P?Q)?R)，P，Q├R

由推理定理知

((P?Q)?R))?(P?(Q?R))

（4）((P?Q)?((P?R)?(Q?S)))?(S?R)證明

（1）(P?Q)?((P?R)?(Q?S))假設（2）(P?Q)?P公理8（3）(P?Q)?Q公理9（4）((P?Q)?((P?R)?(Q?S)))?(P?Q)

（2）式中P用P?Q代入，Q用(P?R)?(Q?S)代入

（5）((P?Q)?((P?R)?(Q?S)))?((P?R)?(Q?S))

（3）式中P用P?Q代入，Q用(P?R)?(Q?S)代入

（6）P?Q分（4）（1）

(P?R)?(Q?S)分（7）（5）（1）

（8）P分（2）（6）（9）（3）（6）Q分（10）((P?R)?(Q?S))?(P?R)（2）式中P用P?R，Q用Q?S代入（11）((P?R)?(Q?S))?(Q?S)（3）式中P用P?R，Q用Q?S代入（12）P?R分（10）（7）（13）Q?S分（11）（7）（14）R分（12）（8）（15）S分（13）（9）（16）P?(Q?(P?Q))公理10

18

（17）R?(S?(R?S))P用R，Q用S代入（18）S?(R?S)分（17）（14）（19）（18）（15）R?S分由假設推理過程的定義知

(P?Q)?((P?R)?(Q?S))├R?S

由推理定理知

((P?Q)?((P?R)?(Q?S)))?(S?R)

2.4用歸結原理證明以下公式

（1）((P?Q)?((P?R)?(Q?S)))?(S?R)證明

化為合取范式：

((P?Q)?((P?R)?(Q?S)))??(S?R)

=((P?Q)?((?P?R)?(?Q?S)))?(?S??R)=P?Q?(?P?R)?(?Q?S)?(?S??R)建立子句集（1）P（2）Q

（3）?P?R（4）?Q?S

（5）?S??R

（6）R（7）?S（8）?Q（9）?（2）(P?Q)?((P??Q)??P)證明

化為合取范式：

(P?Q)??((P??Q)??P)=(?P?Q)??(?(?P??Q)??P)=(?P?Q)?(?P??Q)???P)

1）（3）歸結5）（6）歸結4）（7）歸結2）（8）歸結19

（（（（

建立子句集：（1）?P?Q（2）?P??Q（3）??P

（4）Q（1）（3）歸結（5）?Q（2）（3）歸結（6）?（3）?(P??Q)?(?Q?R)??R??P證明

化為合取范式：

?(P??Q)?(?Q?R)??R???P=(?P?Q)?(?Q?R)??R???P建立子句集：（1）?P?Q（2）?Q?R

（3）?R（4）??P

（5）Q（6）?Q（7）?（4）?P?P證明

化為合取范式：?(?P?P)=P??P

化為子句集：（1）P（2）?P

（3）?4）（5）歸結

1）（4）歸結2）（3）歸結5）（6）歸結1）（2）歸結

20

（（（（（

第三章謂詞演算基礎

3.1試把以下語句符號化

（1）假使我知道你不在家，我就不去找你了。

解

設A(e1,e2)表示e1知道e2不在家；

B(e1,e2)表示e1去找e2；a表示我；b表示你；

則原句表示為：

A(a,b)??B(a,b)。

（2）他送給我這只大的紅氣球。

解

設A(e1,e2,e3)表示e1送給e2e3；

B(e)表示e為大的；C(e)表示e為紅的；D(e)表示e為氣球；

a表示他，b表示我，c表示這只；則原句譯為：

A(a,b,c)?B(c)?C(c)?D(c)。

（3）蘇州位于南京與上海之間。

解

設A(e1,e2,e3)表示e1位于e2與e3之間；

a表示蘇州，b表示南京，c表示上海；則原句表示為：

A(a,b,c)。

（4）他既熟悉C++語言，又熟悉PASCAL語言。

解

設A(e1,e2)表示e1熟悉e2；

a表示他，b表示C++語言，c表示PASCAL語言；則原句譯為：

21

A(a,b)?A(a,c)。

3.2試將以下語句符號化為含有量詞的謂詞演算公式：（1）沒有不犯錯誤的人。

解

設P(e)表示e為人；

M(e)表示e為錯誤；A(e1,e2)表示e1犯e2。

則原句譯為：

??x(P(x)??y(M(y)?A(x,y)))。

（2）有不是奇數的質數。

解

設O(e)表示e為奇數；

P(e)表示e為質數。

則原句譯為：

?x(?O(x)?P(x))。

（3）盡管有人能干，但未必一切人能干。

解

設P(e)表示e為人；

A(e)表示e能干。

則原句譯為：

?x(P(x)?A(x))???x(P(x)?A(x))。

（4）魚我所欲，熊掌亦我所欲。

解

設F(e)表示e為魚；

B(e)表示e為熊掌；W(e1,e2)表示e1所欲e2。a表示我；

則原句表示為：

?x(F(x)?W(a,x))??x(B(x)?W(a,x))。22

（5）人不犯我，我不犯人；人若犯我，我必犯人。

解

設P(e)表示e為人；

C(e1,e2)表示e1犯e2。a表示我；

則原句譯為：

?x((P(x)??C(x,a))??C(a,x))??x((P(x)?C(x,a))?C(a,x))。

（6）有一種液體可熔化任何金屬。

解

設L(e)表示e為液體；M(e)表示e為金屬；

C(e1,e2)表示e1熔化e2。

則原句可譯為：

?x(L(x)??y(M(y)?C(x,y)))。

（7）并非“人為財死，鳥為食亡〞。

解設P(e)表示e為人；

A(e)表示e為財；B(e)表示e為鳥；F(e)表示e為食；C(e1,e2)表示e1為e2死；D(e1,e2)表示e1為e2亡。

則原句譯為：

?(?x?y((P(x)?A(y))?C(x,y))??x?y((P(x)?F(y))?D(x,y)))

（8）若要人不知，除非己莫為。

解設P(e)表示e為人；

A(e)表示e為某一事情；

23

B(e1,e2)表示e1做了e2；

C(e1,e2,e3)表示e1知道e2做了e3。

則原句譯為：

?x?y((P(x)?A(y)?B(x,y))??z(P(z)?C(z,x,y)))

（9）任何一數均有一數比它大。

解設A(e)表示e為數；

B(e1,e2)表示e1比e2大；

則原句譯為：

?x(A(x)??y(A(y)?B(y,x)))

（10）每個作家均寫過作品。

解設A(e)表示e為作家；

N(e)表示e為作品；W(e1,e2)表示e1寫了e2。

則原句譯為：

?x(A(x)??y(N(y)?W(x,y)))

（11）有些作家沒寫過小說。

解設A(e)表示e為作家；

N(e)表示e為小說；W(e1,e2)表示e1寫了e2。

則原句譯為：

?x(A(x)??y(N(y)??W(x,y)))

（12）天下烏鴉一般黑。

解設A(e)表示e為烏鴉；

B(e1,e2)表示e1與e2一樣黑。

24

則原句譯為：

?x?y((A(x)?A(y))?B(x,y))

3.3令P(e)表示“e為質數〞；

E(e)表示“e為偶數〞；O(e)表示“e為奇數〞

；D(e1,e2)表示“e1除盡e2〞。

試把以下語句翻譯為日常語句：

（1）E(2)?P(2)解

2為偶數且2為質數。（2）?x(D(2,x)?E(x))解

任何能被2除盡的數均為偶數。（3）?x(?E(x)??D(2,x))

解

任何不是偶數的數均不能被2除盡。（4）?x(E(x)??y(D(x,y)?E(y)))

解

任何一個數，若能被任何偶數除盡，則該數一定是偶數。（5）?x(E(x)?P(x))

解

有是偶數的質數。

3.4指出以下公式的約束關系、自由變元和約束變元：

（1）?x(A(x,y)??y(B(x,y)?C(z)))解

A(x,y)中的x和B(x,y)中的x受?x約束；B(x,y)中的y受?y約束；

A(x,y)中的x為約束變元，B(x,y)中的x和y為約束變元；A(x,y)中的y和C(z)中的z為自由變元。

25

（2）?x(A(x)?B(x,t))??y(A(y)?B(x,y))解

A(x)?B(x,t)中的x受?約束，A(y)?B(x,y)中的y受?約束；A(x)?B(x,t)中的x和A(y)?B(x,y)中的y為約束變元；A(x)?B(x,t)中的t和A(y)?B(x,y)中的x為自由變元。

3.5已知公式?xA(x)??y(B(x,y)?P(y))

（1）試對公式中的自由變元x代以y3?2。解

先對公式改名，以防止代入后改變變元的約束關系

原式=?xA(x)??u(B(x,u)?P(u))公式中的自由變元x代以y3?2后得：?xA(x)??u(B(y3?2,u)?P(u))

（2）試對公式中的謂詞變元B(e1,e2)代以式子?xC(e1,e2,x,y)。解

先對公式和代入進行改名，以防止代入后改變變元的約束關系原式改名為：

?xA(x)??u(B(x,u)?P(u))代入式改名為：?vC(e1,e2,v,y)代入后的式子為：

?xA(x)??u(?vC(x,u,v,y)?P(u))

3.6試探討公式?x?yX(x,y)在個體域{1,2}上的成真解釋和成假解釋。

解

個體域{1,2}上的二元謂詞共有16類謂詞，見下表：

26

1231516e1e2XXX??XX

11TFT??FF12TTF??FF21TTT??FF22TTT??TF

所以，公式的成假解釋為({1,2};Xi)其中i?2..16；成真解釋為({1,2};X1)。3.7利用量詞的等價公式判斷以下兩組公式是否等價，其中?中不含自由的x。

（1）r??x?(x)和?x(r??(x))解

由于r??x?(x)=????x?(x)=?x(????(x))=?x(???(x))所以，兩公式等價。

（2）??x??(x)????x(?(x)??)解

由于??x??(x)????x??(x)????x(??(x)??)??x(?(x)??)??x(?(x)?r)所以，兩公式不等價。

3.8試探討公式?x(X(x)?Y(x))?(?xX(x)??x(Y(x))的永真性和可滿足性。

解

（1）探討公式在1域{1}上的狀況原式=(X(1)?Y(1))?(X(1)?Y(1))?T公式在1域上永真。

（2）探討公式在2域{1,2}上的狀況

2域上的一元謂詞共有四類，見下表：

eX1X2X3X4

1TFTF

2TTFF由于公式在解釋(I;X,Y)?({1,2);X2,X3)下

原式=?x(X2(x)?X3(x))?(?xX2(x)??xX3(x))

27

=T?(F?F)

=T?F=F

所以，公式在2域上存在成假解釋。

又由于公式在1域上永真，所以由定理知，公式在2域上可滿足。綜上，公式在2域上可滿足，但非永真。（3）探討公式在k(k?3)域上的狀況

由于公式在2域上可滿足，所以由定理知，公式在k域上可滿足。

假設公式在k域上永真，由定理大永真可推出小永真知，公式在2域上永真，矛盾，因此公式在k域上非永真。

3.9試探討公式?x(X(x)?Y(x))?(?xX(x)??xY(x))的永真性和可滿足性。

解

公式在k域{1,2,3,??,k}上永真。

由于?x(X(x)?Y(x))?(X(1)?Y(1))?(X(2)?Y(2))???(X(k)?Y(k))?(X(1)?X(2)???X(k))?(Y(1)?Y(2)???Y(k))?(?xX(x)??xY(x))所以，公式在k域{1,2,3,??,k}上永真。3.10試求出以下公式的前束范式和SKOLEM標準形。

（1）??x(?(?yX(x,y))?(??zY(z)?Z(x)))解

原式=??x(?yX(x,y)?(??zY(z)?Z(x)))=?x(?y?X(x,y)?(?zY(z)??Z(x)))

=?x?y?z(?X(x,y)?(Y(z)??Z(x)))（前束范式）

)??x?z(?X(x,f(x))?(Y(z)??Z(x))

??x(?X(x,f(x))?(Y(g(x))??Z(x)))（SKOLEM標準形）（2）?x?y?z(X(x,y,z)?(?uY(u,x)??xW(y,x)))解

原式=?x?y?z(X(x,y,z)?(?u?Y(u,x)??xW(y,x)))

28

=?x?y?z(X(x,y,z)?(?u?Y(u,x)??vW(y,v)))

=?x?y?z?u?v(X(x,y,z)?(?Y(u,x)?W(y,v)))（前束范式）??y?z?u?v(X(a,y,z)?(?Y(u,a)?W(y,v)))

??y?z?u(X(a,y,z)?(?Y(u,a)?W(y,f(x,y,z))))（SKOLEM標準形）

3.11試用唯一性量詞或摹狀詞符號化以下語句：

（1）只有一個人去過南極。解

令P(e)表示e為人；A(e1,e2)表示e1去過e2；a表示南極；則原句譯為：

?!x(P(x)?A(x,a))

（2）最終一個離開辦公室的人關門窗關電源。解

令P(e)表示e為人；

A(e1,e2)表示e1比e2晚離開辦公室；B(e1,e2)表示e1關e2；b表示門窗；c表示電源；

又令t??yx(P(x)??z(P(z)?A(x,z)))

則原句譯為：B(t,b)?B(t,c)。（3）并非年齡最大的人最有知識。解

令P(e)表示e為人；

A(e1,e2)表示e1比e2年齡大；B(e1,e2)表示e1比e2有知識；

又令t??yx(P(x)??z(P(z)?A(x,z)))

29

則原句譯為：

??x(P(x)?B(t,x))。

（4）每個數均有唯一的一個數是它的后繼。解

令P(e)表示e為數；

A(e1,e2)表示e1是e2的后繼；則原句譯為：

?x(P(x)??!y(P(y)?A(y,x)))。30

第四章謂演算的推理理論

4.1用永真的公理系統(tǒng)證明以下定理

（1）?x(??P(x))?(???xP(x))證明

先證?x(??P(x))?(???xP(x))

（1）?x(??P(x))?(??P(x))公理20（2）（1）?x(??P(x))?(???xP(x))全2規(guī)則再證(???xP(x))??x(??P(x))

（3）?xP(x)?P(x)公理20（4）(?xP(x)?P(x))?((???xP(x))?(??P(x)))定理（5）（4）（3）(???xP(x))?(??P(x))分（6）(???xP(x))??x(??P(x))全規(guī)則（5）（7）(?x(??P(x))?(???xP(x)))?(((???xP(x))??x(??P(x)))?(?x(??P(x))?(???xP(x))))公理7（8）((???xP(x))??x(??P(x)))?(?x(??P(x))?(???xP(x)))分（7）（2）（9）（8）（6）?x(??P(x))?(???xP(x))分（2）?x(P(x)??)?(?xP(x)??)證明

先證?x(P(x)??)?(?xP(x)??)

（1）?x(P(x)??)?(P(x)??))公理20（2）?x(P(x)??)?(?xP(x)??))存1規(guī)則（1）再證(?xP(x)??)??x(P(x)??)

31

（3）P(x)??xP(x)公理21（4）(P(x)??xP(x))?(?x(P(x)??)?(P(x)??))公理3（5）?x(P(x)??)?(P(x)??)分（4）（3）（6）?x(P(x)??)??x(P(x)??)全（5）（7）(?x(P(x)??)?(?xP(x)??))?((?x(P(x)??)??x(P(x)??))?(?x(P(x)??)?(?xP(x)??)))公理7（8）(?x(P(x)??)??x(P(x)??))?(?x(P(x)??)?(?xP(x)??))分（7）（（2）（9）（8）（6）?x(P(x)??)?(?xP(x)??)分4.2已知公理

(A)?(P?(Q?P))(B)?(P?P)

及分開規(guī)則和全稱規(guī)則，全稱規(guī)則為：

?(?1?(?2??(x)))├?(?1?(?2??x?(x)))試證明：全0規(guī)則??(x)├??x?(x)。

證明（1）??(x)

（2）?(?(x)?((???)??(x)))公理(A)（3）?((???)??(x))分（2）（1）（4）?(((???)??(x))?((???)?((???)??(x))))公理(A)（5）?((???)?((???)??(x)))分（4）（3）

?((???)?((???)??x?(x)))全（6）（5）

（7）?(???)公理(B)

?((???)??x?(x))分（8）（6）（7）

32

（9）??x?(x)分（8）（7）4.3指出以下推理過程的錯誤所在

（1）①?x?y(x?y)假設

②?y(z?y)全稱量詞消去③z?b額外假設引入④?z(z?b)全0規(guī)則⑤b?b全稱量詞消去⑥?x(x?x)全0規(guī)則解

第④步有錯，由于額外假設中的自由變元不能實施全0稱規(guī)則。（2）?xP(x)??xP(x)的證明過程如下：

①?xP(x)假設②P(e)額外假設③?xP(x)全0規(guī)則

解

第③步有錯，由于額外假設中的自由變元不能實施全0稱規(guī)則。

（3）①?x(P(x)?Q(x))假設

②?xP(x)假設③P(c)?Q(c)全稱量詞消去④P(c)額外假設引入⑤Q(c)分③④⑥?xQ(x)存在量詞引入解

第④步P(c)中的c為使用過的變元，額外假設要求引入的變元為未使用過的變元。4.4用假設推理證明以下公式

（1）?x(P(x)?Q(x))?((?xQ(x)??xR(x))?(?xP(x)??xR(x)))

證明

33

（1）?x(P(x)?Q(x))假設（2）?xQ(x)??xR(x)假設（3）?xP(x)假設（4）（1）P(x)?Q(x)全稱量詞消去規(guī)則（5）（3）P(x)全稱量詞消去規(guī)則（6）（4）（5）Q(x)分（7）（6）?xQ(x)全0規(guī)則（8）?xR(x)分（2）（7）由假設推理的定義過程知

?x(P(x)?Q(x))，?xQ(x)??xR(x)，?xP(x)├?xR(x)由推理定理知

?x(P(x)?Q(x))?((?xQ(x)??xR(x))?(?xP(x)??xR(x)))（2）?xP(x)??x((P(x)?Q(x))?R(x))，?xP(x)├?x?y(R(x)?R(y))

證明

?xP(x)??x((P(x)?Q(x))?R(x))假設（1）

（2）?xP(x)假設

?x((P(x)?Q(x))?R(x))分（3）（1）（2）

（4）P(a)額外假設（5）P(a)?(P(a)?Q(a))公理11（6）P(a)?Q(a)分（5）（4）（7）(P(a)?Q(a))?R(a)全稱量詞消去（3）（8）R(a)分（7）（6）（9）P(b)額外假設（10）P(b)?(P(b)?Q(b))公理11

34

（11）P(b)?Q(b)分（10）（9）（12）（3）(P(b)?Q(b))?R(b)全稱量詞消去（13）R(b)分（12）（11）（14）（8）（13）R(a)?R(b)合取規(guī)則（15）(R(a)?R(b))??y(R(a)?R(y))公理21（16）（15）（14）?y(R(a)?R(y))分（17）?y(R(a)?R(y))??x?y(R(x)?R(y))公理21（18）（17）（16）?x?y(R(x)?R(y))分由假設推理過程的定義知

?xP(x)??x((P(x)?Q(x))?R(x))，?xP(x)├?x?y(R(x)?R(y))4.5已知知識如下：

（1）桌子上的每本書均是杰作；（2）寫出杰作的人是天才；

（3）某個不有名的人寫了桌上某本書；結論：某個不有名的人是天才。（1）試用歸結原理證明之；（2）試用假設推理證明之。證明先對知識符號化

令P(e)表示e為人；

A(e)表示e為桌子的書；B(e)表示e為杰作；W(e1,e2)表示e1寫了e2；

C(e)表示e有名；D(e)表示e為天才。

則已知知識翻譯為：（1）?x(A(x)?B(x))

（2）?x?y((P(x)?B(y)?W(x,y))?D(x))

35

（3）?x?y(P(x)??C(x)?A(y)?W(x,y))結論翻譯為：

?x(P(x)??C(x)?D(x))歸結原理證明（1）?A(x1)?B(x1)

（2）?P(x2)??B(y)??W(x2,y)?D(x2)（3）P(a)（4）?C(a)（5）A(b)（6）W(a,b)

（7）?P(x3)?C(x3)??D(x3)

（8）C(a)??D(a)（9）?D(a)（10）?P(a)??B(y)??W(a,y)（11）?B(y)??W(a,y)（12）?B(b)（13）?A(b)（14）□假設推理證明

（1）

?x(A(x)?B(x))（2）?x?y((P(x)?B(y)?W(x,y))?D(x))（3）?x?y(P(x)??C(x)?A(y)?W(x,y))（4）P(a)??C(a)?A(b)?W(a,b)（5）(P(a)??C(a)?A(b)?W(a,b))?P(a){a/x3}（7）（3）歸結（4）（8）歸結{a/x2}（9）（2）歸結（3）（10）歸結{b/y}（11）（6）歸結a/x1}（12）（1）歸結（13）（5）歸結假設假設假設額外假設公理36

{

（6）(P(a)??C(a)?A(b)?W(a,b))??C(a)公理（7）(P(a)??C(a)?A(b)?W(a,b))?A(b)公理（8）(P(a)??C(a)?A(b)?W(a,b))?W(a,b)公理（9）P(a)分（5）（4）（10）?C(a)分（6）（4）（11）A(b)分（7）（4）（12）（8）（4）W(a,b)分（13）A(b)?B(b)全稱量詞消去（1）（14）（13）（11）B(b)分（15）（2）(P(a)?B(b)?W(a,b))?D(a)全稱量詞消去（16）P(a)?B(b)?W(a,b)合?。?）（14）（12）（17）D(a)分（15）（16）

P(a)??C(a)?D(a)合取（18）（9）（10）（17）(P(a)??C(a)?D(a))??x(P(x)??C(x)?D(x))公理21（19）

（20）?x(P(x)??C(x)?D(x))分（19）（18）4.6用歸結方法證明以下公式

（1）?x(P(x)?Q(x))，?x(Q(x)??R(x))，?xR(x)├?xP(x)證明

（1）P(x1)?Q(x1)（2）?Q(x2)??R(x2)（3）R(x3)（4）?P(a)

（5）Q(a){a/x1}（4）（1）歸結

37

（6）?R(a){a/x2}（2）（5）歸結（7）□{a/x3}（6）（3）歸結（2）?x?y((P(f(x))?Q(f(b)))?(P(f(a))?P(x)?Q(y)))證明

目標公式的否定

??x?y((P(f(x))?Q(f(b)))?(P(f(a))?P(x)?Q(y)))

=?x?y((?(P(f(x))?Q(f(b)))?(P(f(a))?P(x)?Q(y))))=?x?y(P(f(x))?Q(f(b))?(?P(f(a))??P(x)??Q(y)))化為子句集：（1）P(f(x1))（2）Q(f(b))

（3）?P(f(a))??P(x2)??Q(y)

（4）?P(x2)??Q(y){a/x1}（1）（3）歸結（5）?P(x2){f(b)/y}（4）（2）歸結（6）□{f(x1)/x2}（5）（1）歸結4.7已知知識如下：

（1）每個程序員均寫過程序；（2）病毒是一種程序；

（3）有些程序員沒寫過病毒。結論：有些程序不是病毒。試用霍恩子句規(guī)律程序證明之。

證明先對知識符號化

令P(e)表示e為程序員；

A(e)表示e為程序；B(e)表示e為病毒；W(e1,e2)表示e1寫了e2

則已知知識翻譯為：

（1）?x(P(x)??y(A(y)?W(x,y)))

38

（2）?x(B(x)?A(x))

（3）?x(P(x)??y(B(y)??W(x,y)))結論翻譯為：

?x(A(x)??B(x))（1）A(f(x1))?P(x1)（2）W(x2,f(x2))?P(x2)（3）A(x3)?B(x3)（4）P(a)?（5）?B(y),W(a,y)（6）B(x4)?A(x4)

（7）?A(y),W(a,y){y/x4}（5）（6）歸結（8）?P(x1),W(a,f(x1)){f(x1)/y}（7）（1）歸結（9）?W(a,f(a)){a/x1}（8）（4）歸結（10）?P(a){a/x2}（9）（2）歸結（11）□（4）（10）歸結4.8已知有關公司信息的知識：（1）John是PD公司經理；（2）Smith在PD公司任職；（3）Jones在PD公司任職；（4）Peter在PD公司任職；（5）Hall是SD公司經理；（6）Mary在SD公司任職；（7）Bell在SD公司任職；（8）Jones和Mary已結婚；

（9）在某家公司當經理者必在該公司任職；

（10）在某家公司當經理者必是在該公司任職的人的老板；（11）A和B結婚，則B和A結婚；（12）一對夫婦不在同一公司任職；

（13）所有在SD公司任職的已婚者可享有EC保險的人壽保險?，F在查詢：

Mary是否在SD公司任職？她結婚了嗎？丈夫是誰？她是否享有保險？

39

試用霍恩子句規(guī)律程序證明之。證明

令A(e1,e2)表示e1為e2公司的經理；B(e1,e2)表示e1為e2公司的任職；M(e1,e2)表示e1和e2夫婦；C(e1,e2)表示e1為e2的老板；D(e1,e2)表示e1享有e2的人壽保險；E(e)表示e已婚；P(e)表示e為人；F(e)表示e為公司；G(e)表示e已婚；

化為霍恩子句：

（1）A(John，PD)?（2）B(Smith，PD)?（3）B(Jones，PD)?（4）B(Peter，PD)?（5）A(Hall，SD)?（6）B(Mary，SD)?（7）B(Bell，SD)?（8）M(Jones,Mary)?（9）E(Mary)?（10）E(Jones)?（11）F(a)?

40

（12）B(y,a)?P(y),A(y,x)（13）P(c)?（14）F(b)?（15）A(c,b)?（16）C(c,z)?A(z,b)（17）M(x1,y1)?M(y1,x1)（18）G(Jones)?（19）G(Mary)?

（20）D(x2,EC)?B(x2,SD),E(x2)問Mary是否在SD公司任職？翻譯為子句：（21）?B(Mary,SD)

（22）□所以Mary在SD公司任職。問