离散数学discrete2A

1、第二讲数理逻辑一、命题逻辑(Propositional Logic)1.内容概述简单命题与复合命题：什么是命题？命题联结词及其含义。命题公式与赋值：命题逻辑公式的归纳定义，命题公式的真值表。等值演算：命题公式的等值赋值，重要的等值式。命题联结词的完备集：通过等值演算得到命题联结词的完备集和极小完备集。命题公式的范式：析取范式与合取范式。命题演算系统：使用命题逻辑公式进行推理的形式系统。命题演算系统的语义与命题演算系统的元性质：注意区别形式系统的语法和语义。2.简单命题与复合命题命题(proposition)：经典命题逻辑中，称能判断真假但不能既真又假的陈述句为命题。命题对于命题逻辑来说是一个原

2、始的概念，不能在命题逻辑的范围内给出它的精确定义，只能描述它的性质。命题必须为陈述句，不能为疑问句、祈使句、感叹句等，例如下述句子为命题：1.3 是有理数2.8小于103.2是素数4.乌鸦是黑色的下列句子不是命题：1.这个小男孩多勇敢啊！2.乌鸦是黑色的吗？3.但愿中国队能取胜。4.请把门开一开！下列句子不可能判断其为真或为假，所以也不是命题：1.x + y 102.我正在撒谎命题必须具有真假值，从某种意义上来说，疑问句、祈使句、感叹句没有真假之分。但能判断真假，并不意味着现在就能确定其是真还是假，只要它具有能够唯一确定的真假值即可，例如下述陈述句是命题：1.明年的中秋节的晚上是晴天2.地球外

3、的星球上存在生物3.21世纪末，人类将居住在太空4.哥德巴赫猜想是正确的经典命题逻辑不区分现在已确定为真，还是将来可能确定为真这种情况，处理与时间有关的真值问题是时态逻辑的任务。经典命题逻辑也不区分是在技术上可以确定为真，还是现在的技术条件下不可以确定为真的这种情况，只承认在技术上，或者说能给出某种方法确定为真的那些东西才为真是直觉逻辑的观点。真命题和假命题：命题是为真或为假的陈述句，称这种真假的结果为命题的真值。如果命题的真值为真，则称为真命题，否则称为假命题。命题常量与命题变量：使用符号来表示命题，通常用p, q或带下标来表示命题常量或者变量。如果命题符号p代表命题常量则意味它是某个具体命

4、题的符号化，如果p代表命题变量则意味着它可指代任何具体命题。如果没有特别指明，通常来说命题符号p等是命题变量，即可指代任何命题。简单命题与复合命题：不能分成更简单的陈述句的命题为简单命题或原子命题，否则称为复合命题，复合命题使用命题联结词联结简单命题而得到。复合命题的联结词通常包括：设p是任意命题，复合命题“非p”称为p的否定（非），记为 p。设p和q是任意命题，复合命题“p且q”称为p和q的合取（与），记为pq。设p和q是任意命题，复合命题“p或q”称为p和q的析取（或），记为pq。设p和q是任意命题，复合命题“如果p则q”称为p蕴涵q，记为pq。设p和q是任意命题，复合命题“p当且仅当q”

5、称为p与q等价，记为pq。上述定义中的非(negation)、合取(conjunction)、析取(disjunction)、蕴涵(implication)和等价(equivalence)是在命题逻辑中的术语，而引号中给出的复合命题是自然语言中的典型用法。当然，命题逻辑中符号化形式的复合命题在自然语言中有许许多多的表达方法，这也是为什么自然语言有歧义的原因，参见教材中的各例题，并注意以下几点：pq的逻辑关系是pq为真当且仅当p和q中至少有一个为真。但自然语言中的“或”既可能具有相容性，也可能具有排斥性。命题逻辑中采用了“或”的相容性。pq的逻辑关系是pq为假当且仅当p为真，而q为假，称p为蕴涵

