第1章 命题逻辑3

1、第1章 命题逻辑1.6 全功能联结词集全功能联结词集 定义定义1.6.1 设设p和和q是两个命题，复合命题是两个命题，复合命题p q称作称作p和和q的的不可兼析取不可兼析取，也叫，也叫异或异或。定义为：。定义为：p q为为T当且仅当当且仅当p和和q的的真值不相同时。联结词真值不相同时。联结词“ ”称为异或联结词。称为异或联结词。 表表1.18pq000011101110pq不可兼析取有下列的性质不可兼析取有下列的性质： p qq p (交换律交换律) (p q) rp (q r) (结合律结合律) 联结词联结词“ ”的真值表的真值表如表如表1.18所示。所示。 “ ”也可以看成逻辑也可以看成逻

2、辑运算，它是二元逻辑运算。运算，它是二元逻辑运算。它在程序设计中有广泛的应它在程序设计中有广泛的应用。用。第1章 命题逻辑 p(q r)(pq) (pr) (合取对异或的分配律合取对异或的分配律) p q(p q)( pq) p q(pq) p p0，0 pp，1 pp 定理定理1.6.1 设设A，B，C为命题公式，如果为命题公式，如果A BC，则，则A CB，B C A，A B C为一矛盾式。为一矛盾式。 第1章 命题逻辑 定义定义1.6.2 设设p和和q是两个命题，复合命题是两个命题，复合命题pq称作称作p和和q的的与非与非。定义为：当且仅当。定义为：当且仅当p和和q真值都是真时，真值都是

3、真时，pq才为假。才为假。 联结词联结词“”称为称为与非联结词与非联结词。 由定义可以看出下式成立：由定义可以看出下式成立： pq(pq) 联结词联结词“”的真值表如表的真值表如表1.19所所示。示。 “”也可以看成逻辑运算，它是二元逻辑运算。也可以看成逻辑运算，它是二元逻辑运算。 联结词联结词“”还有以下几个性质：还有以下几个性质：表表1.19pqpq001011101110 pp(pp) p (pq)(pq) (pp)(qq) (pq) (pq) (pq)(p)(q)pqpq第1章 命题逻辑定义定义1.6.3 设设p和和q是两个命题，复是两个命题，复合命题合命题pq称作称作p和和q的的或非

4、或非。定。定义为：当且仅当义为：当且仅当p、q的真值都为的真值都为假时，假时，pq的真值为真。联结词的真值为真。联结词“”称为称为或非联结词或非联结词。 表表1.20pqpq001010100110由此定义可得到下面的公式：由此定义可得到下面的公式： pq(pq) 联结词联结词还有下面的几个性质：还有下面的几个性质： pp(pp) p (pq)(pq) (pq) (pq)pq (pp)(qq) pq(pq)pq 第1章 命题逻辑 至此已经学了至此已经学了8个联结词：个联结词：，。类似于定义类似于定义1.2.1的方法，可以定义包含上述的方法，可以定义包含上述8个联结词的命个联结词的命题公式。题公

5、式。 定义定义1.6.4 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n1)个变元组个变元组成的公式，都可以由成的公式，都可以由S中的联结词来表示，则称中的联结词来表示，则称S是是全功能全功能联结词集联结词集。 利用下列利用下列3个等价式可将任何命题公式中的命题联结词个等价式可将任何命题公式中的命题联结词“ ”、“”和和 “”去掉。去掉。 根据命题公式的定义根据命题公式的定义 ， 是全功能联结词集。是全功能联结词集。第1章 命题逻辑 p q(pq) pq(pq) pq(pq) 所以所以 ， 是全功能联结词集。是全功能联结词集。 利用下列利用下列2个等价式可将任何命题公式中的命

6、题联结词个等价式可将任何命题公式中的命题联结词“”和和“”去掉。去掉。 用德摩根律可证明用德摩根律可证明 ， 和和 ， 分别都分别都是全功是全功能联结词集。能联结词集。 可以证明可以证明 ， 不是全功能联结词集。不是全功能联结词集。 pqpqpq(pq)(qp)(pq)(qp) 所以所以 ， 是全功能联结词集。是全功能联结词集。第1章 命题逻辑 可以证明可以证明 ， ， ， ， ， 是最小全是最小全功能联结词集。功能联结词集。 定义定义1.6.5 设设S是全功能联结词集，如果去掉其中的任何是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集，则称联结词后，就不是全功能联结词集，则

