离散数学课件-20命题逻辑小结

第一章小结知识网络：命题原子命题复合命题联结词命题公式永真式永真蕴涵式等价公式范式命题逻辑推理直接推理间接推理条件论证反证法析取合取主析取主合取本章的重点内容、及要求：１.逻辑联结词，要熟练掌握联结词的真值表定义以及它们在自然语言中的含义。其中特别要注意“∨”和“→”的用法。２.会命题符号化。３.掌握永真式的证明方法：

(1).真值表。

(2).等价变换，化简成Ｔ。

(3).主析取范式。４.掌握永真蕴含式的证明方法，熟练记忆并会应用

43页中表1-8.3中的永真蕴含式。５.掌握等价公式的证明方法，熟练记忆并会应用

43页表1-8.4中的等价公式。６.熟练掌握范式的写法及其应用。７.熟练掌握三种推理方法。第一章习题课一.命题符号化注意讲过的命题符号化方法。P8习题(3)

P:天下雪。Q:我将去镇上。R:我有时间。a)

如果天不下雪且我有时间，那么我将去镇上。(

P∧R)→Qb)

我将去镇上，仅当我有时间。Q→Rd)

天下雪，那么我不去镇上。P→

QP12习题(5)

a)

或者你没有给我写信，或者它在途中丢失了。显然这里的“或者”是“不可兼取的或”。令P:你给我写信。Q:信在途中丢失了。

表达式为:PQ或

(P∧Q)∨(

P∧Q)

c)

我们不能既划船又跑步。令P:我们划船。Q:我们跑步。

表达式为

(P∧Q)d)如果你来了，那么他唱不唱歌将看你是否为他伴奏而定。令P:你来了。Q:你为他伴奏。R:他唱歌。表达式为:P→((Q→R)∧(

Q→

R))

也可以写成：P→(Q

R)P12习题(7)a)

假如上午不下雨，我去看电影，否则就在家里读书或看报。令P:上午下雨。Q:我去看电影。R:我在家里读书。S:我在家里看报。表达式为:(

P→Q)∧(P→(R∨S))不可以写成：(

P→Q)∨(P→(R∨S))(P→Q)∨(P→(R∨S))(P∨Q)∨(P∨(R∨S))(P∨Q)∨(P∨(R∨S))P∨Q∨P∨R∨SP∨P∨Q∨R∨ST

b)

我今天进城，除非下雨。令P:我今天进城。Q:今天下雨。表达式为:Q→Pc)

仅当你走我将留下。令P:你走。Q:我留下。表达式为:Q→P或者

P→

Q二.重言式的证明方法

方法1：列真值表。

方法2：公式的等价变换，化简成“T”。

方法3：用公式的主析取范式。P23

(2)证明(P→Q)→(P→(P∧Q))是重言式。方法1:PQP→QP→(P∧Q)(P→Q)→(P→(P∧Q))FFTTTFTTTTTFFFTTTTTT方法2:(P→Q)→(P→(P∧Q))(P∨Q)∨(P∨(P∧Q))(E16)(P∧

Q)∨((P∨P)∧(P∨Q))

摩根，分配

(P∧

Q)∨(T∧(P∨Q))

互补

(P∧

Q)∨(P∨Q)同一

(P∨(P∨Q))∧(

Q∨(P∨Q)分配

((P∨P)∨Q))∧(

Q∨(Q∨P)结合、交换

(T∨Q))∧((

Q∨Q)∨P)

互补、结合

T∧(T∨P)零律、互补

T∧T

零律

T幂等方法3

(P→Q)→(P→(P∧Q))(P∨Q)∨(P∨(P∧Q))

去→

(P∧

Q)∨P∨(P∧Q)

后移

(P∧

Q)∨(P∧(Q∨

Q))∨(P∧Q)补变元Q(P∧

Q)∨(P∧Q)∨(P∧

Q)∨(P∧Q)分配

(P∧Q)∨(P∧

Q)∨(P∧Q)∨(P∧

Q)整理可见，该公式的主析取范式含有全部(四个)小项，这表明(P→Q)→(P→(P∧Q))是永真式。三.重言蕴涵式的证明方法方法1.列真值表。(即列永真式的真值表)(略)方法2.假设前件为真，推出后件也为真。方法3.假设后件为假，推出前件也为假。P12(8)e)证明(

A(B∨C))∧(D∨E)∧((D∨E)

A)

B∨C方法2证明：设前件(

A(B∨C))∧(D∨E)∧((D∨E)

A)为真，则

A(B∨C),D∨E,(D∨E)

A均为真。由D∨E,(D∨E)

A均为真用I11得

A为真,又由

A(B∨C)为真，得B∨C为真。所以得(

A(B∨C))∧(D∨E)∧((D∨E)

A)

B∨C(

A(B∨C))∧(D∨E)∧((D∨E)

A)

B∨C方法3

证明：设后件B∨C为F，则B与C均为F，1.如果D∨E为T，则

1).若A为T，则

A为F，则(D∨E)

A为F，于是前件(

A(B∨C))∧(D∨E)∧((D∨E)

A)

为F。

2).若A为F，则

A为T，于是

A(B∨C)

为F，故前件(

A(B∨C))∧(D∨E)∧((D∨E)

A)

为F。2.如果D∨E为F，则前件

(

A(B∨C))∧(D∨E)∧((D∨E)

A)为F。∴(

A(B∨C))∧(D∨E)∧((D∨E)

A)

B∨C四..等价公式的证明方法方法1：用列真值表。（不再举例）方法2：用公式的等价变换.(用置换定律)P19(7)h)证明((A∧B)→C)∧(B→(D∨C))

