离散数学-第1章-命题逻辑

第1章命题逻辑

1.1命题及联结词

1.2命题公式与翻译

1.3真值表和等价公式

1.4重言式

1.5范式

1.6全功能联结词集

1.7对偶式与蕴含式

1.8命题逻辑的推理理论

返回总目录1.1命题及联结词1.1.1命题的根本概念命题的定义在数理逻辑中把能判断真假的陈述句称为命题。命题的表示一般用小写英文字母或带下标的小写英文字母表示。Remark：⑴只有陈述句才有可能成为命题⑵能判断真假的陈述句⑶虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。命题的真值：一个命题表达的判断结果称为命题的真值。任何命题的真值是惟一的。真值为“真〞TrueT1(真)真命题真值为“假〞FalseF0(假)假命题【例1.1】判断以下语句是否为命题。假设是命题，确定其真值。⑴上海是个小村庄。⑵存在外星人。⑶禁止吸烟！⑷北京是中国的首都。⑸4是素数或6是素数。⑹今天你吃了吗？⑺11+1=100 ⑻我正在说谎。解：⑴命题(F)，⑵命题(待定)，⑶不是命题(祈使句)，⑷命题(T)，⑸命题(F)，⑹不是命题(疑问句),⑺命题(由上下文确定),⑻不是命题(悖论)。

命题常量与命题变元表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。？命题变元是命题吗？不是命题变元代表任意的命题，其真值是不确定的。因而不是命题。

原子命题与复合命题〔将命题完整分类〕原子命题:如果一个命题不能再分解成更简单的命题复合命题:如果一个命题不是原子命题原子变元：顾名思义，原子变元表示的是任意一个原子命题。思考：原子命题和复合命题之间有什么样的关系呢？

在自然语言中，可以通过“如果…，那么…〞，“不但…，而且…〞这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。1.1.2命题联结词常用的逻辑联结词有五种：否认、合取、析取、条件和双条件。

1.否认联结词〔否〕设p为命题，那么p的否认是一个复合命题.记作：¬p，读作“非p〞或“p的否认〞。定义为：假设p为T，那么¬p为F；假设p为F，那么¬p的真值为T。表1.1

p¬p

0110【例1.2】否认以下命题。p：中国的每一个城市都是沿海城市。¬p：??中国的每一个城市都不是沿海城市。中国的每一个城市不都是沿海城市。2.合取联结词〔与〕设p和q均为命题，那么p和q的合取是一个复合命题记作p∧q，读作“p与q〞或“p合取q〞。定义：当且仅当p和q均为T时，p∧q的才为T。联结词“∧〞是二元逻辑运算。

pqp∧q000010100111

【例1.3】设p：2023年在北京举办奥运会。q：中国是世界四大文明古国之一。那么p∧q：2023年在北京举办奥运会并且中国是世界四大文明古国之一。补充说明：在自然语言中：p和q假设没有内在的联系，p∧q所表示的命题没有实际意义在命题逻辑中：只要p和q的真值能确定，那么p∧q就可以成为一个新命题，不管这新命题在自然语言中是否有意义。3.析取联结词〔或者〕设p和q均为命题，那么p和q的析取是一个复合命题，记作p∨q，读作“p或q〞或者“p析取q〞。定义为：当且仅当p和q均为F时，p∨q才为F。联结词“∨〞是二元逻辑运算。pqp∨q000011101111

“∨〞与汉语中的“或〞相似，但又不相同。【例1.4】以下两个命题中的“或〞，哪个是可兼或？哪个是不可兼或？⑴在电视上看这场杂技或在剧场里看这场杂技。(不可兼)⑵灯泡有故障或开关有故障。(可兼,“∨〞是可兼或)4.条件联结词〔如果…那么…〕设p和q均为命题，其条件命题是个复合命题。记为：p→q。读作“如果p，那么q〞或“假设p，那么q〞。定义为：当且仅当p为T，q为F时，p→q才为F。pqp→q00011011

p称为条件命题p→q的前件，q称为条件命题p→q的后件。联结词“→〞是二元逻辑运算。【例1.5】p：小王努力学习。q：小王学习成绩优秀。p→q：如果小王努力学习，那么他的学习成绩就优秀。

