离散数学 第一章 命题逻辑-8节

《离散数学 第一章 命题逻辑-8节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1-8.命题推理理论学习要求核心知识点1掌握各种不同类型的规则和公理，特别是命题逻辑的推理规则和公理2熟练掌握不同证明方法的证明原理、不同的应用场景21、“甲在河南工业大学上学”2、“甲在郑州上大学”如果“甲在河南工业大学上学”真的，则显然“甲在郑州上大学”也是真的。推理形式“如果甲在河南工业大学上学，则甲在郑州上大学”；甲在河南工业大学上学；则可推出甲在郑州上大学。符号化为：P表示“甲在河南工业大学上学”；Q表示“甲在郑州上大学”；PQ表示“如果甲在河南工业大学上学，则甲在郑州上大学”。推理形式可以表示为

2、PQ为真；P为真；则可推出Q为真。可以抽象地写成(PQ)∧PQ3、“如果甲在河南工业大学上学，则甲在郑州上大学”是成立的命题公式之间的关系命题公式之间的关系蕴含关系等价关系4复习例如，证明(P∧(PQ))Q为重言式。重言式的真值表的最后一列全是“T”。PQ(PQ)P∧(PQ)(P∧(PQ))QTTTTTTFFFTFTTFTFFTFT设A、B为两个命题公式，AB当且仅当AB为一重言式。5方法2：(P→Q)∧P→Q(┐P∨Q)∧P→Q（公式E16）┐((┐P∨Q)∧P)∨Q（公式E16）

3、(┐(┐P∨Q)∨┐P)∨Q（德-摩根律）((P∧┐Q)∨┐P)∨Q（德-摩根律）((P∨┐P)∧(┐Q∨┐P))∨Q（分配律）(T∧(┐Q∨┐P))∨Q（否定律）(┐Q∨┐P)∨Q（同一律）Q∨(┐Q∨┐P)(交换律)(Q∨┐Q)∨┐P(结合律)T∨┐P（否定律）T（零律）所以，(P→Q)∧P→Q是重言式6一、蕴含式标注：有些重言(永真)式，如(P∧(PQ))Q，公式中间是“”联结词，是很重要的，称之为蕴含式。1、定义1-5.3：当且仅当AB是一个重言式时，称A蕴含B，记作AB，

4、也称B是A的有效结论，或B可由A逻辑地推出（P40）。(P∧(PQ))Q可以写成(P∧(PQ))Q注意：符号“”不是联结词，它是表示公式间的“蕴含”关系，也可以看成是“推导”关系。即AB可以理解成由A可推出B，即由A为真，可以推出B也为真。72、重要的蕴含式P43I1.P∧QPI2.P∧QQI3.PP∨QI4.QP∨QI5.PPQI6.QPQI7.(PQ)PI8.(PQ)QI9.P,QP∧QI10.P∧(P∨Q)QI11.P∧(PQ)QI12.Q∧(P

5、Q)PI13.(PQ)∧(QR)PRI14.(P∨Q)∧(PR)∧(QR)RI15.AB(A∨C)(B∨C)I16.AB(A∧C)(B∧C)8化简规则P∧QP现在气温在冰点以下并且正在下雨。因此，现在气温在冰点以下。附加规则PP∨Q现在气温在冰点以下。因此，要么现在气温在冰点以下，要么现在下雨。9假言推理规则P∧(PQ)Q若今天下雪,则将去滑雪。今天下雪，所以去滑雪。假言三段论(PQ)∧(QR)PR前提:1.如果我不能起床，则我不能上班。2.如果我不能上班，则我不

6、能得到报酬。结论:如果我不能起床，则我不能得到报酬。10析取三段论P∧(P∨Q)Q前提:某人被杀害，凶手为王某或陈某，但王某有不在作案现场证明，结论:陈某为凶手。二难推理(P∨Q)∧(PR)∧(QR)R前提:1.如果某同学为省级运动员，则他被大学录取；2.如果某同学高考总分590分以上，则他被大学录取；3.某同学为省级运动员或高考总分590分以上。结论:该同学被大学录取113、蕴含常见的几个性质性质1:A，B为任意命题公式，若AB，且A为重言式，则B必为重言式。性质2:A，B，C为任意命题公式,若

7、AB，BC，则AC。（蕴含关系可传递）性质3:A，B，C为任意命题公式，若AB，AC，则AB∧C。（两个蕴含式结论的合并）性质4:A，B，C为任意命题公式，若AB且CB，则A∨CB。（两个蕴含式前提的合并）124.蕴含常见的几个性质性质1:A，B为任意命题公式，若AB，且A为重言式，则B必为重言式。证：因为AB，所以A→B为重言式，即A→B永真，当A永为T，所以B必永为T。A→BABTTT定义1-5.3：当且仅当AB是一个重言式时，称A蕴含B，记作AB。13性质2:A，B，C为任意命

8、题公式,若AB，BC，则AC。（蕴含关系可传递）证明：因为AB，BC，所以(A→B)和(B→C)为重言式，即永真，所以(A→B)∧(B→C)永真，为重言式，由P21中第11个公式，可得(A→B)∧(B→C)(A→C)由性质1可以，得(A→C)也永真，即为重言式。因此，AC。A→BB→C(A→B)∧(B→C)A→CTTTT(A→B)∧(B→C)(A→C)14性质3:A，B，C为任意命题