离散数学-命题演算

1、命题逻辑的等值演算和推理演算Lu Chaojun, SJTU 2主要内容 公式间的等值关系与等值演算 利用真值表列写公式 联结词的完备集 对偶定理 范式和主范式 公式间的重言蕴涵关系与推理演算2Lu Chaojun, SJTU 3公式间的等值关系 一种重要的数学论证方法是:将一个命题用另一个等值命题替换. 给定两个命题公式和,设P1 , Pn是出现在和 中的所有命题变项. 若在所有解释(共2n个)下和 的真值都相同, 就称和 等值等值(或逻辑等价逻辑等价,logical equivalence).记作 = (或 ). 例如: PQ = P Q这两个公式语法上是不同的,但语义上相同(即有相同意义

2、).Lu Chaojun, SJTU 4如何证明两公式等值? 真值表法 利用等值定理 利用基本等值式进行推导4Lu Chaojun, SJTU 5例:利用真值表证明等值证明(PP)Q = Q.证:列出真值表即可看出等式成立.PQPP(PP)QFFFFFTFTTFFFTTFTLu Chaojun, SJTU 6等值定理 等值定理等值定理:对公式对公式 和和 , = iff 是重言式是重言式证明:若 是重言式,则在任一解释下,其真值都为T,依的定义知和真值相同.故 =.若 =, 则在任一解释下,和都有相同的真值,依的定义即真值为T.故是重言式.Lu Chaojun, SJTU 7 = 与 的异同

3、从形式系统角度看 是系统内的符号, 是系统内的合式公式.(语法) =是系统外的符号, = 不是合式公式! =是在系统外观察系统内两个公式是否等值.(语义) 从真假性来看 写下,不代表和 等值.只有为真,才能得知和 等值.但 可为假. 写下 =,则肯定了和 等值.Lu Chaojun, SJTU 8等值关系“=”的性质 和大家在数学里用的等号一样,具有下面三个性质:1.自反性: =2.对称性: 若 =, 则 =3.传递性: 若 =且 =, 则 = 这三条性质体现了两事物“等同”、“同一性”概念. 满足这三条性质的关系称为等价关系.8Lu Chaojun, SJTU 9例:利用等值定理证明等值证明

4、(PQ) = (PQ).证:转化为证明(PQ)(PQ)是重言式.比如列出此公式的真值表. 这里本质上还是在利用真值表. 还可利用重言式推理系统(见3.2)证明重言式.9Lu Chaojun, SJTU 10基本等值式(等价定律)1.结合(associative)律(P Q) R = P (Q R)(P Q) R = P (Q R)(P Q) R = P (Q R)2. 交换(commutative)律P Q = Q PP Q = Q PP Q = Q P注意:没有的结合律和交换律.Lu Chaojun, SJTU 11基本等值式(续)3. 分配(distributive)律P (Q R) =

5、(P Q) (P R)P (Q R) = (P Q) (P R)P(QR) = (PQ)(PR)4.吸收(absorption)律P (P Q) = PP (P Q) = PLu Chaojun, SJTU 12基本等值式(续)5. 关于否定词的等值式P = P(双重否定律)(P Q) = P Q(De Morgan律)(P Q) = P Q(De Morgan律)(PQ) = P Q(PQ) = PQ = P Q = (P Q) (P Q)Lu Chaojun, SJTU 13基本等值式(续)6.幂等律P P = PP P = PP P = TP P = T注:这两组等值公式的共同特点是“变

6、元混同”.7.补余律P P = TP P = FP P = PPP = PP P = F13Lu Chaojun, SJTU 14基本等值式(续)8.同一律P F = PP T = PTP = PP F = PTP = PF P = P9.零律P T = TP F = FPT = TFP = T注:这两组等值式的共同特点是“部分指派”.14Lu Chaojun, SJTU 15其他常用等值式 由于,更易理解和处理,常将含和的公式改写成仅含有,的公式.10.PQ = P Q = (P Q)11.PQ = Q P 正定理与逆否定理12. P(QR) = (P Q)R 合取前提13. PQ = PQ

7、14. PQ = (PQ)(PQ) 同真或同假15. PQ = (PQ)(PQ) 一真一假Lu Chaojun, SJTU 16其他常用等值式(续)16. PQ = (PQ) (QP) 充分必要17. P(QR) = Q(PR) 交换前提18. (PR)(QR) = (P Q)R 析取前提补充:19. P(QR) = (PQ) (PR)20. P(QR) = (PQ) (PR)21. (PQ)R = (PR) (QR)22. (PQ)R = (PR) (QR)Lu Chaojun, SJTU 17置换规则 置换置换:对公式的子公式用等值公式替换. 与代入代入不同! 定理定理:若对公式若对公式

