第1章 命题逻辑

1、第1章 命题逻辑第1章 命题逻辑 1.1 命题及联结词命题及联结词 1.2 命题公式与翻译命题公式与翻译 1.3 真值表和等价公式真值表和等价公式 1.4 重言式重言式 1.5 范式范式 1.6 全功能联结词集全功能联结词集 1.7 对偶式与蕴含式对偶式与蕴含式 1.8 命题逻辑的推理理论命题逻辑的推理理论 第1章 命题逻辑第1章 命题逻辑 1.1命题及联结词 1.1.1 命题的基本概念 在数理逻辑中把能判断真假的陈述句称为命题。一般用小写英文字母或小写英文字母带下标表示。 命题的概念包含了以下3个要素： 只有陈述句才有可能成为命题，而其它的语句，如：感叹句、祈使句、疑问句等都不是命题。 一个

2、语句虽是陈述句,但不能判断真假不是命题。 虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。 一个命题表达的判断结果称为命题的真值。命题的真值有“真”和“假”两种，分别用True、T、1(真)和False、F、0(假)来表示。真值为真的命题称为真命题，真值为假的命题称为假命题。任何命题的真值是惟一的。第1章 命题逻辑 在命题逻辑中对命题不再细分，因而命题是数理逻辑中最基本的也是最小的研究单位。 【例1.1】判断以下语句是否为命题。若是命题，确定其真值。 上海是个小村庄。 存在外星人。 禁止吸烟！ 北京是中国的首都。 4是素数或6是素数。 今天你吃了吗？ 11+1=100

3、 我正在说谎。 解：命题(F)，命题(待定)，不是命题(祈使句)， 命题(T)，命题(F)，不是命题(疑问句), 命题(由上下文确定), 不是命题(悖论)。第1章 命题逻辑 表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。命题变元无确定的真值。 命题是能判断真假的陈述句。而命题变元代表任意的命题，其真值是不确定的。因而不是命题。 如果一个命题不能再分解成更简单的命题，则称该命题为原子命题。如果一个命题不是原子命题，称该命题为复合命题。 如果命题变元表示原子命题时，该命题变元称为原子

4、变元。 在自然语言中，可以通过“如果，那么”，“不但，而且”这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将原子变元联结起来表示复合命题。第1章 命题逻辑 1.1.2 命题联结词 常用的逻辑联结词有五种：否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。 1. 否定联结词 定义1.1.1 设p为命题，则p的否定是一个复合命题，记作：p，读作“非p”或“p的否定”。定义为：若P为T，则p为F；若p为F，则p的真值为T。 表1.1 p p 0 1 1 0 p和p的关系如表1.1所示，表1.1叫做否定联结词“”的真值表(下同)。 联结词“”也可以看作逻辑

5、运算，它是一元运算。 【例1.2】否定下列命题。 p：王强是一名大学生。 p：王强不是一名大学生。 第1章 命题逻辑 2. 合取联结词 定义1.1.2设p和q均为命题，则p和q的合取是一个复合命题，记作pq，读作“p与q”或“p合取q”。定义为：当且仅当p和q均为T时，pq的才为T。 联结词“”的真值表如表1.2所示。 联结词“”也可以看成逻辑运算，它是二元逻辑运算。 表1.2 pqpq0 00010100111 【例1.3】设 p：2008年将在北京举办奥运会。 q：中国是世界四大文明古国之一。 则pq：2008年将在北京举办奥运会并且中国是世界四大文明古国之一。第1章 命题逻辑 3. 析取

6、联结词 定义1.1.3 设p和q均为命题，则p和q的析取是一个复合命题，记作pq，读作“p或q”或者“p析取q”。定义为：当且仅当p和q均为F时，pq才为F。 联结词“”的真值表如表1.3所示。 联结词“”也可以看成逻辑运算，它是二元逻辑运算。表1.3pqpq000011101111 “”与汉语中的“或”相似，但又不相同。汉语中的或有可兼或与不可兼或(排斥或)的区分。 【例1.4】下列两个命题中的“或”，哪个是可兼或？哪个是不可兼或？ 在电视上看这场杂技或在剧场里看这场杂技。(不可兼) 灯泡有故障或开关有故障。(可兼, “”是可兼或) 第1章 命题逻辑 4. 条件联结词 定义1.1.4 设p和