6、式的前件，q为蕴涵式的后件。现实世界中的“如果则”与这种蕴涵有比较大的区别。简单命题逻辑中的这种蕴涵常常称为“实质蕴涵”，相对应地有“严格蕴涵（p严格蕴涵q，意味着p为真，则q不可能为假）”、“相干蕴涵”等。实质蕴涵意味着可从假的前提推出任何命题来，或两个不没有内在联系的命题之间存在蕴涵关系。将日常生活中的陈述句符号化为命题逻辑中的公式是在今后的程序编写等课程中应用数理逻辑知识的重要基础。但就数理逻辑这门课程本身而言，我们只关心公式之间的真值关系，而不关心公式所具体指代的命题。复合命题与简单命题之间的真值关系可用下表给出，其中0代表假，1代表真：pq ppqpqpqpq001001101101

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

8、公式。【例子1.1】(p q) (p) (q r)是命题公式，它通过以下步骤生成：1.p是公式；/ 根据定义1.1的12.q是公式；/ 根据定义1.1的13.(p q)是公式；/ 根据定义1.1的24.(p)是公式；/ 根据定义1.1的25.r是公式；/ 根据定义1.1的16.(q r)是公式；/ 根据定义1.1的27.(p) (q r)是公式；/ 根据定义1.1的2，以及4, 68.(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)

