离散数学discrete2A

第二讲 数理逻辑

一、命题逻辑(Propositional Logic)

1. 内容概述

·简单命题与复合命题：什么是命题？命题联结词及其含义。

·命题公式与赋值：命题逻辑公式的归纳定义，命题公式的真值表。 ·等值演算：命题公式的等值赋值，重要的等值式。

·命题联结词的完备集：通过等值演算得到命题联结词的完备集和极小完备集。

·命题公式的范式：析取范式与合取范式。

·命题演算系统：使用命题逻辑公式进行推理的形式系统。

·命题演算系统的语义与命题演算系统的元性质：注意区别形式系统的语法和语义。

2. 简单命题与复合命题

·命题(proposition)：经典命题逻辑中，称能判断真假但不能既真又假的陈述句为命题。 ·命题对于命题逻辑来说是一个原始的概念，不能在命题逻辑的范围内给出它的精确定义，只能描述它的性质。 ·命题必须为陈述句，不能为疑问句、祈使句、感叹句等，例如下述句子为命题： 1. ?3 是有理数 2. 8小于10 3. 2是素数 4. 乌鸦是黑色的 下列句子不是命题： 1. 这个小男孩多勇敢啊！ 2. 乌鸦是黑色的吗？ 3. 但愿中国队能取胜。 4. 请把门开一开！ 下列句子不可能判断其为真或为假，所以也不是命题： 1. x + y > 10 2. 我正在撒谎 ·命题必须具有真假值，从某种意义上来说，疑问句、祈使句、感叹句没有真假之分。但能判断真假，并不意味着现在就能确定其是真还是假，只要它具有能够唯一确定的真假值即可，例如下述陈述句是命题： 1. 明年的中秋节的晚上是晴天 2. 地球外的星球上存在生物 3. 21世纪末，人类将居住在太空 4. 哥德巴赫猜想是正确的 ·经典命题逻辑不区分现在已确定为真，还是将来可能确定为真这种情况，处理与时间有关的真值问题是时态逻辑的任务。经典命题逻辑也不区分是在技术上可以确定为真，还是现在的技术条件下不可以确定为真的这种情况，只承认在技术上，或者说能给出某种方法确定为真的那些东西才为真是直觉逻辑的观点。 ·真命题和假命题：命题是为真或为假的陈述句，称这种真假的结果为命题的真值。如果命题的真值为真，则称为真命题，否则称为假命题。 ·命题常量与命题变量：使用符号来表示命题，通常用p, q或带下标来表示命题常量或者变量。如果命题符号p代表命题常量则意味它是某个具体命题的符号化，如果p代表命题变量则意味着它可指代任何具体命题。如果没有特别指明，通常来说命题符号p等是命题变量，即可指代任何命题。

·简单命题与复合命题：不能分成更简单的陈述句的命题为简单命题或原子命题，否则称为复合命题，复合命题使用命题联结词联结简单命题而得到。 ·复合命题的联结词通常包括： ·设p是任意命题，复合命题“非p”称为p的否定（非），记为? p。 ·设p和q是任意命题，复合命题“p且q”称为p和q的合取（与），记为p?q。 ·设p和q是任意命题，复合命题“p或q”称为p和q的析取（或），记为p?q。 ·设p和q是任意命题，复合命题“如果p则q”称为p蕴涵q，记为p?q。 ·设p和q是任意命题，复合命题“p当且仅当q”称为p与q等价，记为p?q。 ·上述定义中的非(negation)、合取(conjunction)、析取(disjunction)、蕴涵(implication)和等价(equivalence)是在命题逻辑中的术语，而引号中给出的复合命题是自然语言中的典型用法。当然，命题逻辑中符号化形式的复合命题在自然语言中有许许多多的表达方法，这也是为什么自然语言有歧义的原因，参见教材中的各例题，并注意以下几点： ·p?q的逻辑关系是p?q为真当且仅当p和q中至少有一个为真。但自然语言中的“或”既可能具有相容性，也可能具有排斥性。命题逻辑中采用了“或”的相容性。 ·p?q的逻辑关系是p?q为假当且仅当p为真，而q为假，称p为蕴涵式的前件，q为蕴涵式的后件。现实世界中的“如果…则…”与这种蕴涵有比较大的区别。简单命题逻辑中的这种蕴涵常常称为“实质蕴涵”，相对应地有“严格蕴涵（p严格蕴涵q，意味着p为真，则q不可能为假）”、“相干蕴涵”等。实质蕴涵意味着可从假的前提推出任何命题来，或两个不没有内在联系的命题之间存在蕴涵关系。 ·将日常生活中的陈述句符号化为命题逻辑中的公式是在今后的程序编写等课程中应用数理逻辑知识的重要基础。但就数理逻辑这门课程本身而言，我们只关心公式之间的真值关系，而不关心公式所具体指代的命题。 ·复合命题与简单命题之间的真值关系可用下表给出，其中0代表假，1代表真：

