离散数学(第2讲)命题逻辑2.ppt

,第1章命题逻辑(2),栾新成四川大学软件学院luanxch8599782213808024081,主要内容,命题公式及其赋值命题公式与赋值永真式矛盾式命题公式的等价基本等价式等价式的判断对偶原理,2020年6月7日,2,1.2命题合适公式与真值表,一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。(具体内容的原子命题)而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的值域是集合T，F(或0，1)。当原子命题是命题变元时，其复合命题也即为命题变元的“函数”，且该“函数”的值仍为“真”或“假”值，这样的函数可形象地称为“真值函数”,或称为命题公式,此命题公式没有确切真值。,2020年6月7日,3,命题公式,定义1-2.1由命题变元、逻辑联结词和括号按照下述规则构成的表达式称为（命题）合适公式。原子命题变元是合适公式；如果，是合适公式，则（），（），（），（），（）都是合适公式；只有经过有限次使用或得到的命题表达式才是合适公式。该公式常用符号G、H、等表示。哪些形式可以组成命题公式（？）,2020年6月7日,4,命题公式,为书写和输入计算机及计算方便起见，约定：（1）最外层括号可以省略（2）按联结词的优先级的括号可以省略联结词的优先顺序：括号最优先，符合优先次序者，可省去括号。相同联结词，按从左到右。最外层括号可省去。,2020年6月7日,5,命题公式,例2.1符号串：(P(QR)(Q(SR)；(PQ)；(P(PQ)；(PQ)(RQ)(PR)。等都是命题公式。符号串：(PQ)Q)；(PQ；(PQ(R；PQ。等都不是合法的命题公式。定义1-2.2：如公式A是公式B的一部分，则称A是B的子公式。,2020年6月7日,6,公式的解释与真值表,定义1-2.3设P1、P2、Pn是出现在公式G中的所有命题变元，指定P1、P2、Pn的一组真值（如1，0，1，0，1），则这组真值称为G的一个解释。一般来说，若有个命题变元，则应有2n个不同的解释。定义1-2.4如果公式G在某一解释下是真的，则称这一解释为G的成真赋值；如果G在某一解释下是假的，则称这一解释为G的成假赋值。将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。,2020年6月7日,7,公式的解释与真值表,如何构造真值表1）把表分成3部分2）最左边为原子变员3）中间为子式4）最后为公式例2.2构造公式G1：PQ的真值表如下：PQ和PQ的真值表完全一致,2020年6月7日,8,公式的解释与真值表,例2.3构造公式G2：(PQ)()的真值表,2020年6月7日,9,该公式对所有可能的解释取值均为0,公式的解释与真值表,例2.4构造公式G3：(PQ)的真值表该公式对所有可能的解释取值均为1,2020年6月7日,10,公式的解释与真值表,从这三个真值表可以看到一个非常有趣的事实：公式G3：(PQ)对所有可能的解释具有“真”值公式G2：(PQ)()对所有可能的解释均具有“假”值公式G1：PQ则具有“真”和“假”值,2020年6月7日,11,永真式、矛盾式、可满足公式,定义1-2.5公式G3称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G2称为永假公式(矛盾式，不可满足公式),如果在它的所有解释之下都为“假”。公式G1称为可满足公式，如果它不是永假的（即存在解释使公式取值1）。,2020年6月7日,12,永真式、矛盾式、可满足公式,永真式的特点永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可满足式,可满足式不一定是永真式。两个永真式的合取、析取、条件、双条件均为永真式。这样由简单的重言式，可以推出无数个复杂的重言式。判定给定公式是否为永真式，永假式或可满足式的问题，称为给定公式的判定问题。在逻辑研究和计算机推理以及决策判断时，人们对于所研究的命题，最关心的莫过于“真”、“假”问题，所以永真公式在数理逻辑的研究中占有特殊且重要的地位。,2020年6月7日,13,永真式的判断,命题逻辑的基本任务之一，就是找出那些属于永真式的命题公式。（1）真值表法（简单、直观）,2020年6月7日,14,永真式的判断,（2）置换（代换，代入）法如果公式A中的一些变元，用一些公式代入，而且每次出现同一变元时，总用同一公式代入，就可从公式A得到公式B，则称公式B为公式A的置换（代入）实例（例式）。置换定理：永真式的任何置换（代入）实例仍是一个永真式。例如：（RS）（MN）（RS）是否为永真式PQP（永真式）对上式中的P，用（RS）代入，对Q，用（MN）代入后得到：（RS）（MN）（RS）该公式也是一个永真式,2020年6月7日,15,永真式的判断,（3）公式推演法（等价变换、替换（取代）规（范）则）具体方法在下节中介绍,2020年6月7日,16,1.3命题公式的等价,定义1-3.1设G、H是公式，如果在任意解释下，G与H的真值相同，则称公式G、H是等价的，记作GH。定理1-3.2公式G、H等价的充分必要条件是公式GH是永真公式。此定理是从另一角度来看待等价性等价式的性质:1）自反性：AA2）对称性：若AB，则BA3）可传递性:若AB，BC，则AC,2020年6月7日,17,基本等价式,“”与“”的区别首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH的结果不是命题公式。（公式是否可以替换）其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式,2020年6月7日,18,基本等价式,基本等价式命题定律Equivalence设G，H，S是任何的公式，则：1:(GH)(GH)(HG)(等价)2：(GH)(GH)(蕴涵)3：GGG(幂等律)4：GGG5：GHHG(交换律)6：GHHG7：G(HS)(GH)S(结合律)8:G(HS)(GH)S9：G(GH)G(吸收律)10：G(GH)G,2020年6月7日,19,基本等价式,11：G(HS)(GH)(GS)(分配律)12：G(HS)(GH)(GS)13：GFG(同一律)14：GTG15：GTT(零律)16：GFF17：GGT(矛盾律),2020年6月7日,20,基本等价式,18：GGF19：(G)G(双重否定律)20：（GH)SG（HS）（输出律）21：（GH）(GH)(GH)(排中律)22：PQQP（逆反律）23：(GH)GH(DeMorgan定律)24：(GH)GH。,2020年6月7日,21,基本等价式,替换定理定理1-3.1设G1是G的子公式(即G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1H1，则GH。替换定理是经常使用的重要定理。,2020年6月7日,22,等价式的判定,1.真值表法2.公式推演（等价变换）例3.1：试证PQQP证：PQPQ蕴涵E2PQ双重否定E19QP交换律E5QPE2,2020年6月7日,23,等价式的判定,例3.2试用较少的开关设计一个与下图有相同功能的电路。,2020年6月7日,24,等价式的判定,解：可将上图所示之开关电路用下述命题公式表示：(PQS)(PRS)利用基本等价公式，将上述公式转化为：(PQS)(PRS)(PS)Q)(PS)R)(结合律)(PS)(QR)（分配律）所以其开关设计图可简化为：,2020年6月7日,25,等价式的判定,例3.3试将下图所示之逻辑电路简化。,2020年6月7日,26,PQR,并联符号,AND,AND,AND,OR,OR,与门,或门,P,Q,R,等价式的判定,解:可将上述电路写成如下命题公式：(PQ)(PR)(QR)利用基本等价公式转化为：(PQ)(PR)(QR)(P(QR)(QR)（分配律）P(QR)(幂等律)所以该电路图可简化为：,2020年6月7日,27,PQR,等价式的判定,例3.4证明P(PQ)Q)是永真公式。证：P(PQ)Q)P(PQ)Q(DeMorgan定律)(PQ)(PQ)(交换律)(结合律)T（矛盾律）,2020年6月7日,28,等价式的判定,例3.5证明P(QR)(PQ)R证：P(QR)P(QR)（蕴涵）P(QR)（蕴涵）(PQ)R(结合律)(PQ)R（蕴涵）(PQ)R（蕴涵）,2020年6月7日,29,等价式的判定,例3.6试证明(P(QR)(PQR)P证明：(P(QR)(PQR)P(QR)(QR)（分配律）P(QR)(QR)(DeMorgan定律)PT（矛盾律）P(同一律),2020年6月7日,30,等价式的判定,例3.7试证明(P(QR)(QR)(PR)R证明：(P(QR)(QR)(PR)(PQ)R）(QP)R)（结合律、分配律）(PQ)R)(QP)R)(DeMorgan定律)(PQ)(QP)）R（分配律）TR(交换律、矛盾律）R（同一律）,2020年6月7日,31,等价式的判定,将下列语句化简：情况并非如此：如果他不来，那么我也不去。解：设P：他来，Q：我去此语句为：（PQ）化简（PQ）（PQ）（PQ）PQ我去了但他没来。,2020年6月7日,32,等价式的判定,世界冰球赛在激烈地进行，看台上三位观众正在热烈地议论着这场比赛的名次。甲：中国第一，匈牙利第三；乙：奥地利第一，中国第三；丙：匈牙利第一，中国第二。比赛结束后，发现三位观众每人恰好都猜对了一个。问：中国、奥地利、匈牙利各队的名次各是第几（无并列名次）？,2020年6月7日,33,等价式的判定,解：设命题如下：P1：中国第一，P2：中国第二，P3：中国第三,Q1:奥地利第一,R1:匈牙利第一,R3:匈牙利第三由于甲、乙、丙各猜对了一个，故有等值式（P1R3）（P1R3）1（Q1P3）（Q1P3）1（R1P2）（R1P2）1由于重言式的合取仍为重言式，先对，两式左端求合取有：,2020年6月7日,34,等价式的判定,（P1R3）（P1R3）)（Q1P3）（Q1P3）)1对式左端进行等值演算。得：（P1R3Q1P3)（P1R3Q1P3）（P1R3Q1P3）（P1R3Q1P3）1在式中，第一个合取式P1和Q1同时存在，即中国第一和奥地利第一同时成立。在逻辑上是矛盾的，因此，把它消去。同理，第三、四个合取式消去得,2020年6月7日,35,等价式的判定,P1R3Q1P31再将和作同样处理得P1R3Q1P3R1P21各命题间不再有任何矛盾。因而它们的合取为1，这意味着各命题的取值均为1。由此得结论：奥地利第一，中国第二，匈牙利第三。,2020年6月7日,36,对偶式,E3E18，E23E24都是成对出现的，它是逻辑系统对偶性的反映，即对偶式，利用对偶式可以扩大等价式的个数，也可减少证明的次数。定义：在给定的仅使用联结词、的命题公式A中，若把和，F和T互换而得的公式A*，则称A*为A的对偶（公）式。将公式中的命题变为其否定，所得公式为A的相反式。如公式（PQ）R的对偶式为（PQ）RP（QR）的对偶式为P（QR）,2020年6月7日,37,对偶式,问题：如果两个公式等价，那么它们的对偶式是否也是等价的？引理：设P1,P2,Pn是公式A和A*中的所有命题变元，则A（P1,P2,Pn）A*（P1,P2,Pn）A(P1,P2,Pn)A*(P1,P2,Pn)证：由DeMorgan定律可知（PQ）PQ，（PQ）PQTF，FT对公式的否定可以直接作用到原子本身，并且把公式中的变成，把变成，即得A（P1,P2,Pn）A*（P1,P2,Pn）,2020年6月7日,38,对偶式,对偶原理设A和B是两个命题公式，若AB，则A*B*例3.8证明（a）(PQ)(P(PQ)PQ（b）(PQ)(P(PQ)PQ证明:（a）(PQ)(P(PQ)(PQ)(P(PQ)（蕴涵）(PQ)(PQ)(幂等律)(PP)(QP)Q(结合律)（分配律）PQQPQ（矛盾律）(同一