定理3:任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的.证明 设A¢是A的析取范式,即AÛA¢.若A¢的某个简单合取式Ai中不含命题变元P及其否定ØP,
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/05 17:02:33
![定理3:任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的.证明 设A¢是A的析取范式,即AÛA¢.若A¢的某个简单合取式Ai中不含命题变元P及其否定ØP,](/uploads/image/z/2933836-52-6.jpg?t=%E5%AE%9A%E7%90%863%3A%E4%BB%BB%E6%84%8F%E5%90%ABn%E4%B8%AA%E5%91%BD%E9%A2%98%E5%8F%98%E5%85%83%E7%9A%84%E9%9D%9E%E6%B0%B8%E5%81%87%E5%91%BD%E9%A2%98%E5%85%AC%E5%BC%8FA%E9%83%BD%E5%AD%98%E5%9C%A8%E4%B8%8E%E5%85%B6%E7%AD%89%E4%BB%B7%E7%9A%84%E4%B8%BB%E6%9E%90%E5%8F%96%E8%8C%83%E5%BC%8F%2C%E5%B9%B6%E4%B8%94%E6%98%AF%E6%83%9F%E4%B8%80%E7%9A%84.%E8%AF%81%E6%98%8E+%E8%AE%BEA%26%23162%3B%E6%98%AFA%E7%9A%84%E6%9E%90%E5%8F%96%E8%8C%83%E5%BC%8F%2C%E5%8D%B3A%26%23219%3BA%26%23162%3B.%E8%8B%A5A%26%23162%3B%E7%9A%84%E6%9F%90%E4%B8%AA%E7%AE%80%E5%8D%95%E5%90%88%E5%8F%96%E5%BC%8FAi%E4%B8%AD%E4%B8%8D%E5%90%AB%E5%91%BD%E9%A2%98%E5%8F%98%E5%85%83P%E5%8F%8A%E5%85%B6%E5%90%A6%E5%AE%9A%26%23216%3BP%2C)
定理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