离散数学命题逻辑.ppt

1-6其他联结词

;PQ的真值为:;定理1-6.1设P,Q,R为命题公式，如果;6.2条件否认;6.3与非“”;6.4或非“”;目前为止我们已经介绍了9个联结词，够用吗？;又因为P∧Q??〔?P∨?Q〕;定理2{?},{?},{?,?},{?,F}都是最小联结词组.;7.1对偶式;例题1-7.2求P?Q，P?Q的对偶式。;定理1-7.2设A和B为两个命题公式，假设A?B，那么A*?B*。;1-7范式;2.析取范式

公式A如果写成如下形式：

A1∨A2∨...∨An(n≥1)其中每个Ai(i=1,2..n)是合取式，称之为A的析取范式。

3.合取范式

公式A如果写成如下形式：

A1∧A2∧...∧An(n≥1)其中每个Ai(i=1,2..n)是析取式，称之为A的合取范式。

例如，P?Q的析取范式与合取范式：

P?Q?(P∧Q)∨(?P∧?Q)----析取范式

P?Q?(?P∨Q)∧(P∨?Q)----合取范式;对于任何一命题公式，都存在与其等价的析取范式和合取范式。;例题1-7.1求(P?Q)?R的析取范式与合取范式

(P?Q)?R

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

?(P∧?Q)∨(?P∧Q)∨R------析取范式

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

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

?(?P∨?Q∨R)∧(P∨Q∨R)---合取范式;4.范式的不唯一性;例如，两个命题变元P和Q，其构成的小项有;2.小项的性质

m11m10m01m00

PQP∧QP∧?Q?P∧Q?P∧?Q

00FFFFFT

01FTFFTF

10TFFTFF

11TTTFFF

a).每一组指派与编码相同时，小项为T。

b).任意两个不同小项合取为F，即mi∧mj?Ｆ，i≠j。

c).全体小项的析取为T，记

上例中m0,m1,m2,…,m2n-1

m0??P∧?Qm1??P∧Q

m2?P∧?Qm3?P∧Q;析取范式A1∨A2∨...∨An,,其中每个Ai(i=1,2..n)都是小项，称之为主析取范式。;方法Ⅰ：真值表法〔定理1-7.3〕

⑴列出给定公式的真值表。

⑵找出真值表中每个“T”对应的小项。

(如何根据一组指派写对应的为“T”的项：如果变元P被指派为T，P在小项中以P形式出现；如变元P被指派为F,P在小项中以?P形式出现(因要保证该小项为T))。

⑶用“∨”联结上述小项，即可。;例如求P?Q和P?Q的主析取范式

PQP?QP?Q

FFTT

FTTF

TFFF

TTTT

P?Q?m0∨m1∨m3

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

P?Q?m0∨m3

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

思考题:永真式的主析取范式是什么样？;方法Ⅱ：用公式的等价变换

⑴先写出给定公式的析取范式A1∨A2∨...∨An。

⑵为使每个Ai都变成小项，对缺少变元的Ai补全变元，比方缺变元R，就用∧联结永真式(R∨?R)形式补R。

(3)用分配律等公式加以整理(去掉永假合取项及相同项)。

例：P?Q??P∨Q

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

?(?P∧