合取范式
E14 分配律
2)、将否定联结词¬移到命题变量的前面, 摩根律E10,E11；
析取范式
E11: (P∧Q) P∨ Q; E10: (P∨Q) P∧ Q
3)、消除多余的否定联结词，双否定律 PP 4)、用∧对∨的分配律化成，析取范式。
∨对∧的分配律
（合取范式）
6
1、范式---析取范式与合取范式
n
必出现一次，且仅出现
一次
~ 1, P 为 P i i i ~ 0 Pi 为 Pi
8
2、主范式
极小项的个数：n个命题变元可以构成 2 个极小项。 例如：2 个变元P , Q 可构造 4 个极小项
m3 P 0 0 1 1 Q 0 1 0 1 PQ 0 0 0 1
m0 P Q m1 P Q m2 P Q m3 P Q
特殊的质合取式
Pi ~ Pi Pi
极小项定义：
1 .P1 , P2 , P n 的顺序确定； 2 .P i 与 P i 不同时存在，二者之一
~ ~ ~ P1 P 2 P n m 1 2 n m r ( r 0 ,1, ,2 1)
极小项的性质： 1).极小项之间彼此不等价；
2).极小项与使其为真的指派之间建立了一一对应关系
3).主析取范式中，极小项与真值表中相应指派处公式真 值为1的相对应。
13
2、主范式
3.大项
~ ~ ~ 设有 n 个命题变元 P1 , P2 , P n , 形如 P1 P2 Pn 的命题公式 称为由 P1 , P2 , Pn 产生的大项， Pi ~ Pi Pi
15
2、主范式
例4 求(P∧Q)∨R的主合取范式.
解： (P∧Q)∨R
(P∨R)∧(Q∨R) (合取范式) (P∨(Q∧ Q)∨R)∧((P∧ P)∨Q∨R)
(P∨Q∨R)∧(P∨ Q∨R)
∧(P∨Q∨R) ∧(P∨Q∨R) (P∨Q∨R)∧(P∨ Q∨R)∧(P∨Q∨R)
M0∧M2∧M4
24
3、主析取范式的个数
22=16 共2
个。以此类推, n个命题变元,
2n 个不同 可构造2 23=256, 如n=3时2
的主析取范式(包括F)。这个数字增长非常快,
n=4
24=65 时2
536。
主合取范式和主析取范式是一一对应的, 因此, n 个命 题变元, 也可构造22 个不同的主合取范式(包括T)。
即 A mjl ∨ mj2 ∨… A A (mjl ∨ mj2 ∨… mjl ∧ mj2∧…∧ Mjl ∧ Mj2 ∧…∧ )
Mj
Mj mj
n 2 k
mj
Mj
n 2 k
n 2 k
n 2 k
n 2 k
n 2 k
M j mj mj
n 2 k
n 2 k
14
2、主范式
4. 主合取范式 若干个大项的合取,若与公式A等价，则称它为A 的主合 取范式。 例4 求(P∧Q)∨R的主合取范式. 求命题公式A的主合取范式的步骤： （1）先求出合取范式A′. （2）若A′的某简单析取式B中不含命题变项Pi ,或其否定Pi, 则将B展成如下形式： B B∨F B∨(Pi∧ Pi) (B∨Pi)∧(B∨ Pi).
n
25
作业：P21 习题1.3 2 ( 2)、 3 (2)、
26
Mj mj
n 2 k
n 2 k
17
极小项与极大项之间的关系
3.
主析取范式与主合取范式的关系
例题： A (P Q ) R m1 m3 m5 m 6 m7 主合取范式 3 5 6 7 （ 1，，，，） 主析取范式
M0 M2 M4 （ 0 ，，） 2 4
第三讲
范式与主范式
1.为什么引入范式？ 命题公式千变万化，不易于研究其性质和应用。 2.解决办法：将命题公式转化为逻辑等价的标准形。
范式----逻辑等价的标准形式
1
第三讲
讲授内容：
1. 范式
范式与主范式
析取范式 合取范式
2. 主范式
主析取范式 主合取范式 3. 主析取范式的个数
讲授重点：范式与主范式的求法 讲授难点：主范式的求法
P P P, P P F
4) 排序：小项的序号从小到大。
11
2、主范式
例2. 求命题公式(P∧Q)∨R的主析取范式。 A (P∧Q)∨R P∧Q∧(R∨ R)∨(P∨ P)∧(Q∨ Q)∧R
P∧Q∧R∨P∧Q∧ R∨P∧Q∧R∨P∧ Q∧R∨

P∧Q∧R∨
2
1、范式---析取范式与合取范式
1.文字：命题变元或命题变元否定，P, ¬ Q； 2.质合取式：若干个文字的合取, P∧ ¬ Q ∧ R; 3.质析取式：若干个文字的析取, P ∨ Q ∨ ¬ R; 4.析取范式: 若干质合取式的析取,若与公式A等价，
则称它为A 的析取范式。
5.合取范式: 若干质析取式的合取，若与公式A等价，
20
2、主范式