p q ? p p?q p?q p?q p?q 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 3. 命题逻辑公式

【定义1.1】命题逻辑公式(propositional logic formula)由以下子句归纳定义：

[1]. 归纳基：命题常量或命题变量是命题逻辑公式，称为命题逻辑公式的原子项。 [2]. 归纳步：如果A, B是逻辑公式，则(?A)、(A?B)、(A?B)、(A?B)和(A?B)也是命题逻辑公式。 [3]. 最小化：所有的命题逻辑公式都通过1和2得到。 □ 在这里我们隐含地使用的字母表是大小写的英文字母、命题联结符和园括号。英文字母还可带下标。其它的符号都不属于我们的符号表，即在命题逻辑公式中不能出现这些符号。后面我们将命题逻辑公式简称为命题公式，或在没有二义的情况下进一步简称为公式。 【例子1.1】((p ? q) ? ((?p) ? (q ? r)))是命题公式，它通过以下步骤生成： 1. p是公式； // 根据定义1.1的[1] 2. q是公式； // 根据定义1.1的[1] 3. (p ? q)是公式； // 根据定义1.1的[2] 4. (?p)是公式； // 根据定义1.1的[2] 5. r是公式； // 根据定义1.1的[1] 6. (q ? r)是公式； // 根据定义1.1的[2]

7. ((?p) ? (q ? r))是公式； // 根据定义1.1的[2]，以及4, 6 8. ((p ? q) ? ((?p) ? (q ? r)))是公式。 // 根据定义1.1的[2]，以及3, 7 这种生成过程，可以形象地用下面的一棵树来表示： ((p ? q) ? ((?p) ? (q ? r)))

(p ? q) ((?p) ? (q ? r))

p q (?p) (q ? r)

p q r 这种树在形式语言与自动机中就称为语法分析树。 【反例1.2】

·根据定义1.1，p ? q不是公式，因为两边没有园括号

·根据定义1.1，(p ? q ? r)不是公式，实际上，由定义1.1生成的公式，每个命题

联结符都会对应一对园括号。