7、q均为命题，其条件命题是个复合命题，记为：pq。读作“如果p，那么q”或“若p，则q”。定义为：当且仅当p为T，q为F时，pq才为F。p称为条件命题pq的前件，q称为条件命题pq的后件。 联结词“”真值表如表1.4所示。 联结词“”也可以看成逻辑运算，它是二元逻辑运算。 表1.4 pqpq001011100111 【例1.5】 p：小王努力学习。q：小王学习成绩优秀。 pq：如果小王努力学习，那么他的学习成绩就优秀。 联结词“”与汉语中的“如果，那么”或“若，则”相似，但又是不相同的。第1章 命题逻辑 5. 双条件联结词 定义1.1.5设p和q均为命题，其复合命题pq称为双条件命题，读作：“p

8、双条件q”或者“p当且仅当q”。定义为：当且仅当p和q的真值相同时，pq为T。 联结词“”的真值表如表1.5所示。 联结词“”也可以理解成逻辑运算，它是二元逻辑运算。 双条件联结词表示的是一个充分必要关系，与前面所述相同，也可以不必表1.5 pqpq001010100111顾及其前因后果，而只根据联结词的定义来确定其真值。 【例1.6】设p：张华是三好学生。 q：张华德、智、体全优秀。 pq：张华是三好学生当且仅当德、智、体全优秀。第1章 命题逻辑 1.2 命题公式与翻译 把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。当使用联结词集，时，合

