命题逻辑的等值和推理演算PPT讲稿.ppt

命题逻辑的等值和推理演算第1页，共74页，编辑于2022年，星期六n本章对命题等值和推理演算进行讨论，是以语义的观点进行的非形式的描述，不仅直观且容易理解，也便于实际问题的逻辑描述和推理。n严格的形式化的讨论见第三章所建立的公理系统。第2页，共74页，编辑于2022年，星期六2.1 等值定理 n若把初等数学里的、等运算符看作是数与数之间的联结词，那么由这些联结词所表达的代数式之间，可建立许多等值式如下：x2y2=(xy)(xy)(xy)2=x22xyy2 sin2xcos2x=1在命题逻辑里也同样可建立一些重要的等值式。第3页，共74页，编辑于2022年，星期六2.1.1 等值的定义 n给定两个命题公式A和B,而P1Pn是出现于A和B中的所有命题变项,那么公式A和B共有2n个解释,若对其中的任一解释,公式A和B的真值都相等,就称A和B是等值的(或等价的)。记作A=B或A B。第4页，共74页，编辑于2022年，星期六n显然，可以根据真值表来判明任何两个公式是否是等值的。第5页，共74页，编辑于2022年，星期六例1:证明(PP)Q=Q证明:画出(PP)Q与Q的真值表可看出等式是成立的。第6页，共74页，编辑于2022年，星期六例2:证明PP=QQn证明:画出PP,QQ的真值表,可看出它们是等值的,而且它们都是重言式。第7页，共74页，编辑于2022年，星期六n从例1、2还可说明,两个公式等值并不要求它们一定含有相同的命题变项。若仅在等式一端的公式里有变项P出现,那么等式两端的公式其真值均与P无关。例1中公式(PP)Q与Q的真值都同P无关,例2中PP,QQ都是重言式,它们的真值也都与P、Q无关。第8页，共74页，编辑于2022年，星期六2.1.2 等值定理 n定理 对公式A和B,A=B的充分必要条件是A B是重言式。n若A B为重言式(A、B不一定都是简单命题,可能是由简单命题P1,Pn构成的对A,B的一个解释,指的是对P1,Pn的一组具体的真值设定),则在任一解释下A和B都只能有相同的真值,这就是定理的意思。第9页，共74页，编辑于2022年，星期六证明n若A B是重言式,即在任一解释下,A B的真值都为T。依A B的定义只有在A、B有相同的值时,才有A B=T。于是在任一解释下,A和B都有相同的真值,从而有A=B。反过来，若有A=B,即在任一解释下A和B都有相同的真值,依A B的定义,A B只有为真,从而A B是重言式。第10页，共74页，编辑于2022年，星期六n有了这个等值定理，证明两个公式等值，只要证明由这两个公式构成的双条件式是重言式即可。第11页，共74页，编辑于2022年，星期六不要将“”视作联结词，在合式公式定义里没有“”出现。A=B是表示公式A与B的一种关系。这种关系具有三个性质:1.自反性 A=A。2.对称性 若A=B则B=A。3.传递性若A=B,B=C则A=C。这三条性质体现了“”的实质含义。第12页，共74页，编辑于2022年，星期六2.2 等值公式2.2.1 基本的等值公式(命题定律)1.双重否定律P=P2.结合律(PQ)R=P(QR)(PQ)R=P(QR)(P Q)R=P (Q R)第13页，共74页，编辑于2022年，星期六3.交换律PQ=QPPQ=QPP Q=Q P4.分配律P(QR)=(PQ)(PR)P(QR)=(PQ)(PR)P(QR)=(PQ)(PR)5.等幂律(恒等律)PP=PPP=PPP=TPP=T第14页，共74页，编辑于2022年，星期六6.吸收律P(PQ)=PP(PQ)=P7.摩根律(PQ)=PQ(PQ)=PQ对蕴涵词、双条件词作否定有(PQ)=PQ(PQ)=PQ=PQ=(PQ)(PQ)第15页，共74页，编辑于2022年，星期六n8.同一律nPF=PnPT=PnTP=PnTP=Pn还有nPF=PnFP=P第16页，共74页，编辑于2022年，星期六 9.零律PT=TPF=F还有PT=TFP=T10.补余律PP=TPP=F还有PP=PPP=PPP=F 第17页，共74页，编辑于2022年，星期六n所有这些公式，都可使用直值表加以验证。第18页，共74页，编辑于2022年，星期六Venn图n若使用Venn图也容易理解这些等值式,这种图是将P、Q理解为某总体论域上的子集合,而规定PQ为两集合的公共部分(交集合),PQ为两集合的全部(并集合),P为总体论域(如矩形域)中P的余集。第19页，共74页，编辑于2022年，星期六从Venn 图因PQ较P来得“小”,PQ较P来得“大”，从而有P(PQ)=PP(PQ)=P第20页，共74页，编辑于2022年，星期六对这些等式使用自然用语加以说明，将有助于理解。如P表示张三是学生,Q表示李四是工人,那么(PQ)就表示并非“张三是学生或者李四是工人”。这相当于说，“张三不是学生而且李四也不是工人”，即可由PQ表示,从而有(PQ)=PQ。第21页，共74页，编辑于2022年，星期六2.2.2 若干常用的等值公式 n由于人们对、更为熟悉，常将含有和的公式化成仅含有、的公式。这也是证明和理解含有，的公式的一般方法。n公式11-18是等值演算中经常使用的,也该掌握它们,特别是能直观地解释它们的成立。第22页，共74页，编辑于2022年，星期六11.PQ=P Qn通常对PQ进行运算时,不如用PQ来得方便。而且以PQ表示PQ帮助我们理解如果P则Q的逻辑含义。问题是这种表示也有缺点，丢失了P、Q间的因果关系。第23页，共74页，编辑于2022年，星期六12.PQ=QPn如将PQ视为正定理,那么QP就是相应的逆否定理,它们必然同时为真,同时为假,所以是等值的。第24页，共74页，编辑于2022年，星期六13.P(QR)=(PQ)RnP是(QR)的前提,Q是R的前提,于是可将两个前提的合取PQ作为总的前提。即如果P则如果Q则R,等价于如果P与Q则R。第25页，共74页，编辑于2022年，星期六14.PQ=(PQ)(PQ)n这可解释为PQ为真,有两种可能的情形,即(PQ)为真或(PQ)为真。而PQ为真,必是在P=Q=T的情况下出现,PQ为真,必是在P=Q=F的情况下出现。从而可说,PQ为真,是在P、Q同时为真或同时为假时成立。这就是从取真来描述这等式。第26页，共74页，编辑于2022年，星期六15.PQ=(PQ)(PQ)n这可解释为PQ为假,有两种可能的情形,即(PQ)为假或(PQ)为假,而PQ为假,必是在P=F,Q=T的情况下出现,PQ为假,必是在P=T,Q=F的情况下出现。从而可说PQ为假,是在P真Q假或P假Q真 时成立。这就是从取假来描述这等式 第27页，共74页，编辑于2022年，星期六16.PQ=(PQ)(QP)n这表明PQ成立,等价于正定理PQ和逆定理QP都成立。第28页，共74页，编辑于2022年，星期六17.P(QR)=Q(PR)n前提条件P、Q可交换次序。第29页，共74页，编辑于2022年，星期六18.(PR)(QR)=(PQ)Rn左端说明的是由P而且由Q都有R成立。从而可以说由P或Q就有R成立,这就是等式右端。第30页，共74页，编辑于2022年，星期六2.2.3 置换规则 定理:对公式A的子公式,用与之等值的公式来代换便称置换。置换规则 公式A的子公式置换后A化为公式B,必有A=B。当A是重言式时,置换后的公式B必也是重言式。n置换与代入是有区别的。置换只要求A的某一子公式作代换,不必对所有同一的子公式都作代换。第31页，共74页，编辑于2022年，星期六2.2.4 等值演算举例 例1:证明(P(QR)(QR)(PR)=R证明:左端=(P(QR)(QP)R)(分配律)=(PQ)R)(QP)R)(结合律)=(PQ)R)(QP)R)(摩根律)=(PQ)(QP)R(分配律)=(PQ)(PQ)R(交换律)=TR(置 换)=R(同一律)第32页，共74页，编辑于2022年，星期六例2:试证 (PQ)(P(QR)(PQ)(PR)=T证明:左端=(PQ)(P(QR)(PQ)(PR)(摩根律)=(PQ)(PQ)(PR)(PQ)(PR)(分配律)=(PQ)(PR)(PQ)(PR)(等幂律)=T第33页，共74页，编辑于2022年，星期六2.6 范式nn 个命题变项所能组成的具有不同真值的命题公式仅有22n个,然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个。这样，首先就要问凡与命题公式A等值的公式，能否都可以化为某一个统一的标准形式。希望这种标准形能为我们的讨论带来些方便，如借助于标准形对任意两个形式上不同的公式，可判断它们的是否等值。借助于标准形容易判断任一公式是否为重言式或矛盾式。第34页，共74页，编辑于2022年，星期六求解公式的成真指派和成假指派 n一个公式，其中含有命题变元P1,Pn,表示为 P1,Pn，（P1,Pn）称为变元组，公式的变元组（P1,Pn）的任意一组确定的值，称为对该公式的关于该变元组（P1,Pn）的一个完全指派。如果仅对变元组中的部分变元确定值，其余变元没有赋以确定的值，则称这样的一组值为该公式的关于变元组的一个部分指派。第35页，共74页，编辑于2022年，星期六完全指派与部分指派例如公式 ：p(qr)。变元组为（p，q，r），一个完全指派为（T，F，F），在此指派下，公式取真值。即=T。可这样来表示：（p，q，r）=（T，F，F）=T或者有时记为：（p，q，r）=（T，F，F）=T 一个部分指派为（T，T，）这时候 的值不能确定，当r=T时，=T，当r=F时，=F。这一点通常都能理解，因为一个公式的值取决于公式中所含变元的值，当其中某些变元未确定时，公式最终的值也不能定。但是这一点也未必绝对，例如，赋（p，q，r）以（F，X，X）时，公式肯定是取假值，即=F。这时候可看出对q，r 的指派已经无关紧要了。第36页，共74页，编辑于2022年，星期六成真指派与成假指派n定义：对于任一公式，凡是使得 取真值=T 的指派，不管是完全指派还是部分指派，都称为 的成真指派。凡是使 取假值=F 的指派，不管是完全指派还是部分指派，都称为 的成假指派。第37页，共74页，编辑于2022年，星期六例子：P 的成真指派 P=F,成假指派P=T。：PQ 的成真指派（P，Q）=（T，T）成假指派（P，Q）=（F，F），（F，T），（T，F）：PQ 的成真指派（P，Q）=（T，T），（T，F），（F，T）成假指派（P，Q）=（F，F）第38页，共74页，编辑于2022年，星期六永真式、永假式、可满足式有的公式没有成真指派，如：PP,称为永假式（反驳式）；有的公式没有成假指派，如：PP,称为永真式（重言式）。永假式，又称为矛盾式，不可满足。如果一个公式，有成真指派，则称为公式 可满足。与它相对的，如果没有成真指派，就是不可满足的。如果一个公式，有成假指派，则称该公式为非永真公式。第39页，共74页，编辑于2022年，星期六部分指派公式 的变元组（P1,Pn），一个部分指派：（V1,Vi-1,X,Vi+1,Vn），其中Vi为具体真假值。它为公式 的成真指派，当且仅当：（V1,Vi-1,T,Vi+1,Vn）及（V1,Vi-1,F,Vi+1,Vn）均为成真指派。成假指派情况是相似的。第40页，共74页，编辑于2022年，星期六求解成真指派和成假指派的方法n一个直截了当的办法是将公式 的所有完全指派全都列举出来，逐个验算该指派下 取的真假值，从而确定每个完全指派是成真指派还是成假指派。但是，含n个变元的公式，共有2n个完全指派，当n为5、6、时，指数的总数就会相当可观，按指数级数增长，难以全部枚举。因此应当选择更为简单、可行的办法部分指派。求部分指派的前提是将原来的公式 化简，使得原来含有n个变元的公式化为可能含变元数更少的公式，于是便大大地削减了运算的数量。第41页，共74页，编辑于2022年，星期六部分指派的步骤n第一步，否定深入。将外层的否定深入到内层，一直深入到变元为止。n第二步，部分指派。选定一个变元对其作真和假两种指派，得到两个不含该变元但较原式简单的公式。如果这两个公式直接得到真假值，则得部分指派，否则n第三步，化简。得到的两公式虽然较原公式简单，但仍含有变元，于是重复第二步，逐个减少变元，直到确定真假值为止。n第二步中如何选定一个变元，希望化简效果最好，因此选择在公式中出现次数最多的变元作指派。还有一种情况就是对该变元赋以一个指派后，立即使整个公式有确定的真假值。第42页，共74页，编辑于2022年，星期六试求给定公式的成真成假指派n：(p r)(p q)(p (q r)n第一步 否定深入：n (p r)(p q)(p (q r)n第二步 部分指派：选择出现最多的命题，指派以T,F。（分别情况）。n 上式中，P出现最多，故 分为 p=T n p=F两种情况。第43页，共74页，编辑于2022年，星期六 p=T：(T r)（T q）（T (q r)）化简(q(q r)也可最终化简为r，p=F：(F r)（F q）（F (q r)）化简得 r（T F）最终化简得r组合起来，的成真指派（p,q,r）=(T,X,F),(F,X,T),成假指派（p,q,r）=(T,X,T),(F,X,F)。第44页，共74页，编辑于2022年，星期六不完全成真指派(p,q,r):(T,X,F)可以生成相应的完全成真指派 (T,T,F)和(T,F,F)。(p,q,r):(F,X,T)(F,T,T)和(F,F,T)。因此，写完整的话，的完全成真指派：(T,T,F)，(T,F,F)，(F,T,T)，(F,F,T)。相仿地，的完全成假指派：(T,X,T)(T,T,T)，(T,F,T)，(F,X,F)(F,T,F)，(F,F,F)完全成假指派：(T,T,T)，(T,F,T)，(F,T,F)，(F,F,F)。第45页，共74页，编辑于2022年，星期六析取范式如果一个完全指派能使一个合取式取真值，那么这个完全指派和合取式之间是对应的。例如：(T,T,F)，(T,F,F)，(F,T,T)，(F,F,T)p q r p q r p q r p q r 将上述四个合取式再析取，即得析取范式：（p q r）（p q r）（p q r）（p q r）第46页，共74页，编辑于2022年，星期六合取范式相仿地：对应于成假指派对应的析取式为：(T,T,T)，(T,F,T)，(F,T,F)，(F,F,F)pqrpqrpqrp q r将四个析取式再合取，即得合取范式：（pqr）（pqr）（pqr）（pqr）第47页，共74页，编辑于2022年，星期六求范式等值变换法n消去和n否定深入到变元n等值变换第48页，共74页，编辑于2022年，星期六主范式n主析取范式n主合取范式第49页，共74页，编辑于2022年，星期六2.4 联结词的完备集 除了所详述过的五个联结词外,还可定义更多的联结词。像计算机的硬件电路设计分析就常使用异或(半加):PQ=(PQ)(PQ)与非:P Q=(PQ)或非:P Q=(PQ)等联结词。问题是对n 个命题变项P1Pn 来说,共可定义出多少个联结词?还可以问,在那么多联结词中有多少是独立的?第50页，共74页，编辑于2022年，星期六2.4.1 命题联结词的个数n按照合式公式的定义，由命题变项和命题联结词可以构造出无限多个合式公式。可把所有的合式公式加以分类，将等值的公式视为同一类，从中选一个作代表称之为真值函项。对一个真值函项就有一个联结词与之对应。第51页，共74页，编辑于2022年，星期六n一元联结词是联结一个命题变项的，如P。它取值只有真假两种情形，于是联结词作用于P,可建立四种不同的真值函项,相应的可定义出四个不同的一元联结词f0f1f2f3。图6.2.4.1给出这些联结词fi或说真值函数fi(P)的定义。第52页，共74页，编辑于2022年，星期六写出真值函项：f0(P)=Ff1(P)=Pf2(P)=Pf3(P)=T其中f0(P)是永假式,f3(P)是永真式,均与P无关,而f1(P)就是变项P本身,从而新的公式只有f2(P),这就是由否定词所建立的真值函项。第53页，共74页，编辑于2022年，星期六n二元联结词联结两个命题变项，两个变项PQ共有四种取值情形,于是联结词作用于PQ可建立起16种不同的真值函项,相应的可定义出16个不同的二元联结词g0,g1,g15。图2.4.2给出了这些联结词gI或说真值函项gi(P,Q)的定义。第54页，共74页，编辑于2022年，星期六第55页，共74页，编辑于2022年，星期六写出各真值函项:g0(P,Q)=Fg1(P,Q)=PQg2(P,Q)=PQg3(P,Q)=(PQ)(PQ)=P(QQ)=Pg4(P,Q)=PQg5(P,Q)=(PQ)(PQ)=(PP)Q=Qg6(P,Q)=PQg7(P,Q)=PQg8(P,Q)=PQ=P Qg9(P,Q)=P Qg10(P,Q)=(PQ)(PQ)=(PP)Q=Qg11(P,Q)=PQ=QPg12(P,Q)=(P Q)(PQ)=P(QQ)=Pg13(P,Q)=PQ=P Qg14(P,Q)=PQ=P Qg15(P,Q)=T第56页，共74页，编辑于2022年，星期六n一般地说，对n 个命题变元P1Pn,每个Pi有两种取值,从而对P1Pn来说共有2n种取值情形。于是相应的直值函项就有22n个,或说可定义22n个n元联结词。第57页，共74页，编辑于2022年，星期六2.4.2 联结词的完备集 n由于可定义的联结词的数量是极大的,需要考虑它们是否都是独立的?也就是说这些联结词是否能相互表示呢?n定义:设C是联结词的集合，如果对任一命题公式都有由C中的联结词表示出来的公式与之等值，就说C是完备的联结词集合，或说C是联结词的完备集。第58页，共74页，编辑于2022年，星期六n显然全体联结词的无限集合是完备的,而,就不是完备的。n定理 ,是完备的联结词集合n从节2.3介绍的由真值表列写逻辑公式的过程可知,任一公式都可由,表示出来,从而,是完备的,一般情形下,这定理的证明可使用数学归纳法,施归纳于联结词的个数来论证。第59页，共74页，编辑于2022年，星期六又由于PQ=(PQ)PQ=(PQ)这说明,可由,表示,可由,表示,故,都是联结词的完备集。还可证明,也都是联结词的完备集。但,不是完备的。尽管,是完备的,但使用起来并不够方便,我们愿意采取折衷方案,不是仅用两个也不是使用过多的联结词,还是选用详细讨论过的五个联结词集,当然是完备的,只是相互并不独立。第60页，共74页，编辑于2022年，星期六最小的联结词的完备集基底 n基底：完备的联结词集合的联结词是独立的，也就是说这些联结词不能相互表示第61页，共74页，编辑于2022年，星期六基底 n只含一个联结词的:NK;NAn含两个联结词的:N,C;N,K;N,A;N,NC;F,C;T,NC;C,NE;E,NC;C,NC;n含三个联结词的:F,K,E;F,A,E;T,K,NE;T,A,NE;K,E,NE;A,E,NE;A-K-E-C-N-第62页，共74页，编辑于2022年，星期六基底 n任取四个一元或二元联结词，它们必组不成基底。第63页，共74页，编辑于2022年，星期六加法器 Ai00001111Bi00110011Ei01010101_Ci01101001Ei+100010111Ci=(AiBiEi)(AiBiEi)(AiBiEi)(AiBiEi)Ei+1=(AiBiEi)(AiBiEi)(AiBiEi)(AiBiEi)E1=0Cn+1=En+1第64页，共74页，编辑于2022年，星期六2.5 对偶式 n假定公式A仅出现、这三个联结词n定义 将A中出现的、分别以、代换,得到公式A*,则称A*是A的对偶式,或说A和A*互为对偶式。(PQ)R的对偶式为(PQ)R不难知道,若(PQ)R=(PR)(QR)成立,相应的对偶式 (PQ)R=(PR)(QR)也成立。第65页，共74页，编辑于2022年，星期六为方便,若A=A(P1,Pn)令 A=A(P1,Pn)定理2.5.1(A*)=(A*),(A)=(A)定理2.5.2 (A*)*=A,(A)=A定理2.5.3 A=A*第66页，共74页，编辑于2022年，星期六可用数学归纳法,施归纳于A中出现的联结词个数n来证明。基始:设n=0,A中无联结词,便有A=P,从而 A=P但 A*=P n=0时定理成立。第67页，共74页，编辑于2022年，星期六归纳：设n k时定理成立，来证n=k+1时定理也成立 n=k+1 1,A中至少有一个联结词，可分为三种情形。A=A1,A=A1A2,A=A1A2 其中A1,A2中联结词个数k。第68页，共74页，编辑于2022年，星期六依归纳法假设，A1=A1*,A2=A2*当 A=A1时。A=(A1)=(A1*)归纳法假设 =(A1)*定理2.5.1,2.5.2 =A*第69页，共74页，编辑于2022年，星期六当A=A1A2时。A=(A1A2)=A1A2摩根律 =A1*A2*归纳法假设 =(A1*A2*)A定义 =(A1A2)*A*定义 =A*另一种情况同理，从而定理得证。这定理实为摩根律的另一种形式。它把、*、联系起来了。第70页，共74页，编辑于2022年，星期六定理 2.5.4 若A=B必有A*=B*证明:因为A=B等价于AB 永真。从而AB 永真。依定理2.5.3,A=A*,B=B*于是 A*B*永真必有 A*B*永真故 A*=B*第71页，共74页，编辑于2022年，星期六定理2.5.5 若AB永真,必有B*A*永真定理2.5.6 A与A同永真,同可满足 A与A*同永真,同可满足对偶性是逻辑规律,给证明公式的等值和求否定都带来了方便。第72页，共74页，编辑于2022年，星期六作业(p37)1(1,3),2,3,5(8)第73页，共74页，编辑于2022年，星期六补充作业给出一组满足下列要求的能用以设计四分邮票自动出售机的电路的布尔函数：（1）每次输入一个一分、二分、五分的硬币，电路中分别用c1,c2,c5三个量表示一分、二分、五分的硬币；（2）当输入值总和小于4分时，等待输入，当大于等于4分时，输出一张四分邮票并找零。电路中邮票用变量s表示，找零之数用r1,r2,r2三个量分别表示一分、二分、二分的硬币。第74页，共74页，编辑于2022年，星期六