联结词“→〞与汉语中的“如果…，那么…〞或“假设…，那么…〞相似，但又是不相同的。(区别有2条)5.双条件联结词(当且仅当)设p和q均为命题，其复合命题p↔q称为双条件命题。读作：“p双条件q〞或者“p当且仅当q〞。定义为：当且仅当p和q的真值相同时，p↔q为T。联结词“↔〞是二元逻辑运算。

pqp↔q00011011双条件联结词表示的是一个充分必要关系，可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。本节学习目标：〔1〕理解并掌握命题的概念，学会判断一个语句是否为命题并确定其真值。〔2〕牢固掌握五类联结词的定义与其真值表。1.2命题公式与翻译把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。

定义按以下规那么构成的符号串称为命题演算的合式公式。〔根底〕⑴单个命题变元和常元是合式公式。〔归纳〕⑵如果A是合式公式，那么¬A是合式公式。〔归纳〕⑶如果A和B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(A↔B)是合式公式。〔界限〕⑷当且仅当有限次地应用了⑴、⑵、⑶所得到的符号串是合式公式。

命题公式一般的用大写的英文字母A，B，C，…表示。为方便起见，对命题公式约定如下：

⑴最外层括号可以省略。⑵规定联结词的优先级由高到低依次为

¬，∧，∨，→，↔。按此优先级别，如果去掉括号，不改变原公式运算次序，也可以省掉这些括号。？命题公式是命题吗？一般地说，命题公式中包含命题变元，因而无法计算其真值，所以不是命题。

用命题公式表示复合命题，常将这个过程称为命题的符号化。〔翻译〕命题的符号化可按如下步骤进行：⑴找出原子命题。⑵用小写的英文字母或带下标的小写的英文字母表示原子命题。⑶用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。

从例1.7中可以看出：〔1〕具有否认意义的命题一定不是原子命题〔2〕对于不可兼或的表示，可用¬(p↔q)本小节学习目标：〔1〕了解命题公式的概念，掌握五类连接词的优先级〔2〕掌握如何将一个复合命题符号化？1.3真值表和等价公式命题公式的真值表定义设pl，p2，…，pn是出现在公式A中的全部命题变元，给pl，p2，…，pn各指定一个真值，称为对公式A的一个赋值或解释。假设赋值使A的真值为T，那么称这个赋值为A的成真赋值，假设赋值使A的真值为F，那么称这个赋值为A的成假赋值。

定义1.3.2在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。构造真值表的几点注意：[1]先找出公式中所含的所有命题变元[2]第1行：命题变元；排列：由小到大；字典顺序[3]前n列：赋值；排列：从00…0到11…1递增如果公式A有n个命题变元，那么A的真值表应该有多少行？【例1.8】构造命题公式¬p∨q的真值表，并求成真赋值和成假赋值。解：表1.6pq¬p¬p∨q001011100110表1.7pqp∧q¬p¬q¬p∧¬q(p∧q)∨(¬p∧¬q)0001111010100010001001110001【例1.9】构造命题公式(p∧q)∨(¬p∧¬q)的真值表，并求成真赋值和成假赋值。解：命题公式(p∧q)∨(¬p∧¬q)的真值表如表1.7所示。00，11是成真赋值，01，10是成假赋值。Remark：1.如果公式A有n个命题变元，那么A的真值表应该有多少行？2.什么叫做两个真值表相等？取决于真值表的最后一列是否相同。命题公式的等价定义1.3.3设A和B是两个命题公式，对A和B的任一赋值，A和B的真值都相同，那么称A和B等价的或逻辑相等的，记为AB命题公式等价有下面的三条性质：⑴自反性，AA⑵对称性，假设AB，那么BA⑶传递性，假设AB，BC，那么AC

所谓两个命题公式等价即为两个公式的真值表相同，所以我们可以用真值表来验证两个命题公式是否等价.

【例1.12】根据等价的定义，用真值表证明

p→(q→p)

¬p→(p→¬q)证明：构造p→(q→p)和

p→(p→

q)的真值表表1.10pq¬p¬qq→pp→(q→p)p→¬q¬p→(p→¬q)00111111011001111001111111001101证明等价的另外一种方法叫做等价演算法，其根本思想是：先用真值表证明一组根本等价式，以它们为根底进行公式之间的演算。根本等价式常叫命题定律。下面是常用的命题定律。1.双重否认律 A¬¬A2.交换律 A∨BB∨A，A∧BB∧A3.结合律 (A∨B)∨CA∨(B∨C) (A∧B)∧CA∧(B∧C)4.分配律 A∧(B∨C)(A∧B)∨(A∧C) A∨(B∧C)(A∨B)∧(A∨C)5.德摩根律