9、式公式定义如下： 定义1.2.1按下列规则构成的符号串称为命题演算的合式公式，也称为命题公式，简称公式。 单个命题变元和常元是合式公式。 如果A是合式公式，那么A是合式公式。 如果A和B是合式公式，那么(AB)、(AB)、(AB)和(AB)是合式公式。 当且仅当有限次地应用了、所得到的符号串是合式公式。 命题公式一般的用大写的英文字母A，B，C，表示。 依照这个定义，下列符号串是合式公式：第1章 命题逻辑 (pq)，(pq)，(p(pq)， (pq)(qr)(st) 下列符号串不是合式公式： (pq)(q)，(pq，(pq)q) 定义1.2.1给出合式公式定义的方法称为归纳定义，它包括三部分：

10、基础，归纳和界限。定义1.2.1中的是基础，和是归纳，是界限。下文中还将多次出现这种形式的定义。 为方便起见，对命题公式约定如下： 最外层括号可以省略。 规定联结词的优先级由高到低依次为，。按此优先级别，如果去掉括号，不改变原公式运算次序，也可以省掉这些括号。 一般地说，命题公式中包含命题变元，因而无法计算其真值，所以不是命题。 命题公式中的命题变元，也叫命题公式的分量。第1章 命题逻辑 有了命题公式的概念，就可以用命题公式表示复合命题，常将这个过程称为命题的符号化。命题的符号化可按如下步骤进行： 找出复合命题中的原子命题。 用小写的英文字母或带下标的小写的英文字母表示这些原子命题。 使用命题

11、联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。 【例1.7】将下列命题符号化： 他或者骑自行车去学校，或者乘公共汽车去学校。 解：令 p：他骑自行车去学校。 q：他乘公共汽车去学校。 此命题中的或是不可兼或，所以不能符号化为：pq。而要符号化为：(pq)或(pq)(pq)。稍后会看到这个表示是正确的。第1章 命题逻辑 1.3真值表和等价公式 1.3.1命题公式的真值表 定义1.3.1 设pl，p2，pn是出现在公式A中的全部命题变元，给pl，p2，pn各指定一个真值，称为对公式A的一个赋值或解释。若指定的赋值使A的真值为T，则称这个赋值为A的成真赋值，若使A的真值为F，则称这个赋

12、值为A的成假赋值。 例如，给公式(pqr)赋值011是指p=0，q=1，r=1，它是该公式的成真赋值；赋值110是指p=1，q=1，r=0，它是该公式的成假赋值。 定义1.3.2 在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。 第1章 命题逻辑 【例1.8】构造命题公式pq的真值表，并求成真赋值和成假赋值。 解：命题公式pq的真值表如表1.6所示。00，01，11是成真赋值，10是成假赋值。 表1.6pqppq0011011110001101第1章 命题逻辑表1.7pqpqpqpq(pq)(pq)0001111010100010001001

13、110001 【例1.9】构造命题公式(pq)(pq)的真值表，并求成真赋值和成假赋值。 解：命题公式(pq)(pq)的真值表如表1.7所示。00， 11是成真赋值，01，10是成假赋值。 第1章 命题逻辑 1.3.2命题公式的等价 定义1.3.3 设A和B是两个命题公式，对A和B的任一赋值，A和B的真值都相同，则称A和B是等价的或逻辑相等的，记为AB 可以证明，命题公式等价有下面的三条性质： 自反性，即对任意命题公式A， AA 对称性，即对任意命题公式A和B，若AB，则BA 传递性，即对任意命题公式A，B和C，若AB，BC，则AC 根据定义1.3.3，可以用真值表证明命题公式是等价的，请看下

14、面的例题。 【例1.12】根据等价的定义，用真值表证明 p(qp)p(pq) 证明：构造p(qp)和p(pq)的真值表，如表1.10所示。p(qp)和p(pq)所在的列完全相同，它们具有相同的真值表。所以p(qp)p(pq) 第1章 命题逻辑表1.10 pqpqqpp(qp)pqp(pq)00111111011001111001111111001101 证明等价的另外一种方法叫做等价演算法，其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。基本等价式常叫命题定律。下面是常用的命题定律。 1.双重否定律 AA 2.交换律 ABBA， ABBA 3.结合律 (AB)CA(

15、BC) (AB)CA(BC)第1章 命题逻辑 4.分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 5.德摩根律 (AB)AB (AB)AB 6.幂等律 AAA，AAA 7.吸收律 A(AB)A， A(AB)A 8.零律 A11，A00 9.同一律 A0A， A1A 10.排中律 AA1 11.矛盾律 AA0 12.条件等价式ABAB 13.双条件等价式AB(AB)(BA) 14.假言易位式ABBA 15.双条件否定等价式 ABAB第1章 命题逻辑 以上共23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。 【例1.13】用真值表证明德摩根律 (AB)AB 解

16、：表1.11是(AB)和AB的真值表，从表中可以看出德摩根律成立。 表1.11ABABABAB (AB)0011101011001010010101100010第1章 命题逻辑 定义1.3.4如果X是合式公式A的一部分且X本身也是合式公式，则称X为公式A的子公式。 例如，Aq(p(pq)，Xpq，则X是A的子公式。 定理1.3.1设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，得到的公式记为B，则B与A等价，即AB 证明：对A、B的任一赋值，X与Y的真值相同，而A、B的其它部分完全相同，公式B与公式A的真值必相同。AB 满足此定理的置换叫做等价置换。 【例1.17】用等价演算法证明

17、 pq(pq)(pq) 证明： pq(pq)(qp) (双条件等价式) (pq)(qp) (条件等价式) (pq)(pp)(qq)(qp)(分配律) (pq)00(qp) (矛盾律) (pq)(qp) (同一律) (pq)(pq) (交换律) pq(pq)(pq) (等价的传递性)第1章 命题逻辑 1.4重言式 定义1.4.1 设A是任一命题公式。 若对A的任意赋值，其真值永为真，则称命题公式A为重言式或永真式。 若对A的任意赋值，其真值永为假，则称命题公式A为矛盾式或永假式。 若A不是矛盾式，则称命题公式A为可满足的。 由定义1.4.1可以看出，任何重言式都是可满足的。 显然，重言式的真值表

18、的最后一列全为1，矛盾式的真值表的最后一列全为0，可满足的公式真值表的最后一列至少有一个1。根据这个结论借助于真值表可以判断一个公式是否为重言式，矛盾式或可满足的。当然也可以用等价演算法判断公式的类型。 【例1.18】用等价演算法判断下列公式的类型。 q (pq)p)第1章 命题逻辑 (pp)(qq)r) (pq)p 解： q(pq)p) q(pp)(qp) (分配律) q(0(qp) (矛盾律) q(qp) (同一律) q(qp) (德摩根律) (qq)p (结合律) 1p (排中律) 1 (零律) 由此可知，为重言式。 (pp)(qq)r) 1(qq)r) (排中律) 1(0r) (矛盾律

19、) 10 (零律) 0 (条件联结词的定义)第1章 命题逻辑 由此可知，为矛盾式。 (pq)p (pq)p (条件等价式) p (吸收律) 由此可知，是可满足的。 定理1.4.1 任何两个重言式的合取或析取都是重言式。 证明：设A、B是重言式，对A和 B的任何赋值，总有A为1，B为1，所以 AB1，AB1，故AB和AB都是重言式。 推论 任何两个矛盾式的合取或析取是矛盾式。 定理1.4.2 一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。 推论：一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。第1章 命题逻辑 【例1.19】利用定理1.4.2