7、称S是是最小全功能最小全功能联结词集联结词集。第1章 命题逻辑表表1.21pq公式公式001或或0011或或0101或或0111或或0 两个命题变元构成的命题公式两个命题变元构成的命题公式的真值表的格式如表的真值表的格式如表1.21所示。所示。讨论讨论:n个命题变元可以构成多少个不等价的命题公式个命题变元可以构成多少个不等价的命题公式? 两个命题变元可以构成多少个不等价的命题公式？两个命题变元可以构成多少个不等价的命题公式？ 由等价的概念知道，等价的命题公式有相同的真值表，所由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两个命题变元构成的命题公式有多少个不以上述问题就转化

8、为两个命题变元构成的命题公式有多少个不同的真值表？同的真值表？222222222 真值表中每行公式的真值都真值表中每行公式的真值都有有1，0两种可能，所以命题公式两种可能，所以命题公式的真值有的真值有2222=24= =16种可能，既有种可能，既有 个不同的真值表。个不同的真值表。故有故有 种不等价的公式。种不等价的公式。 三个变元可构成三个变元可构成28= 个不等价的命题公式，个不等价的命题公式，n个变元可个变元可构成构成 个不等价的命题公式。个不等价的命题公式。 322n22第1章 命题逻辑1.7 对偶式与蕰含式对偶式与蕰含式1.7.1对偶式对偶式 从从1.3节的命题定律中可以看出，很多常

9、用等价式是成对节的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的出现的，只要将其中的“”和和“”分别换成分别换成“”和和“”，就可以由一个得到另一个。例如，将命题定律，就可以由一个得到另一个。例如，将命题定律 (AB) C(A C)(B C )中的中的“”换成换成“”, “”换成换成“”就得到了命题定律就得到了命题定律 (AB) C(AC) (B C )这些成对出现的等价式反映了这些成对出现的等价式反映了等价的对偶性等价的对偶性。本节介绍对偶。本节介绍对偶式和对偶原理。式和对偶原理。 定义定义1.7.1在在仅含联结词仅含联结词，的命题公式的命题公式A中，将联中，将联结词结词，F，

10、T分别换成分别换成，T，F所得的公式称所得的公式称为公式为公式A的的对偶式对偶式，记为，记为A*。 第1章 命题逻辑【例例1.27】求求pq和和pq的对偶式。的对偶式。 解：解： pq(pq) (pq)的对偶式是的对偶式是(pq)pq 故故pq的对偶式是的对偶式是pq；同样的方法可以证明；同样的方法可以证明pq的对偶的对偶式是式是pq。 根据例根据例1.27，对偶式概念可以推广为：在，对偶式概念可以推广为：在仅含有联结词仅含有联结词，的命题公式中，将联结词的命题公式中，将联结词，F，T分别换成分别换成 ，T，F，就得到了它的对偶式。，就得到了它的对偶式。 ，T，F，就会得到，就会得到A。即。即

11、A 是是A*的对偶式，的对偶式，(A*)*A。所以说所以说A*和和A互为对偶式。互为对偶式。 设设A*是是A的对偶式，将的对偶式，将A*中的中的，F，T分别换成分别换成第1章 命题逻辑 关于对偶式有以下两个结论。关于对偶式有以下两个结论。定理定理1.7.1 设设A*是是A的对偶式，的对偶式，p1，p2，pn是出现在是出现在A和和A*中的原子变元，则中的原子变元，则 A(p1，p2，pn)A*(p1，p2，pn) A(p1，p2，pn)A*(p1，p2，pn)【例例1.28】设命题公式设命题公式A(p,q,r)(pq)r，试用此公式验证，试用此公式验证定理定理1.7.1的有效性。的有效性。 证明