¬(A∨B)

¬A∧¬B

¬(A∧B)

¬A∨¬B6.幂等律

A∧A

A，A∨A

A7.吸收律

A∨(A∧B)

A，

A∧(A∨B)

A8.零律

A∨1

1，A∧0

09.同一律A∨0

A，

A∧1

A

10.排中律 A∨¬A111.矛盾律A∧¬A012.条件等价式 A→B¬A∨B13.双条件等价式 A↔B(A→B)∧(B→A)14.假言易位式 A→B¬B→¬A15.双条件否认等价式A↔B¬A↔¬B

定义〔子公式〕如果X是合式公式A的一局部且X本身也是合式公式，那么称X为公式A的子公式。例如，Aq→(p∨(p∧q))，Xp∧q，那么X是A的子公式。定理〔等价置换〕设X是合式公式A的子公式，假设XY，如果将A中的X用Y来置换，得到的公式记为B，那么B与A等价，即AB

返回章目录本小节学习目标：1.能够写出任一命题公式的真值表。2.能熟练地应用命题定律来证明两个命题公式的等价。1.4重言式定义设A是任一命题公式。⑴假设对A的任意赋值，其真值永为真，那么称命题公式A为重言式或永真式。⑵假设对A的任意赋值，其真值永为假，那么称命题公式A为矛盾式或永假式。⑶假设A不是矛盾式，那么称命题公式A为可满足的。Remark：1.任何重言式都是可满足的。2.重言式的真值表的最后一列全为1，矛盾式的真值表的最后一列全为0，可满足的公式真值表的最后一列至少有一个1。3.亦可以用等价演算法判断公式的类型。

定理

任何两个重言式的合取或析取都是重言式。任何两个矛盾式的合取或析取都是矛盾式。定理

一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。【例1.19】由排中律知p∨¬p为重言式，以((p∨q)∧r)去置换其中的p，得公式((p∨q)∧r)∨¬((p∨q)∧r)，这是重言式。

定理

设A、B为两个命题公式，A

B当且仅当A↔B是重言式。证明：设A

B，下证A↔B是重言式。因为A

B，所以A，B具有相同的真值，由双条件联结词的定义知A↔B为真，所以A↔B为重言式。设A↔B为重言式，下证A

B给A，B的任何赋值，因为A↔B为重言式，故A，B的真值相同，由命题公式等价的定义知A

B1.5范式析取范式与合取范式定义1.5.1(根本和)由一些命题变元或其否认构成的析取式称为根本和，也叫简单析取式。约定单个变元或其否认是根本和。定义1.5.2(根本积)由一些命题变元或其否认构成的合取式称为根本积，也叫简单合取式。约定单个变元或其否认是根本积。定义1.5.3(合取范式)由根本和的合取构成的公式叫做合取范式。约定单个根本和是合取范式。定义1.5.4(析取范式)由根本积的析取构成的公式叫做析取范式。约定单个根本积是析取范式。

任何命题公式都可以化成与其等价的析取范式或合取范式。步骤如下：⑴消去联结词“→〞和“↔〞⑵消去“¬〞(双重否认律)内移“¬〞(德摩根律)⑶利用分配律，结合律将公式归约为合取范式和析取范式。

【例1.21】求命题公式(p∨q)↔p的合取范式和析取范式。解：⑴求合取范式(p∨q)↔p

((p∨q)→p)∧(p→(p∨q))(消去↔)

(¬(p∨q)∨p)∧(¬p∨(p∨q))(消去→)

((¬p∧¬q)∨p)∧(¬p∨(p∨q))(

内移)

(¬p∨p)∧(¬q∨p)∧(¬p∨p∨q)(分配律，合取范式)

1∧(¬q∨p)∧(1∨q)(排中律)

1∧(¬q∨p)∧1(零律，合取范式)

(¬q∨p)(同一律，合取范式)

⑵求析取范式(p∨q)↔p

((p∨q)∧p)∨(¬(p∨q)∧¬p)(消去↔)

