交大数理逻辑课件2-3命题逻辑的等值和推理演算.ppt

第2章 命题逻辑的等值和推理演算,2.1 等值定理 2.2 等值公式 2.3 命题公式与真值表的关系 2.4 联结词的完备集 2.5 对偶式 2.6 范式 2.7 推理形式 2.8 基本的推理公式 2.9 推理演算 2.10 归结推理法,讨论等值演算,讨论推理演算,极大项,定义 n个命题变项的简单析取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单析取式称为极大项。 如：两个命题变元P和Q，其极大项为： P Q， P Q ， P Q ， P Q 说明 n个命题变项产生2n个极大项，它们互不等值 用Mi表示第i个极大项，每个小项的n个变元排序相同。（按下标或字典顺序），分别记为 其中i是该极大项成假赋值的十进制表示的补. （正变项：0，变元的否定：1）,M11 M10 M01 M00,由P, Q, R三个命题变项形成的极小项与极大项,主合取范式,主合取范式 由极大项构成的合取范式 如n=3, 命题变项为P, Q, R时，主合取范式: (PQR)(PQR) = M6M2 定理 任何命题公式都存在与之等值的主合取范式, 并且是惟一的. 求主合取范式的方法 等值演算法和真值表法,1. 求A的合取范式A ； 2. 若A 的某简单析取式B中不含某命题变项或其否定，则将B展成如下形式： B = B 0 = B (Pi Pi ) = (B Pi) (B Pi) 3. 将重复出现的命题变项、重言式及重复出现的极大项都“消去”。 4. 将极大项按由小到大的顺序排列，并用 表示之，如 M1 M2 M6 用 (1,2,6) 表示。,用等价演算法求主合取范式的步骤,求公式(PQ)R 的主合取范式,解1: ： (PQ)R = ( P Q) R = (PQ) R = (PQ) (QR) PR = (PR) (Q Q ) =(PRQ) ( P Q R) =M111 M101 QR =(QR) (P P ) =(PQ R) ( P Q R) =M111 M011 , 代入并排序，得主合取范式： =M3 M5 M7 = (3,5,7),解2: (PQ)R = ( P Q) R = (PQ) R = (PR)(QR) (合取范式) = M1x1 Mx11 = M101 M111 M011 M111 = M3 M5 M7 = (3,5,7),求公式(PQ)R 的主合取范式,= (PQ)R （析取范式） = m11x mxx1 = (m110 m111)( m001 m011 m101 m111) = (1,3,5,6,7),主析取范式与主合取范式的转换 (1,3,5,6,7) = (07)-(1,3,5,6,7)补 = (0,2,4)补 = (3,5,7),2.7 推理形式,推理引例: (1) 正项级数收敛当且仅当部分和有上界. (2) 若ACBD，则AB且CD. 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。 推理从前提出发，应用推理规则推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理. 推理的组成 前提推理所根据的已知命题 结论从前提出发通过推理而得到的新命题 证明 描述推理正确或错误的过程.,推理形式,例：如果我有时间，那么我就去上街； 如果我上街，那么我就去书店买书； 但我没有去书店买书， 所以我没有时间。 解：令 P：我有时间。 Q：我去上街。 R： 我去书店买书。 根据题意，前提为：PQ，QR，R 结论为：P 推理的形式为： (PQ)(QR)R P,反映了一类推理关系,重言蕴涵,定义 若（A1A2 Ak）B为重言式，则称 由A1,A2, Ak推出结论B的推理正确（有效结论） 否则推理不正确（错误）. “A1, A2, , Ak 推出B” 的推理正确 当且仅当 A1A2AkB为重言式. 推理的形式结构 A1A2AkB 或 前提： A1, A2, , Ak 结论： B 若推理正确，则记作：A1A2Ak B,例：判断下面推理是否正确,（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。 解题方法 将命题符号化 写出前提、结论和推理的形式结构 进行判断 解： 设 P：天气凉快，Q：小王去游泳. 前提： PQ，P 结论： Q 推理的形式结构为： (PQ)P) Q 判断上式是否为重言式,例：判断下面推理是否正确,（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。 判断 (PQ)P) Q 是否为重言式 方法1：真值表法,(PQ)P) Q,例：判断下面推理是否正确,（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。 判断 (PQ)P) Q 是否为重言式 方法2：等值演算法 (PQ)P) Q = (PQ)P)Q = (PQ) P Q = (PQ) (PQ) = T,(PQ)P) Q,例：判断下面推理是否正确,（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。 判断 (PQ)P) Q是否为重言式 方法3：主析取范式法 (PQ)P) Q = (PQ)P)Q = (PQ) P Q = m11m0xmx0 = m11m00m01m00m10 = (0,1,2,3) = T,(PQ)P) Q,例：判断下面推理是否正确,（2）若我上街，我一定去新华书店。我没上街，所以我没去新华书店。 解： 设 P：我上街，Q：我去新华书店. 前提： PQ，P 结论： Q 推理的形式结构为： (PQ)P) Q 判断上式是否为重言式 (PQ) P) Q = (P Q) P) Q = (P Q) P Q = m10m1xmx0 = m10m10m11m00m10 = (0,2,3),不是重言式！ 所以推理不正确,重言蕴涵的几个结果,如果A B，A为重言式，则B也是重言式 如果A B， B A同时成立，必有A=B 反之，如果A=B，必有A B，B A 如果A B， B C，则A C 如果A B， A C，则A BC 如果A C， B C，则AB C,2.8 基本的推理公式,判断推理是否正确的方法 真值表法、等值演算法、主析取范式法 推理演算法一个描述推理过程的命题公式序列 其中的每个命题公式是已知的前提、或是由某些前提依据等值公式或蕴涵关系式、应用推理规则得到的结论 说明： 当命题变项比较少时，用前3个方法比较方便, 此时采用形式结构“ A1A2AkB” . 而在推理演算时，采用下面形式： 前提: A1, A2, , Ak, 结论: B,基本的推理公式,PQ P 化简律 (PQ) P (PQ) Q P PQ 附加律 P PQ Q PQ P (P Q) Q 析取三段论 P (PQ) Q 假言推理 Q (PQ) P 拒取式,基本的推理公式,10. (PQ)(QR) PR 假言三段论 11.(PQ)(QR) P R 等价三段论 12. (PR)(QR) (PQ) R 13. (PQ)(RS)(PR) QS 构造性二难 14. (PQ)(RS)( QS) (PR) 破坏性二难 15. (QR) (PQ) (PR) 16. (QR) (PQ) (PR),证明推理公式的方法,定理2.8.1 AB成立的充分必要条件是 AB 是重言式。 定理2.8.2 AB成立的充分必要条件是 A B 是矛盾式。 (AB)=( AB)= A B 说明： 可用AB 是重言式或A B 是矛盾式来证明推理公式AB,2.9 推理演算推理规则,推理规则(续),使用推理规则的推理演算举例,例1：证明： 前提：P Q, Q R, P 结论：R 证： (1) P 前提引入 (2) P Q 前提引入 (3) Q (1)(2)分离（假言推理） (4) Q R 前提引入 (5) R (3)(4)分离（假言推理）,推理演算直接证明法,例2 证明： 前提： P Q， P R, Q S 结论：S R 证明：(1) P Q 前提引入 (2) P Q (1)置换 (3) Q S 前提引入 (4) P S (2)(3)假言三段论 (5) S P (4)置换 (6) P R 前提引入 (7) S R (5)(6)假言三段论 (8) S R (7)置换,(PQ)(RS)(PR) QS 构造性二难,在大城市球赛中，如果北京队第三，那么如果上海队第二，则天津队第四；沈阳队不是第一或北京队第三，上海队第二。从而知：如果沈阳队第一，那么天津队第四。 解：设 P：北京队第三 Q：上海队第二 R：天津队第四 S：沈阳队第一 前提： P(QR)，SP, Q 结论： S R,写出对应下面推理的证明,(1) P (Q R) 前提 (2) Q (P R) (1)置换 (3) Q 前提 (4) P R (2)(3)假言推理 (5) SP 前提 (6) S P (5)置换 (7) S R (6)(4) 析取三段论,推理演算附加前提证明法,欲证明 前提：A1, A2, , Ak 结论：CB 等价地证明 前提：A1, A2, , Ak, C 结论：B 理由： (A1A2Ak)(CB) = ( A1A2Ak)(CB) = ( A1A2Ak)C) B = ( A1A2AkC)B = (A1A2AkC)B,例如：证明下列推理。 前提： P(QR)，SP, Q 结论： S R 证明：(1) S P 前提 (2) S 附加前提引入 (3) P (1)(2) 析取三段论 (4) P (Q R) 前提 (5) Q R (3)(4) 假言推理 (6) Q 前提 (7) R (5)(6) 假言推理,附加前提证明法 举例,2.10 归结推理法（反证法）,欲证明 前提：A1, A2, , Ak 结论：B 将B加入前提，若推出矛盾，则得证推理正确. 理由: A1A2AkB = (A1A2Ak)B = (A1A2Ak) (B) = (A1A2AkB) 括号内部为矛盾式当且仅当 (A1A2AkB )为 重言式,证明AB是重言式的归结证明过程,建立子句集S 将AB化成合取范式，如 P (PR) (PQ) (PR) 的形式，进而将所有句子构成子句集合： S=P，(PR)，(PR)， (PR) 对S作归结 对S的子句消去互补对： 子句：PR，PQ 作归结，得 归结式：RQ 并将此归结式仍放入S中，重复此过程 直至归结出矛盾式，证明结束,归结推理法 举例,例 构造下面推理的证明 前提：(PQ)R, RS, S, P 结论：Q 证明： Q 结论否定引入 RS 前提引入 RS 置换 S 前提引入 R 归结 (PQ)R 前提引入 (PQ) 归结 PQ 置换 P 归结 P 前提引入