12、：验证证明：验证 A(p,q,r)A*(p, q, r) A(p,q,r)(pq)r A(p,q,r)(pq)r)(pq)r A*(p,q,r)(pq)r A*(p, q, r)( pq)r所以所以，A(p,q,r) A*(p,q,r) 第1章 命题逻辑验证验证 A(p,q,r)A*(p,q,r) A(p,q,r)(pq)r (pq)r)A*(p,q,r)第1章 命题逻辑定理定理1.7.2 (对偶原理对偶原理)设设p1，p2，pn是出现在公式是出现在公式A和和B中的所有原子变元，如果中的所有原子变元，如果AB，则，则A*B* 根据定理根据定理1.4.2（公式置换），在上述重言式中用（公式置换）

13、，在上述重言式中用pi置换置换 pi，i1, ,n，所得的公式仍为重言式，即，所得的公式仍为重言式，即 A(p1，p2，pn)B(p1，p2，pn)是重言式。是重言式。所以所以 A(p1，p2，pn)B(p1，p2，pn)由定理由定理1.7.1A*(p1，p2，pn)B*(p1，p2，pn)即即: A*B*由双条件否定等价式知由双条件否定等价式知 A*B* 定理定理1.7.2叫做对偶原理。对偶原理是数理逻辑中最基叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。本的规律之一。 证明：因为证明：因为 AB所以所以 A(p1，p2，pn)B(p1，p2，pn)是重言式。是重言式。第1章 命题逻辑

14、【例例1.29】证明重言式的对偶式是矛盾式，矛盾式的对偶式证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。是重言式。 证明：证明：设设A是重言式，即是重言式，即A1，因为，因为1的对偶式是的对偶式是0，由对偶，由对偶原理知原理知A*0。所以。所以A*是矛盾式；设是矛盾式；设A是矛盾式，即是矛盾式，即A0，而而0的对偶式是的对偶式是1，所以，所以A*1。所以。所以A*是重言式。是重言式。 1.7.2蕴含式蕴含式定义定义1.7.2 设设A和和B是命题公式，是命题公式，若若AB是重言式是重言式，则称，则称A蕴蕴含含B，记为，记为AB。 根据定义可以用真值表或等价演算证明根据定义可以用真值表或等价

15、演算证明AB。 AB定义为：定义为：AB为重言式。又由条件命题的定义知，仅在为重言式。又由条件命题的定义知，仅在AT，BF时，时，AB为假，其余情况都为真。故要证明为假，其余情况都为真。故要证明AB，只需排除只需排除AT，BF的情况。于是就有了证明的情况。于是就有了证明AB的两种方的两种方法：法：第1章 命题逻辑 对对A指定真值指定真值T，若由此推出，若由此推出B的真值不为的真值不为F，而为，而为T，则则AB是重言式，即是重言式，即AB。 对对B指定真值指定真值F，若由此推出，若由此推出A的真值不为的真值不为T，而为，而为F，则则AB是重言式，即是重言式，即AB。 【例例1.31】推证推证p(

16、pq)q 解：证法解：证法1： 证法证法2：假定假定q为为F，假定假定p(pq)为为Tp为为T且且pq为为Tp为为F且且pq为为Tq为为T。所以所以 p(pq)q 当当p为为T时，时，p为为F，所以，所以p(pq)为为F。 当当p为为F时，时，(pq)为为F，所以，所以p(pq)为为F。故故 p(pq)q第1章 命题逻辑 蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。它们都可以用上述两种方法证明，其中式。它们都可以用上述两种方法证明，其中A，B，C，D是是任意的命题公式。任意的命题公式。 1.附加律附加律 AAB， BAB 2.化简律化简律

17、 ABA， ABB 3.假言推理假言推理 A(AB)B 4.拒取式拒取式 B(AB)A 5.析取三段论析取三段论 A(AB)B， B(AB)A 6.假言三段论假言三段论 (AB)(BC)(AC) 7.等价三段论等价三段论 (AB)(BC)(AC) 8.构造性二难构造性二难 (AC)(AB)(CD)BD (AA)(AB)(AB)B 9.破坏性二难破坏性二难 (BD)(AB)(CD)(AC) 第1章 命题逻辑 等价式和蕴含式有下面的关系。等价式和蕴含式有下面的关系。定理定理1.7.3 设设A，B为任意两个命题公式，则为任意两个命题公式，则AB的充分必要的充分必要条件是条件是AB且且BA 证明证明：

