关闭

关闭

关闭

封号提示

内容

首页 离散数学

离散数学

离散数学

王乐乐
2010-12-19 0人阅读 0 0 0 暂无简介 举报

简介:本文档为《离散数学ppt》,可适用于自然科学领域

离散数学DiscreteMathematics第二章命题逻辑等值演算ChapterTwoPropositionLogic第二章内容第二章内容等值式析取范式与合取范式联结词的完备集等值式定义基本等值式等值演算(置换规则)简单析取(合取)式极大(小)项(主)析(合)取范式真值函数联结词完备集可满足性问题与消解法哑元设公式A、B中总共含有命题变项p,p,…pn但A或B并不全含有这些变项。如果某个变项未在公式A中出现则称该变项为A的哑元。同样可定义B的哑元。在讨论A与B是否有相同的真值表时应将哑元考虑在内即将A、B都看成含所有p,p,…pn的命题公式如果在所有n个赋值下A与B的真值相同则AB为重言式。哑元定义定义设A,B是两个命题公式若A,B构成的等价式A↔B为重言式则称A与B是等值的,记为A⇔B。例判断公式┐(p∨q)与┐p∧┐q是否等值。解:用真值表法判断,如下:注:A与B等值当且仅当A与B的真值表相同。因此检验A与B是否等值也可通过检查A与B的真值表是否相同来实现。从表中可见┐(p∨q)与┐p∨┐q等值。定义例判断下列两组公式是否等值:()p→(q→r)与(p∧q)→r()(p→q)→r与(p∧q)→r。解:所给的个公式的真值表如下:由真值表可见p→(q→r)⇔(p∧q)→r,例判断下列两组公式是否等值:等值式模式当命题公式中变项较多时用上述方法判断两个公式是否等值计算量很大。为此人们将一组经检验为正确的等值式作为等值式模式通过公式间的等值演算来判断两公式是否等值。常用的等值式模式如下:双重否定律:A⇔┐(┐A)幂等律:A⇔A∨A,A⇔A∧A交换律:A∨B⇔B∨A,A∧B⇔B∧A结合律:(A∨B)∨C⇔A∨(B∨C),(A∧B)∧C⇔A∧(B∧C)分配律:A∨(B∧C)⇔(A∨B)∧(A∨C)(∨对∧的分配律)A∧(B∨C)⇔(A∧B)∨(A∧C)(∧对∨的分配律)德摩根律:┐(A∨B)⇔┐A∧┐B,┐(A∧B)⇔┐A∨┐B吸收律:A∨(A∧B)⇔A,A∧(A∨B)⇔A等值式模式等值式模式(续)零律:A∨⇔,A∧⇔同一律:A∨⇔A,A∧⇔A排中律:A∨┐A⇔矛盾律:A∧┐A⇔蕴含等值式:A→B⇔┐A∨B等价等值式:(A↔B)⇔(A→B)∧(B→A)假言易位:A→B⇔┐B→┐A等价否定等值式:A↔B⇔┐A↔┐B归谬论:(A→B)∧(A→┐B)⇔┐A等值式模式(续)等值演算利用这组个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为等值演算。在等值演算中,经常用到如下置换规则。置换规则:设Φ(A)是含公式A的命题公式Φ(B)是用公式B置换了Φ(A)中所有的A后所得的公式。若B⇔A,则Φ(B)⇔Φ(A)。等值演算等值演算例子例如对公式(p→q)→r,如果用┐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)为简便起见,以后凡用到置换规则时,均不必标出。(蕴含等值式置换规则)(蕴含等值式置换规则)(德摩根律置换规则)(分配律置换规则)等值演算例子例例用等值演算证明:(p∨q)→r⇔(p→r)∧(q→r)注:用等值演算证明等值式时既可以从左向右推演也可以从右向左推演。证:(p→r)∧(q→r)⇔(┐p∨r)∧(┐q∨r)⇔(┐p∧┐q)∨r⇔┐(p∨q)∨r⇔(p∨q)→r (蕴含等值式)(分配律)(德摩根律)(蕴含等值式) 例例证明:(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 易见是A的成假赋值而它们是B的成真赋值。方法二:观察法。证方法一:真值表法。故(蕴含等值式)(蕴含等值式)(德摩根律)(蕴含等值式)(结合律)例例()(p→q)∧p→q()┐(p→(p∨q))∧r()p∧(((p∨q)∧┐p)→q)解:()(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⇔(∧(┐q∨┐p))∨q⇔(┐q∨┐p)∨q⇔(┐q∨q)∨┐p⇔∨┐p⇔故(p→q)∧p→q是重言式。用等值演算判断下列公式的类型(蕴含等值式)(蕴含等值式)(德摩根律)(德摩根律)(分配律)(排中律)(同一律)(交换律结合律)(排中律)(零律)例例(续)()┐(p→(p∨q))∧r⇔┐(┐p∨p∨q)∧r⇔(p∧┐p∧┐q)∧r⇔(∧┐q)∧r⇔∧r⇔故┐(p→(p∨q))∧r是矛盾式。(蕴含等值式结合律)(德摩根律)(矛盾律)(零律)(零律)例(续)例(续)p∧(((p∨q)∧┐p)→q)⇔p∧(┐((p∨q)∧┐p)∨q)(蕴含等值式)⇔p∧(┐((p∧┐p)∨(q∧┐p))∨q)(分配律)⇔p∧(┐(∨(q∧┐p))∨q)(矛盾律)⇔p∧(┐(q∧┐p))∨q)(同一律)⇔p∧((┐q∨p)∨q)(德摩根律双重否定律)⇔p∧((┐q∨q)∨p)(交换律结合律)⇔p∧(∨p)(排中律)⇔p∧(零律)⇔p(同一律) 可见()中公式不是重言式因为都是成假赋值它也不是矛盾式因为都是其成真赋值故它是可满足式。例(续)例例例在某次研讨会的休息时间名与会者根据王教授的口音对他是哪个省市的人进行了判断:甲说王教授不是苏州人是上海人。乙说王教授不是上海人是苏州人。丙说王教授不是上海人也不是杭州人。听完人的判断王教授笑着说他们人中有一人说得全对有一人说对了一半有一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人?解:设命题p,q,r分别表示:王教授是苏州、上海、杭州人。则p,q,r中必有一个真命题两个假命题。要通过逻辑演算将真命题找出来。设:甲的判断为:A=┐p∧q乙的判断为:A=p∧┐q丙的判断为:A=┐q∧r。例(续)例(续)那么甲的判断全对:B=A=┐p∧q甲的判断对一半:B=((┐p∧┐q)∨(p∧q))甲的判断全错:B=p∧┐q乙的判断全对:C=A=p∧┐q乙的判断对一半:C=((p∧q)∨(┐p∧┐q))乙的判断全错:C=┐p∧q丙的判断全对:D=A=┐q∧┐r丙的判断对一半:D=((q∧┐r)∨(┐q∧r))丙的判断全错:D=q∧r由王教授所说E=(B∧C∧D)∨(B∧C∧D)∨(B∧C∧D)∨(B∧C∧D)∨(B∧C∧D)∨(B∧C∧D)为真命题例(续)例(续)B∧C∧D=(┐p∧q)∧((p∧q)∨(┐p∧┐q))∧(q∧r)((┐p∧q∧┐q∧r)∨(┐p∧q∧p∧r)B∧C∧D=(┐p∧q)∧(┐p∧q)∧((q∧┐r)∨(┐q∧r))(┐p∧q∧┐r)∨(┐p∧q∧┐q∧┐r)┐p∧q∧┐rB∧C∧D=((┐p∧┐q)∨(p∧q))∧(p∧┐q)∧(q∧r)(┐p∧p∧p∧┐q∧q∧r)∨(p∧q∧┐q∧r)类似可得B∧C∧D,B∧C∧Dp∧┐q∧r,B∧C∧D于是由同一律可知E(┐p∧q∧┐r)∨(p∧┐q∧r)但因为王教授不能既是苏州人又是杭州人因而p,r必有一个为假命题即p∧┐q∧r。于是E┐p∧q∧┐r为真命题因而必有p,r为假命题q为真命题即王教授为上海人甲说得全对丙说对了一半而乙全说错啦。§析取范式与合取范式定义命题变项及其否定统称作文字。仅由有限个文字构成的析取式称作简单析取式仅由有限个文字构成的合取式称作简单合取式。§析取范式与合取范式例如:p┐pq∨┐qp∨┐q┐p∨┐q∨r都是简单析取式p┐pq∧q┐p∧┐q∧r┐p∧p∧r都是简单合取式。注:单个文字既是简单析取式又是简单合取式。定理()一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式()一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及其否定式。定义例如:(p∧┐q)∨(┐q∧┐r)∨r是一个析取范式而(p∨q∨r)∧(┐p∨┐q)∧r是一个合取范式。注:单个文字既是简单析取式又是简单合取式。因此形如┐p∧q∧r的公式既是由一个简单合取式构成的析取范式又是由三个简单析取式构成的合取范式。类似地形如p∨┐q∨r的公式既可看成析取范式也可看成合取范式。定义由有限个简单合取式构成的析取式称为析取范式由有限个简单析取式构成的合取式成为合取范式析取范式与合取范式统称为范式。定义范式的一般形式析取范式的一般形式:A⇔AA…An,其中Ai(i=,…,n)是简单合取式合取范式的一般形式:A⇔AA…An,其中Ai(i=,…,n)是简单析取式。定理()一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式()一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。范式的一般形式范式存在定理定理(范式存在定理)任一命题公式都存在着与之等值的析取范式与合取范式。证明:首先由蕴含等值式和等价等值式可知:A→B⇔┐A∨B,A↔B⇔(┐A∨B)∧(A∨┐B)。由双重否定律和德摩根律可知:┐┐A⇔A,┐(A∧B)⇔┐A∨┐B,┐(A∨B)⇔┐A∧┐B。利用分配律可得:A∧(B∨C)⇔(A∧B)∨(A∧C)A∨(B∧C)⇔(A∨B)∧(A∨C)。使用这些等值式便可将任一公式化成与之等值的析取范式或合取范式。范式存在定理求范式的步骤求给定公式的范式的步骤:()消去联结词→和↔()否定号┐的消去(双重否定)或内移(德摩根律)()利用∨对∧的分配律求合取范式利用∧对∨的分配律求析取范式。求范式的步骤例解:()合取范式:(p→q)↔r⇔(┐p∨q)↔r⇔((┐p∨q)→r)∧(r→(┐p∨q))⇔(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q))⇔((p∧┐q)∨r)∧(┐p∨q∨┐r)⇔(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)()析取范式(p→q)↔r⇔((p∧┐q)∨r)∧(┐p∨q∨┐r)⇔(p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)⇔(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)(消去→)(消去↔)(消去→)(否定号内移,结合律,交换律)(∨对∧的分配律)(见上述第一至四步)(∧对∨的分配律)(矛盾律和同一律)例求公式(p→q)↔r的析取范式与合取范式。范式的注解注:在演算过程中利用交换律可使每个简单析取式或简单合取式中命题变项都按字典序出现。上述求析取范式的过程中第二步和第三步结果都是析取范式。这说明命题公式的析取范式是不唯一的。同样合取范式也是不唯一的。为了得到唯一的规范化形式的范式需要定义主析取范式和主合取范式。为此先引入如下极小项和极大项概念。范式的注解极大、小项定义定义在含有n个命题变项的简单合取式(简单析取式)中若每个命题变项和它的否定式恰好出现一个且仅出现一次并且命题变项或其否定式按下标从小到大或按字典序排列)则称该简单合取式(简单析取式)为极小项(极大项)。注:由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次因而n个命题变项共可产生n个不同的极小项。每个极小项仅有一个成真赋值若一个极小项的成真赋值对应的二进制数转化为十进制数为i则将该极小项记为mi。类似地n个命题变项可产生n个不同的极大项。每个极大项只有一个成假赋值。若一个极大项的成假赋值对应的十进制数为i则将该极大项记为Mi。极大、小项定义极大、小项真值表两个变项p、q形成的极小项与极大项┐p∧┐q┐p∧qp∧┐qp∧qp∨qp∨┐q┐p∨q┐p∨┐q极大、小项真值表极大、小项真值表(续)三个变项p,q,r形成的极小项与极大项极大、小项真值表(续)主范式定义定理设mi与Mi是命题变项p,p…,pn形成的极小项和极大项则┐mi⇔Mi┐Mi⇔mi。证明:略可从以上两表验证该定理。定义如果由n个命题变项构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项),则称该析取式(合取式)为主析取范式(主合取范式)。定理任何命题公式都存在着与之等值的主析取范式和主合取范式并且是唯一的。证明:见教材页。主范式定义主范式求法注:主析取范式和主合取范式的求法:()先通过等值推演将所给的命题公式化为析取范式(合取范式)()若某个简单合取式(简单析取式)A中既不含变项pi,又不含变项┐pi,则通过:A⇔A∧⇔A∧(pi∨┐pi)⇔(A∧pi)∨(A∧┐pi)或:A⇔A∨⇔A∨(pi∧┐pi)⇔(A∨pi)∧(A∨┐pi)补齐变项。()消去重复变项和矛盾式如用p,mi,分别代替p∧pmi∨mi和矛盾式等。主范式求法例解:()主析取范式由例知(p→q)↔r⇔(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)∵(┐p∧r)⇔┐p∧(┐q∨q)∧r⇔(┐p∧┐q∧r)∨(┐p∧q∧r)⇔m∨m(q∧r)⇔(┐p∨p)∧q∧r⇔(┐p∧q∧r)∨(p∧q∧r)⇔m∨m(p∧┐q∧┐r)⇔m∴(p→q)↔r⇔m∨m∨m∨m求公式(p→q)↔r的主析(合)取范式。例例(续)() 主合取范式由例知(p→q)↔r⇔(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)∵(p∨r)⇔p∨(q∧┐q)∨r⇔(p∨q∨r)∧(p∨┐q∨r)⇔M∧M(┐q∨r)⇔(p∧┐p)∨┐q∨r⇔(p∧┐q∨r)∧(┐p∨┐q∨r)⇔M∧M(┐p∨q∨┐r)⇔M∴(p→q)↔r⇔M∧M∧M∧M例(续)例例求p→q的主析取范式和主合取范式解:()主合取范式p→q⇔┐p∨q⇔M ()主析取范式p→q⇔(┐p∨q)⇔(┐p∧(┐q∨q))∨((┐p∨p)∧q)⇔(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)⇔(┐p∧┐q)∨(┐p∧q)∨(p∧q)⇔m∨m∨m例关于主合取范式的两点说明.主合取范式可由主析取范式直接得到。设公式A含有n个变项A的主析取范式为未在主析取范式中出现的极小项设为事实上因则A的主合取范式为:故关于主合取范式的两点说明关于主合取范式的两点说明例由公式的主析取范式求主合取范式:()A⇔m∨m,(A含两个变项p,q)()B⇔m∨m∨m(B含三个变项p,q,r)。解:()主析取范式中未出现的极小项为:m,m,故A的主合取范式为:A⇔M∧M。()主析取范式中未出现的极小项为m,m,m,m,m故A的主合取范式为:A⇔M∧M∧M∧M∧M。重言式与矛盾式的主合取范式重言式无成假赋值因而其主合取范式不含任何极大项。重言式的主合取范式记为。矛盾式无成真赋值故其主合取范式含有所有n个极大项。关于主合取范式的两点说明范式的用途 主析取范式和主合取范式的用途(以主析取范式为例)。求公式的成真与成假赋值对含有n个变项的命题公式A若其主析取范式含s(≤s≤n)个极小项则A有s个成真赋值它们是极小项下标的二进制表示其余n–s个赋值都是成假赋值。例如在例中(p→q)↔r⇔m∨m∨m∨m,因各极小项含三个文字故各极小项下标的长为的二进制数为该公式的成真赋值而其余赋值为成假赋值。范式的用途范式的用途 判断公式的类型设公式A中含n个变项则() A为重言式当且仅当A的主析取范式含全部n个极小项() A为矛盾式当且仅当A的主析取范式不含任取极小项。(此时记A的主析取范式为)。()  A为可满足式当且仅当A的主析取范式中至少含一个极小项。范式的用途例()┐(p→q)∧q()p→(p∨q)()(p∨q)→r解:()┐(p→q)∧q⇔┐(┐p∨q)∧q⇔p∧┐q∧q⇔()p→(p∨q)⇔┐p∨p∨q⇔(┐p∧(┐q∨q))∨(p∧(┐q∨q))∨((┐p∨p)∧q)⇔(┐p∧┐q)∨(┐p∧q)∨(p∧┐q)∨(p∧q)∨(┐p∧q)∨(p∧q)⇔(┐p∧┐q)∨(┐p∧q)∨(p∧┐q)∨(p∧q)⇔m∨m∨m∨m`利用公式的主析取范式判断公式的类型:注:另一种推演:p→(p∨q)⇔┐p∨p∨q⇔∨q⇔⇔m∨m∨m∨m该主析取范式含全部个极小项故p→(p∨q)是重言式。故┐(p→q)∧q是矛盾式。例例(续)()(p∨q)→r⇔┐(p∨q)∨r⇔(┐p∧┐q)∨r⇔(┐p∧┐q∧(┐r∨r))∨((┐p∨p)∧(┐q∨q)∧r)⇔(┐p∧┐q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧r)⇔m∨m∨m∨m∨m故该公式是可满足式,但不是重言式。例(续)范式的用途判断两公式是否等值设公式A,B共有n个变项。按n个变项求出A,B的主析取范式。若A与B有相同的主析取范式则A⇔B否则A⇔B。例判断下面两组公式是否等值。()p与(p∧q)∨(p∧┐q)()(p→q)→r与(p∧q)→r解:()p⇔p∧(┐q∨q)⇔(p∧┐q)∨(p∧q)⇔m∨m而(p∧q)∨(p∧┐q)⇔m∨m故p⇔(p∧q)∨(p∧┐q)() 因(p→q)→r⇔m∨m∨m∨m∨m而(p∧q)→r⇔m∨m∨m∨m∨m∨m∨m故(p→q)→r⇔(p∧q)→r范式的用途范式的用途例某单位欲从三人A,B,C中挑选~人出国进修。由于工作需要选派时要满足以下条件()若A去则C同去()若B去则C不能去()若C不去则A或B可以去。问应如何选派?解:设p:派A去q:派B去r:派C去。由条件得:(p→r)∧(q→┐r)∧(┐r→(p∨q))经演算得其主析取范式为:m∨m∨mm=┐p∧┐q∧rm=┐p∧q∧┐rm=p∧┐q∧r由此可知,有种选派方案:()C去A,B都不去()B去A,C都不去()A,C同去B不去。利用主析取范式和主合取式解决应用问题范式的用途本节结束语含n个变项的所有公式共有n种不同的主析取范式(主合取范式)。这是因为n个变项共可产生n个极小项(极大项)因而可产生n种主析取范式(主合取范式)(因每个极小项可以在主析取范式中出现或不出现)。A⇔B当且仅当A与B有相同的真值表又当且仅当A与B有相同的主析取范式(主合取范式)。可见真值表与主析取范式(主合取范式)是描述命题公式标准形式的两种不同的等价形式。本节结束语§联结词的完备集定义称映射F:{,}n→{,}为n元真值函数。其中{,}n表示由组成的长为n的字符串集合。注:元真值函数有=个元真值函数有=个元真值函数有=个。个一元真值函数§联结词的完备集真值函数真值函数联结词完备集注:每个真值函数与唯一的主析取范式(主合取范式))等值而每个主析取范式(主合取范式)对应无穷多个与之等值的命题公式。因此每个真值函数对应无穷多个与之等值的命题公式。另一方面由定理每个命题公式都有唯一一个真值函数与之等值。定义设S是一个联结词集合。如果任何n元(n≥))真值函数都可以由仅含S中的联结词构成的公式表示则称S是联结词完备集。定理S={┐∧∨}是联结词完备集。证:因任何n元真值函数都与唯一一个主析取范式等值而主析取范式中仅含联结词┐,∧,∨,故结论成立。联结词完备集推论S={┐,∧,∨,→}S={┐,∧,∨,→,↔}S={┐,∧}S={┐,∨}S={┐,→}证:()、()显然()因任何真值函数都可由只用完备集S={┐,∧,∨}中的联结词表示而对任意公式A和BA∨B⇔┐┐(A∨B)⇔┐(┐A∧┐B)。故任意真值函数都可用S={┐,∧}中的联结词的公式表示。因此S={┐,∧}是联结词完备集。()、()的证明留作练习。 推论:以下联结词集都是完备集:推论联结词完备集注解注:可以证明{∧,∨,→,↔}不是联结词完备集其任何子集如{∧}{∨}{∧,→}{∧,∨,→}{∧,∨,↔}等也不是联结词完备集。设S和S是两个不同的联结词完备集。用S中联结词构成的任何公式必可等值转化成用S中联结词构成的公式反之亦然。因此在某一特定的系统中只需采用一种联结词完备集即可。但在不同的应用中人们往往采用不同的联结词完备集。例如在计算机硬件设计中常用如下的“与非门”或者“或非门”来设计逻辑线路。联结词完备集注解与非、或非式定义设p,q为两个命题。复合命题“p与q的否定式”(“p或q的否定式”)称为p,q的“与非式”(“或非式”)记作p↑q(p↓q)。符号↑称作与非联结词(↓称作或非联结词)。p↑q为真当且仅当p与q不同时为真(p↓q为真当且仅当p与q同时为假)。定理{↑}和{↓}都是联结词完备集。证明:由定义p↑q=┐(p∧q),p↓q=┐(p∨q)由于{┐,∧,∨}是联结词完备集故只需证明其中每个联结词都可以由↑表示即可。事实上┐p⇔┐(p∧p)⇔p↑pp∧q⇔┐┐(p∧q)⇔┐(p↑q)⇔(p↑q)↑(p↑q)(利用前一式)p∨q⇔┐┐(p∨q)⇔┐(┐p∧┐q)⇔┐p↑┐q⇔(p↑p)↑(q↑q)与非、或非式§可满足性问题与消解法§可满足性问题与消解法

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/49

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料