交大数理逻辑课件23 命题逻辑的等值和推理演算

1、第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是该极大项成假

2、赋值的十进制表示的补. （正变项：0，变元的否定：1） M11 M10 M01 M00 由P, Q, R三个命题变项形成的极小项与极大项 极小项 极大项 公式 成真赋值名称 公式 成假赋值名称 P Q RP Q RP Q RP Q R PQ RP Q RP Q RP Q R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7P Q R P Q R P Q R P Q R P Q R P Q R P Q RP Q R 1 1 11 1 01 0 11 0 00 0 10 1 00 0 10 0 0M0M1M2M3M4M5M6M7 主合取

3、范式主合取范式由极大项构成的合取范式如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) 表示。用等价演算法求主合取范式的步骤求公

4、式(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

5、（析取范式） = 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)是错误的推理. 推理的组成前提推理所根据的已知命题结论从前提出发通过推理而得到的新命题证明 描述推理

6、正确或错误的过程. 推理形式例：如果我有时间，那么我就去上街； 如果我上街，那么我就去书店买书； 但我没有去书店买书， 所以我没有时间。 解：令 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 若推理

7、正确，则记作：A1A2Ak B例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。解题方法将命题符号化写出前提、结论和推理的形式结构进行判断解： 设 P：天气凉快，Q：小王去游泳. 前提： PQ，P 结论： Q 推理的形式结构为： (PQ)P) Q 判断上式是否为重言式 例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断 (PQ)P) Q 是否为重言式 方法1：真值表法PQPQ(PQ) P(PQ) P) QFFTFTFTTFTTFTTTTTFFT(PQ)P) Q例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天

8、气凉快，所以小王没去游泳。判断 (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 = m11m0 xmx0 = m11m00m01m00m10 = (0,1,2,3) = T(PQ)P) Q例：判断下面推理是否正确（2）若我上街，我一定去新华书店。我没上街，所以我没去新华书店。解： 设

9、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 C2.8 基本的推理公式判断推理是否正确的方法真值表法、等值演算法、主析取范式法

10、推理演算法一个描述推理过程的命题公式序列其中的每个命题公式是已知的前提、或是由某些前提依据等值公式或蕴涵关系式、应用推理规则得到的结论 说明：当命题变项比较少时，用前3个方法比较方便, 此时采用形式结构“ A1A2AkB” . 而在推理演算时，采用下面形式： 前提: A1, A2, , Ak, 结论: B基本的推理公式PQ P 化简律(PQ) P(PQ) QP PQ 附加律 P PQQ PQ P (P Q) Q 析取三段论P (PQ) Q 假言推理Q (PQ) P 拒取式基本的推理公式10. (PQ)(QR) PR 假言三段论11.(PQ)(QR) P R 等价三段论12. (PR)(QR)

11、(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 是矛盾式来证明推理公式AB2.9 推理演算推理规则 (1) 前提引入规则(2) 结论引入规则(3) 置换规则(4) 假言推理(分离规则) PQ P Q(5) 附加规则 P PQ (6) 化简规则 PQ

12、P (7) 拒取式规则 PQ Q P(8) 假言三段论规则 PQ QR PR 推理规则(续) (11) 破坏性二难推理规则 PQ RS QS PR(12) 合取引入规则 P Q PQ (9) 析取三段论规则 PQ Q P (10)构造性二难推理规则 PQ RS PR QS使用推理规则的推理演算举例例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)

13、 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) 前提 (

14、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)

15、(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 前提引入 (