18、设设AB，下证，下证AB且且BA 因为因为AB，所以，所以ABT由双条件等价式得由双条件等价式得 (AB)(BA)ABT因而因而AB与与BA都是重言式，故有都是重言式，故有AB且且BA。 设设AB且且BA，下证，下证AB。 因为因为AB且且BA，所以，所以AB与与BA都是重言式，重都是重言式，重言式的合取也是重言式，即言式的合取也是重言式，即 (AB)(BA)T再由双条件等价式得再由双条件等价式得 (AB)(AB)(BA)T 即即AB为重言式，故有为重言式，故有AB。 第1章 命题逻辑 根据此定理，以前学过的所有等价式都可以作两个蕴根据此定理，以前学过的所有等价式都可以作两个蕴含式来使用。含式

19、来使用。 例如吸收律例如吸收律A(AB)A可以作两个蕴含式可以作两个蕴含式A(AB)A和和AA(AB) 来使用。来使用。 第1章 命题逻辑证明：仅证明证明：仅证明 。 因为因为AB，CB, 所以所以ABT，CBT (AC)B(AC)B(AC)B (AB)(CB)(AB)(CB)TTT由等价的传递性，由等价的传递性，(AC)BT，故，故ACB定理定理1.7.4 设设A、B、C为合式公式。为合式公式。 AA (即蕴含是自反的即蕴含是自反的) 若若AB且且A为重言式，则为重言式，则B必为重言式。必为重言式。 若若AB且且BC，则，则AC (即蕴含是传递的即蕴含是传递的) 若若AB且且AC，则，则AB

20、C 若若AB且且CB，则，则ACB 若若AB，C是任意公式，则是任意公式，则 ACBC 第1章 命题逻辑 1.8 命题逻辑的推命题逻辑的推理理理论理论 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。数理逻辑的主要任务是用逻辑的方法研究数学中的推理。所谓推理是指从前提出发，应用推理规则推出结论的思维过所谓推理是指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由程。任何一个推理都由前提前提和和结论结论两部分组成。前提就是推两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。的新命题。 要研究推理，首

21、先应该明确什么样的推理是有效的或正要研究推理，首先应该明确什么样的推理是有效的或正确的。确的。 定义定义1.8.1 设设A1，A2，An和和C是是n+1个命题公式，若个命题公式，若A1A2AnC，则称，则称C为为A1，A2，An 的有效结论。的有效结论。也称也称C可由可由A1，A2，An 逻辑的推出。逻辑的推出。A1，A2，An叫叫做做C的一组前提。的一组前提。 A1A2AnC，亦可记为，亦可记为A1，A2，AnC。 第1章 命题逻辑 由定义由定义1.8.1可以看出，要证明可以看出，要证明C是一组前提是一组前提A1，A2，An 的有效结论，只需证明的有效结论，只需证明A1A2AnC为为重言式。

22、重言式。 用真值表证明有效结论有以下两种方法：用真值表证明有效结论有以下两种方法： 证明一个公式为重言式，可以用真值表、等价演算、证明一个公式为重言式，可以用真值表、等价演算、主析主析(合合)取范式或已知的蕴含式等方法进行。用等价演取范式或已知的蕴含式等方法进行。用等价演算和主析算和主析(合合)取范式证明重言式的方法前面已经讨论过取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说了，我们已经非常熟悉了。这里仅对真值表法作简单说明。明。 用全真值表证明用全真值表证明 要要证明证明C为前提为前提A1，A2，An 的有效结论，只需构造的有效结论，只需构造命题公式命题

23、公式A1A2AnC的真值表，证明它是重言式。的真值表，证明它是重言式。 第1章 命题逻辑 用部分真值表证明用部分真值表证明 条件命题条件命题A1A2AnC为假当且仅当它的前件为假当且仅当它的前件A1A2An为真，后件为真，后件C为假。为假。 只要能排除前件为真，后件为假的情况，只要能排除前件为真，后件为假的情况，A1A2AnC就是重言式。从而就是重言式。从而C为一组前提为一组前提A1，A2，An 的有效结论。于是就有了下面方法：的有效结论。于是就有了下面方法： 构造构造A1，A2，An与与C的真值表，且作在一个表上。的真值表，且作在一个表上。 找出找出A1，A2，An都为真的行，若都为真的行，