((p∨q)∧p)∨((¬p∧¬q)∧¬p)(

内移)

p∨(¬p∧¬q∧¬p) (吸收律，析取范式)

p∨(¬p∧¬p∧¬q) (交换律)

p∨(¬p∧¬q) (幂等律，析取范式)命题公式的公式的合取范式并不唯一,析取范式也不惟一。

主析取范式定义1.5.5(极小项)在根本积中，每个变元及其否认不同时存在，但两者之一必须出现且仅出现一次，这样的根本积叫做布尔合取也叫小项或极小项。两个命题变元的极小项有:p∧q，p∧¬q，¬p∧q，¬p∧¬qn个命题变元共有几个极小项??2n表1.13极小项成真赋值名称¬p∧¬q00m0¬p∧q01m1p∧¬q10m2p∧q11m3表1.12

pqp∧qp∧¬q¬p∧q¬p∧¬q000001010010100100111000极小项有以下的性质：⑴每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码;(极小项与其成真赋值的对应关系为：变元对应1，而变元的否认对应0。)(2)任意两个不同的极小项的合取为永假式;(3)所有极小项的析取为永真式;表1.14极小项成真赋值名称¬p∧¬q∧¬r000m0¬p∧¬q∧r001m1¬p∧q∧¬r010m2¬p∧q∧r011m3p∧¬q∧¬r100m4p∧¬q∧r101m5p∧q∧¬r110m6p∧q∧r111m7

定义1.5.6(主析取范式)对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取组成，称该公式为原公式的主析取范式.任何命题公式都存在着与之等价的主析取范式。可由以下两种方法求得：⑴等价演算法⑵真值表法

用等价演算法求主析取范式的步骤如下：①化归为析取范式。②除去析取范式中所有永假的根本积。③在根本积中，将重复出现的合取项和相同变元合并。④在根本积中补入没有出现的命题变元，即添加∧(p∨¬p)，再用分配律展开，最后合并相同的极小项。

用真值表求主析取范式的步骤如下：①构造命题公式的真值表。

②找出公式的成真赋值对应的极小项。③这些极小项的析取就是此公式的主析取范式。

【例1.24】用等价演算法和真值表法，求(p→q)→r的主析取范式。

解：表1.15pqrp→q(p→q)→r0001000111010100111110001101011101011111公式的成真赋值对应的极小项为：¬p∧¬q∧r (成真赋值为001)¬p∧q∧r (成真赋值为011)p∧¬q∧¬r (成真赋值为100)p∧¬q∧r (成真赋值为101)p∧q∧r (成真赋值为111)(p→q)→r的主析取范式为：(p∧q∧r)∨(p∧¬q∧r)∨(p∧¬q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)

m111∨m101∨m100∨m011∨m001

m7∨m5∨m4∨m3∨m1

∑1，3，4，5，7Remark:(1)矛盾式无成真赋值，因而主析取范式为0。(2)重言式无成假赋值，因而主析取范式含2n

(n为公式中命题变元的个数)个极小项。主合取范式定义1.5.7(极大项)在根本和中，每个变元及其否认不同时存在，但两者之一必须出现且仅出现一次，这样的根本和叫作布尔析取，也叫大项或极大项。两个变元p，q构成的极大项为：p∨q，p∨¬q，¬p∨q，¬p∨¬qn个变元共有2n个极大项。极大项有以下三个性质：⑴每个极大项只有一个成假赋值，极大项不同，成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码;(极大项与成假赋值的对应关系为：变元对应0，而变元的否认对应1。)⑵任意两个不同的极大项的析取式为永真式;⑶全体极大项的合取式为永假式;定义(主合取范式)对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，那么该等价式称为原公式的主合取范式。

任何命题公式都存在着与之等价的主合取范式。也可由以下两种方法求得。⑴等价演算法(2)真值表法

用等价演算法求主合取范式,步骤如下：①化归为合取范式。②除去所有永真的根本和。③在根本和中合并重复出现的析取项和相同的变元。④在根本和中补入没有出现的命题变元。即增加∨(p∧¬p)，然后，应用分配律展开公式，最后合并相同的极大项。

用真值表求主合取范式的步骤如下：①构造命题公式的真值表。②找出公式的成假赋值对应的极大项。③这些极大项的析取就是此公式的主合取范式。