8、的子公式置换后得到公的子公式置换后得到公式式 ,则有则有 = .证明思路:考虑 和 的解释时,将子公式及其替换公式视为新变元.再判断 和 的的同真假. 推论推论:若若 是重言式是重言式,则置换后得到的则置换后得到的 也也是重言式是重言式.Lu Chaojun, SJTU 18等值演算 等值演算等值演算:利用等值定律及替换规则进行公式推演. 一般是为了化简公式. 例如:证明(P(QR)(QR)(PR) = R.证明:左端= (P(QR)(QP)R)(分配律)=(PQ)R) (QP)R) (结合律)=(PQ)R) (QP)R) (摩根律)=(PQ)(QP)R(分配律)=(PQ)(PQ)R (交换律

9、)=TR (置换)=R(同一律) Lu Chaojun, SJTU 19命题公式与真值表 给定公式,列出其真值表是容易的. 给定真值表(包括命题变元P1,Pn及相应的真值),如何写出公式 ? 有两种方法: 方法一:利用使为真的解释(真值指派) 方法二:利用使为假的解释(真值指派)Lu Chaojun, SJTU 20方法一 从每个使为真的解释写出一个各命题变元的合取式;然后写出各合取式的析取式.例:有三个成真解释.由(P,Q)=(F,F)可写出合取式:P Q由(P,Q)=(F,T)可写出合取式:P Q由(P,Q)=(T,T)可写出合取式:P Q于是得到: (PQ) (PQ) (PQ)20PQF

10、FTFTTTFFTTTLu Chaojun, SJTU 21方法二 从每个使为假的解释写出一个各命题变元的析取式;然后写出各析取式的合取式.例:有两个成假解释.由(P,Q)=(T,F)可写出析取式:P Q由(P,Q)=(T,T)可写出析取式:P Q于是得到: (P Q) (P Q)21PQFFTFTTTFFTTFLu Chaojun, SJTU 22还有别的联结词吗? 除,外还可定义其他联结词.如:异或: P Q = (P Q) (P Q)与非(NAND): P | Q = (P Q)Sheffer stroke或非(NOR): P Q = (P Q)Peirce arrow 问题:给定n个命

11、题变项P1,Pn ,可定义出多少种命题联结词? Lu Chaojun, SJTU 23联结词是真值函数 命题联结词可看作是真值函数真值函数,即以真值为定义域和值域的函数. 例如: 是一元真值函数,其真值表实际上给出了这个函数定义.若用常见函数记法可记为: : T,F T,FT | FT | T 又如: 是二元真值函数: : T,FT,F T,F 前述问题转化成: n元真值函数有多少个?Lu Chaojun, SJTU 24一元联结词的个数 一元真值函数只有一个自变元P(命题变项). P只有T和F两种取值,对每一种取值又有两种可能的函数值T和F.于是可定义22 种不同的真值函数.即下表中的f0

12、f3. 相应地共有4种不同的一元联结词. 例如上面的f2就是我们熟悉的.Pf0(P)f1(P)f2(P)f3(P)FFFTTTFTFTLu Chaojun, SJTU 25二元联结词的个数 二元真值函数有两个自变元P和Q,可取4种真值组合.对每一种取值组合又有两种可能的函数值T和F.于是可定义24种不同的真值函数. 即下表中的g0 g15. 相应地共有16种不同的二元联结词. 显然g1就是我们熟悉的. g0 g15 中除了,之外,也定义了, , 等等.PQg0(P,Q)g1(P,Q)g2(P,Q)g15(P,Q)FFFFFTFTFFFTTFFFTTTTFTFTLu Chaojun, SJTU

13、26n元联结词的个数 一般地, n元真值函数有n个自变元P1, , Pn .每个Pi有两种取值,从而P1, , Pn共有2n种真值组合.对每一种取值组合又有两种可能的函数值T和F.于是可定义22n种不同的真值函数. 相应地可定义22n个n元联结词. 例:定义一个三元联结词#(P,Q,R)为真 iff P,Q,R中至少两个为真. 无法用习惯的中缀法表示.Lu Chaojun, SJTU 27联结词的完备集 可定义的联结词很多,但并非都彼此独立,即:能够相互表示. 例如: PQ = P Q. 即可用和表示. 定义: 设C是联结词的集合.如果对任一命题公式都有由C中联结词表示出来的公式与之等值,就说

14、C是完备的完备的(adequate)联结词集合,或联结词的完备集. Lu Chaojun, SJTU 28联结词的完备集(续) 全体联结词的集合(无穷集)是完备的. 和,都不是完备的. 定理: ,是完备的联结词集合. 证明思路:回顾由真值表列写命题公式的过程可知任一公式都可由,表示出来. 是后面即将学到的范式定理范式定理的直接推论. 由PQ = (PQ)可知:可由,表示,故,也是联结词的完备集.类似地,等也是.Lu Chaojun, SJTU 29对偶式 观察下面两个等值公式(分配律):P (Q R) = (P Q) (P R)P (Q R) = (P Q) (P R) 命题逻辑公式存在“对偶