24、若C也为真，则也为真，则A1A2AnC，即，即C为前提为前提A1，A2，An 的有效结的有效结论。论。 找出找出C为假的行，若在每个这样的行中，为假的行，若在每个这样的行中，A1，A2，An的真值至少有一个为假，则的真值至少有一个为假，则A1A2AnC，即，即C为为一组前提一组前提A1，A2，An 的有效结论。的有效结论。 第1章 命题逻辑【例例1.32】分析事实：分析事实：“如果我有时间，那么我就去上街；如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。所以我没有时间。”。试指出这个推理前提和

25、结论，并证明。试指出这个推理前提和结论，并证明结论是前提的有效结论。结论是前提的有效结论。 解：令解：令 p：我有时间。：我有时间。 q：我去上街。：我去上街。 r：我去书店买书。：我去书店买书。 根据题意，根据题意，前提为：前提为：pq，qr，r 结论为：结论为：p 以下证明以下证明p是一组前提是一组前提pq，qr，r的有效结论。的有效结论。即证明：即证明：(pq)(qr)rp 第1章 命题逻辑 下面用部分真值下面用部分真值表进行证明。表进行证明。 作 公 式作 公 式 p q ，qr，r，p的真的真值表值表.表表1.23pqrpq qrrp0001111001110101010110111

26、1011000110101010011010101111100第1章 命题逻辑 我们已经有了判断推理是否正确的我们已经有了判断推理是否正确的4 4种方法，即真值表种方法，即真值表法、等值演算法、主范式法和蕴含演算法。当推理中包含的法、等值演算法、主范式法和蕴含演算法。当推理中包含的命题变元较多时，以上命题变元较多时，以上4 4种方法的演算量太大，给推理带来种方法的演算量太大，给推理带来了困难。为此引入命题逻辑的推理理论。了困难。为此引入命题逻辑的推理理论。 命题逻辑的推理是一个描述推理过程的命题公式序列，命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由

27、某些前提其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论应用推理规则得到的结论(中间结论或推理中的结论中间结论或推理中的结论)。它有。它有两种方法：直接推理和间接推理。两种方法：直接推理和间接推理。第1章 命题逻辑 直接推理直接推理 直接推理的基本思想是：由一组前提出发，利用一些公认直接推理的基本思想是：由一组前提出发，利用一些公认的规则，根据已知的等价式或蕴含式，推演得到有效结论。的规则，根据已知的等价式或蕴含式，推演得到有效结论。 公认的推理规则有公认的推理规则有4条：条： P规则规则：前提在推导过程中的任何时候都可以引入使用。：前提在推导过程中的任何时候都可以引入

28、使用。 T规则规则：推理中，如果一个或多个公式，蕴含了公式：推理中，如果一个或多个公式，蕴含了公式 S，则公式，则公式S可以引入到以后的推理之中。可以引入到以后的推理之中。 置换规则置换规则：在推导过程的任何步骤上，命题公式中的子：在推导过程的任何步骤上，命题公式中的子公式都可以用与之等价的公式置换。公式都可以用与之等价的公式置换。 合取引入规则合取引入规则：任意两个命题公式：任意两个命题公式A，B可以推出可以推出AB 常用的等价式和蕴合式包括常用的等价式和蕴合式包括1.3节中的节中的23个命题定律，以个命题定律，以及及1.7节中的节中的13个重要的蕴含式。个重要的蕴含式。 第1章 命题逻辑【例例1.34】用直接推理法证明用直接推理法证明(pq)(qr)pr 证明：证明： pq p q qr r间接推理间接推理 间接推理常有下列两种方法：间接推理常有下列两种方法： CP规则规则 有时要证明的有效结论是一个条件命题，即要证明：有时要证明的有效结论是一个条件命题，即要证明： PPPT假言推理假言推理T假言推理假言推理第1章 命题逻辑 H1H2Hn(AB) (*) 其中，其中，H1，H2，Hn，A，B是命题公式。是命题公式。令令 SH1H2Hn 则则(*)式可以简化为式可以简化为 S(AB)而由而由S(AB)S(AB) (SA)B(SA)B (SA)B