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

《离散数学课件-第1章-2.ppt》由会员分享，可在线阅读，更多相关《离散数学课件-第1章-2.ppt（53页珍藏版）》请在三一文库上搜索。

1、1,2019/2/21,离散数学 Discrete Mathematics,汪荣贵 教授 合肥工业大学软件学院专用课件 2010.3,第一章 逻辑与证明,学习内容,1.1 逻辑 1.2 命题等价 1.3 谓词和量词 1.4 对偶与范式 1.5 推理规则 1.6 证明导论 1.7 证明的方法和策略 1.8 数理逻辑的应用,命题等价,命题公式 真值表 等价公式 重言式和蕴含式,命题变元,如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。 命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。,复合

2、命题,如果一个命题不能再分解成更简单的命题，则称该命题为原子命题。如果一个命题不是原子命题，称该命题为复合命题。 如果用命题变元表示原子命题时，该命题变元称为原子变元。 命题逻辑中，可以通过命题联结词将原子变元联结起来表示复合命题。,命题公式,把命题常元，命题变元按照一定的逻辑顺序和规则，用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。,命题公式,合式公式 ( wff ) (well formed formulas)： 按下列规则构成的符号串称为命题演算的合式公式，也称为命题公式，简称公式。 单个命题变元和常元是合式公式。 如果A是合式公式，那么A是合式公式。 如果A和B是合式公

3、式，那么(AB)、(AB)、(AB)和(AB)是合式公式。 当且仅当有限次地应用了、所得到的符号串是合式公式。,命题公式,上面的定义给出合式公式定义的方法称为归纳定义，它包括三部分： 基础、归纳、界限 其中是基础，和是归纳，是界限。 以后将多次出现这种形式的定义。,命题公式,下列符号串是合式公式： (pq)，(pq)，(p(pq)， (pq)(qr)(st) 下列符号串不是合式公式： (pq)(q)，(pq，(pq)q),命题公式,约定：为方便，最外层括号可以不写，合式公式可以写成： PQ，PR，(PQ)R 如果规定逻辑联接词的优先级： 、 、 、 、 则： P Q R也是合式公式,命题等价,

4、命题公式 真值表 等价公式 重言式和蕴含式,命题公式的赋值,设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的

5、一个真值，把它们汇列成表，称该表为命题公式A的真值表。 例如：,真值表的概念,说明: 设P1，P2,Pn为命题公式P中的命题变量，对于命题变元每一种真值指派的可能组合，都能唯一确定P的真值（即有2的n次幂种分布）。 为了有序地列出公式的真值表，在对命题变元做指派时，可以按照二进制数的次序列表。,【例】构造命题公式pq的真值表，并求成真赋值和成假赋值。 解：命题公式pq的真值表如表1.6所示。00，01，11是成真赋值，10是成假赋值。,【例】构造命题公式(pq)(pq)的真值表，并求成真赋值和成假赋值。 解：命题公式(pq)(pq)的真值表如下表所示。00， 11是成真赋值，01，10是成假赋

6、值。,为了有序地列出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)的真

7、值表,观察下面的真值表,在上面的真实表中你是否发现什么问题？,命题等价,命题公式 真值表 等价公式 重言式和蕴含式,命题公式的等价,AB的定义：A、B是含有命题变元P1,P2, Pn的命题公式，如不论对P1, P2 , , Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价，记作AB。 显然 P Q P Q （P Q）（ P Q ） P Q 提示：判断两个公式是否等价，更好的方法是当变元数不多时，直接构造两个公式的真值表，看两个真值表是否相等即可。,命题公式的等价,可以证明（例如可以用真值表证明）： 命题公式等价有下面的三条性质： 自反性，即对任意命题公式A， AA 对称性，即对任意命

8、题公式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.双重否定律 AA 2.交换律 ABBA， ABBA 3.结合律 (AB)CA(BC) (AB)CA(BC),命题公

9、式的等价,4.分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 5.德摩根律 (AB)AB (AB)AB 6.幂等律 AAA，AAA 7.吸收律 A(AB)A， A(AB)A 8.零律 A11，A00,命题公式的等价,9.同一律 A0A， A1A 10.排中律 AA1 11.矛盾律 AA0 12.条件等价式 ABAB 13.双条件等价式 AB(AB)(BA) 14.假言易位式 ABBA 15.双条件否定等价式 ABAB,命题公式的等价,以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律： (AB)AB 下表是(AB)和AB的真值表，从表中可以看出德摩根律

10、成立。,命题公式的等价,以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律： (AB)AB 下表是(AB)和AB的真值表，从表中可以看出德摩根律成立。,31,2019/2/21,(p q) (q p) (q p) (p q ) p q,命题公式的等价,证明等价公式成立的常用方法： 方法1： 真值表。 方法2：等价公式推导。(用置换定律),置换定律: A是一个命题公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，则AB。 满足置换定律 的变换称为等价变换。,命题公式的等价,例题1. 求证吸收律 P(PQ)P 证明 P(PQ) (PF)(PQ)

11、(同一律) 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 证明

12、p(qr) (pq)r 证 p(qr) p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq) r （蕴涵等值式，置换规则）,说明: 也可以从右边开始演算(操作一遍) 因每一步都用置换规则，故可不写 熟练后，基本等值式也可以不写出,证明两公式等值,37,Example 2Show that ( p ( p q) and p q are logically equivalent. Solution:,38,Example 3Show that is a tautology.,Solution:,命题等价,命题公式 真值表 等价公式 重

13、言式和蕴含式,重言式,命题公式 真值表 等价公式 重言式和蕴含式,Formula,观察下面真值表：,可见不论P、Q取值如何，PP 的真值总为真， ( P Q) ( P Q)的真值总为假。故称 PP为重言式(永真式)； 称 ( P Q) ( P Q)为矛盾式(永假式)。,重言式,永真(重言)式（Tautology）公式中的命题变量元论怎样指派，公式对应的真值恒为T。 永假（矛盾）式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。 可满足公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。 一般命题公式（Contingen

14、cy）既不是永真公式也不是永假公式。,若干定义,如果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也是永真式。 结论：如果可以断定给定公式是某个永真式的置换例式的话，则这个公式也是永真式。,

15、重言式的基本性质,定理：,设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)

16、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) 为F 2.如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. PQQ I3. PPQ I4. QPQ

17、I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q PQ I10. P(PQ)Q I11. P(PQ)Q I12. Q(PQ)P I13. (PQ)(QR)PR I14. (PQ)(PR)(QR)R I15. AB (AC)(BC) I16. AB (AC)(BC),重要的蕴含式,定理：,设P、Q为两个命题公式，PQ当且仅当PQ且QP,证明,必要性：若PQ，则对于任何指派，P、Q都同真值，故PQ为T， QP为T，即PQ，QP 充分性：若PQ，QP，则PQ为T ，QP为T，所以，P Q为T，P Q为重言式，即PQ,等价式与蕴含式的关系,AB且A为重言式，则B必为重言式 若AB且BC，则AC (传递性) 若AB且AC，则A(B C) 若AB且C B，则(AC) B,蕴含式的性质,谢谢大家！,