·显然(pq?r)、(q?(r?p)等都不是公式。

【定理1.2】设R是某个性质，如果有： [1]. 对于所有的原子项p，都满足性质R；

[2]. 如果对任意的公式A和B都满足性质R，就有(?A)、(A?B)、(A?B)、(A?B)

和(A?B)也满足性质R。

那么，所有的公式A就都满足性质R。 □ 该定理的证明类似数学归纳法的证明，很容易根据定义1.1得到。 【定义1.3】命题公式A的复杂程度deg(A)定义为： [1]. 如果A是原子项，则deg(A) = 0； [2]. deg(?A) = deg(A) + 1; [3]. deg(A * B) = max(deg(A), deg(B)) + 1，其中*代表?、?、?、?之一。 □ 此定义等价于教材p11的定义1.7。只不过我们在这里给出的是递归定义。使用归纳法，我们可证明下面定理：

【定理1.4】deg(A)小于等于命题公式A中的命题联结符号的数目。 【证明】根据命题公式A的结构进行归纳证明： 1. 归纳基：如果A是原子项，则根据定义1.3有deg(A) = 0，显然定理成立。 2. 归纳步：假设定理对于命题公式A和B成立（归纳假设），记命题公式A中的命题联结符号数为Sym(A)，即有deg(A) ? Sym(A)和deg(B) ? Sym(B)。那么由于deg(?A) = deg(A) + 1，而Sym(?A) = Sym(A) + 1，所以定理对于?A也成立。同样由于deg(A * B) = max(deg(A), deg(B)) + 1，而Sym(A * B) = Sym(A) + Sym(B) + 1，因而有deg(A * B)? Sym(A * B)，从而定理对所有的命题公式都成立。 □ 【定理1.5】任意命题逻辑公式A中出现相等数目的左右园括号，实际上，左右园括号的个数都等于A中的命题联结符号数。 □ 【定理1.6】任意命题逻辑公式A具有下列6种形式之一，且只具有其中一种形式： [1]. A为原子项； [2]. (?A) [3]. (A?B) [4]. (A?B) [5]. (A?B) [6]. (A?B) □ 定理1.6的确切含义包括以下几点：

1. 任意命题公式必然具有上述6中形式之一； 2. 这6中形式都互不相同； 3. 如果(?A)与(?A1)相同，则必有A与A1相同； 4. 如果(A * B)与(A1 * B1)相同，则必有A与A1相同，且B与B1相同。

根据定理1.5和定理1.6，我们不难明白例子1.1是如何得到该其中命题公式的语法分析树的。实际上每个命题公式的最左边都是左园括号，如果从第二个符号不是左园括号，那么这个公式只有一个命题联结符。否则找与第二个左园括号配对的右园括号，从而将命题公式划分为这样的形式：((…) * (…))，如果原来的命题公式为根的话，那么左右两边的两个命题公式分别为它的左右子树了，而且对这两个公式可作类似的分析，最后到原子项。 在后面，为了书写方便起见，我们省略最外边的括号，并规定各个命题联结符的优先级别为?大于?，?大于?，?大于?，?大于?，从而可省略命题公式中一些不必要的园括号，例如例子1.1中的公式可写为：p ? q ? ?p ? q ? r。不过在后面我们书写公式的原则是尽量简便，但又能让读者容易理解。而有关命题公式的性质的讨论，则只针对可由上面定义1.1所能生成的公式形式。 上面讨论的命题公式的语法结构，下面讨论命题公式的赋值。

【定义1.7】 对命题公式的一次真值赋值t是从所有命题变量所组成的集合到集合{0, 1}的函数。实际上，对于某个命题公式A来说，我们只关心t在A中的命题变量上的值。这里我们假定存在一个所有命题变量所组成的集合U，或者说我们所有命题公式中的变量都取之于集合U，我们记命题公式A中的所有命题变量所组成的集合为Var(A)。设有一个真值赋值t : U?{0, 1}，而对于命题公式A的真值赋值来说，我们只关心t在Var(A)上的值。

【例子1.3】对于命题公式A = ((p ? q) ? ((?p) ? (q ? r)))，有： Var(A) = {p, q, r}

这里不妨假定U = Var(A)，真值赋值就是一个函数t : {p, q, r}?{0, 1}，例如可令： t(p) = 0, t(q) = 1, t(r) = 0

【定义1.8】命题公式A在真值赋值t : U?{0, 1}下的真值t(A)递归定义如下： [1]. 如果命题公式A是一个命题常量p，则如果p为真，t(A) = 1，否则t(A) = 0； [2]. 如果命题公式A是一个命题变量p，则t(A) = t(p) [3]. 若t(A) = 0则t(?A) = 1，否则t(?A) = 0。 [4]. 若t(A) = t(B) = 1，则t(A?B) = 1，否则t(A?B) = 0。 [5]. 若t(A) = t(B) = 0，则t(A?B) = 0，否则t(A?B) = 1。 [6]. 若t(A) = 0或者t(B) = 1，则t(A?B) = 1，否则t(A?B) = 0。 [7]. 若t(A) = t(B)，则t(A?B) = 1，否则t(A?B) = 0。

【例子1.3，续】对于命题公式A = ((p ? q) ? ((?p) ? (q ? r)))，及真值赋值函数t： t(p) = 0, t(q) = 1, t(r) = 0 有： 1. t(p) = 0, t(q) = 1; 2. t(p ? q) = 1; // 根据定义1.8的[5] 4. t(?p) = 1; // 根据定义1.8的[3] 5. t(r) = 0; 6. t(q ? r) = 0; // 根据定义1.8的[4] 7. t((?p) ? (q ? r)) = 0; // 根据定义1.8的[7] 8. t((p ? q) ? ((?p) ? (q ? r))) = 0; // 根据定义1.8的[6]