最新离散数学2教学讲义PPT课件.ppt

《最新离散数学2教学讲义PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学2第一章命题逻辑等值演算ChapteronePropositionLogic9/10/20212DiscreteMath.2.1等值式2.2析取范式与合取范式2.3联结词的完备集等值式定义基本等值式等值演算（置换规则）简单析取（合取）式极大（小）项（主）析（合）取范式真值函数联结词完备集2.4可满足性问题与消解法第一章内容9/10/20213DiscreteMath.当命题公式中变项较多时，用上述方法判断两个公式是否等值计算量很大。为此，人们将一组经检验为正确的等值式作为等值式模式，通过公式间的等值演算来判断两公式是否等值。常用的等值式模式如下：1.双重否定律：A⇔┐(┐A

2、)2.幂等律：A⇔A∨A,A⇔A∧A3.交换律:A∨B⇔B∨A,A∧B⇔B∧A4.结合律:(A∨B)∨C⇔A∨(B∨C),(A∧B)∧C⇔A∧(B∧C)5.分配律：A∨(B∧C)⇔(A∨B)∧(A∨C)(∨对∧的分配律)A∧(B∨C)⇔(A∧B)∨(A∧C)(∧对∨的分配律)6.德摩根律：┐(A∨B)⇔┐A∧┐B,┐(A∧B)⇔┐A∨┐B7.吸收律：A∨(A∧B)⇔A,A∧(A∨B)⇔A等值式模式9/10/20217DiscreteMath.8.零律：A∨1⇔1,A∧0⇔09.同一律：A∨0⇔A,A∧1⇔A10.排中律：A∨┐A⇔111.矛盾律：A∧┐A⇔012.蕴含等值式：A→B

3、⇔┐A∨B13.等价等值式:(A↔B)⇔(A→B)∧(B→A)14.假言易位:A→B⇔┐B→┐A15.等价否定等值式:A↔B⇔┐A↔┐B16.归谬论:(A→B)∧(A→┐B)⇔┐A等值式模式（续）9/10/20218DiscreteMath.利用这16组24个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为等值演算。在等值演算中,经常用到如下置换规则。置换规则:设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后所得的公式。若B⇔A,则Φ(B)⇔Φ(A)。等值演算9/10/20219DiscreteMath.例如，对公式(p→q)→r

4、,如果用┐p∨q置换其中的p→q,则得(┐p∨q)→r.由于p→q⇔┐p∨q，故(p→q)→r⇔(┐p∨q)→r。类似地，可进行如下等值演算：(p→q)→r⇔(┐p∨q)→r⇔┐(┐p∨q)∨r⇔(p∧┐q)∨r⇔(p∨r)∧(┐q∨r)为简便起见,以后凡用到置换规则时,均不必标出。(蕴含等值式，置换规则）(蕴含等值式，置换规则）(德摩根律，置换规则）(分配律，置换规则）等值演算-例子9/10/202110DiscreteMath.例2.3用等值演算证明:(p∨q)→r⇔(p→r)∧(q→r)注：用等值演算证明等值式时，既可以从左向右推演，也可以从右向左推演。证：(p→r)∧(q→

5、r)⇔(┐p∨r)∧(┐q∨r)⇔(┐p∧┐q)∨r⇔┐(p∨q)∨r⇔(p∨q)→r(蕴含等值式)(分配律)(德摩根律)(蕴含等值式)例2.39/10/202111DiscreteMath.证明：(p→q)→r⇔p→(q→r）.方法三:记A=(p→q)→r,B=p→(q→r)。先将A,B等值演算化成易于观察真值的公式，再进行判断。A=(p→q)→r⇔(┐p∨q)→r⇔┐(┐p∨q)∨r⇔(p∧┐q)∨rB=p→(q→r)⇔┐p∨(┐q∨r)⇔┐p∨┐q∨r易见，000，010是A的成假赋值，而它们是B的成真赋值。方法二：观察法。(p→q)→r⇔p→(q→r)。证方法一：真值表法。

6、故(蕴含等值式)(蕴含等值式)(德摩根律)(蕴含等值式)(结合律)例249/10/202112DiscreteMath.(1)（p→q)∧p→q;(2)┐(p→(p∨q))∧r;(3)p∧(((p∨q)∧┐p)→q).解:(1)（p→q)∧p→q⇔(┐p∨q)∧p→q⇔┐((┐p∨q)∧p)∨q⇔(┐(┐p∨q)∨┐p)∨q⇔((p∧┐q)∨┐p)∨q⇔((p∨┐p)∧(┐q∨┐p))∨q⇔(1∧(┐q∨┐p))∨q⇔(┐q∨┐p)∨q⇔(┐q∨q)∨┐p⇔1∨┐p⇔1故(p→q)∧p→q是重言式。用等值演算判断下列公式的类型(蕴含等值式)(蕴含等值式)(德摩根律)(德摩根律)(分

7、配律)(排中律)(同一律）(交换律，结合律）（排中律）（零律）例2.59/10/202113DiscreteMath.(2)┐(p→(p∨q))∧r⇔┐(┐p∨p∨q)∧r⇔(p∧┐p∧┐q)∧r⇔(0∧┐q)∧r⇔0∧r⇔0故┐(p→(p∨q))∧r是矛盾式。(蕴含等值式，结合律）(德摩根律）(矛盾律）(零律)(零律）例2.5（续）9/10/202114DiscreteMath.p∧(((p∨q)∧┐p)→q)⇔p∧(┐((p∨q)∧┐p)∨q)(蕴含等值式)⇔p∧