9、 p q r这种树在形式语言与自动机中就称为语法分析树。【反例1.2】根据定义1.1，p q不是公式，因为两边没有园括号根据定义1.1，(p q r)不是公式，实际上，由定义1.1生成的公式，每个命题联结符都会对应一对园括号。显然(pqr)、(q(rp)等都不是公式。【定理1.2】设R是某个性质，如果有：1.对于所有的原子项p，都满足性质R；2.如果对任意的公式A和B都满足性质R，就有(A)、(AB)、(AB)、(AB)和(AB)也满足性质R。那么，所有的公式A就都满足性质R。该定理的证明类似数学归纳法的证明，很容易根据定义1.1得到。【定义1.3】命题公式A的复杂程度deg(A)定义为：1.

10、如果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(

11、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.(AB

12、)4.(AB)5.(AB)6.(AB)定理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是如何得到该其中命题公式的语法分析树的。实际上每个命题公式的最左边都是左园括号，如果从第二个符号不是左园括号，那么这个公式只有一个命题联结符。否则找与第二个左园括号配对的右园括号，从而将命题公式划分为这样的形式：() * ()，如果原来的命题公式为根的话，那么左右两边的两个命

13、题公式分别为它的左右子树了，而且对这两个公式可作类似的分析，最后到原子项。在后面，为了书写方便起见，我们省略最外边的括号，并规定各个命题联结符的优先级别为大于，大于，大于，大于，从而可省略命题公式中一些不必要的园括号，例如例子1.1中的公式可写为：p q p q r。不过在后面我们书写公式的原则是尽量简便，但又能让读者容易理解。而有关命题公式的性质的讨论，则只针对可由上面定义1.1所能生成的公式形式。上面讨论的命题公式的语法结构，下面讨论命题公式的赋值。【定义1.7】 对命题公式的一次真值赋值t是从所有命题变量所组成的集合到集合0, 1的函数。实际上，对于某个命题公式A来说，我们只关心t在A中

14、的命题变量上的值。这里我们假定存在一个所有命题变量所组成的集合U，或者说我们所有命题公式中的变量都取之于集合U，我们记命题公式A中的所有命题变量所组成的集合为Var(A)。设有一个真值赋值t : U0, 1，而对于命题公式A的真值赋值来说，我们只关心t在Var(A)上的值。【例子1.3】对于命题公式A = (p q) (p) (q r)，有：Var(A) = p, q, r这里不妨假定U = Var(A)，真值赋值就是一个函数t : p, q, r0, 1，例如可令：t(p) = 0, t(q) = 1, t(r) = 0【定义1.8】命题公式A在真值赋值t : U0, 1下的真值t(A)递归

15、定义如下：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(AB) = 1，否则t(AB) = 0。5.若t(A) = t(B) = 0，则t(AB) = 0，否则t(AB) = 1。6.若t(A) = 0或者t(B) = 1，则t(AB) = 1，否则t(AB) = 0。7.若t(A) = t(B)，则t(AB) = 1，否则t(AB) = 0。【例子1.3，续】对于命题公式A = (p

16、 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的54.t(p) = 1;/ 根据定义1.8的35.t(r) = 0;6.t(q r) = 0;/ 根据定义1.8的47.t(p) (q r) = 0;/ 根据定义1.8的78.t(p q) (p) (q r) = 0;/ 根据定义1.8的6因此命题公式A在上述真值赋值下的真值t(A)是0。不难看出，定义1.8与上一节中给出的复合命题与简单命题之间的真值关系表是一致的。而且从上面的例子与例1.1的比较也可

17、看出，对于命题公式的真值，可根据该命题公式的生成步骤来得到。命题公式的真值只与命题公式中所出现的命题变量的真值赋值有关，如果命题公式中含有n个命题变量，则对这些命题变量的真值赋值共有2n种不同情况，可通过一个表，列出在这所有情况下命题公式的真值，这种表称为该命题公式的真值表，例如上述命题公式A的真值表为：pqr(pq)(p)(qr)(p)(qr)(pq) (p)(qr)0000100100101001010110000111111110010011101100111101001111110100【定义1.9】如果命题公式A在任意的真值赋值函数t : U0, 1下的真值t(A)都为1,则称命题公

18、式A为永真式(tautology)（或称重言式）；如果命题共A在任意的真值赋值函数下的真值都为0，则称A为矛盾式(contradiction)；如果A不是矛盾式，则称为可满足式。【例子1.4】根据命题公式A = (p q) (p) (q r)的真值表，我们知该命题公式是可满足式，但不是永真式。而公式B = (p(qp)r)是永真式，其真值表为：pqr(qp)(p(qp)(p(qp)r)000011001011010111011111100111101111110111111111而公式(pq)q)r)（教材14页简写为(pq)qr）是矛盾式，其真值表为：pqr(pq)(pq)(pq)q)(pq

19、)q)r)00010000011000010100001110001000100101010011010001111000【定义1.10】我们使用符号S来表示一组命题公式所构成的集合。定义S在真值赋值函数t : U0, 1下的真值t(S)为：t(S) = 1当且仅当对S中任意公式A有t(A) = 1，否则定义t(S) = 0(注意只要S中存在某个公式A使得t(A) = 0，就有t(S) = 0)。说S是可满足的，如果存在某个真值赋值函数t使得t(S) = 1，这时称t满足S。【定义1.11】设S是一组命题公式的集合，说命题公式A是以S为前提的永真式，如果满足对任意满足S的真值赋值函数t都有t(

20、A) = 1，这时我们记为SA。注意在定义1.11中，如果S为空集，则fA表示A为永真式，因为对于空集S来说，显然任意的真值赋值函数t都满足它（因为S中没有命题公式），从而fA意味着对任意的真值赋值函数t都有t(A) = 1，即A为永真式。4.等值演算【定义1.12】当S = A1, A2, , An时，我们也记SA为A1, A2, , AnA。如果有AB且BA，则称命题公式A与B等值，记为AB。实际上公式A与B等值记为AB会更准确些，但教材采用了符号AB，为了不会过于混淆，我们也使用这种记号。实际上，根据定义1.11，AB就意味着对任意的真值赋值函数t有t(A) = 1当且仅当t(B) =