15、”规律. 设公式 中只出现,. 将 中的, 分别以,替换, 所得公式称为的对偶式对偶式*. 将 中所有肯定形式出现的变元Pi换成Pi, 所有否定形式出现的变元Pi换成Pi, 所得公式记为. 注意:求*时不能有,;求时无此限制.Lu Chaojun, SJTU 30*和的性质 定理(*)* = ()= 定理(*) = ()*() = () 定理 = *(De Morgan律的一般形式)Lu Chaojun, SJTU 31对偶定理 定义和 同永真同永真: 永真 iff 永真和 同可满足同可满足: 可满足 iff 可满足 定理:以下两对公式都是同永真且同可满足的: 与, 与*. 对偶定理对偶定理:

16、以下两对公式都是同永真且同以下两对公式都是同永真且同可满足的可满足的: 与与 * *, 与与 * *. 推论推论: = iff * = *.Lu Chaojun, SJTU 32公式有没有标准形式? 公式的数量是无穷多的. 即便只有一个变元P,也可以写出P , P P , P P P , P P P P, 但若按等值关系对全体公式进行划分, n个命题变项所能形成的不同公式仅有22n个. 问题:与命题公式 等值的公式能否都化为某种标准形式? 借助于标准形容易判断两个公式是否等值. 借助于标准形容易判断公式是否重言式或矛盾式.Lu Chaojun, SJTU 33范式(normal form) 由

17、命题变元或命题变元的否定利用()联结而成的公式称为合合(析析)取式取式. 合取式例:P, P, PQ, PQP 析取式例:P, P, PQ, PQP 由合(析)取式利用()联结而成的公式称为析析(合合)取范式取范式. 析取范式形如: 1 2 n (诸i是合取式) 合取范式形如: 1 2 n (诸i是合取式)Lu Chaojun, SJTU 34公式转化为范式 范式定理范式定理: 任一公式都有与之等值的合取任一公式都有与之等值的合取范式和析取范式范式和析取范式. 根据真值表列写公式就是求范式一法. 等值变换法求范式1.消去,2.否定词深入到变元前3.合(析)取词深入这时已经是范式.4.(可选)化

18、简34Lu Chaojun, SJTU 351.消去, 方法:利用下列等值式 = = ( )( ) 适合求析取范式 = ( )( ) 适合求合取范式 例:求(PQ)(PQ)的析取范式 (PQ)(PQ)= (PQ) (PQ) (PQ) (PQ)35Lu Chaojun, SJTU 362.否定词深入 方法:利用下列等值式( ) = ( ) = = 例 (PQ)(PQ) = (PQ) (PQ) (PQ) (PQ)= (PQ PQ) (PQ) (PQ)36Lu Chaojun, SJTU 373.合(析)取词深入 方法:利用分配律 ( ) = ( ) ( ) 用于析取范式 ( ) = ( ) ( )

19、 用于合取范式 例 (PQ)(PQ) = (PQ) (PQ) (PQ) (PQ)= (PQ PQ) (PQ) (PQ)= (PQ PQ) (PP) (PQ) (QP) (QQ)37Lu Chaojun, SJTU 384.(可选)化简 方法:利用下列等值式消去矛盾式P F = F F = 例 (PQ)(PQ) = (PQ) (PQ) (PQ) (PQ)= (PQ PQ) (PQ) (PQ)= (PQ PQ) (PP) (PQ) (QP) (QQ)= (PQ) (PQ)38Lu Chaojun, SJTU 39范式的用途 判断是否重言式 求的合取范式,若每个析取式都含有某个变元及其否定(如P和P

20、),则是重言式. 判断是否矛盾式 求的析取范式,若每个合取式都含有某个变元及其否定(如P和P),则是矛盾式. 判断 = ? 求 和 的同一种范式,看是否相同. 问题是: 范式唯一吗?39Lu Chaojun, SJTU 40主范式假设以下讨论的公式都只涉及n个命题变元P1, , Pn. 极小项极小项: n个命题变元都在其中出现一次的合取式. 极小项有2n个. 主析取范式主析取范式:仅由极小项构成的析取式. 定理:任一公式都有唯一与之等值的主析取范式.假设以下讨论的公式都只涉及n个命题变元P1, , Pn. 极大项极大项: n个命题变元都在其中出现一次的析取式. 极大项有2n个. 主合取范式主合