Remark:(1)矛盾式无成真赋值，因而矛盾式的主合取范式含2n(n为公式中命题变元的个数)个极大项。(2)重言式无成假赋值，因而主合取范式记为1。同一公式的主析取范式中m的下标和主合取范式中M的下标是互补的。因此，知道了主析(合)取范式就可以写出主合(析)取范式。本小节学习目标:1.能熟练写出任一命题公式的等价主合取范式和主析取范式.不可兼析取有以下性质:(1)交换律(2)结合律定义(与非)设p和q是两个命题，复合命题p↑q称作p和q的与非。定义为：当且仅当p和q真值都是真时，p↑q才为假。由定义可以看出下式成立：p↑q

¬(p∧q)

表1.19pqp↑q001011101110

联结词“↑〞还有以下几个性质：⑴p↑p¬(p∧p)¬p⑵(p↑q)↑(p↑q)¬(p↑q)¬¬(p∧q)p∧q⑶(p↑p)↑(q↑q)(¬p)↑(¬q)¬(¬p∧¬q)p∨q

定义1.6.3(或非)设p和q是两个命题，复合命题p↓q称作p和q的或非。定义为：当且仅当p、q的真值都为假时，p↓q的真值为真。表1.20pqp↓q001010100110由此定义可得：p↓q

¬(p∨q)联结词↓还有下面的几个性质：⑴

p↓p

¬(p∨p)

¬p⑵(p↓q)↓(p↓q)¬(p↓q)

¬¬(p∨q)

p∨q⑶(p↓p)↓(q↓q)¬p↓¬q¬(¬p∨¬q)

p∧q

定义1.6.4设S是一个联结词集合，如果任何n(n≥1)个变元组成的公式，都可以由S中的联结词来表示，那么称S是全功能联结词集。¬，∧，∨¬，∧和¬，∨定义1.6.5(最小全功能联结词集)设S是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集.

¬，∧

，

¬，∨

，

↑

，

↓

是最小全功能联结词集。n个命题变元可以构成多少个不等价的命题公式??

上述问题就转化为n个命题变元构成的命题公式有多少个不同的真值表？

表1.21pq公式001或0011或0101或0111或0返回章目录

1.7对偶式与蕰含式

对偶式定义在仅含联结词¬，∧，∨的命题公式A中，将联结词∨，∧，F，T分别换成∧，∨，T，F所得的公式称为公式A的对偶式，记为A*。设A*是A的对偶式，那么A

是A*的对偶式，(A*)*

A。A*和A互为对偶式。

【例1.27】求p↑q和p↓q的对偶式。解：

p↑q

¬(p∧q)¬(p∧q)的对偶式是¬(p∨q)

p↓q故p↑q的对偶式是p↓q对偶式概念可以推广为：在仅含有联结词¬，∧，∨，↑，↓的命题公式中，将联结词∨，∧，↑，↓，F，T分别换成

∧，∨，↓，↑，T，F，就得到了它的对偶式。

定理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)

(p∨q)∧r，试用此公式验证定理的有效性。证明：⑴验证¬A(p,q,r)

A*(¬p,¬q,¬r)A(p,q,r)

(p∨q)∧r¬A(p,q,r)

¬((p∨q)∧r)

(¬p∧¬q)∨¬rA*(p,q,r)

(p∧q)∨rA*(¬p,¬q,¬r)

(¬p∧¬q)∨¬r所以，¬A(p,q,r)

A*(¬p,¬q,¬r)⑵验证A(¬p,¬q,¬r)

¬A*(p,q,r)A(¬p,¬q,¬r)

(¬p∨¬q)∧¬r

¬((p∧q)∨r)

¬A*(p,q,r)

定理1.7.2(对偶原理)设p1，p2，…，pn是出现在公式A和B中的所有原子变元，如果AB，那么A*B*证明：因为AB所以A(p1，p2，…，pn)↔B(p1，p2，…，pn)是重言式A(¬p1，¬p2，…，¬pn)↔B(¬p1，¬p2，…，¬pn)是重言式。所以A(¬p1，¬p2，…，¬pn)B(¬p1，¬p2，…，¬pn)由定理1.7.1¬A*(p1，p2，…，pn)¬B*(p1，p2，…，pn)即¬A*¬B*由双条件否认等价式知A*B*