21、1，也就是说对任意的t有t(A) = t(B)。从而定义1.12与教材中关于命题公式等值的定义是等价的，即有下述定理：【定理1.13】AB当且仅当AB是永真式。使用真值表，不难证明下面的定理：【定理1.14】设A, B, C是任意的命题公式，有：1.双重否定律：A (A)2.等幂律：A(AA)A(AA)3.交换律：(AB) (BA)(AB) (BA)4.结合律：(AB)B) (A(BB)(AB)B) (A(BB)5.分配律：(A(BC) (AB)(AC)(A(BC) (AB)(AC)6.德摩根律：(AB) (A)(B)(AB) (A)(B)7.吸收律：(A(AB) A(A(AB) A8.零律：

22、(A1) 1(A0) 09.同一律：(A 0) A(A1) A10.排中律：(A(A) 111.矛盾律：(A(A) 012.蕴涵等值式：(AB) (A)B)13.等价等值式：(AB) (AB)(BA)14.假言易位：(AB) (B)(A)15.等价否定等值式：(AB) (A)(B)16.归谬论：(AB)(A(B) (A)要注意的是，上述定理中的0代表真值为0的任意命题常量，而1代表真值为1的任意命题常量。由于命题联结符号和都满足结合律，因此我们可有如下的简写：A1A2AnA1A2An根据以上简写，我们可推广定理1.13为以下定理1.15：【定理1.15】1.A1, A2, , AnA当且仅当f

23、(A1A2An)A)。2.A1, A2, , AnA当且仅当f(A1(A2(AnA)。【引理1.16】设有AA和BB，则有：1.(A)(A)2.(AB)(AB)3.(AB)(AB)4.(AB)(AB)5.(AB)(AB)根据引理1.16，不难证明下面的置换规则：【定理1.17】设有BC，而A是命题公式A通过使用C替换A中出现的某些B（不需要是替换所有的B）而得到的命题公式，则有AA。【证明】对命题公式A的结构进行归纳。首先如果B = A，则有C = A，从而有AA。归纳基：如果A是命题变量和命题常量，那么必有B = A，因此定理成立。归纳步：根据定理1.6，命题公式A必为如下5种形式之一：A1

24、, A1A2, A1A2, A1A2, A1A2。设A的形式为A1，如果B = A则定理成立，否则必有B出现A1中，将A1中的B用C替换后得到的为A1，按归纳假设有A1 = A1，再根据引理1.15有A1 = A1。定理成立。若A的形式为A1 * A2，则如果B = A则定理成立，否则必有B出现在A1或A2中，或同时出现在这两者中。设将A1中的B用C替换后得到的为A1，而将A2中的B用C替换后得到的为A2，按归纳假设有A1A1和A2 A2，再根据引理1.15有A1*A2A1*A2，即定理成立。【定义1.18】如果命题公式A中只出现命题变量、命题常量、命题联结符号、和则称为限制性（命题）公式。定

25、义：1.对于限制性公式A，将其中的命题联结符号换成，命题联结符号换成得到的公式称为A的对偶公式(dual formula)，记为Aop。2.对于限制性公式A，将其中出现的所有原子项（命题变量或命题常量）p换成p得到的公式称为A的内否式，记为A。【例子1.5】设公式A = (pq)(r)，则：(1).A的对偶式Aop = (pq)(r)(2).A的内否式A = (p) (q) r)【引理1.19】设公式A、B都是限制性公式，有：1.(Aop)op A(A) A2.(A B)op Aop Bop(A B) A B3.(A B)op Aop Bop(A B) A B4.(Aop) (A)op引理1.

26、19中的(恒等号)表示两边的公式在（语法）形式上完全一样，例如(Aop)op A表示对A的对偶公式Aop再做一次对偶操作得到的就是A本身。而(Aop) (A)op表示对A做一次对偶操作得到Aop，然后再求Aop的内否式，得到的公式与先求A的内否式，然后再做对偶操作得到的公式完全一样，用代数学的术语来说，就是这两种操作可交换。引理1.19很容易根据定义1.18证明，也可直观理解引理1.19所代表的含义。读者可通过对一些公式求它的对偶式和内否式来验证引理1.19的每个恒等式，例如：【例子1.5，续】设公式A = (pq)(r)，则：(1).Aop = (pq)(r), (Aop) = (p)(q) r)(2).A = (p) (q) r), (A)op = (p) (q) r)显然有(Aop) (A)op。【定理1.20】设公式A是任意的限制性公式，有：1.(A)op (Aop)(A) (A)2.(Aop) A【证明】略【推论1.21】设公式A和B都是限制性公式，有A B则(Aop) (Bop)【证明】根据引理1.16