P （ P Q） P （ P Q）.ppt

P ( P  Q)  P (¬ P  Q)
(P ¬ 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) (P  Q)) (¬(P  Q) ¬ (P  Q))
((P  Q) (¬P ¬Q))
(合取范式)
((P  Q) ¬P) ( (P  Q) ¬Q))
(析取范式)
(Q ¬P) (P ¬Q)
A的真值为T的指派所对应的小项为m1,m2…mk,
本定理就等价于要证明: A  B
对于A为T的某一指派,设在这种指派下所对应的小项为mi,
故 B 为 T。
对于 A 为 F 的某一指派,设在这种指派下所对应的小项为mi,
则mi为 T,但根据 B 的定义, mi不在B中,
故B为 F。
在真值表中,一个公式的真值为 T 的指派所对应的小项的析取,
即为此公式的主析取范式。
定理3
证明:
设给定的命题公式为 A。
记B= m1  m2 … mk,
则mi为 T,根据小项的性质,B 中其余小项在这种指派下均为 F,
总之, A  B
即B中所有的小项在这种指派下均为F,
则命题公式A可表示为:A(P,Q,R,S…),A的真值表如下:
实例说明:设命题公式A中的原子变元为P,Q,R,S……。
P
Q
R
S
…
小项
A
T
T
T
T
mi: m1111…
T
T
F
T
F
mj: m1010…
F
T
F
T
T
mk: m1011…
T
F
T
T
T
ml: m0111…
T
F
F
F
F
mm: m0000…
F
…
…
…
…
…
…
…
…
…
…
此真值表中使A的真值为T的真值指派对应的小项为mi,mk,ml…
本定理就等价于要证明: A  B
记B= mi  mk  ml …,
对于A的任意指派,设在此指派下A的真值为T,则这种指派对
应的小项必然是B中的某一个,设这种指派为此真值表中的第
一行:T,T,T,T,…,对应的小项为mi:m1111…,则在此指派下mi的真值为T,则B= mi  mk  ml …中只有mi为T,其余皆为F,则B为T。
若给 P1,P2,P3…Pn 任一组真值指派,A和 B的真值都相同, 则称A 和 B 为等价的,或逻辑相等的。记作 A  B。
A  B
设 P1,P2,P3…Pn 为所有出现在 A 和 B 中的原子变元:
对于A的任意指派,设在此指派下A的真值为F,则这种指派对
应的小项必然不是B中的某一个,设这种指派为此真值表中的第二行:T,F,T,F,…,对应的小项为mj:m1010…则在此指派下mj为T,则其余的所有小项在此指派下真值必然为F,即
B= mi  mk  ml …中全部为F,则B的真值在此指派下为F。
P
Q
P  Q
P  Q
P  Q
(P  Q)
(P  Q) (  P  Q )
T
T
T
T
T
F
T
T
F
F
T
F
T
T
F
T
T
T
F
T
T
F
F
T
F
F
T
T
由定理3可得:
P  Q (P  Q) (¬ P  Q) (¬ P ¬ Q)
P  Q (P  Q) (P ¬ Q) (¬ P  Q)
P  Q  P  Q
¬ (P  Q) (P ¬ Q) (¬ P  Q) (¬ P ¬ Q)
例3、求 P  Q、 P  Q、 P  Q、¬ (P  Q)和
(P  Q) (¬ P  Q)的主析取范式。
1、化为析取范式;
2、去掉析取范式中所有永假的项(包含形如: ¬ P  P 的项);
3、合并相同变元和相同的合取项;
4、对合取项补入没有出现的命题变元,添加( ¬ P  P)式,
然后应用分配律展开公式。
等价公式法求主析取范式
¬ P ((¬ P  Q) (P  Q))
¬ P ((¬ P  P  Q) (Q  P  Q))
¬ P (P  Q)
原式
¬ P (¬ Q  Q) (P  Q)
(¬ P  Q) (¬ P ¬ Q) (P  Q)
例、求P ((P