(B∧(D→A))→c左式

(

(A∧B)∨C)∧(B∨(D∨C))E16((

A∨

B)∨C)∧(B∨(D∨C))摩根

((

B

∨

A)∨C)∧((B∨D)∨C)交换结合

((

B

∨

A)∧(B∨D))∨C

分配

(B

∨(

A∧D))∨C

分配

(B∧(A∨

D))∨C

摩根

(B∧(D→A))→C

E16P19(8)c)化简(A∧B∧C)∨(

A∧B∧C）上式

(A∨

A)∧(B∧C）分配

T∧(B∧C）互补

B∧C

同一提示：化简时注意使用下面使式子变短的公式：分配律E6P∧(Q∨R)(P∧Q)∨(P∧R)

E7P∨(Q∧R)(P∨Q)∧(P∨R)

用分配律时，是提取公因式。幂等律E10P∨P

PE11P∧P

P同一律E12

P∨F

PE13P∧T

P零律E14P∨T

TE15P∧F

F吸收律P∨(P∧Q)

PP∧(P∨Q)

P互补律P∨

PTP∧

P

F五.范式的写法及应用P39(4)d)写出(P(Q∧R))∧(

P(Q∧R))的主析取范式和主合取范式方法1，用真值表

令A(P,Q,R)

(P(Q∧R))∧(

P(Q∧R))它的真值表见下页。A(P,Q,R)

m0∨

m7(P∧

Q∧

R)∨(P∧Q∧R)A(P,Q,R)

M1∧M2∧M3∧M4∧M5∧M6

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)A(P,Q,R)的主析取范式中含有小项m0,

m7。主合取范式中含有大项M1,M2,M3,M4,M5,M6。PQRP(Q∧R)

P(Q∧R

)A(P,Q,R)0FFFTTT1FFTTFF2FTFTFF3FTTTFF4TFFFTF5TFTFTF6TTFFTF7TTTTTT方法2.等价变换(P(Q∧R))∧(

P(Q∧R))

(

P∨(Q∧R))∧(P∨(Q∧R))E16

(

P∧P)∨(P∧Q∧R))∨(P∧Q∧R))∨

((Q∧R)∧(Q∧R))

分配

F∨(P∧Q∧R))∨(P∧Q∧R)∨F互补

(P∧Q∧R))∨(P∧Q∧R)

同一范式的应用P39(7)A,B,C,D四个人中要派两个人出差，按下述三个条件有几种派法？①若A去则C和D中要去一个人。②B和C不能都去。③C去则D要留下。解.设A,B,C,D分别表示A去，B去，C去，D去。①A

((C∧

D)∨(

C∧D))

A∨(C∧

D)∨(

C∧D)②(B∧C)

B∨C③C

D

C∨D总的条件为：(A∨(C∧

D)∨(

C∧D))∧(B∨C)∧(C∨D)令此式为真。将(A∨(C∧

D)∨(

C∧D))∧(B∨C)∧(C∨D)化成析取范式。上式

(

A∨(C∧

D)∨(

C∧D))∧

(C∨(B∧D))

(A∧C)∨(C∧

D∧C)∨(

C∧D∧C)∧

(A∧B∧D)∨(C∧

D∧B∧D)

∨(

C∧D∧B∧D)

(A∧C)∨F∨(

C∧D)∨(A∧B∧D)∨(C∧

D∧B)∨F可以取

A∧C为T，得B和D去。取C∧D为T，得A和D去，或者B和D去。取C∧

D∧B为T，得A和C去。最后得三种派法：A和C去、A和D去、B和D去。*补充题：有工具箱A、B、C、D，各个箱内装的工具如下表所示。试问如何携带数量最少工具箱，而所包含的工具种类齐全。解：设A、B、C、D分别表示带A、B、C、D箱。则总的条件为：

(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D)为真。

改锥

扳手钳子锤子

工具箱改锥扳手钳子锤子A

有有B

有有有

C

有有

D

有有将(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D)写成析取范式，上式

((A∨C)∧(B∨C))∧((A∨(B∨D))∧(B∨D))(交换)((A∧B)∨C))∧(B∨D)(分配(提取C)、吸收)

(A∧B∧B)∨(C∧B)∨(A∧B∧D)∨(C∧D)(分配)

(A∧B)∨(C∧B)∨(A∧B∧D)∨(C∧D)分别可以取(A∧B)、(C∧B)、(C∧D)为真。于是可以得到三种携带方法：带A和B箱，带B和C箱，带C和D箱。六.逻辑推理熟练掌握三种推理方法。P47(2)c)(A∨B)

(C∧D),(D∨E)

F

AF1.直接推理

⑴(A∨B)

(C∧D)P⑵

(A∨B)∨(C∧D)T⑴E16⑶(

A∧

B)∨(C∧D)T⑵E9⑷(

A∨C)∧(

B∨C)∧(

A∨D)∧(

B∨D)T⑶E7⑸

A∨DT⑷I2⑹ADT⑸E16⑺(D∨E)

FP⑻

(D∨E)∨FT⑺E16⑼(

D∧

E)∨FT⑻E9⑽(

D∨F)∧(

E∨F)T⑼E7⑾

D∨FT⑽I1

⑿D

F

T⑾E16

⒀A

F

T⑹⑿I13P47(2)c)(A∨B)

(C∧D),(D∨E)

F

AF2.条件论证⑴AP(附加前提)

⑵A∨BT⑴I3⑶(A∨B)

(C∧D)T⑷C∧DT⑵⑶I11⑸DT⑷I2⑹D∨ET⑸I3

⑺(D∨E)

FP⑻FT⑹⑺I11⑼AF