《离散数学课件-第1章-5(上)》由会员分享，可在线阅读，更多相关《离散数学课件-第1章-5(上)（55页珍藏版）》请在金锄头文库上搜索。
1、1离散数学 Discrete Mathematics 汪荣贵贵 教授合肥工业业大学软软件学院专专用课课件2010.06第一章第一章 逻辑与证明逻辑与证明& 学习内容 1.1 1.1 逻辑逻辑 1.2 1.2 命题等价命题等价 1.3 1.3 谓词和量词谓词和量词 1.4 1.4 对偶与范式对偶与范式 1.5 1.5 推理规则推理规则 1.6 1.6 证明导论证明导论 1.7 1.7 证明的方法和策略证明的方法和策略 1.8 1.8 数理逻辑的应用数理逻辑的应用命题逻辑题逻辑 推理推理推理前提集推理规则有效论证结论有效结论推理的过程就是证明永真蕴含式的过程定义1：令H1，H2，Hn是已知的命题公
2、式(前提)，若有 H1H2Hn C ，则称C是H1，H2，Hn的有效结论，简称结论。真值表法 依据A B的概念和定理直接证法 利用P、T规则间接证法 CP规则、反证法判别有效结论的常用方法判别有效结论的常用方法论证步骤：论证步骤：自然语 言描述符号化前提 结论结论有效？结论成立结论不成立有效无效1. 用全真值表证明要证明C 为前提A1，A2，An 的有效结论，只需构造命 题公式A1A2AnC的真值表，证明它是重言式。2. 用部分真值表证明因为条件命题A1A2 An C为假当且仅当它的前件 A1A2An为真，后件C为假。只要能排除前件为真， 后件为假的情况，A1A2 An C就是重言式。从而C
3、为一组前提A1，A2，An的有效结论。于是就有了下面方法：真值表法真值表法构造A1，A2，An与C 的真值表，且作在一个表上。找出A1，A2，An 都为真的行，若C也为真，则A1A2An C，即C为前提A1，A2，An的有效结论。 找出C 为假的行，若在每个这样的行中， A1，A2，An 的真值至少有一个为假，则A1A2 An C，即C为一组前提A1，A2，An的有效结论。【example】分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。solution：令 p：我有时间。
4、q：我去上街。r：我去书店买书。根据题意，前提为：pq，qr，r结论为：p以下证明p是一组前提 p q，q r，r的有效结论。即证明：( p q )( q r ) r p 下面用部分真值表进行证明。 作公式pq，qr，r，p的真值表，如表1所示。 表1pqrpqqrrp 0001111 0011101 0101011 0111101 1000110 1010100 1101010 1111100qr，r至少有一个为0，所以 (pq)(qr)rp从表中可以看出：pq，qr，r都为1的行(赋值000的行)，p也为1。p为0的行(赋值100，101，110，111的行) pq，【example】甲乙
5、两队进行乒乓球比赛，小张上场则小李上场，小李上场则甲队取胜，小张或小李上场了，所以甲队取胜。Solution：(1)命题符号化令 P:小张上场；Q:小李上场；R:甲队取胜本例符号化为:(PQ)(QR) (PQ)R (2)列真值表（见后页）（3）分析结论有效性：由第四行、第八行可知，当前件为真时，结论为真，所以蕴含式成立，结论有效。PQRPQQRPQ FFFTTF FFTTTF FTFTFT FTTTTT TFFFTT TFTFTT TTFTFT TTTTTT直接证法直接证法 规则P(引入前提规则)：在推理过程中，可以随时 引入前提。 规则T(引入结论规则)：在推理过程中，如果前边 有一个或几个
6、公式永真蕴涵公式S，则可将S纳入推 理过程中。推理规则推理规则直接直接证证证证法就是由一法就是由一组组组组前提，利用一些公前提，利用一些公认认认认的的推理推理规则规则规则规则 ，根，根据已知的等价或据已知的等价或蕴蕴蕴蕴含公式，推演得到有效的含公式，推演得到有效的结论结论结论结论 。推理过程中，要应用下面所列出的永真蕴涵 式I1-I16和等价公式E1-E22。具体公式见下表。 下面请看一些例子。I1P Q PI9P,Q P Q I2P Q QI10P, P Q QI3P P Q I11P, P Q QI4Q P Q I12Q, P Q PI5P P QI13P Q, Q R P RI6Q P
7、Q I14P Q, P R, Q R R I7(P Q ) P I15A B (A C ) (B C)I8(P Q ) QI16A B (A C ) (B C)常见的蕴涵规则表常见的蕴涵规则表E1 P PE12R (P P) RE2PQ QPE13R (P P) RE3PQQ PE14R (P P) TE4(PQ ) R P (Q R)E15R (P P) FE5(P Q ) R P (Q R)E16P Q P Q E6P (Q R) (P Q) (P R)E17(P Q ) P Q E7P (Q R) (P Q) (P R)E18P Q Q P E8(PQ ) P Q E19P (Q R)
8、(PQ ) RE9(P Q ) P Q E20PQ (P Q ) (Q P ) E10PP PE21PQ (PQ ) (P Q )E11P P PE22(PQ ) PQ 等价式规则表等价式规则表【example】求证 PQ，QR，P R ProofProof：序号 前提或结论 所用规则 从哪几步得到 所用公式(1) P P(2) PQ P (3) Q T (1)(2) I11 (4) QR P (5) R T (3)(4) I11（注公式I11为： P,PQ Q ）【example】证明(pq)(qr)pr证明： pqP p P q T qr P r T【example】证明(P Q) (P
9、R) (Q S) S R.Proof(1):(1) P Q P(2) P Q T(1) E(3) Q S P(4) P S T(2),(3) I(5) S P T(4) E(6) P R P(7) S R T(5),(6) I(8) S R T(7)EProof(2):(1) P R P(2) P Q R Q T(1) I(3) Q S P(4) QR S R T(3) I(5) P Q S R T(2),(4) I(6) P Q P(7) S R T(5),(6) I【example】证明(W R) V, V C S, SU, CU W Proof:(1) CU P(2) U T(1) I(
10、3) SU P(4) S T(2),(3)I(5) C T(1)I(6) CS T(4),(5)I(7) (C S) T(6)E(8) (W R) V P(9) V C S P(10) (W R) (C S) T(8),(9)I(11) (W R) T(7),(10)I(12) W R T(11)E(13) W T(12)I【example】用逻辑推理方法证明推理的有效性： 如果我学习，那么我数学不会不及格。如果我不热衷于玩朴 克，那么我将学习。但是我数学不及格。因此，我热衷于玩 朴克。 Proof：设 P：我学习。 Q：我数学及格。R：我热衷于玩朴克。于是符号化为：PQ，RP，Q RPQ，R
11、P，Q R(1) PQ P(2) Q P (3) P T (1)(2) I12 (4) RP P(5) R T (3)(4) I12 (6) R T (5) E1 注：公式I12为： Q，PQ P公式E1 为： RR 【exampleexample】求证P(QS),RP,Q RS proof:proof: (1) P(QS) P(2) P(QS) T (1) E16(3) P(SQ) T (2) E3(4) (PS)Q T (3) E5 (5) Q P (6) PS T (4)(5) I10(7) PS T (6) E16(8) RP P(9) RP T (8) E16(10) RS T (7)(9) I13间接证法间接证法 不仅使用P规则，T规则，还是用反证法或CP规则的推理方法 被称为间接证法。 相容性定义：假设公式H1, H2，