由对偶定理显然有：重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。

蕴含式 定义1.7.2〔蕴含式〕设A和B是命题公式，假设A→B是重言式，那么称A蕴含B，记为AB。证明AB的方法：⑴对A指定真值T，假设由此推出B的真值不为F，而为T，那么A→B是重言式，即AB。⑵对B指定真值F，假设由此推出A的真值不为T，而为F，那么A→B是重言式，即AB。

【例1.31】推证¬p∧(p∨q)q证法1：假定¬p∧(p∨q)为T¬p为T且p∨q为Tp为F且p∨q为Tq为T。所以¬p∧(p∨q)q证法2：假定q为F，那么p可以为T或F。①当p为T时，¬p为F，所以¬p∧(p∨q)为F。②当p为F时，(p∨q)为F，所以¬p∧(p∨q)为F。故¬p∧(p∨q)q蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。1.附加律AA∨B，BA∨B2.化简律A∧BA，A∧BB3.假言推理A∧(A→B)B4.拒取式¬B∧(A→B)¬A5.析取三段论¬A∧(A∨B)B，¬B∧(A∨B)A6.假言三段论(A→B)∧(B→C)(A→C)7.等价三段论(A↔B)∧(B↔C)(A↔C)8.构造性二难(A∨C)∧(A→B)∧(C→D)B∨D(A∨¬A)∧(A→B)∧(¬A→B)B9.破坏性二难(¬B∨¬D)∧(A→B)∧(C→D)(¬A∨¬C)4、5的证明做为练习〔作业〕等价式和蕴含式有下面的关系。定理1.7.3设A，B为任意两个命题公式，那么AB的充分必要条件是AB且BA证明：设AB，下证AB且BA因为AB，所以A↔BT(A→B)∧(B→A)A↔BTA→B与B→A都是重言式，故有AB且BA。设AB且BA，下证AB。因为AB且BA，所以A→B与B→A都是重言式，(A→B)∧(B→A)T(A↔B)(A→B)∧(B→A)T即A↔B为重言式，故有AB。

定理设A、B、C为合式公式。⑴AA(即蕴含是自反的)⑵假设AB且A为重言式，那么B必为重言式。⑶假设AB且BC，那么AC⑷假设AB且AC，那么AB∧C⑸假设AB且CB，那么A∨CB⑹假设AB，C是任意公式，那么A∧CB∧C

本小节学习目标：1、理解对偶式和蕴含式的概念。2、学会如何判断两个命题公式之间是否有蕴含关系。1.8命题逻辑的推论理论定义〔前提和有效结论〕设A1，A2，…，An和C是n+1个命题公式，假设A1∧A2∧…∧AnC，那么称C为A1，A2，…，An的有效结论，A1，A2，…，An叫做C的一组前提。要证明C是一组前提A1，A2，…，An的有效结论，只需证明A1∧A2∧…∧An→C为重言式。找出C为假的行，假设在每个这样的行中，A1，A2，…，An的真值至少有一个为假，那么A1∧A2∧…∧AnC，即C为一组前提A1，A2，…，An的有效结论。

【例1.32】分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。〞。试指出这个推理前提和结论，并证明结论是前提的有效结论。解：令p：我有时间。q：我去上街。r：我去书店买书。根据题意，前提为：p→q，q→r，¬r结论为：¬p以下证明(p→q)∧(q→r)∧¬r¬p

表1.23pqrp→qq→r¬r¬p00011110011101010101101111011000110101010011010101111100命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是前提，或者是由某些前提应用推理规那么得到的结论(中间结论或推理中的结论)。它有两种方法：直接推理和间接推理。⑴直接推理直接推理的根本思想是：由一组前提出发，利用一些公认的规那么，根据的等价式或蕴含式，推演得到有效结论。公认的推理规那么有4条：P规那么：前提在推导过程中的任何时候都可以引入使用。T规那么：推理中，如果一个或多个公式，蕴含了公式S，那么公式S可以引入到以后的推理之中。置换规那么：在推导过程的任何步骤上，命题公式中的子公式都可以用与之等价的公式置换。合取引入规那么：任意两个命题公式A，B可以推出A∧B。例1.34用直接推理法证(p→q)∧(q→r)∧p

r

证明：

⑴p→q P⑵p P