20、证明(pq)r)(pq)r)为重言式。 证明：由排中律知pp为重言式，以(pq)r)去置换其中的p，得公式(pq)r)(pq)r)，根据定理1.4.2，这是重言式。 定理1.4.3 设A、B为两个命题公式，AB当且仅当AB是重言式。 证明：设AB，下证AB是重言式。 给A，B的任何赋值，因为AB，所以A，B具有相同的真值，由双条件联结词的定义知AB为真，所以AB为重言式。 设AB为重言式，下证AB 给A，B的任何赋值，因为AB为重言式，故A，B的真值相同，由命题公式等价的定义知AB第1章 命题逻辑 1.5范式 1.5.1析取范式与合取范式 定义1.5.1由一些命题变元或其否定构成的析取式称为基

21、本和，也叫简单析取式。约定单个变元或其否定是基本和。 例如，pq、pq、pq、q、p、q都是基本和。 定义1.5.2由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。 例如，pq、pq、pq、p、q、p都是基本积。 定义1.5.3由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。 定义1.5.4由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。 任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下： 消去联结词“”和“”第1章 命题逻辑 利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词

22、“”移到各命题变元前(内移)。 利用分配律，结合律将公式归约为合取范式和析取范式。 【例1.21】求命题公式(pq)p的合取范式和析取范式。 解：求合取范式 (pq)p (pq)p)(p(pq) (消去) (pq)p)(p(pq) (消去) (pq)p)(p(pq) (内移) (pp)(qp)(ppq) (分配律，合取范式) 1(qp)(1q) (排中律) 1(qp)1 (零律，合取范式) (qp) (同一律，合取范式) 由此例可以看出，公式的合取范式并不惟一。第1章 命题逻辑 求析取范式 (pq)p (pq)p)(pq)p) (消去) (pq)p)(pq)p) (内移) p(pqp) (吸收

23、律，析取范式) p(ppq) (交换律) p(pq) (幂等律，析取范式) 由此例可以看出，命题公式的析取范式也不惟一。 1.5.2主析取范式 由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。 析取范式和合取范式的基本成分是基本积和基本和，而主析取范式和主合取范式的基本成分是极小项和极大项，它们分别是特殊的基本积和基本和。 第1章 命题逻辑 定义1.5.5在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。 p，q的极小项为：pq，

24、pq，pq，pq 两个命题变元的极小项共4(=22)个, 三个命题变元的极小项共8(=23)个, 。一般地说，n个命题变元共有2n个极小项。 表1.12是两个变元p和q的极小项的真值表。极小项有下列的性质： 每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。 两个命题变元的极小项、成真赋值和名称如表1.13所示。 三个命题变元的极小项，成真赋值和名称如表1.14所示。 从表1.13和表1.14中可以看出，极小项与其成真赋值的对应关系为：变元对应1，而变元的否定

25、对应0。 第1章 命题逻辑表1.12 pqpqpqpqpq000001010010100100111000表1.13极小项成真赋值名称pq00m0pq01m1pq10m2pq11m3第1章 命题逻辑表1.14极小项成真赋值名称pqr000m0pqr001m1pqr010m2pqr011m3pqr100m4pqr101m5pqr110m6pqr111m7第1章 命题逻辑 任意两个不同的极小项的合取式为永假式。 例如： m001m100 (pqr)(pqr) pqrpqr0 全体极小项的析取式为永真式。记为： 120niimm0m1 1 定义1.5.6 对于给定的命题公式，如果有一个它的等价公式，

