作业帮定理3:任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的.证明 设A¢是A的析取范式,即AÛA¢.若A¢的某个简单合取式Ai中不含命题变元P及其否定ØP,
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/05 18:16:54
定理3:任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的.证明 设A¢是A的析取范式,即AÛA¢.若A¢的某个简单合取式Ai中不含命题变元P及其否定ØP,
定理3:任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的.
证明 设A¢是A的析取范式,即AÛA¢.若A¢的某个简单合取式Ai中不含命题变元P及其否定ØP,将Ai展成形式AiÛAi∧1ÛAi∧(P∨ØP)Û(Ai∧P)∨(Ai∧ØP),继续这个过程,直到所有的简单合取式成为小项.然后,消去重复的项及矛盾式之后,得到A的主析取范式.
下面证明其惟一性.若A有两个与之等价的主析取范式B和C,则BÛC.由B和C是A的不同的主析取范式,不妨设小项mi只出现在B中而不在C中,于是i的二进制为B的成真赋值,C的成假赋值,与BÛC矛盾.因而A的主析取范式是惟一的.
定理3:任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的.证明 设A¢是A的析取范式,即AÛA¢.若A¢的某个简单合取式Ai中不含命题变元P及其否定ØP,
1.3.1命题演算的合式公式规定为：
（1）单个命题变元本身是一个合式公式.
（2）如果A是合式公式,那么┐A是合式公式.
（3）如果A和B是合式公式,那么（A∨B）、（A∧B）、（A→B）、（ADB）、都是合式公式.
（4）当且仅当有限次地应用（1）（2）（3）所得到的包含命题变元,连接词和圆括号的符号串是合式公式.
1.3.2 设Ai是公式A的一部分,且Ai是一个合式公式,称Ai是A的子公式.
1.3.3 设P为一命题公式,P1,P2,……,Pn为出现在P中的所有命题变元,对P1,P2,……,Pn指定一组真值称为对P的一种指派.若指定的一种指派,使P的值为真,则称这组指派为成真指派.若指定的一种指派,使P的值为假,则称这种指派为成假指派.
含n个命题变元的命题公式,共有2n个指派.
1.3.4 给定两个命题公式A和B,设P1,P2,……,Pn为所有出现于A和B中的原子变元,若给P1,P2,……,Pn任一组真值指派,A和B的真值都相同,称A和B是等价的,记做A B.
1.3.5 设A为一命题公式,若A在它的各种指派情况下,其取值均为真,则称A为重言式或永真式.
1.3.6 设A为一命题公式,若A在它的各种指派情况下,其取值均为假,则称A为矛盾式或永假式.
1.3.7设A为一命题公式,若A在它的各种指派情况下至少存在一组成真指派,则称A为可满足式.
1.4.1 设X式合式公式A的子公式,若有Y也是一个合式公式,且XY,如果将A中的X用Y置换,得到公式B,则AB.
1.4.2 设A,B为两个命题公式,AB,当且仅当A ←→B为一个重言式.
P=>Q称做P蕴含Q或蕴含式,又称永真条件式.
蕴含式有下列性质：
（1）对任意公式A,又A=>A；
（2）对任意公式A,B和C,若A=>B,B=>C,则A=>C；
（3）对任意公式A,B和C,若A=>B,A=>C,则A=>(B∧C);
（4）对任意公式A,B和C,若A=>C,B=>C,则A∨B=>C.
1.4.3设P,Q为任意两个命题公式,PQ的充分必要条件式P=>Q,Q=>P