《离散数学 第2版 教学课件 ppt 作者 王元元 离散第16讲 复习讨论》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第16讲 复习讨论（40页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,指挥自动化学院计算机系,PowerPoint Template_Sub,复习讨论,习题讨论,-3-,第10讲 逻辑等价式和逻辑蕴涵式,PowerPoint Template_Sub,命题与逻辑联结词,逻辑等价式和逻辑蕴涵式,范式,证明技术（补充）,-4-,第16讲 逻辑等价式和逻辑蕴涵式,内容提要,重言式 重要的逻辑等价式 重要的逻辑蕴含式 代入与替换原理 逻辑等价式和逻辑蕴涵式的证明方法,-5-,第16讲 逻辑等价式和逻辑蕴涵式,重言式 (tautology, 同义反复,重复),设A为一命题公式 若对A中所有命题变元的任一组指派，
2、A均取真的真值，则称A为重言式或永真式。 若对A中所有命题变元的任一组指派，A均取假的真值，则称A为永假式或不可满足式。 如果至少存在一组指派使A取真的真值，则称A为可满足式(satisfactable formula)。,-6-,第16讲 逻辑等价式和逻辑蕴涵式,逻辑等价式 (logically equivalent),当命题公式AB为永真式时，称A逻辑等价于B，记成AB蕴涵命题A B和其逆否命题B A等价： A B B A为永真式 即： A B B A 逻辑等价：使A为真的指派一定使B为真；使A为假的指派一定使B为假。,-7-,第16讲 逻辑等价式和逻辑蕴涵式,逻辑等价式的证明,证明：(A
3、B)AB,1)假设(AB)=1，要证(AB)=1 得(AB)=0，得(A)=0且(B)=0； 从而(A)=1且(B)=1，得到(AB)=1。 2)假设(AB)=0 ，要证(AB)=0 得(AB)=1 2.1) (A)=1： 得(A)=0，得到(AB)=0 2.2) (B)=1： 得(B)=0，得到(AB)=0,-8-,第16讲 逻辑等价式和逻辑蕴涵式,一些重要的逻辑等价式,E1 AA 双重否定律 E2 AAA ， AAA 幂等律 E3 ABBA，ABBA交换律 E4 (AB)CA(BC) 结合律 (AB)CA(BC) E5 A(BC)(AB)(AC) 分配律 A(BC)(AB)(AC),-9-
4、,第16讲 逻辑等价式和逻辑蕴涵式,一些重要的逻辑等价式,E6 (AB)AB De Morgan律 (AB)AB E7 A(AB)A 吸收律 A(AB)A E8 ABAB 蕴涵表达式 E9 AB(AB) (BA) 等值表达式 E10 Att ，Aff 0-1律 AfA，AtA,-10-,第16讲 逻辑等价式和逻辑蕴涵式,一些重要的逻辑等价式,E11 AAt 排中律 E12 AAf 矛盾律 E13 tf，ft E14 ABCA(BC) 输出律 E15 ABBA 逆反律 E16 (AB) (AB) A 归缪律 E17 AB(AB)(AB),-11-,第16讲 逻辑等价式和逻辑蕴涵式,逻辑蕴涵式 (
5、logically implication),定义3：当命题公式AB是永真式时，称A逻辑蕴涵B，记成A B，后者称为逻辑蕴涵式 不是联结词，仅是一个记号。A B仅表示AB是永真式，即对任意的指派AB均取真的真值。,-12-,第16讲 逻辑等价式和逻辑蕴涵式,一些重要的逻辑蕴涵式,I1 A AB, B AB I2 AB A, AB B I3 A(AB) B I4 (AB)B A I5 A(AB) B， B(AB) A I6 (AB)(BC) AC I7 (AB)(CD) (AC)(BD) I8 (AB)(BC) AC,-13-,第16讲 逻辑等价式和逻辑蕴涵式,逻辑等价式及逻辑蕴涵式的证明,三种
6、证明逻辑等价式及逻辑蕴涵式的方法： 真值表法。为证AB，A B，可用真值表证明AB，AB永真 对指派进行讨论 利用已知的永真式及代入、替换原理进行推演,-14-,第16讲 逻辑等价式和逻辑蕴涵式,证明举例5真值表方法,证明：(AB)(AC) (BC) C,0 0 1 1 1 1 1 1,1 1 1 1 0 0 1 1,1 1 0 1 1 1 0 1,0 0 0 1 0 0 0 1,1 1 1 1 1 1 1 1,-15-,第16讲 逻辑等价式和逻辑蕴涵式,证明举例5指派讨论方法,证明：(AB)(AC) (BC) C,假设任一指派 ，使得(AB)(AC) (BC) )=1，要证(C)=1 由(A
7、B)(AC) (BC) )=1， 得(AB)=1且(AC) =1且(BC) =1 (A)=1，又因为(AC) =1，可得到(C)=1 (B)=1，又因为(BC) =1，可得到(C)=1,-16-,第16讲 逻辑等价式和逻辑蕴涵式,证明举例5演绎方法,证明：(AB)(AC) (BC) C,(AB)(AC) (BC) (AB)(AC)(BC) (AB)A) (AB)C)(BC) (AA)(BA) (A C )(BC)(BC) (BA) (AC)(BC)(BC) (AB B)(AB C) (ABC) (ACC) (BBC) (BCC) (AB C) (ABC) (AC) (BC) (AB)(AB)A
8、B)C C,证明方法习题讨论,1、构造下面推理的证明：只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯；A曾到过受害者房间；如果A在11点以前离开房间，看门人会看见他；看门人没有看见他。所以，A是谋杀嫌犯 p: A曾到过受害者房间 q: A 11点以前离开受害者房间 r: A是谋杀嫌犯 s: 看门人会看见A 前提 (1) pqr (2) p (3) q s (4) s 结论 r,证明方法习题讨论,证明 (1) qs 前提 (2) s q 由(1)及E15 (3) s 前提 (4) q 由(2)(3)及I3 (5) P 前提 (6) pq 由(4)(5)得 (7) pqr 前提 (8)
9、 r 由(6)(7)及I3,证明方法习题讨论,证明下列推理是错误的(无效的) 形式化：p：我有钱；q：我买书；r：我去淮海路 原推理可表示为：,考虑指派，满足(p)=0，(q)=0，(r)=1。则(AB)= (BC)= (B)=1，而(C)=0，即弄真前提，弄假结论。所以，推理错误。原推理无效。,PowerPoint Template_Sub,谓词演算基本概念(语句形式化),谓词演算永真式,谓词的自然语句形式化,没有不犯错误的人 F(x)：x犯错误 M(x)：x是人 x (M(x)F(x) x (M(x)F(x) 凡是实数，不是大于0，就是等于0或小于0 R(x)：x是实数 x (R(x)x0
10、x=0x0) 尽管有人聪明，但未必一切人都聪明 S(x)：x聪明 M(x)：x是人 x (M(x) S(x) x (M(x) S(x),谓词的自然语句形式化,所有步行的、骑马的或乘车的人，凡是口渴的，都喝泉水 M(x)：x是人；P(x)：x步行；Q(x)：x骑马； R(x)：x乘车；T(x)：x口渴；S(x)：x喝泉水 x(M(x)(P(x)Q(x)R(x)(T(x)S(x) 有且仅有一个偶质数 P(x)：x是偶数；Q(x)：x是质数 !x (P(x)Q(x) !也是一个存在量词，其含义是“存在唯一的一个”，用法与存在量词的用法相同，即特性谓词也要作为合取项加入。,谓词的自然语句形式化:多元谓
11、词,对于所有的自然数x，均有 x + 1 x N(x)：x是自然数 M(x,y)：x+y=x x (N(x) M(x,1) 我为人人，人人为我 M(x)：x是人 H(x,y)：x为(帮助)y x (M(x)H(我,x) x (M(x)H(x,我),谓词的自然语句形式化:量词嵌套,每个人都有些缺点 M(x): x是人；F(x): x是缺点；H(x,y):x有y x (M(x) y(F(y)H(x,y) 每个人都有人爱，但没有人为所有人爱 M(x)：x是人，L(x,y)：x爱y x (M(x)y(M(y)L(y,x) x (M(x)y(M(y)L(y,x) 有且仅有一个偶质数 P(x)：x是偶数；
12、Q(x)：x是质数 !x(P(x)Q(x) x(P(x)Q(x)y(P(y)Q(y)x=y) x(P(x)Q(x)xy(P(x)Q(x)P(y)Q(y) x=y),谓词的自然语句形式化:量词嵌套,并不是火车都比汽车跑的快，有的汽车比有的火车跑的快 T(x): x是火车；C(x): x是汽车；F(x,y):x比y快 x (T(x)y(C(y)F(x,y)x(C(x)y(T(y)F(x, y) xy(T(x)C(y)F(x,y)x(C(x)y(T(y)F(x, y) 有位妇女已搭乘过世界上每一条航线上的航班 W(x)：x是妇女；L(x)：x是航线；F(x)：x是航班 Q(x, y)：x是y航线上的
13、航班； P(x, y)：x搭乘过y航班 x(W(x)y(L(y)z(F(z)Q(z,y)P(x, z),谓词演算永真式:由命题演算重言式得到,ABAB,A(x)B(x)A(x)B(x),AA,A(x) A(x),(AB)AB,(A(x) B(x) A(x) B(x),A(BC)(AB)(AC),A(x)(B(x)C(x)(A(x)B(x)(A(x)C(x),(AB) (AB) A,(A(x) B(x) (A(x) B(x) A(x),命题演算的重言式中，同一命题变元用相同的谓词公式代替后所得的仍是永真式,pp,P(x) P(x) yP(x,y) yP(x,y),p(qp),P(x,y) (yP(x,y)Q(y) P(x,y),谓词演算永真式,1、消去量词等价式 设个体域为有限集D=a1,a2,an，有 xA(x)A(a1) A(a2) A(an) xA(x)A(a1