21、取范式:仅由极大项的构成的合取式. 定理:任一公式都有唯一与之等值的主合取范式.Lu Chaojun, SJTU 41主范式的求法求主析取范式 方法一: 利用真值表中的成真指派列写公式. 例:根据PQ的真值表中的T行(PQ) (PQ)求主合取范式 方法一: 利用真值表中的成假指派列写公式. 例:根据PQ的真值表中的F行(PQ)(PQ)41Lu Chaojun, SJTU 42主范式的求法(续)求主析取范式 方法二: 为析取范式中的合取式补足未出现的命题变元. 例: PQ = P QP = P (Q Q)= (PQ) (PQ)Q = Q (P P) = (PQ) (PQ)于是PQ = 求主合取范

22、式 方法二: 为合取范式中的析取式补足未出现的命题变元 例: (PQ) = PQP = P (Q Q)= (PQ) (PQ)Q = Q (P P) = (PQ) (PQ)于是(PQ) = 42Lu Chaojun, SJTU 43极小(大)项的性质 极小项与真值指派(解释)一一对应,都有2n个. 每个极小项只在一个解释下为真. 一个解释下两个极小项不能都为真.(其合取为F) 极小项两两不等值. 若由k个极小项的析取组成,则其余2nk个极小项的析取就是. 若k = 2n,则是重言式. 极大项与真值指派(解释)一一对应,都有2n个. 每个极大项只在一个解释下为假. 一个解释下两个极小项不能都为假.

23、(其析取为真) 极大项两两不等值. 若由k个极大项的合取组成,则其余2nk个极大项的析取就是. 若k = 2n,则是矛盾式.43Lu Chaojun, SJTU 44推理形式 用命题公式来描述在科学和日常生活中进行的推理,称为推理形式推理形式. 公式形状都 是蕴涵式. 例如下面三个推理形式都是常见的:(PQ) P) Q正确(即MP)(PQ) P) Q错误(PQ) Q) P正确(即换质位法) 问题:什么样的推理形式描述了正确的推理?Lu Chaojun, SJTU 45重言蕴涵关系 给定两个公式和,在任何解释下,若为真则 也为真, 就称 重言蕴涵重言蕴涵,或称是的逻辑推论逻辑推论.记作 . 这是

24、讨论从前提推出结论的问题. 是前提,一般形如12 n.也可理解成有n个前提. 例如:若PQ为真,显然P也为真,所以PQ Q45Lu Chaojun, SJTU 46 与 的异同 从形式系统角度看 是系统内的符号, 是系统内的合式公式.(语法) 是系统外的符号, 不是合式公式! 这是在系统外观察系统内两个公式间的逻辑蕴涵关系.(语义) 从表达的意思来看 只是表达“不能真而 假”,因此除了包含“真则 真”的意思之外,还包含“假则 可真可假”的意思. 表达且仅表达“真则 真”的意思.Lu Chaojun, SJTU 47如何证明 ?1.利用真值表 列出所有命题变元的所有指派,以及公式 和 相应的真值

25、. 若使 为真的解释也都使 为真,则 成立;否则, 就不成立.2.利用下面的定理定理定理: iff 是重言式是重言式所以 称为“重言蕴涵式重言蕴涵式”.定理定理: iff 是矛盾式是矛盾式47Lu Chaojun, SJTU 48如何证明 ?(续)3.利用的一些性质(1) 自反性(2)若 且 , 则 =反对称性(3)若 且 , 则 传递性(4)若 且 , 则 (5)若 且 , 则 (6)若 , 则 (7)若 , 则 48Lu Chaojun, SJTU 49基本的重言蕴涵式作为基本的推理定律(1) P Q P(2) P P Q(3) P PQ假前提啥都蕴涵(4) (PQ) P啥都不能蕴涵的前提

26、,必真(5) Q PQ真结论被一切前提蕴涵(6) (PQ) Q啥前提都不蕴涵的结论,必假(7) P(PQ) Q排除法(8) P(PQ) Qmodus ponens, 或分离规则49Lu Chaojun, SJTU 50基本的重言蕴涵式(续)(9) (PQ)Q Pmodus tollens(10) (PQ)(QR) PR三段论法之一(11) (PQ)(QR) PR(12) (PR)(QR)(PQ) R(13) (PQ)(RS)(PQ) R S(14) (PQ)(RS)(QS) P R(15) (QR) (PQ) (PR)(16) (QR) (PQ) (PR)50Lu Chaojun, SJTU 51推理演算 前面介绍的证明 的方法,都是根据公式的真值来论证的.体现不出证明的层层推进过程,而且变元很多时不方便. 推理演算推理演算:引入一些推理规则,利用前提和基本推理公式(重言式),实现逐步推进的推理过程. 从若干前提1 ,2 , ,n 出发欲证明. 利用推理规则不断产生中间结论 直至得出最终结论.51Lu Cha