26、仅由极小项的析取组成，称该公式为原公式的主析取范式。 任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得： 等价演算法：即用基本等价公式推出。 12 nm第1章 命题逻辑 用等价演算法求主析取范式的步骤如下： 化归为析取范式。 除去析取范式中所有永假的基本积。 在基本积中，将重复出现的合取项和相同变元合并。 在基本积中补入没有出现的命题变元，即添加(pp)，再用分配律展开，最后合并相同的极小项。 【例1.22】用等价演算法求(pq)(pr)(qr)的主析取范式。 解：(pq)(pr)(qr) (pq(rr)(pr(qq)(qr(pp) (pqr)(pqr)

27、(pqr)(pqr) (pqr)(pqr) (pqr)(pqr)(pqr)(pqr) m111m110m011m001 m7m6m3m11，3，6，7第1章 命题逻辑 真值表法：即用真值表求主析取范式。 用真值表求主析取范式的步骤如下： 构造命题公式的真值表。 找出公式的成真赋值对应的极小项。 这些极小项的析取就是此公式的主析取范式。 【例1.24】用真值表法，求(pq)r的主析取范式。 解：表1.15是(pq)r的真值表，公式的成真赋值对应 的极小项为： pqr(成真赋值为001) pqr (成真赋值为011) pqr (成真赋值为100) pqr (成真赋值为101) pqr (成真赋值为

28、111) (pq)r 的主析取范式为：第1章 命题逻辑 (pqr)(pqr)(pqr) (pqr) (pqr) m111m101m100m011m001m7m5m4m3m1 1，3，4，5，7表1.15pqrpq(pq)r0001000111010100111110001101011101011111第1章 命题逻辑 矛盾式无成真赋值，因而主析取范式不含任何极小项，将矛盾式的主析取范式记为0。而重言式无成假赋值，因而主析取范式含2n (n为公式中命题变元的个数)个极小项。至于可满足式，它的主析取范式中极小项的个数一定小于等于2n。 1.5.3主合取范式 定义1.5.7在基本和中，每个变元及其否

29、定不同时存在，但两者之一必须出现且仅出现一次，这样的基本和叫作布尔析取，也叫大项或极大项。 两个变元p，q构成的极大项为： pq，pq，pq，pq 三个命题变元p，q，r构成的极大项为： pqr， pqr， pqr， pqr， pqr，pqr，pqr，pqr 两个命题变元的极大项共4(=22)个, 三个命题变元的极大项共8(=23)个, 。一般地说，n个变元共有2n个极大项。第1章 命题逻辑 极大项有下列三个性质： 每个极大项只有一个成假赋值，极大项不同，成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码，并把编码作为M的下标来表示该极大项，叫做极大项的

30、名称。 例如，两个变元p，q的极大项pq，它的成假赋值是11，表示为M11，把11理解为2进制数，它的10进制表示为3，所以M 11又表示为M3。 表1.16极大项成假赋值名称pq00M0pq01M1pq10M2pq11M3 两个命题变元的极大项，成假赋值及名称见表1.16，三个命题变元的极大项，成假赋值及名称见表1.17。 第1章 命题逻辑 从表1.16和表1.17中可以看出，极大项与成假赋值的对应关系为：变元对应0，而变元的否定对应1。 任意两个不同的极大项的析取式为永真式。 全体极大项的合取式为永假式。记为：表1.17极大项成假赋值名称pqr000M0pqr001M1pqr010M2pq

31、r011M3pqr100M4pqr101M5pqr110M6pqr111M7120niiMM0M1 12 nM0 第1章 命题逻辑 定义1.5.8 对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式。 任何命题公式都存在着与之等价的主合取范式。主合取范式也可以由以下两种方法求得。 等价演算法：即用基本等价公式推出。 其演算步骤如下： 化归为合取范式。 除去所有永真的基本和。 在基本和中合并重复出现的析取项和相同的变元。 在基本和中补入没有出现的命题变元。即增加(pp)，然后，应用分配律展开公式，最后合并相同的极大项。 【例1.25】用等价演算法求

32、(pq)r的主合取范式。 解：(pq)r第1章 命题逻辑 (pq)r(pq)r(pr)(qr) (pr(qq)(qr(pp) (prq)(prq)(pqr)(pqr) (pqr)(pqr)(pqr) M000M010M110M0M2M60，2，6 真值表法：用真值表求主合取范式。 用真值表求主合取范式的步骤如下： 构造命题公式的真值表。 找出公式的成假赋值对应的极大项。 这些极大项的析取就是此公式的主合取范式。 【例1.26】用真值表法求(pq)r的主合取范式。 解：(pq)r的真值表是表1.15。公式的成假赋值对应的大项为： pqr (成假赋值为000) pqr (成假赋值为010)第1章

33、命题逻辑 pqr(成假赋值为110) 主合取范式为：(pqr)(pqr)(pqr)M000M010M110M0M2M60，2，6 矛盾式无成真赋值，因而矛盾式的主合取范式含2n (n为公式中命题变元的个数)个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重言式的主合取范式记为1。至于可满足式，它的主合取范式中极大项的个数一定小于2n。 在例1.23和例1.24中求出(pq)r的主析取范式为： m7m5m4m3m11，3，4，5，7 在例1.25和例1.26中求出该公式的主合取范式为： M0M2M60，2，6 比较这两个结果，得出以下的结论：同一公式的主析取范式中m的下标和主合取范

34、式中M的下标是互补的。因此，知道了主析(合)取范式就可以写出主合(析)取范式。 第1章 命题逻辑 1.6全功能联结词集 定义1.6.1 设p和q是两个命题，复合命题p q称作p和q的不可兼析取，也叫异或。定义为：p q为T当且仅当p和q的真值不相同时。联结词“ ”称为异或联结词。 表1.18pq000011101110pq 联结词“ ”的真值表如表1.18所示。 “ ”也可以看成逻辑运算，它是二元逻辑运算。它在程序设中有广泛的引用。 不可兼析取有下列的性质： p qq p (交换律) (p q) rp (q r) (结合律)第1章 命题逻辑 p(q r)(pq) (pr) (合取对异或的分配律

35、) p q(pq)(pq) p q(pq) p p0，0 pp，1 pp 定理1.6.1 设A，B，C为命题公式，如果A BC，则A CB，B CA，A B C为一矛盾式。 定义1.6.2 设p和q是两个命题，复合命题pq称作p和q的与非。定义为：当且仅当p和q真值都是真时，pq才为假。 联结词“”称为与非联结词。 联结词“”的真值表如表1.19所示。 “”也可以看成逻辑运算，它是二元逻辑运算。 由定义可以看出下式成立： pq(pq) 联结词“”还有以下几个性质： 第1章 命题逻辑表1.19pqpq001011101110 pp(pp) p (pq)(pq) (pq) (pq)pq (pp)(

36、qq)(p)(q) (pq)pq 定义1.6.3 设p和q是两个命题，复合命题pq称作p和q的或非。定义为：当且仅当p、q的真值都为假时，pq的真值为真。联结词“”称为或非联结词。 联结词“”的真值表如表1.20所示。 “”也可以看成逻辑运算，它是二元逻辑运算。表1.20pqpq001010100110第1章 命题逻辑 由此定义可得到下面的公式： pq(pq) 联结词还有下面的几个性质： pp(pp) p (pq)(pq) (pq) (pq)pq (pp)(qq) pq(pq)pq 至此已经学了8个联结词：，。类似于定义1.2.1的方法，可以定义包含上述8个联结词的命题公式。 定义1.6.4

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

38、联结词后，就不是全功能联结词集，则称S是最小全功能联结词集。第1章 命题逻辑 可以证明，是最小全功能联结词集。 现在讨论，n个命题变元可以构成多少个不等价的命题公式。 两个命题变元可以构成多少个不等价的命题公式？ 由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两个命题变元构成的命题公式有多少个不同的真值表？ 表1.21pq公式001或0011或0101或0111或0 两个命题变元构成的命题公式的真值表的格式如表1.21所示。真值表中每行公式的真值都有1，0两种可能，所以命题公式的真值有2222=24= =16种可能，既有 个不同的真值表。故有 种不等价的公式。 22222

39、2222第1章 命题逻辑 三个变元可构成28= 个不等价的命题公式，n个变元可构成 个不等价的命题公式。 1.7对偶式与蕰含式 1.7.1对偶式 从1.3节的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“”和“”分别换成“”和“”，就可以由一个得到另一个。例如，将命题定律(AB)CA(BC)中的“”换成“”就得到了命题定律(AB)CA(BC)。这些成对出现的等价式反映了等价的对偶性。本节介绍对偶式和对偶原理。 定义1.7.1在仅含联结词，的命题公式A中，将联结词，F，T分别换成，T，F所得的公式称为公式A的对偶式，记为A*。 设A*是A的对偶式，将A*中的，F，T分别换成，T，

40、F，就会得到A。即A 是A*的对偶式，(A*)*A。所以说A*和A互为对偶式。 322n22第1章 命题逻辑 【例1.27】求pq和pq的对偶式。 解： pq(pq) (pq)的对偶式是(pq)pq 故pq的对偶式是pq；同样的方法可以证明pq的对偶式是pq。 根据例1.27，对偶式概念可以推广为：在仅含有联结词，的命题公式中，将联结词，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

41、章 命题逻辑 【例1.28】设命题公式A(p,q,r)(pq)r，试用此公式验证定理1.7.1的有效性。 证明：验证 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) 验证 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* 证明：因为 AB所以 A(p1，p2，pn

42、)B(p1，p2，pn)是重言式 根据定理1.4.2，在上述重言式中用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叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。 第1章 命题逻辑 【例1.29】证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。 证明：设A是重言式，即A1，因为1的对偶式是0，由对偶原理知A*0。所以A*是矛盾式；设A是矛盾式，即A0，

43、而0的对偶式是1，所以A*1。所以A*是重言式。 1.7.2蕴含式 定义1.7.2 设A和B是命题公式，若AB是重言式，则称A蕴含B，记为AB。 根据定义可以用真值表或等价演算证明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(pq)q 解：证法1： 假定p(pq)为Tp为T且pq为

44、Tp为F且pq为Tq为T。所以 p(pq)q 证法2： 假定q为F，则p可以为T或F。 当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.化简律 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)(

45、AB)(CD)BD (AA)(AB)(AB)B 9.破坏性二难 (BD)(AB)(CD)(AC) 第1章 命题逻辑 等价式和蕴含式有下面的关系。 定理1.7.3 设A，B为任意两个命题公式，则AB的充分必要条件是AB且BA 证明：设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章 命题逻辑 根据此定理，以前学过的所有等价式都可

46、以作两个蕴含式来使用。例如吸收律A(AB)A可以作两个蕴含式A(AB)A和AA(AB) 来使用。 定理1.7.4 设A、B、C为合式公式。 AA (即蕴含是自反的) 若AB且A为重言式，则B必为重言式。 若AB且BC，则AC (即蕴含是传递的) 若AB且AC，则ABC 若AB且CB，则ACB 若AB，C是任意公式，则 ACBC 证明：仅证明 。 因为AB，CB, 所以ABT，CBT (AC)B(AC)B(AC)B (AB)(CB)(AB)(CB)TTT由等价的传递性，(AC)BT，故ACB第1章 命题逻辑 1.8命题逻辑的推论理论 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。所谓推理是指

47、从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。要研究推理，首先应该明确什么样的推理是有效的或正确的。 定义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.8.1可以看出，要证明C是一组前提A1，A2，An 的有效结论，只需证明A1A2AnC为重言式。证明一个公式为重言式，可以用真值表、等价演算、主

48、析(合)第1章 命题逻辑取范式或已知的蕴含式等方法进行。用等价演算和主析(合)取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。 用真值表证明有效结论有以下两种方法： 用全真值表证明 要证明C为前提A1，A2，An 的有效结论，只需构造命题公式A1A2AnC的真值表，证明它是重言式。 用部分真值表证明 因为条件命题A1A2AnC为假当且仅当它的前件A1A2An为真，后件C为假。只要能排除前件为真，后件为假的情况，A1A2AnC就是重言式。从而C为一组前提A1，A2，An 的有效结论。于是就有了下面方法： 构造A1，A2，An与C的真值表，且作在一个表上。 找出A1，A2，An都为真的行，若C也为真，则A1A2AnC，即C为前提A1，A2，An 的有效结论。第1章 命题逻辑 找出C为假的行，若在每个这样的行中，A1，A2，An的真值至少有一个为假，则A1A2AnC，即C为一组前提A1，A2，An 的有效结论。 【例1.32】分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。 解：令