离散数学课件-第1章-4.ppt
*;第一章逻辑与证明;学习内容;对偶与范式;命题公式P的对偶公式〔Dual〕：
将P中的联结词∨换成∧，∧换成∨，假设有特殊变元T和F
，那么将T换成F，F换成T，所得公式称为P的对偶式，记为P*。
显然，P也为P*的对偶式。;定理1：设A和A*是对偶式，P1,P2,…,Pn是出现在A和A*中的原子变元，那么
?A(P1,P2,…,Pn)?A*(?P1,?P2,…,?Pn)
A(?P1,?P2,…,?Pn)??A*(P1,P2,…,Pn);验证：由德-摩根定律
P∧Q??(?P∨?Q),
P∨Q??(?P∧?Q)
故
?A(P1,P2,…,Pn)?A*(?P1,?P2,…,?Pn)
同理
A(?P1,?P2,…,?Pn)??A*(P1,P2,…,Pn);【example】设A*(S,W,R)是?S∧(?W∨R),证明
A*(?S,?W,?R)??A(S,W,R)
Proof：
由于A*(S,W,R)是?S∧(?W∨R),那么A*(?S,?W,?R)是
S∧(W∨?R),但A(S,W,R)是?S∨(?W∧R),
故?A(S,W,R)是?(?S∨(?W∧R))?S∧(W∨?R).
所以A*(?S,?W,?R)??A(S,W,R)
;对偶原理
设P1,P2,…,Pn是出现在公式P和Q中的所有原子变元，
如果P?Q那么P*?Q*;;2.析取范式与合取范式
公式A如果写成如下形式：
A1∨A2∨...∨An(n≥1)其中每个Ai(i=1,2..n)是合取式
，称之为A的析取范式。
公式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)----合取范式;3.析取范式的化法
(1)将公式中的联结词化成由?，∧，∨组成的限定性公式。
P?Q??P∨Q
P?Q?(P∧Q)∨(?P∧?Q)
P?Q?(P?Q)∧(Q?P)
P?Q?(?P∨Q)∧(P∨?Q)
(2)将否认联结词移到命题变量的前面。
?A(P1,P2,…,Pn)?A*(?P1,?P2,…,?Pn)
?(P∨Q)??P∧?Q、?(P∧Q)??P∨?Q
(3)用分配律、幂等律等公式进行整理，使之成为所要求的形式;【example】求(P∧(Q?R))?S的合取范式。
Solution：
(P∧(Q?R))?S?(P∧(?Q∨R))?S
??(P∧(?Q∨R))∨S
????P∨(Q∧?R)∨S
?(?P∨S)∨(Q∧?R)
?(?P∨S∨Q)∧(?P∨S∨?R);【example】求命题公式(p∨q)?p的合取范式和析取范式。
solution：
⑴求合取范式
(p∨q)?p
?((p∨q)→p)∧(p→(p∨q))(消去?)
?(?(p∨q)∨p)∧(?p∨(p∨q))(消去→)
?((?p∧?q)∨p)∧(?p∨(p∨q))(?内移)
?(?p∨p)∧(?q∨p)∧(?p∨p∨q)(分配律，合取范式)
?1∧(?q∨p)∧(1∨q)(排中律)
?1∧(?q∨p)∧1(零律，合取范式)
?(?q∨p)