离散数学课件-第1章-2.ppt

1,2020/6/10,离散数学DiscreteMathematics,汪荣贵教授合肥工业大学软件学院专用课件2010.3,第一章逻辑与证明,学习内容,1.1逻辑1.2命题等价1.3谓词和量词1.4对偶与范式1.5推理规则1.6证明导论1.7证明的方法和策略1.8数理逻辑的应用,命题等价,命题公式真值表等价公式重言式和蕴含式,命题变元,如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。,复合命题,如果一个命题不能再分解成更简单的命题，则称该命题为原子命题。如果一个命题不是原子命题，称该命题为复合命题。如果用命题变元表示原子命题时，该命题变元称为原子变元。命题逻辑中，可以通过命题联结词将原子变元联结起来表示复合命题。,命题公式,把命题常元，命题变元按照一定的逻辑顺序和规则，用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。,命题公式,合式公式(wff)(wellformedformulas)：按下列规则构成的符号串称为命题演算的合式公式，也称为命题公式，简称公式。单个命题变元和常元是合式公式。如果A是合式公式，那么A是合式公式。如果A和B是合式公式，那么(AB)、(AB)、(AB)和(AB)是合式公式。当且仅当有限次地应用了、所得到的符号串是合式公式。,命题公式,上面的定义给出合式公式定义的方法称为归纳定义，它包括三部分：基础、归纳、界限其中是基础，和是归纳，是界限。以后将多次出现这种形式的定义。,命题公式,下列符号串是合式公式：(pq)，(pq)，(p(pq)，(pq)(qr)(st)下列符号串不是合式公式：(pq)(q)，(pq，(pq)q),命题公式,约定：为方便，最外层括号可以不写，合式公式可以写成：PQ，PR，(PQ)R如果规定逻辑联接词的优先级：、则：PQR也是合式公式,命题等价,命题公式真值表等价公式重言式和蕴含式,命题公式的赋值,设pl，p2，pn是出现在公式A中的全部命题变元，给pl，p2，pn各指定一个真值，称为对公式A的一个赋值或解释。若指定的赋值使A的真值为T，则称这个赋值为A的成真赋值，若使A的真值为F，则称这个赋值为A的成假赋值。例如，给公式(pqr)赋值011是指p=0，q=1，r=1，它是该公式的成真赋值；赋值110是指p=1，q=1，r=0，它是该公式的成假赋值。,真值表的概念,在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。,真值表的概念,在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。例如：,真值表的概念,说明:设P1，P2,Pn为命题公式P中的命题变量，对于命题变元每一种真值指派的可能组合，都能唯一确定P的真值（即有2的n次幂种分布）。为了有序地列出公式的真值表，在对命题变元做指派时，可以按照二进制数的次序列表。,【例】构造命题公式pq的真值表，并求成真赋值和成假赋值。解：命题公式pq的真值表如表1.6所示。00，01，11是成真赋值，10是成假赋值。,【例】构造命题公式(pq)(pq)的真值表，并求成真赋值和成假赋值。解：命题公式(pq)(pq)的真值表如下表所示。00，11是成真赋值，01，10是成假赋值。,为了有序地列出A(P1,P2,Pn)的真值表，可以将F看成0，将T看成1，按照二进制数000,0001,00010,1110,111(即十进制的0,1,2,.,2n-1)的次序进行指派列真值表。如A(P,Q)的真值表可按照如下次序指派：00(F,F)，01(F,T)，10(T,F)，11(T,T)如A(P,Q,R)的真值表可按照如下次序指派：000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T),真值表构造总结,例如列出P(QR)的真值表,观察下面的真值表,在上面的真实表中你是否发现什么问题？,命题等价,命题公式真值表等价公式重言式和蕴含式,命题公式的等价,AB的定义：A、B是含有命题变元P1,P2,Pn的命题公式，如不论对P1,P2,Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价，记作AB。显然PQPQ（PQ）（PQ）PQ提示：判断两个公式是否等价，更好的方法是当变元数不多时，直接构造两个公式的真值表，看两个真值表是否相等即可。,命题公式的等价,可以证明（例如可以用真值表证明）：命题公式等价有下面的三条性质：自反性，即对任意命题公式A，AA对称性，即对任意命题公式A和B，若AB，则BA传递性，即对任意命题公式A，B和C，若AB，BC，则AC,命题公式的等价,【例】根据等价的定义，用真值表证明p(qp)p(pq)证明：构造p(qp)和p(pq)的真值表，如下表所示。p(qp)和p(pq)所在的列完全相同，它们具有相同的真值表。所以p(qp)p(pq),命题公式的等价,证明等价的另外一种方法叫做等价演算法，其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。基本等价式常叫命题定律。下面是常用的命题定律：1.双重否定律AA2.交换律ABBA，ABBA3.结合律(AB)CA(BC)(AB)CA(BC),命题公式的等价,4.分配律A(BC)(AB)(AC)A(BC)(AB)(AC)5.德摩根律(AB)AB(AB)AB6.幂等律AAA，AAA7.吸收律A(AB)A，A(AB)A8.零律A11，A00,命题公式的等价,9.同一律A0A，A1A10.排中律AA111.矛盾律AA012.条件等价式ABAB13.双条件等价式AB(AB)(BA)14.假言易位式ABBA15.双条件否定等价式ABAB,命题公式的等价,以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律：(AB)AB下表是(AB)和AB的真值表，从表中可以看出德摩根律成立。,命题公式的等价,以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律：(AB)AB下表是(AB)和AB的真值表，从表中可以看出德摩根律成立。,31,2020/6/10,(pq)(qp)(qp)(pq)pq,命题公式的等价,证明等价公式成立的常用方法：方法1：真值表。方法2：等价公式推导。(用置换定律),置换定律:A是一个命题公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，则AB。满足置换定律的变换称为等价变换。,命题公式的等价,例题1.求证吸收律P(PQ)P证明P(PQ)(PF)(PQ)(同一律)P(FQ)(分配律)PF(零律)P(同一律),命题公式的等价,例题2.求证(PQ)(PQ)P证明(PQ)(PQ)(PQ)(PQ)(公式E11)(PQ)(PQ)(摩根定律)(PQ)(PQ)(对合律)P(QQ)(分配律)PT(互补律)P(同一律)公式E11：PQPQ,例题3.化简(PQ)(P(PQ)解原公式(PQ)(PP)Q)(E11,结合)(PQ)(PQ)(对合律，幂等律)(PQ)(QP)(交换律)(PQ)Q)P(结合律)QP(吸收律)公式E11：PQPQ,命题公式的等价,36,Example1证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r（结合律，置换规则）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式，置换规则）,说明:也可以从右边开始演算(操作一遍)因每一步都用置换规则，故可不写熟练后，基本等值式也可以不写出,证明两公式等值,37,Example2Showthat(p(pq)andpqarelogicallyequivalent.Solution:,38,Example3Showthatisatautology.,Solution:,命题等价,命题公式真值表等价公式重言式和蕴含式,重言式,命题公式真值表等价公式重言式和蕴含式,Formula,观察下面真值表：,可见不论P、Q取值如何，PP的真值总为真，(PQ)(PQ)的真值总为假。故称PP为重言式(永真式)；称(PQ)(PQ)为矛盾式(永假式)。,重言式,永真(重言)式（Tautology）公式中的命题变量元论怎样指派，公式对应的真值恒为T。永假（矛盾）式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。,若干定义,如果A是永真式，则A是永假式。如果A，B是永真式，则(AB)、(AB)、(AB)和(AB)也都是永真式。如果A是永真式，则A的置换例式也是永真式。,重言式的基本性质,如果用公式X替换命题公式A中的某个变元,替换后得到的新公式B称为A的置换例式。,公式A：P(P(PQ)R)用(DE)替换A中P得到A的置换例式B：(DE)(DE)(DE)Q)R)如果A是永真式，例如A为PP，用(DE)替换A中P，得到A的置换例式B：(DE)(DE)，显然B也是永真式。结论：如果可以断定给定公式是某个永真式的置换例式的话，则这个公式也是永真式。,重言式的基本性质,定理：,设A、B为两个命题公式，AB当且仅当AB为重言式,证明,若AB，则无论进行怎样的指派，A、B的真值都相同，即AB为重言式。若AB为重言式，则无论进行怎样的指派，AB的真值都为T，也就是说A和B的真值相同，即AB。,AB与AB的关系,定义：如果公式AB是重言式，则称A重言(永真)蕴涵B，记作AB。例如：(P(PQ)Q可记作P(PQ)Q,注意：AB可以理解成由A可推出B，即由A为真，可以推出B也为真。,重言（永真）蕴含式,方法列真值表。（略）方法假设前件为真，推出后件也为真。方法假设后件为假，推出前件也为假。,蕴含式的证明方法,例：求证(AB)C)D(CD)AB证明:设前件(AB)C)D(CD)为真。则(AB)C)、D、(CD)均真，,由此可得(AB)为T，即AB为T。(AB)C)D(CD)AB,蕴含式的证明方法,例：求证(AB)C)D(CD)AB证明:假设后件AB为F,则A与B均为T。1.如C为F，则(AB)C为F，所以前件(AB)C)D(CD)为F2.如C为T，则若D为T，则D为F，所以前件(AB)C)D(CD)为假若D为F，则CD为F，所以前件(AB)C)D(CD)为假。(AB)C)D(CD)AB,蕴含式的证明方法,I1.PQP,I2.PQQI3.PPQI4.QPQI5.PPQI6.QPQI7.(PQ)PI8.(PQ)QI9.P,QPQI10.P(PQ)QI11.P(PQ)QI12.Q(PQ)PI13.(PQ)(QR)PRI14.(PQ)(