15对偶与范式 ■对偶式与对偶原理 ■析取范式与合取范式 主析取范式与主合取范式
1 1.5 对偶与范式 ▪对偶式与对偶原理 ▪析取范式与合取范式 ▪主析取范式与主合取范式
对偶式和对偶原理 定义在仅含有联结词→,∧,∨的命题公式4中,将 换成∧,∧换成∨,若A中含有0或1,就将0换成 1,1换成0,所得命题公式称为A的对偶式,记为A 从定义不难看出,(4)还原成A 定理设A和A4互为对偶式,P12D2…1是出现在A和 A中的全部命题变项,将A和A*写成n元函数形式, 则(1)-A(D12D2…)分A"(-p1-p2…,-pn (2)A(P1,p2,…,=P A"(p12…n 定理(对偶原理)设A,B为两个命题公式, 若A分B,则A兮B
2 对偶式和对偶原理 定义 在仅含有联结词, ∧,∨的命题公式A中，将 ∨换成∧, ∧换成∨，若A中含有0或1，就将0换成 1，1换成0，所得命题公式称为A的对偶式，记为A* . 从定义不难看出，(A* ) *还原成A 定理 设A和A*互为对偶式，p1 ,p2 ,…,pn是出现在A和 A*中的全部命题变项，将A和A*写成n元函数形式， 则 (1) A(p1 ,p2 ,…,pn ) A* ( p1 , p2 ,…, pn ) (2) A( p1 , p2 ,…, pn ) A* (p1 ,p2 ,…,pn ) 定理（对偶原理）设A，B为两个命题公式， 若A B，则A* B*
析取范式与合取范式 文字:命题变项及其否定的总称 简单析取式:有限个文字构成的析取式 如 P9-4,pV-4,qV, 简单合取式:有限个文字构成的合取式 如 P,-q,p-4,p∧q∧r, 析取范式:由有限个简单合取式组成的析取式 AV42…A,其中A142,…,4,是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1~42^…,A,其中A1,42,,4是简单析取式
3 析取范式与合取范式 文字:命题变项及其否定的总称 简单析取式:有限个文字构成的析取式 如 p, q, pq, pqr, … 简单合取式:有限个文字构成的合取式 如 p, q, pq, pqr, … 析取范式:由有限个简单合取式组成的析取式 A1A2Ar , 其中A1 ,A2 ,,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1A2Ar , 其中A1 ,A2 ,,Ar是简单析取式
析取范式与合取范式(续) 范式:析取范式与合取范式的总称 公式A的析取范式:与A等值的析取范式 公式4的合取范式:与A等值的合取范式 说明 单个文字既是简单析取式,又是简单合取式 形如p∧-q∧r,mqr的公式既是析取范式, 又是合取范式(为什么?
4 析取范式与合取范式(续) 范式:析取范式与合取范式的总称 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 形如 pqr, pqr 的公式既是析取范式， 又是合取范式 (为什么?)
命题公式的范式 定理任何命题公式都存在着与之等值的析取范式 与合取范式 求公式4的范式的步骤: (1)消去A中的→,4(若存在) (2)否定联结词一的内移或消去 (3)使用分配律 ∧对√分配(析取范式) v对入分配(合取范式) 公式的范式存在,但不惟一,这是它的局限性
5 命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式 与合取范式. 求公式A的范式的步骤： (1) 消去A中的→, （若存在） (2) 否定联结词的内移或消去 (3) 使用分配律 对分配（析取范式） 对分配（合取范式） 公式的范式存在，但不惟一，这是它的局限性