西 华 大 学
例如：求A=p∧(q→r)→s的析(合)取范式 解:A 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) 分配律 合 取范式 课堂作业： 求( p→q)→(q∨p)的析（合）取范式。
例如：求A=p∧(q→r)的主析、合取范式
法一：Ap∧(q∨r)
西 华 大 学
合取范式
……
(p∨q∨r) ∧(p∨q∨r)
∧
(p∨q∨r) ∧(p∨q∨r) ∧
(p∨q∨r) ∧(p∨q∨r)
1 1 0 1 0 M 0∧M1 ∧M2 ∧M3 ∧M6（主合取范式 (0,1,2,3,6) ） 0 0 1 0 0 1 1
~ ~ ~ ~ 1.简单合取式（基本积）: P ∧ P2 ∧… ∧ Pn ,（ Pi 为Pi 1 或Pi） ~ ~ ~ 2 ∨… ∨P n 1∨P 西简单析取式（基本和）： P
华 大 2. 析取范式：基本积的析取式 学
合取范式：基本和的合取式
3. 任何公式A都存在与之等价的 析(合)取范式 证(构造法)：1）将A中的→、化掉，使其只含 ∨ ∧； 2）将否定深入到变元前面； 3）使用分配律将公式化为析（合）取范式
q∨p
~ ~ ~ ~ 1. 极小项： P ∧P2 ∧… ∧Pn ,（Pi 为Pi或Pi）中， 1 1) n个变元全部出现； 2) n个变元的位置有序； 西 华 2) Pi、Pi不同时出现； 大 ~ ~ ~ 学 极大项： P ∨… ∨ Pn 1∨ P 2 极小项、极大项的足标与形式的对应
2. 主析取范式：极小项的析取式 主合取范式：极大项的合取式 3. 任何公式A都存在与之等价的主析(合)取范式 方法 1)：真值表法 2)：先求析(合)取范式，再求主析、合取范式
p 0 0 0 0 1 1 1 1
q 0 0 1 1 0 0 1 1
r 0 1 0 1 0 1 0 1
p∧ (q→r) 0 0 0 0
0
p
西 华 大 学
0 0 0 0 1 1
从真值表求主析(合)取范式： 已知公式A＝ q r p∧ (q→r) p∧(q→r)的真值表， 求A的主析取、主 0 0 0 1 合取范式 0 1 0 1 1 0 0 0 1 1 0 1 成真赋值 100 m4 0 0 1 1 成真赋值 101 m5 0 1 1 1
西 华 大 学
三个命题变元P,Q,R,极大项共有8个: 大项 编码 真值指派 大项的真值 P Q R M000/M0 000 0 PQ┐R M001/M1 001 0 P┐QR M010/M2 010 0 P┐Q┐R M011/M3 011 0 ┐PQR M100/M4 100 0 ┐PQ┐R M101/M5 101 0 ┐P┐QR M110/M6 110 0
0
0
0
0
0
1
m4∨m5∨m7
（主析取范式 (4,5,7) ）
从主析(合)取范式求真值表：
A=p∧(q→r) (p∨q∨r) 西 华 ∧(p∨q∨r) 大 学 ∧ (p∨q∨r) ∧(p∨q∨r) ∧(p∨q∨r) =M 0∧M1 ∧M2 ∧M3 ∧M6
000 001 010 011 110
┐P┐Q┐R
M111/M7
111Leabharlann 0求主析取和主合取范式的方法（一） ——等价演算法
西 华 大 学
1.在公式中消去→ 及 ； 2.利用∧对∨的分配律或∨对∧的分配律 得到析取或合取范式。
3. 进一步由各个基本积推出所有极小项得 到主析取范式或由各个基本和推出所有 极大项得到主合取范式。
4.由主范式可直接利用上述两个性质2判定 该命题公式是否是可满足的。
若AB，则A * B * 证：设P1 , P2 ,…,Pn是出现于A和B中的所有原子变元. 因为 A(P1 , P2 ,…,Pn)B(P1 , P2 ,…,Pn) 则 A(P1 , P2 ,…,Pn)B(P1 , P2 ,…,Pn)永真. 故 A(┐P1 , ┐P2 ,…, ┐Pn)B(┐P1 , ┐P2 ,…, ┐Pn) 永真. 由定理1.7.1得 ┐A*(P1 , P2 ,…,Pn)┐B*(P1 , P2 ,…,Pn ) 因此 A*B* . 显然：如果A是永真式，则A *是永假式。
西 华 大 学
例如,三个命题变元P,Q,R,极小项共有8个: 小项 编码 真值指派 小项的真值 ┐P┐Q┐R m000/m0 000 1 ┐P┐QR m001/m1 001 1 ┐PQ┐R m010/m2 010 1 ┐PQR m011/m3 011 1 P┐Q┐R m100/m4 100 1 P┐QR m101/m5 101 1 PQ┐R m110/m6 110 1 PQR m111/m7 111 1 n个命题变元最多可产生多少个极小（大）项？
对偶式和对偶原理
•
西 华 大 学
• • • • • •
对偶式：将只含∨∧（如有→ ，则应该 化去）联结词公式A中的联结词 ∨------->∧, ∧------->∨, 0 ------->1, 1 -------> 0 得到的新公式A*称为A的对偶式。 例如：A = (p ∧ ( p∧q) ∨T) A*=((p ∨( p∨q))∧F)
显然：一般情况A≠A* (A*)*=A
1. 对偶式 2. 引理:A(p1,p2,…,pn) A* ( p1, p2,…, pn) A *(p1,p2,…,pn) A ( p1, p2,…, pn) 证明:
西 华 大 学
因为 ┐(PQ)(┐P┐Q) ┐(PQ)┐P┐Q 所以┐A(P1 , P2 ,…,Pn )A*（┐P1 , ┐P2 ,…, ┐Pn） 同理 ┐A*(P1 , P2 ,…,Pn )A（┐P1 , ┐P2 ,…, ┐Pn） 3. 对偶原理