第3节真值指派 第2章命题逻辑 围。某种意义上来说,逻辑学关心的不是“原子事实”的真假,而是怎样处理由逻辑符号 生成的复合命题的真假。我们今后会看到,这一点在一阶逻辑的真值理论中表现得更为明 对初学者来说,除了对蕴涵式的规定外,其它的都好理解。当然,我们可以简单地 说:在数学中蕴涵就是这样规定的。但我们还是给出几种解释,希望能说服初学者这样的 规定是有道理的。在专门的模态逻辑课程中对蕴涵的意义往往会有更多的讨论。 第一种解释:考察:“如果中国足球队夺冠,我就把我鼻子吃了” 假设我在看球时跟朋友说了这样的话,而比赛结果真的是中国队夺冠(前件为真), 那朋友绝对有权利要求我把自己的鼻子吃了,因为否则我就说了假话(后件为假,所以整 个命题为假,见真值表的第二行第六列。),无面目站在讲台之上。但是,更为可能的是中 国队没有夺冠(前件为假,在我的记忆中,这个命题总是假。),那朋友就没有权利要求我 吃鼻子了,因为无论如何,我都说了真话(既然前件为假,无论后件是否为真,整个命题 都真。见真值表的第三行第四行,第六列。)。 第二种解释:考察(A∧B)→B。 在这个例子中,后件“包含”在前件中。当我们肯定了前件时,当然肯定了作为其 部分的后件,所以直观上这个命题无论如何都是真的。考察真值表的结果也是一样,不管 A,B取何值,整个公式一定为T。现在考虑如下两种情况:(1)A为假而B为真,则我 们得到的是F→T;(2)B为假,这时前件和后件都是假的,我们得到F→F。但根据 以上的讨论,整个命题依然为真。所以F→T和F→F的真值都应设为T。 第三种解释:我们自行设计我们觉得满意的真值表 B(a→B) aTTFF 首先,大家对前两行应该没有异议。剩下的是选择X和Y的值。我们选了X Y=T大家不满意。现在你们来选。只有三种可能,大家会发现都不合适。第一种可能 X=T,Y=F,这时第二列与第三列完全相同,即A→B与A的真假全无关系。第 种可能:X=F,Y=T,这与A分B相同。第三种可能:X=Y=F,这与AAB相 同 例21.令a为下列合式公式 (B→(A→C)分(B∧A)→C) 假定v(4)=v(B)=T并且v(C)=F。找出v(a)的值。 答案:(a)=T
第 3 节 真值指派 第 2 章 命题逻辑 围。某种意义上来说，逻辑学关心的不是“原子事实”的真假，而是怎样处理由逻辑符号 生成的复合命题的真假。我们今后会看到，这一点在一阶逻辑的真值理论中表现得更为明 显。 对初学者来说，除了对蕴涵式的规定外，其它的都好理解。当然，我们可以简单地 说：在数学中蕴涵就是这样规定的。但我们还是给出几种解释，希望能说服初学者这样的 规定是有道理的。在专门的模态逻辑课程中对蕴涵的意义往往会有更多的讨论。 第一种解释：考察：“如果中国足球队夺冠，我就把我鼻子吃了”。 假设我在看球时跟朋友说了这样的话，而比赛结果真的是中国队夺冠（前件为真）， 那朋友绝对有权利要求我把自己的鼻子吃了，因为否则我就说了假话（后件为假，所以整 个命题为假，见真值表的第二行第六列。），无面目站在讲台之上。但是，更为可能的是中 国队没有夺冠（前件为假，在我的记忆中，这个命题总是假。），那朋友就没有权利要求我 吃鼻子了，因为无论如何，我都说了真话（既然前件为假，无论后件是否为真，整个命题 都真。见真值表的第三行第四行，第六列。）。 第二种解释：考察 (A ∧ B) → B。 在这个例子中，后件“包含”在前件中。当我们肯定了前件时，当然肯定了作为其一 部分的后件，所以直观上这个命题无论如何都是真的。考察真值表的结果也是一样，不管 A，B 取何值，整个公式一定为 T。现在考虑如下两种情况：（1）A 为假而 B 为真，则我 们得到的是 F → T；（2）B 为假，这时前件和后件都是假的，我们得到 F → F。但根据 以上的讨论，整个命题依然为真。所以 F → T 和 F → F 的真值都应设为 T。 第三种解释：我们自行设计我们觉得满意的真值表： α β (α → β) T T T T F F F T X F F Y 首先，大家对前两行应该没有异议。剩下的是选择 X 和 Y 的值。我们选了 X = Y = T 大家不满意。现在你们来选。只有三种可能，大家会发现都不合适。第一种可能： X = T，Y = F，这时第二列与第三列完全相同，即 A → B 与 A 的真假全无关系。第二 种可能：X = F，Y = T，这与 A ↔ B 相同。第三种可能：X = Y = F，这与 A ∧ B 相 同。 例 2.1. 令 α 为下列合式公式 (((B → (A → C)) ↔ ((B ∧ A) → C)))。 假定 v(A) = v(B) = T 并且 v(C) = F。找出 v(α) 的值。 答案：v(α) = T。 6
第2章命题逻辑 第3节真值指派 回到∂的定义。注意在定义中可在定义和被定义的部分同时出现。这样的定义方法是 递归定义的一个例子。递归定义在数学上很常见,比如,阶乘函数n!就可以递归定义成 0!=1并且对所有自然数n,(n+1)!=(n+1)×ml;又比如菲波那契序列f可以递归定 义为f=f1=1并且对所有自然数n,fn+2=fn+fn+1。直观上很容易接受下述定理 定理22.对任意S上的真值指派v都有唯一的一个扩张:5→{T,F}满足前述条件0 5)。 定理2.2的证明本质上是验证递归定义的合理性,即递归定义并没有犯循环定义的错 误。在很多集合论的教科书内都有递归定义合理性的证明,有兴趣的读者可以参考,我们 这里就省略了。 我们称一个真值指派v满足一个公式φ如果可(p)=T。 定义22.我们称一个公式集∑重言蕴涵公式r,记为∑卡T,如果每一个满足∑中所有 公式的真值指派都满足r。 ∑}τ也被读作T是∑的语义后承。如果我们把它的定义用数学语言展开,就会 发现它涉及不止一个量词。∑r当且仅当“对所有的真值指派v[如果(对所有的公式 σ∈∑,列()=T)则列(7)=们”。 例22. 1)验证{(a∧B)}a (2)公式集{A,(A)}重言蕴涵B吗? 答案:是。 我们称一个公式T为一个重言式(记作上T)如果0}r。这与通常的“重言式在所 有真值指派下为真”或“重言式被所有真值指派满足”的说法是一致的。原因是所有的真 值指派υ都满足“空集中每一元素”。不然的话,空集中就会有一个元素让不满足它, 而这显然是不可能的。 如果∑={}只含有一个公式,我们有时会把{a}=r简写成σ卡=T。如果ar和 T}σ都成立,则我们说σ和r重言等价。 重言式举例 (1)结合律 (AV(BVC)分(AVB)VC) (A∧(B∧C)分((AAB)AC) 菲波那契, Fibonacci(约1170-约1250),意大利数学家
第 2 章 命题逻辑 第 3 节 真值指派 回到 v 的定义。注意在定义中 v 在定义和被定义的部分同时出现。这样的定义方法是 递归定义的一个例子。递归定义在数学上很常见，比如，阶乘函数 n! 就可以递归定义成 0! = 1 并且对所有自然数 n, (n + 1)! = (n + 1) × n!；又比如菲波那契1序列 fn 可以递归定 义为 f0 = f1 = 1 并且对所有自然数 n, fn+2 = fn + fn+1。直观上很容易接受下述定理： 定理 2.2. 对任意 S 上的真值指派 v 都有唯一的一个扩张 v : S → {T, F} 满足前述条件 (0) – (5)。 定理 2.2 的证明本质上是验证递归定义的合理性，即递归定义并没有犯循环定义的错 误。在很多集合论的教科书内都有递归定义合理性的证明，有兴趣的读者可以参考，我们 这里就省略了。 我们称一个真值指派 v 满足 一个公式 φ 如果 v(φ) = T。 定义 2.2. 我们称一个公式集 Σ 重言蕴涵 公式 τ，记为 Σ |= τ，如果每一个满足 Σ 中所有 公式的真值指派都满足 τ。 Σ |= τ 也被读作 τ 是 Σ 的语义后承 。如果我们把它的定义用数学语言展开，就会 发现它涉及不止一个量词。Σ |= τ 当且仅当“对所有的真值指派 v [如果（对所有的公式 σ ∈ Σ，v¯(σ) = T）则 v¯(τ ) = T]”。 例 2.2. (1) 验证 {(α ∧ β)} |= α。 (2) 公式集 {A,(¬A)} 重言蕴涵 B 吗？ 答案：是。 我们称一个公式 τ 为一个重言式 （记作 |= τ）如果 ∅ |= τ。这与通常的“重言式在所 有真值指派下为真”或“重言式被所有真值指派满足”的说法是一致的。原因是所有的真 值指派 v 都满足“空集中每一元素”。不然的话，空集中就会有一个元素让 v 不满足它， 而这显然是不可能的。 如果 Σ = {σ} 只含有一个公式，我们有时会把 {σ} |= τ 简写成 σ |= τ。如果 σ |= τ 和 τ |= σ 都成立，则我们说 σ 和 τ 重言等价 。 重言式举例 (1) 结合律： ((A ∨ (B ∨ C)) ↔ ((A ∨ B) ∨ C))。 ((A ∧ (B ∧ C)) ↔ ((A ∧ B) ∧ C))。 1菲波那契，Fibonacci（约 1170 - 约 1250），意大利数学家 7
第4节唯一可读性 第2章命题逻辑 (2)交换律: (AVB)分(BVA) (A∧B)分(B∧A) )分配律 (A∧(B∨C)分(A∧B)V(AAC) (V(BAC)分(AVB)∧(AVC) (4)双重否定 (5)德摩根2定律 (-(A∨B)分(4)∧(=B)。 ((A∧B)分(-4)∨(-B)) (6)其它 排中律:(AV(A) 矛盾律:(-(AA(=4)) 逆否命题:(A→B)4(-B)→(A)) 第4节唯一可读性 自然语言中有大量的与标点有关的有歧义的例子。举一个雅一点的,《论语·子罕》 中的“子罕言利与命与仁”;再举个俗一点的,如段子里的“叔叔亲了我妈妈也亲了 我”。但自然语言中的歧义往往与语义有关。我们这一节要讲的是纯语法的。我们将论证 按照第一节中规则生成的合式公式没有歧义。这里的“歧义”与语义无关,指的是无论 谁来把一个公式分解成子公式,其“结果”都是一样的。或许从反面理解容易一点。像 A→B分C或A∧BVC这样的表达式就有“歧义”,因为没有表达清楚是先处理A和 B之间的运算呢,还是B和C之间的。这一节与后面的内容关系不大,除了最后的一些 约定外,其它内容可以暂时跳过。 定理23(唯一可读性).对任意公式a,下列陈述有且仅有一条适用 2德摩根, Augustus De morgan(1806-1871),英国逻辑学家,数学家 8
第 4 节 唯一可读性 第 2 章 命题逻辑 (2) 交换律： ((A ∨ B) ↔ (B ∨ A))。 ((A ∧ B) ↔ (B ∧ A))。 (3) 分配律： ((A ∧ (B ∨ C)) ↔ ((A ∧ B) ∨ (A ∧ C)))。 ((A ∨ (B ∧ C)) ↔ ((A ∨ B) ∧ (A ∨ C)))。 (4) 双重否定： ((¬(¬A)) ↔ A)。 (5) 德摩根2定律 ： ((¬(A ∨ B)) ↔ ((¬A) ∧ (¬B)))。 ((¬(A ∧ B)) ↔ ((¬A) ∨ (¬B)))。 (6) 其它： 排中律： (A ∨ (¬A))。 矛盾律： (¬(A ∧ (¬A)))。 逆否命题： ((A → B) ↔ ((¬B) → (¬A)))。 第 4 节 唯一可读性 自然语言中有大量的与标点有关的有歧义的例子。举一个雅一点的，《论语·子罕》 中的“子罕言利与命与仁”；再举个俗一点的，如段子里的“叔叔亲了我妈妈也亲了 我”。但自然语言中的歧义往往与语义有关。我们这一节要讲的是纯语法的。我们将论证 按照第一节中规则生成的合式公式没有歧义。这里的“歧义”与语义无关，指的是无论 谁来把一个公式分解成子公式，其“结果”都是一样的。或许从反面理解容易一点。像 A → B ↔ C 或 A ∧ B ∨ C 这样的表达式就有“歧义”，因为没有表达清楚是先处理 A 和 B 之间的运算呢，还是 B 和 C 之间的。这一节与后面的内容关系不大，除了最后的一些 约定外，其它内容可以暂时跳过。 定理 2.3 (唯一可读性). 对任意公式 α，下列陈述有且仅有一条适用： 2德摩根，Augustus De Morgan （1806 - 1871），英国逻辑学家，数学家。 8
第2章命题逻辑 第5节其它联词 1)a是一个命题符号。 2)a形为(-ao)其中a0为一合式公式。 (3)a形为(a1*a2)其中a1和a2为合式公式,*为某个二元联词。 不仅如此,在情形(2)和⑧3)中,公式ao,a1和a2还有二元联词大都是唯一的 证明:首先,令P(a)表示性质“(1)或(2)或(3)对a适用”。对P(a)用归纳很容易证明 三条中至少有一条适用。 然后让我们排除重叠的情形。情形(1)与情形(2)和(3)都没有重叠,因为(1)中第 个符号是命题符号,而(2)和(3)中第一个符号都是左括号;注意我们现在讨论语法,a 是作为字符串来考虑的,两个字符串相等当且仅当它们长度相同,并且每一个字节上的符 号都相同。同样,通过比较第二个字节,容易看出情形(2)和(3)也无重叠。 最后我们检查情形(2)和(3)中的唯一性。我们只看情形(3),因为情形(2)更简单。 假设α=(α1*1a2)=(12B2)(注意:这里=是指作为字符串相等)。则删去第一个左 括号后它们仍相等,a1*1a2)=B12B2)。根据引理2.1,我们有a1=B1,不然的话 个会是另外一个的真前段。继续删去相同段a1和β1,得到为a2)=太2月2)。所以*1=大2 类似地,a2=B2 关于括号省略的一些约定 旦我们知道怎样避免歧义,我们就可以放松一点。记住:底线是一旦有争议,我们 就回到最初,严格遵守规则就好了。 (1)最外的括号总被略去。 (2)否定词的“管辖范围”尽可能短。例如→AVB指的是(-4)VB)。 (3)同一联词反复出现时,以右为先。例如,α→β→γ指的是(a→(B→) 第5节其它联词 让我们再回到语义,研究联词的性质。我们说过,我们之所以选择那五个联词是因为 它们在数学文献中最为常见。很自然的问题是它们够不够用?能不能表达其它所有的联 词?另一方面看,它们有没有多余?在回答这些问题之前,先要把其中涉及的概念搞清 楚。首先,什么是一个任意的联词?字面上看,联词就是把简单句合成复合句的方式。语 义上看,每个联词都唯一确定了从简单句的真假值到复合句真假值的一个规则。说白了
第 2 章 命题逻辑 第 5 节 其它联词 (1) α 是一个命题符号。 (2) α 形为 (¬α0) 其中 α0 为一合式公式。 (3) α 形为 (α1 ⋆ α2) 其中 α1 和 α2 为合式公式，⋆ 为某个二元联词。 不仅如此，在情形 (2) 和 (3) 中，公式 α0，α1 和 α2 还有二元联词 ⋆ 都是唯一的。 证明: 首先，令 P(α) 表示性质“(1) 或 (2) 或 (3) 对 α 适用”。对 P(α) 用归纳很容易证明 三条中至少有一条适用。 然后让我们排除重叠的情形。情形 (1) 与情形 (2) 和 (3) 都没有重叠，因为 (1) 中第一 个符号是命题符号，而 (2) 和 (3) 中第一个符号都是左括号；注意我们现在讨论语法，α 是作为字符串来考虑的，两个字符串相等当且仅当它们长度相同，并且每一个字节上的符 号都相同。同样，通过比较第二个字节，容易看出情形 (2) 和 (3) 也无重叠。 最后我们检查情形 (2) 和 (3) 中的唯一性。我们只看情形 (3)，因为情形 (2) 更简单。 假设 α = (α1 ⋆1 α2) = (β1 ⋆2 β2) （注意：这里 = 是指作为字符串相等）。则删去第一个左 括号后它们仍相等，α1 ⋆1 α2) = β1 ⋆2 β2)。根据引理 2.1，我们有 α1 = β1，不然的话，一 个会是另外一个的真前段。继续删去相同段 α1 和 β1，得到 ⋆1α2) = ⋆2β2)。所以 ⋆1 = ⋆2。 类似地，α2 = β2。 关于括号省略的一些约定 一旦我们知道怎样避免歧义，我们就可以放松一点。记住：底线是一旦有争议，我们 就回到最初，严格遵守规则就好了。 (1) 最外的括号总被略去。 (2) 否定词的“管辖范围”尽可能短。例如 ¬A ∨ B 指的是 ((¬A) ∨ B))。 (3) 同一联词反复出现时，以右为先。例如，α → β → γ 指的是 ((α → (β → γ))。 第 5 节 其它联词 让我们再回到语义，研究联词的性质。我们说过，我们之所以选择那五个联词是因为 它们在数学文献中最为常见。很自然的问题是它们够不够用？能不能表达其它所有的联 词？另一方面看，它们有没有多余？在回答这些问题之前，先要把其中涉及的概念搞清 楚。首先，什么是一个任意的联词？字面上看，联词就是把简单句合成复合句的方式。语 义上看，每个联词都唯一确定了从简单句的真假值到复合句真假值的一个规则。说白了， 9