第三章 形式的命题逻辑系统

(3) AB (1)(2)MP 因此， ├PCAB。 情形2： B是的一个成员。那么下列是从 到 AB的一个推演： (1) B 的成员 (2) B (AB) A1 (3) AB (1)(2)MP 因此， ├PCAB。 情形3：B就是A。那么下列是从到AB的 一个推演： (1) (A((AA)A))((A(AA))(AA)) A2 (2) A( (AA)A) A1 (3) (A (AA) ) (AA) (1)(2)MP (4) A (AA) A1 (5) (AA) (3)(4)MP
• 未知的 已知的 我们要的
但是，我们从YZ和公理(YZ)(X(YZ))
很容易得到 (X(YZ))
3.3.2 PC中的证明
• 思路贯通了： (X(YZ))也是已知的了。只要利用两 次MP规则，我们就可以从(X(YZ)) ((XY)(XZ)) ，利用XY和YZ，得到 (XZ)， 从而完成这个三段论推理的证明。 • （4）在作业和考卷中正式地写出证明（刚开始还不熟 练，就先写在演草纸上，然后誊写过去）。 • 这种模式的证明步骤是这样的： （1） YZ 已知的公理或定理 （2） (YZ)(X(YZ)) A1 （3） X(YZ) (1)(2)MP （4） (X(YZ)) ((XY)(XZ)) A2
3.2 命题逻辑（演算）系统PC
②我们在没有括号的时候，逻辑常项结合的
优先秩序是先再；在同一优先秩 序上，遵从向右结合的原则。因此， A表 示(A) ；ABA表示A (BA)；(ABC)(AB)(AC)表示 (A(BC))((AB)(AC))。
3.2 命题逻辑（演算）系统PC
3.2.5 推理规则 在命题演算系统PC中只有一条推理规 则——MP规则，又叫做分离规则。 PC中的MP规则指的是：从“├PC(AB)”
和“├PCA”可以推出“├PCB”。
3.2 命题逻辑（演算）系统PC
3.3 PC演绎推理的几个重要概念和元定理 3.3.1 证明的概念
定义：系统PC中的一个证明是指这样的一个序列 A1,A2,…,An，使得对于每个i(1in)，或者Ai是PC 的一个公理，或者Ai可由序列中位于Ai前面的两个 公式Aj和Ak(ji,ki)应用MP规则而得到。这样我们 就称序列A1,A2,…,An是在PC中对An的一个证明。 并且，称An是系统PC内的定理（简称定理或内定 理），简记为├PC An。
3.3.3 演绎定理
• 其实这就是内定理1的证明。为了简化证明， 以后只要涉及到前面已经被证明过的内定 理，我们可以直接拿这个结果使用，而不 再重复证明。在理由中间上它是PC内定理 就可以了。同样，对于已经证明的推演我 们也可以把它当作推导规则使用。 • 因此， ├PCAA，即├PCAB 。(注：B 就是A)
3.2 命题逻辑（演算）系统PC
• 3.2.4 公理
（1）A(BA) （2） (A(BC))((AB)( AC)) （3）(A B)(BA) 注意：①我们给出的是一个公理模式，因此 p(qp)， (p(qp))(q(p(qp))) 都是公理1(简记为A1)的具体实例。
3.2 命题逻辑（演算）系统PC • 3.2.2 命题语言的形成规则
（1）任意的命题变元和逻辑常项T,F是合式公式。 （2）如果A,B是合式公式，那么A和AB也是合 式公式。 （3）只有符合以上两条的符号序列才是合式公式， 简记为wffs。
• 3.2.3 其他一些语法符号（元语言符号）
为了便于研究命题演算的性质，我们再引入一些语 法符号(元语言中的符号)： （1）小写英文字母x,y,z是语法变项，它的值是命题 变项中的任意符号（如p,q,r,…）。
举例2： 证明： ├PC(AA) ——(PC内定理2) (1) (A( (AA)A) )( (A (AA) ) (AA) ) A2 (2) A( (AA)A) A1 (3) (A (AA) ) (AA) (1)(2)MP (4) A (AA) A1 (5) (AA) (3)(4)MP
说明： ① Aj和Ak必需是形如“AB”和“A”，或者“A” 和 “AB”这样的形式。 ②如果Ak出现在序列A1,A2,…,An中，那么它也是PC 的内定理。 ③一条公理也是PC的内定理，它的证明是只包含一 项的序列。 ④ “├PC ”显然不是PC中的符号。在这里提请大家 注意元语言和对象语言的区别。一般地，被研究对 象中出现的语言符号称为对象语言符号。用以研究 对象语言的符号称为元语言符号。一般情况下，为 了以示区别我们会在元语言符号的外面加上双引号； 在上下文不会引起混淆的语境下，我们又是也省略 外面的双引号。
3.3.2 推演的概念
• 推演的举例： • 下列是PC中从{A, B(AC)}到BC的推演 (1) A (2) B(AC) (3) A(B A) (4) BA (5) (B(AC))( (BA)(BC)) (6) (BA)(BC) (7) BC 所以， {A, B(AC)} ├PC (BC)。 P*(假设) P*(假设) A1 (1)(3)MP A2 (2)(5)MP (4)(6)MP
3.3.2 推演的概念
3.3.2 推演的概念
PC中的一个证明是从公理出发的一个演绎。我 们将需要从某些给定的公式集得出更为一般的推 演概念。 • 定义：令是PC中的公式集（ 可以是、也可以 不是PC中的公理或内定理）。 PC中公式的序列 A1,A2,…,An是从 的一个推演，如果对于每个 i(1in)，下列之一成立： （1）Ai是PC的一个公理； （2）或者Ai是中的一个成员；
3.3.2 推演的概念
• 推演{A, B(AC)} ├PC (BC)的直观意思是这样的：如 果有A，如果再有B(AC)，那么在PC中一定有BC。 • 内定理├PC A( (B(AC)) (BC) )的直观意思也可 以不规范地看成：在PC中如果有A，如果再有B(AC)， 那么有BC。 • 这似乎提示了我们：是否可以增加一些步骤，从而把PC 的一个推演改造成PC的一个证明。显然，构造推演{A, B(AC)} ├PC (BC)会比构造内定理├PC A( (B(AC)) (BC) )的证明要简单得多。 • PC的演绎定理的出现，满足了简化PC内定理的证明的要 求。演绎定理表明，只要能构造{A, B(AC)} ├PC (BC)就等同于证明了├PC A( (B(AC)) (BC) )。
（3）其次，我们需要一些实战技巧（这些技
巧这能在做题训练中获得） 但是，我们怎么样把这些模糊的思路变成一个具 体的证明呢？例如，我们在这里遇到的就是这样一 个推理模式的实现：从XY和YZ推导出XZ。 • 这其实就是一个三段论的推理，我们可以利用PC的 公理和推理规则这样实现： • 利用A2有(X(YZ)) ((XY)(XZ))
第一节 形式系统
• 3.1.3 形式系统 • 一个形式系统通常由四部分构成： （1）各种初始符号； 系统的语言部分(形式语言) （2）合适公式的形成规则； （3）公理； 系统演绎的基础(演绎工具) （4）推理规则。
3.2 命题逻辑（演算）系统PC
• 3.2 命题逻辑（演算）系统PC • 3.2.1 命题语言的字母表(初始符号) （1）命题变元符号： p,q,r,s,t,p1,q1,r1,s1,t1,p2,… （2）逻辑常项符号：T,F,,。 （3）辅助符号：(,)。 形式语言L0可以由无穷多个符号组成， 即L0＝{T,F,,, (,), p,q,r,s,t,p1 ,…}
3.2 命题逻辑（演算）系统PC
（2）大写英文字母A,B,C是语法变项，它的 值是任意符号序列（如pq,r等）。但在 以后的讨论中，我们一般用它来表示合适 公式，所以上例中的“r”将会被排除掉。 （3）“├”是一个语法符号，它将会被写在 一个合式公式之前，表示这个公式是要被 某个形式系统所肯定的。例如，pp将被 命题演算PC所肯定，我们就记为 “├PC(pp)”。
（5） (XY)(XZ) (3)(4)MP （6） XY 已知的公理或定理 （7） XZ (5)(6)MP • 大家不难发现：如果把X,Y,Z分别代以B, AB, BA。对B(BA)的证明和 我们在这里给出的对XZ 的证明是一样的。 在学习了推演之后，我们再以这种推理模 式举另一个例子。
• （3）或者Ai可由序列中位于Ai前面的两个公式Aj 和Ak(ji,ki)应用MP规则而得到。 • 所以，从的推演就是这样的一个“证明”，其 中的成员暂且被当作公理。我们称序列 A1,A2,…,An最后的An是在PC中从 可推演的。或 者，称An是PC中的（语法）后承，简记为├PC An。 • 注意：如果是空集，那么推演序列A1,A2,…,An 就是一个PC中的证明，记为├PC An，也可以不 太规范地写为├PC An。
• 举例1：PC中的证明(pq)(pp) ——(PC
内定理1) (1) p(qp) A1 (2) ( p(qp) ) ( (pq)(pp) ) A2 (3) (pq)(pp) (1)(2)MP 从(1)到(3)构成了 “├PC(pq)(pp)”的证明。
3.3.1 证明的概念
• 象前面├PCB(BA)这样的证明是比较复杂 的，那么我们怎么才能构造它的证明呢？以下 是我的分析思路： • （1）首先，观察要证的结构 我们看到要证中间出现了否定，一般来说要用 到A3（因为A1和A2不能从一个否定的前提推 导出肯定结论）。 • （2）现在演草纸上把A3：(A B)(BA) 写出来。我们发现A3的后半部分和要证的后半 部分一样。因此，我们重点观察他们的前半部 分。我们发现要证和A3的前提之间是有联系的： 我们可以从B推导出 (A B)。因为，很显 然B(AB) 是一条公理。
3.3.3 演绎定理
演绎定理：如果A├PCB，那么├PCAB，这
里A和B是PC的公式，的公式集（可能是空集）。 证明：我们对构成推演A├PCB的那个序列 A1,A2,…,An中公式的数目n进行归纳证明。 （1）基础步骤：当n=1时，也就是说，这个序列 只有一项，而且这一项就是公式B。因此，B要么 是PC的一条公理，要么是A的一个成员（根 据推演的定义可知）。在后一种情况中又有B 和B就是A两种情况。 情形1：B是PC的一条公理。那么下列是从到 AB的一个推演： (1) B PC的公理 (2) B (AB) A1