主范式的应用
利用主范式可以求解判问题或者证明等价式成立。
(1) 判定命题公式的类型 根据主范式的定义和定理，也可以判定含n个命题变 元的公式，其关键是先求出给定公式的主范式Ａ；其次按 下列条件判定之： (a)若AＴ，或A可化为与其等价的、含2n个小项的主 析取范式，则A为永真式。
19
2、主范式
例： A：(P∧Q)∨R B：m001 ∨m011 ∨m101 ∨m110 ∨m111 (1)对使A的真值为真的指派，由于它所对应 的小项在B中，所以此类指派也使B的真值 为真。 (2)对使A的真值为假的指派，由于它所对应 的小项不在B中，所以此类指派也使B的真 值为假。 故A与B同真假，从而逻辑等价 (P∧Q)∨R的主析取范式 (P∧Q)∨R m001∨m011∨m101∨m110∨m111 Σ(1,3,5,6,7)
R∨ P∧
P∧
Q∧R
Q∧R
P∧Q∧
P∧Q∧R ∨ P∧Q∧ R ∨ P∧ Q ∧ R ∨
m1 ∨ m3 ∨ m5 ∨ m6 ∨ m7
Σ(1 , 3 , 5 , 6 , 7)
12
2、主范式
主析取范式与真值表的关系 例如： 极小项 m5 --P Q R
足标 101
指
派
1，0，1
极大项：
1 . P1 , P2 , Pn 的顺序确定； 2 . Pi与 Pi 不同时存在，二者之一 ~ ~ ~ P1 P 2 P n M
1 2
必出现一次，且仅出现
一次
n
M r ( r 0 ,1, ,2 1)
n
~ 1, P 为 P i i i ~ 0 Pi 为 Pi
3、主析取范式的个数
当n=1时,极小项有21=2个，即P, P。主析取范式有 2 :
2
f1 F f2 P f3 P
没有极小项
f4 P
P 全部极小项
23
3、主析取范式的个数
当 n=2 时，极小项有 22=4 个，即┏ P∧┏Q ， ┏ P∧Q ，
P∧┏Q ，P∧Q。主析取范式有 2 4
则称它为A 的合取范式。 合取式---称为积 析取式---称为和
3
1、范式---析取范式与合取范式
析取范式:
A A 1 A 2 A n ( n 1), n 1时，单个质合取式也是 A ：质合取式 i
析取范式
合取范式:
A B 1 B 2 B m ( m 1) m 1时，单个质析取式也是 B ：质析取式 i

任给一个命题公式A,经过以上四步演算,即得到一个与
A等值的析取范式或合取范式.任何命题公式的析取范式和合取范式 Nhomakorabea不是唯一的
7
2、主范式-主析取范式与主合取范式
1. 小项
设有 n 个命题变元 命题公式称为由 ~ ~ ~ P1 , P2 , P n , 形如 P1 P2 P n 的 P1 , P2 , P n 产生的小项，
合取范式
4
1、范式---析取范式与合取范式
范式存在定理
定理1：任意一个命题公式A都存在与之等价的 析取范式和合取范式。
5
1、范式---析取范式与合取范式
常用公式 1)、化成限定性公式；A中→，化成 ¬ ，∧，∨；
E 14 : P Q P Q E 15 : P Q ( P Q ) ( Q P ) ( P Q ) (P Q ) (P Q ) ( P Q )
10
2、主范式
2.主析取范式: 若干个极小项的析取,若与公式A等价，则称 它为A 的主析取范式。
例2. 求命题公式(P∧Q)∨R的主析取范式。
求命题公式A′的主析取范式的步骤：
1) 求公式A 的析取范式A′ 2) 展开：若A′的某简单质合取式B中不含命题变项pi或其否定 pi,则将 B展成如下形式： B B∧T B∧(Pi∨Pi) (B∧Pi)∨(B∧Pi) 3) 消去：将重复出现的命题变项、矛盾式及重复出现的极小项都“消 去”,如P∧P用P代,P∧P用F代,mi∨mi用mi代。
(1)求出A的主析取范式中没包含的极小项mj1,mj2,··m j ·, (2)求出与(1)中极小项下标相同的极大项Mj1,Mj2,··M j ·, (3)由以上极大项构成的合取式为A的主合取范式.
n
n 2 k
.
.
2 k
18
2、主范式
一个命题公式的真值表是唯一的, 因此一个命题公式的主 析取范式(主合取范式)也是唯一的。 定理2：在真值表中使一个命题公式A的真值为真(假)的 指派所对应的小项(大项)的析取(合取)，即为A的主析取 范式(主合取范式) 。 两个命题公式如果有相同的主析取范式(主合取范式), 那么两个命题公式是逻辑等价的。