第3章 命题逻 辑 3.1　命题概念 数理逻辑的核心是推理,它着重于推理过程的研究。推理的前提和结论应该是表述 明确的陈述句,它是推理的基本单位。逻辑是思维的规律和规则,是思维过程的抽象。 定义3- 1 具有确定真假含义的陈述句称为命题。若一个命题的含义为真,称该命 题是真命题,也称该命题的真值为真,用T或1表示这个真值;若一个命题的含义为假, 称该命题是假命题,也称该命题的真值为假,用F或0表示这个真值。 依据命题的定义,命题有两个特性: (1)命题是陈述句。因此,疑问句、感叹句、祈使句都不是命题; (2)命题有确定的真值。任何存在二义性的句子都不是命题,即命题是真假可判定 的,要么是真命题,要么是假命题。 例3.1 下列句子哪些是命题? 并判断其真假。 (1)上海是中国的大城市。 (2)下午2点上课? (3)全体立正 ! (4)1+1=3 。 (5)我正在说谎。 (6)如果今天天气好,我就去商店。 (7)火星上有生命。 (8)大偶数是两个素数的和。 上例中,语句(1)是真命题。语句(2)是疑问句,语句(3)是感叹句,均不是命题。语 句(4)是假命题。语句(5)是陈述句,但没有明确的真值,如果我在说谎,则我讲了真话, 第 3 章　命题逻辑27 如果我讲了真话,我就是在说谎,所以,这个句子没有明确的真值,不是命题,语句(5)也 称为“说谎者悖论”。语句(6)是命题,是由“今天天气好”和“我就去商店”两个命题通过 “如果…… 就……” 组合成。语句(7)和(8)是命题,但是,真值目前还不能判断,语句(7) 火星上是否有生命,真值是唯一的,只是目前还未知,语句(8)也就是哥德巴赫猜想,目前 还没有被证明,但是,未来一定可以确定其真值。 在数理逻辑中,将命题和它的真值用抽象的符号表示,称为命题的符号化或形式化。 本书中,使用大写字母P、Q、R、…表示命题。数字1或T表示命题为真,数字0或F表 示命题为假,即命题的两个真值。上例中(1)、(4)、(7)命题符号化为: (1)P:上海是中国的大城市。 (4)Q:1+1=3。 (7)R:火星上有生命。 其中, P 的真值为1, Q 的真值为0, R 的真值目前未知。但是,未来一定能知道火星上是 否有生命,其真值只能是0或1之一。 这三个陈述句均无联结词,称为简单命题或原子命题。原子命题是不能再细分的命 题,原子命题通过联结词构造而成的命题称为复合命题。例如,“如果…… 那么……” “与”“并且”“或者”“当且仅当”“若…… 则……” 等联结词,可以用于构造复合命题。 3.2　命题联结词 3.1　否定联结词“..” 2. 定义3- 2 设 P 是一个命题, P 的否定是一个复合命题,记作..P,读作“非P”。若 P 的真值为1,则.. P 的真值为0;若 P 的真值为0,则.. P 的真值为1。真值表如表3-1 所示。 表3- 1 否定联结词及真值表 P ..P 0 1 1 0 例如: 28离散数学 (1)P:4是偶数 。 ..P:4不是偶数 。 (2)Q:参会的都是大学老师 。 ..Q:参会的不都是大学老师 。 需要注意的是,..Q 不能理解为:参会的都不是大学老师 。 3.2　合取联结词“∧” 2. 定义3- 3 设P、 Q 是任意两个命题,复合命题“ P 与Q”称为 P 和 Q 的合取式,记作 P∧Q,读作“ P 与Q”,或者“ P 合取Q”。若P、 Q 的真值都为真(即1), 则P∧ Q 真值为 真,否则为假(即0)。真值表如表3-2所示。书写时,P、 Q 的组合按二进制大小排列。 表3- 2 合取联结词及真值表 P Q P∧ Q P Q P∧ Q 0 0 0 1 0 0 0 1 0 1 1 1 自然语言中的“与”“并且”“和”“与”“不仅…… 而且……”“既…… 又……” 等均可用 “∧“联结词表示,但是不能看到“和”“与”就使用合取联结词。 联结词“∧”本质上是一个二元运算符,与程序设计语言中的“逻辑与”运算类似,仅 当两个条件都成立时,“逻辑与”的结果为真。例如,表达式“ x<5&&y>2为(”) 真,只有当 x 小于5并且 y 大于2。 例如, P:张三是软件专业学生。 Q:张三是男生。 P∧Q:张三是软件专业的男生。 还需要注意,合取与自然语言中的“并且”“和”“与”,有时不完全相同,例如,小王和 小张是好朋友,就不是一个合取命题,它只是一个命题,而不是两个命题的合取。 又如, P 和 Q 是命题, P:厦门是一个城市。 Q:我是一名大学生。 命题 P 和 Q 的合取式P∧Q,表示厦门是一个城市并且我是一名大学生,在自然语 第3章　命题逻辑29 言中,这个合取式没有实际意义, P 和 Q 之间没有关联。但是,在数理逻辑中, P 和 Q 有 确定的真值,P∧ Q 是复合命题,合取式的真值由P、 Q 的真值确定。 例3.将下列命题形式化。 2 (1)2既是偶数又是素数 , P∧Q,其中,P:2是偶数,Q:2是素数 。 (2)6是偶数,7是奇数 , P∧Q,其中,P:6是偶数,Q:7是奇数 。 (3)虽然今天下雨,但我还要去上课, P∧Q,其中,P:今天下雨,Q:我还要去上课 。 (4)2与3的最小公倍数是6, P:2与3的最小公倍数是6,不能使用合取,不能再细分。 (5)张明和张元是亲兄弟, P:张明和张元是亲兄弟,不能使用合取,不能再细分。 3.3　析取联结词“∨” 2. 定义3- 4 设P、 Q 是任意两个命题,复合命题“ P 或Q”称为 P 和 Q 的析取式,记作 P∨Q,读作“ P 或Q”“ P 析取Q”。若P、 Q 的真值都为假,则 P ∨ Q 真值为假,否则为 真。也就是,只要命题 P 或 Q 有一个为真,P∨ Q 就为真。真值表如表3-3所示。 表3- 3 合取联结词及其真值表 P Q P∨ Q P Q P∨ Q 0 0 0 1 0 1 0 1 1 1 1 1 例3.将下列命题形式化。 3 (1)李燕学过C语言或Python语言,P∨Q,其中,P:李燕学过C语言,Q:李燕学 过Python语言。李燕可能只学过C语言,也可能只学过Python语言,还可能C语言和 Python语言都学过。 (2)今天是晴天或者阴天,P∨Q,其中,P:今天是晴天,Q:今天是阴天。 库课 ( 。 3)今天有离散课或数据库课,P∨Q,其中,P:今天有离散数学课,Q:今天有数据 30离散数学 (4)他是这次离散数学考试的第一名或第二名,( P ∧..Q)∨(.. P ∧Q), 其中,P: 他这次考试得第一名,Q:他这次考试得第二名,不会既是第一名又是第二名。 3.4　蕴涵联结词“→” 2. 定义3- 5 设P、 Q 是任意两个命题,复合命题“如果 P 则Q”称为 P 和 Q 的蕴涵式, 记作P→Q,读作“ P 蕴涵Q”。 Q 是 P 的必要条件, P 是蕴涵式的前件, Q 是蕴涵式的后 件。真值表如表3-4所示。 表3- 4 蕴涵联结词及其真值表 P Q P→ Q P Q P→ Q 0 0 1 1 0 0 0 1 1 1 1 1 从表3-4中可以看出,只有当 P 为真, Q 为假,蕴涵式 P → Q 为假,其余为真。蕴涵 式P→ Q 真值的判断,是命题逻辑的精髓之一。若命题 P 为假,不论 Q 是真还是假,P→ Q 永远为真;若命题 Q 为真,不论 P 是真还是假,P→ Q 永远为真。 例3.将下列命题形式化, 4 P:他步行上班,Q:天下雨。 (1)除非天下雨,否则他步行上班。..P→Q,也可以表示为..Q→P。 (2)只要天不下雨,他就步行上班,..Q→P。 (3)只有天不下雨,他才步行上班,P→..Q 。 特别注意在(2)和(3)中“只要…… 就……” 与“只有…… 才……” 的区别 。 3.5　等价联结词“.” 2. 定义3- 6 设P、 Q 是任意两个命题,复合命题“ P 当且仅当Q”称为 P 和 Q 的等价 式,记作P.Q,读作“ P 等价Q”。等价联结词也称为双条件联结词,当 P 和 Q 的真值相 同时,P. Q 的真值为1;当 P 和 Q 的真值不同时,P. Q 的真值为0。真值表如表3-5 所示。 从表3-5中可以看出,当且仅当 P 和 Q 同为真或同为假,P. Q 的真值为真。P. Q 逻辑上是 P 和 Q 互为充分必要条件,等价于(P→Q)∧(Q→P)。 第3章　命题逻辑31 表3- 5 等价联结词及其真值表 P Q P. Q P Q P. Q 0 0 1 1 0 0 0 1 0 1 1 1 例3.将下列命题形式化, 5 (1)当且仅当天下雪的时候,我打车上班。 P:我打车上班,Q:天下雪 , P.Q,P、 Q 无内在联系 。 (2)雪是白色的当且仅当悉尼是澳大利亚首都。 P:雪是白色的,Q:悉尼是澳大利亚首都, P.Q,由于 P 为真, Q 为假,因此P. Q 的真值0,P、 Q 两者无内在联系。 相等 ( 。 3)两个圆的周长相等,则它们的半径相等;若两个圆的半径相等,则它们的周长 P:O1 与O2 周长相等 , Q:O1 与O2 半径相等 , P.Q,真值为1,P、 Q 真值始终相同,两者有内在联系 。 (4)角 A 和角 B 是对顶角,则角 A 等于角B;若角 A 和角 B 相等,则它们是对顶角。 P:角 A 和角 B 是对顶角, Q:角 A 等于角B, P.Q,也可以表示为(P→Q)∧(Q→P), 由于P→ Q 为真,Q→ P 不一定为真(相等 的角不一定是对顶角), 因此P. Q 为假,两者有内在联系。 以上定义了5种最基本的联结词,它们构成了一个联结词集合{..、∧、∨、→、.}, 其中,..是一元联结词,其余4个为二元联结词。 特别说明如下: (1)使用一个联结词联结一个或两个原子命题,组成的复合命题称为基本复合命题。 (2)多次使用联结词,可以组成更复杂的复合命题,在计算复合命题的真值时,需要 注意联结词的优先级,一般规定优先顺序为:()、..、∧、∨、→、.,同一优先级的联结词, 从左向右顺序计算。 (3)数理逻辑中,我们关注复合命题之间的真值关系,不关心命题本身的含义。 例3.6 命题P、Q、 R 定义如下,求下列复合命题的真值。 32 离散数学 P:2+4=6, Q:北京人口大于福州人口, R:2整除7 。 (1)(P∧..Q)→R, (2)(..P∨R).(Q∧..R)。 0, 1) 1∧0→0=0→0=1, 解:P、Q、 R 的真值分别为1、1、因此,复合命题(的真值 = 复合命题(2)的真值=0∨0.(1∧1)=0.1=0。 3.6　其他联结词 2. 除了上述5个基本联结词外,命题逻辑中还有3个联结词:异或(..)、与非(↑)、或 非(↓)联结词。真值表如表3-6所示。 (1)任意命题P、Q,复合命题“ P 等价 Q 的否定”称为P、 Q 的异或,记作P⊕Q。当 P、 Q 一个为真一个为假,则P.. Q 为真;P、 Q 同真或同假,则P.. Q 为假。异或也称为 “不可兼或”“排斥或”。 P..Q=..(P.Q) (2)任意命题P、Q,复合命题“ P 与 Q 的否定”称为P、 Q 的与非,记作 P ↑Q。 P↑ Q 为真当且仅当 P 与 Q 不同时为真。 P↑Q=..(P∧Q),P↑P=..(P∧P)=.. P (3)任意命题P、Q,复合命题“ P 或 Q 的否定”称为P、 Q 的或非,记作P↓Q。P↓ Q 为真当且仅当 P 与 Q 同时为假。 P↓Q=..(P∨Q),P↓P=..(P∨P)=.. P 表3- 6 其他联结词及其真值表 P Q P.. Q P↑ Q P↓ Q 0 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 特别注意:与非、或非不满足结合律。 第 3 章　命题逻辑33 3.3　命题公式 上两节讨论了简单命题(原子命题)和复合命题,简单命题是命题逻辑的基本单位。 对于命题P,我们只关心命题的真假。本节开始,进一步对命题抽象,真值可以变化的命 题称为命题变项或命题变元,用P、Q、R…表示,它们是取值为0或1的变项,命题变元 需要通过上下文来确定它们的真值。 ( 定义3- 7 命题公式也称为合式公式,递归方式定义如下: 1)单个命题变元和命题常量是一个命题公式; (2) P 是命题公式,.. P 也是命题公式; (3) P 和 Q 是命题公式,P∧Q、P∨Q、P→Q、P. Q 也是命题公式; (4)有限次应用上述(1)~(3)条规则得到的符号串也是命题公式。 定义3- 8 如果命题公式 G 中含有 n 个命题变元P1、P2、…、Pn ,称 G 为 n 元命题公 式,可以表示为G(P1、P2…、Pn )。给P1、P2…、Pn 分别指定相应的真值,称为对公式 G 的一种指派或解释。若指定的一组值使得 G 真值为1,则称这组值为 G 的成真指派,若 使得 G 的真值为0,则称这组值为 G 的成假指派。 显然,命题公式在一种指派下有确定的真值,若公式 G 有2个命题变元P、Q,那么 G 就有4种不同的指派(00 、01 、10 、11), 也就是P、 Q 取0或1的组合数。若公式有 n 个 命题变元,那么它就有2n 种指派。 定义3- 9 命题公式 G 在一种指派下,必有确定的真值,若将所有指派下的真值列成 表格,称为该命题公式 G 的真值表。构造真值表的方法如下: (1)找出公式中所有命题变元P、Q、R、…, 或下角标P1、P2、…、Pn ,指派从00…0 开始(第一个指派), 然后按照二进制加1依次写出。 (2)按照命题公式的层次(联结词的优先级), 列出复合公式。 (3)计算各复合公式的真值,直到最后计算出公式的真值 。 例3.求下列公式的真值表 : 7 (1)G1=(P∨Q)→P, (2)G2=(..P∧Q).Q, (3)G3=..(P→Q)∧Q。 解:按照真值表的构造方法,列出真值表。 (1)命题变元P、Q,列出指派组合为00 、01 、10 、11,计算( P ∨Q)的真值,最后计算 34离散数学 公式G1 的真值,真值表如表3-7所示。 表3- 7 G1 的真值表 P Q P∨ Q (P∨Q)→ P P Q P∨ Q (P∨Q)→ P 0 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 (2)命题变元P、Q,列出指派组合为00 、01 、10 、11,计算..P∧Q 的真值,真值表如 表3-8所示。 表3- 8 G2 的真值表 P Q ..P∧ Q (..P∧Q). Q P Q ..P∧ Q (..P∧Q). Q 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 (3)命题变元P、Q,列出指派组合为00 、01 、10 、11 。分别计算P→Q 、..(P→Q)的真 值,真值表如表3-9所示。 表3- 9 G3 的真值表 P Q P→ Q ..(P→Q) ..(P→Q)∧ Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 上例中,公式G1 的成假指派是01,公式G2 全部是成真指派,公式G3 全部是成假指 派。依据公式在不同指派下真值的不同,可以对公式进行分类。 定义3-10 命题公式G,P1、P2、…是 G 中的所有命题变元,那么: (1)如果命题公式 G 在所有指派下真值为1,称公式 G 为永真式或重言式。 (2)如果命题公式 G 在所有指派下真值为0,称公式 G 为永假式或矛盾式。 足式 ( 。 3)如果命题公式 G 在有些指派下真值为1,有些指派下真值为0,称公式 G 为可满 从定义可以看出,重言式一定是可满足式;命题公式不是永真式,它不一定是永假 第3章　命题逻辑35 式;命题公式不是永假式,它一定是可满足式。 例3.构造下列公式的真值表: 8 (1)G1=(P∧Q)→R, (2)G2=(..P∧Q)∨(P∧..Q) , (3)G3=..(P→Q)∧Q 。 解 : (1)G1 的真值表如表3-10 所示 。 表3-10 G1 的真值表 P Q R P∧ Q G1 P Q R P∧ Q G1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 (2)G2 的真值表如表3-11 所示。 表3-11 G2 的真值表 P Q ..P∧ Q P∧.. Q G2 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 (3)G3 的真值表如表3-12 所示。 表3-12 G3 的真值表 P Q (P→Q) ..(P→Q) G3 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 36离散数学 可以看出,G1、G2 两个公式是可满足式,公式G3 是矛盾式(永假式)。 3.4　命题逻辑等值演算 3.1　等值式与等值演算 4. 命题公式G、 H 含有相同的命题变元,并且这两个公式在所有指派下真值相同,称这 两个公式是等价的,记作G= H 。 定理3- 1 命题公式 G 和 H ,G= H 的充要条件是公式G. H 是重言式。 证明:充分性,G. H 是重言式,使得G. H 为真, I 是公式的任意指派, 因此公式 G 和 H 同真,或同假,由于 I 的任意性,因此,G= H 。 必要性,G= H , G 和 H 在任意指派下,同真或同假,依据等价联结词的定义,G. H 在任意指派下都为真,因此,G. H 为永真式(重言式)。 例3.判断下列各组公式是否等值, 9 (1)P→(Q→R)与P∧Q→R, (2)(P→Q)→ R 与P∧Q→R。 解:构造真值表如表3-13 和表3-14 所示,可以看出(1)小题的两个命题公式等值, (2)小题的两个命题公式不等值。 表3-13 P→(Q→R)与P∧Q→ R 的真值表 P Q R Q→ R P→(Q→R) P∧ Q P∧Q→ R 是否等值 0 0 0 1 1 0 1 √ 0 0 1 1 1 0 1 √ 0 1 0 0 1 0 1 √ 0 1 1 1 1 0 1 √ 1 0 0 1 1 0 1 √ 1 0 1 1 1 0 1 √ 1 1 0 0 0 1 0 √ 1 1 1 1 1 1 1 √ 第3章　命题逻辑37 表3-14 (P→Q)→ R 与P∧Q→ R 的真值表 P Q R P→ Q (P→Q)→ R P∧ Q P∧Q→ R 是否等值 0 0 0 1 0 0 1 × 0 0 1 1 1 0 1 √ 0 1 0 1 0 0 1 × 0 1 1 1 1 0 1 √ 1 0 0 0 1 0 1 √ 1 0 1 0 1 0 1 √ 1 1 0 1 0 1 0 √ 1 1 1 1 1 1 1 √ 利用真值表判定等值公式,当变元较多时就显得烦琐。利用公式的等价性,根据等 值式推演出与原命题等值的新公式,这个过程称为等值演算,或命题演算。 定理3- 2 命题公式G、 H 和S,下列基本等价式成立。 (1)双重否定律:....G=G。 (2)幂等律:G=G∨G,G=G∧G。 (3)交换律:G∨ H = H ∨G,G∧ H = H ∧G。 (4)结合律:(G∨ H )∨S=G∨( H ∨S),(G∧ H )∧S=G∧( H ∧S)。 (5)分配律:G∧( H ∨S)=(G∧H)∨(G∧S),G∨( H ∧S)=(G∨H)∧(G∨S)。 (6)德摩根律:..(G∧ H )=..G∨.. H ,..(G∨ H )=..G∧.. H 。 (7)吸收律:G∧(G∨ H )=G,G∨(G∧ H )=G。 (8)零律:G∨1=1,G∧0=0。 (9)同一律:G∨0=G,G∧1=G。 (10)排中律:G∨..G=1。 (11)矛盾律:G∧..G=0。 (12)蕴涵等值式:G→ H =..G∨ H 。 (13)等价等值式:G. H =(G→ H )∧( H →G)。 (14)假言移位:G→ H =.. H →..G。 (15) 10 归谬律:(G→ 9H , )∧(G→.. H )=..G 。 例3.上述例3.使用等值演算法证明 : 38离散数学 (1)P→(Q→R)与P∧Q→R 。 证明 : 左式=..P∨(Q→R) // 蕴涵等值 式 =..P∨(..Q∨R) // 蕴涵等值 式 =(..P∨..Q)∨ R // 结合 律 =..(P∧Q)∨ R // 德摩根 律 =P∧Q→ R // 蕴涵等值 式 =右 式 (2)(P→Q)→ R 与P∧Q→R 。 证明 : 左式=..(P→Q)∨ R // 蕴涵等值 式 =..(..P∨Q)∨ R = ( 右式=.. P( ∧..Q)∨ R P∧Q)∨ R =(..P∨..Q)∨ R 显然,左、右两边不完全等值 。 例3.证明:(→R=(P→R)∧(Q→R) 。 11 P∨Q) 证明 : 左式=..(P∨Q)∨ R // 蕴涵等值 式 =(..P∧..Q)∨ R // 德摩根 律 =(..P∨R)∧(..Q∨R) // 分配 律 =(P→R)∧(Q→R) // 蕴涵等值 式 =右 式 定理3- 3 (置换定理)命题 G 中包含子公式 H ,将 H 置换为公式S,得到新公式G' , 若 H =S,则 G 与G'等价,记作G=G'。 命题公式 G 是永真式(或永假式),P1、P2、…是公式中的命题变元,将其中的一个命 题变元用另一命题公式 H 代入,得到的新命题公式还是永真式(或永假式)。 命题公式(..P∧Q). Q 是永真式,将命题变元Q,用P∨ Q 置换,得到新公式(.. P ∧(P∨Q)).(P∨Q), 依然是永真式。 命题公式G=(P→Q)→R,其中,子公式P→ Q 等价于..P∨Q,置换后得到的新公 式G'=(..P∨Q)→R,新公式G'=G。 第 3 章　命题逻辑39 例3.等值演算验证下列公式类型。 12 (1)P→(P∧Q)。 (2)..(P→Q)∧(..Q→..P) 。 证明(略), 读者自己演算,(1)为可满足式,(2)为永假式 。 例3.使用等值演算法证明:(Q→R) 。 13 P∨Q)→R=(P→R)∧ ( 证明 : 左边=(P∨Q)→ R =..(P∨Q)∨ R // 蕴涵等值式 =(..P∧..Q)∨ R // 德摩根律 =(..P∨R)∧(..Q∨R) // 分配律 =(P→R)∧(Q→R) // 蕴涵等值式 =右边 也可以从右边向左边证明 。 例3.14 证明:(P.Q)→(P∧Q)=P∨Q 。 证明 : 左边=(P.Q)→(P∧Q) =..(P.Q)∨(P∧Q) // 蕴涵等值式 =..((P→Q)∧(Q→P))∨(P∧Q) // 双条件等价 =..((..P∨Q)∧(..Q∨P))∨(P∧Q) // 蕴涵等值式 =..(..P∨Q)∨..(..Q∨P))∨(P∧Q) // 德摩根律 =(// 德摩根律 =( P∧..Q)∨(Q∧..P)∨(PP∧ ∧ QQ) )) // 结合律 P∧..Q)∨((Q∧..P)∨( // 分配律=(P∧..Q)∨(Q∧(..P∨P)) // 排中律,..P∨P= =(P∧..Q)∨(Q∧1) 1 =(P∧..Q)∨ Q // 同一律,Q∧1= Q =(P∨Q)∧(..Q∨Q) // 分配律 =(P∨Q) // 排中律、同一律 =右边 3.2　联结词完备集 4. 前面介绍了常用的命题联结词集合{..、∧、∨、→、.}。联结词本质上是一个函数, 40离散数学 联结词可以构造不同的命题公式,任意的输入将得到唯一的真值。那么,为了构造任意 命题公式,这个联结词集合是否完备? 也就是说,为了构造任意命题公式,是否还需要定 义其他新的联结词? 1.真值函数 n →{ 0,1}00.0,00.11. 定义3-11 函数F:{0,1}0,1}为 n 元真值函数。 函数 F 有 n 个自变项,定义域为{ n ={1,…,1},也就是长度为n, 由0或1组成的符号串,值域为{0,1},即函数 F 的值只有是0或1。 n 个自变项总共可 构造22n 个不同的真值函数。例如,一元真值函数共有4个,当P=0,F(P)=0或1,分别 表示为F0(00 )、F1(01),当P=1,F(P)=0或1,分别表示为F2(10 )、F3(11),如表3-15 所示。同样,二元真值函数共有16个,如表3-16所示,三元真值函数共有256个。 表3-15 一元真值函数 P F0 F1 F2 F3 0 0 0 1 1 1 0 1 0 1 表3-16 二元真值函数 P Q F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 在二元真值函数中,2,定义域自变项数是4,即长度为2的0与1组成的符号串, n= 分别为00 、01 、10 、11 。 从命题公式的构造看,2个命题变元有4种指派,在每一种指派下,公式的真值为0 或1,因此,2个命题变元可以构成16(24)个不等价的命题公式。从二元真值函数表3-16 中,所有16个命题公式可以表示如下: F0=P∧..P,F1=P∧Q,F2=P∧..Q,F3=P,F4=..P∧Q,F5=Q, F6=(P∧..Q)∨(..P∧Q),F7=P∨Q,F8=..(P∨Q),F9=P.Q, F10=..Q,F11=Q→P,F12=..P,F13=P→Q,F14=..(P∧Q),F15=..P∨P, 第 3 章　命题逻辑41 在这16 个不同的命题公式中,F9=P.Q=(P→Q)∧(Q→P)=(..P∨Q)∧(.. Q ∨P),F11=Q→P=..Q∨P,F13=P→Q=..P∨Q。这样,任意一个命题公式,都可以 用联结词{..、∧、∨}来等价表示。不同的联结词,相互之间还可以转换,例如,F0也可以 表示为Q∧..Q,或者表示为..(.. Q ∨Q)。这就导致一个问题,所有联结词是否必须? 最少需要多少个联结词? 这就是联结词的完备集问题。 2.联结词完备集 定义3-12 设 S 是一个联结词集合,任意给定的命题公式,都可以找到一个仅含 S 集合中的联结词构成的命题公式与之等价,则称 S 是一个联结词的完备集。 例3.公式P∧(Q.R)转化为只含有联结词{..、∧}的公式形式 。 解 : P∧(Q.R) =P∧((Q→R)∧(R→Q)) // 等价等值 式 =P∧(..Q∨R)∧(..R∨Q) // 蕴涵等值 式 =P∧....(..Q∨R)∧....(..R∨Q)// 双重否 定 =P∧..(Q∧..R)∧..(R∧..Q) // 德摩根 律 从定义可以看出,以下集合都是联结词完备集: S1={..、∨、∧、→、.} S2={..、∨、∧、→} S3={..、∧、∨} S4={..、∧} S5={..、∨} 在这些联结词的完备集中,很明显,S1={..、∨、∧、→、.}中联结词蕴涵“→”和等 价“.”,可以用S3={..、∧、∨}来表示,同样S3 中的析取“∨”可以用S4={..、∧}来表 示。因此,S4 是S3、S1 的真子集。那么,是否存在更小的联结词完备集,该集合可以表示 所有其他的联结词? 定义3-13 联结词完备集S,若 S 中的任意一个联结词都不能用 S 中的其他联结词 等价表示,则称 S 为极小联结词完备集。也就是说,极小联结词完备集满足下列条件: (1) S 中的联结词可以表示所有联结词; 15 (2)从 S 中删除任意一个联结词,至少存在一个联结词,不能用剩余的联结词表示。 例3.16 对于5个基本联结词,可以进行如下转换: 42离散数学 P→Q=..P∨ Q P∧Q=..(..P∨..Q) P. Q =(P→Q)∧(Q→P) =(..P∨Q)∧(..Q∨P) =..(..(..P∨Q)∨..(..Q∨P) ) 上面讨论了{..、∧、∨}是一个联结词完备集,那么,它是否是一个极小联结词完备 集呢? 由于蕴涵、合取、等价可以用否定和析取表示,因此,{..、∨}是一个极小联结词完 备集,同样{..、∧}也是一个极小联结词完备集。 例3.17 证明{..、∧}是一个极小联结词完备集。 证明:对于5个基本联结词,若能证明{..、∧}可以表示其他3个联结词{∨、→、 .}, 那么{..、∧}就是一个极小完备集。 设命题P、Q, P∨Q=..(..P∧..Q) P→Q=..P∨Q=..(P∧..Q) P.Q=(P→Q)∧(Q→P)=..(P∧..Q)∧..(Q∧..P) 并且,联结词..、∧不能互为表示,也就是删除其中一个联结词,就不能表示其他联 结词了。因此,{..、∧}是联结词的一个极小完备集。 例3.18 证明:{↑}、{↓}都是极小联结词完备集。 证明:由于{..、∧}为联结词的完备集,因此,只需要证明..、∧可以有“与非↑” 表示。..P=..(P∧P)=P↑ P P∧Q=....(P∧Q)=..(P↑Q)=(P↑Q)↑(P↑Q) 因此,{↑}是联结词的一个极小完备集。 同理,{↓}是联结词的一个极小完备集。 3.5　对偶与范式 3.1　公式的对偶 5. 3.比较多的情况是命题公式仅含有联结词{..、∧、∨}, 4节介绍了联结词的完备集, 常用的基本等价式是成对出现,不同的是∧和∨的互换,以及0和1的互换,这种现象具 第3 章　命题逻辑 43 有对偶规律。 定义3-14 设G 是一个仅含有联结词{..、∧、∨}的命题公式,其中用∨替代∧,用 ∧替代∨,用1替代0,用0替代1,所得的新公式称为原公式G 的对偶式,记为G* 。显然 (G* ) * =G 例如,公式..(P ∧Q)与..(P ∨Q)互为对偶式,(P ∨Q)∧R 与(P ∧Q)∨R 互为对 偶式,P ∧0与P ∨1互为对偶式。 特别注意,求公式的对偶式,首先要消去公式中除{..、∧、∨}以外的联结词。 定理3-4 设G 是一个仅含有{..、∧、∨}的命题公式,P1,P2,…,Pn 是出现在公式 中的全部命题变元,则: ..G(P1,P2,…,Pn)=G* (..P1,..P2,…,..Pn) G(..P1,..P2,…,..Pn)=..G* (P1,P2,…,Pn) 证明:略。 对公式..G(P1,P2,…,Pn )反复运用德摩根律,将..移到命题变元或其否定前为 止,这过程中∧和∨互换,0和1互换,Pi变成..Pi。 定理3-5 (对偶原理)设G 和H 是两个仅含有{..、∧、∨}的命题公式,如果G = H ,则G* =H * 。 例如,德摩根律就是对偶原理的运用,..(P ∧Q)=..P ∨..Q。在某些情况下,对偶 原理也可以用来证明两个公式等价。 3.5.2　析取范式与合取范式 通过命题公式的演算,一个命题公式可以存在多种等价的形式。那么,如何判定命 题公式是否等价? 这就需要找到公式的标准形式或规范形式,在不写出真值表的情况 下,确定命题公式在相应指派下的真假,进而判定公式是否等价,这就是命题公式的范式 问题。定 义3-15 命题变元及其否定称为文字,有限个文字构成的析取式称为简单析取 式,有限个文字构成的合取式称为简单合取式。 例如,P 、..Q 均为1个文字构成的简单析取式,或简单合取式。P ∨..Q、..P ∨.. Q 均为2个文字构成的简单析取式。P ∧..Q、..P ∧..Q 均为2个文字构成的简单合 取式。注 意: (1)一个文字既是简单合取式,又是简单析取式。 44离散数学 (2)合取式P∧..Q,也可以看作1个简单合取式构成的析取范式。析取式P∨.. Q,也可以看作1个简单析取式构成的合取范式。 定义3-16 有限个简单合取式构成的析取式称为析取范式,有限个简单析取式构成 的合取式称为合取范式。析取范式和合取范式统称为范式。 设命题变元P、Q、R,那么: G1=(P∧..Q)∨(..P∧..R)∨Q,是一个析取范式。 G2=(P∨..Q)∧..R∧(..P∨Q), 是一个合取范式。 定理3- 6 (1)一个析取范式是矛盾式,当且仅当它的每个简单合取式都是矛盾式; (2)一个合取范式是重言式,当且仅当它的每个简单析取式都是重言式。 定理3- 7 (范式存在定理) 任意命题公式都存在与之等值的析取范式和合取 范式。下 面给出任意命题公式转化为合取范式和析取范式的步骤: (1)消去蕴涵(→)、等价(.)联结词; (2)使用德摩根定律,将否定移至命题变元的前端; (3)运行分配律、结合律、吸收律等,将公式转化为等价的合取范式、析取范式。 例3.求下面公式的析取范式和合取范式: 19 (P→Q)∧.. R 解 : 原式=(P→Q)∧.. R =(..P∨Q)∧.. R // 合取范式,消去蕴涵,2个简单析取式的合取范式 =(..P∧..R)∨(Q∧..R)// 析取范式,分配律,2个简单合取式的析取范式 任意公式可以转化为等价的合取范式和析取范式,但是,析取范式和合取范式不是 唯一。例如, P 可以看作一个简单析取式,还可以如下转化,得到等价的析取范式: P =P∧(Q∨..Q)=(P∧Q)∨(P∧..Q)// P 的析取范式 =P∨(P∧Q) // P 的析取范式,吸收律 因此,求解合取、析取范式时,需要制定更加严格的标准,确保任意公式转化成的析 取范式、合取范式具有唯一性,这就是主范式的求解,包括了主析取范式和主合取范式。 3.3　主析取范式与主合取范式 5. 1. 主析取范式 定义3-17 给定 n 个命题变元,由命题变元或其否定构成的合取式,满足(1)命题变 第 3 章　命题逻辑45 元或其否定只出现其中之一,且不能重复出现,(2)出现的次序与命题变元的次序相同 (字典顺序),下标从小到大的顺序出现,这样的合取式称为命题变元的最小项或极小项。 例如,两个命题P、Q,最小项为: ..P∧..Q、..P∧Q、P∧..Q、P∧ Q //字典序 P 在先,二进制顺序为 0 、01 、10、 1 这样每个最小项,只有一种指派使其为1,其余为0,例如指派10,只有P∧.. Q 为1, 其余为0,如表3-17所示。对最小项编码,用mi表示,下标 i 是成真指派对应的二进制数 或十进制数,通常用十进制数表示下标。 表3-17 两个命题变元P、 Q 的最小项 最小项成真指派最小项符号表示备注 ..P∧.. Q 00 m0 ..P∧ Q 01 m1 P∧.. Q 10 m2 P∧ Q 11 m3 定义3-18 给定命题公式G, G 等值于 G 中所有命题变元产生的若干最小项的析 取,则称该析取式为公式 G 的主析取范式。 求任意公式的主析取范式,一般有两种方法: (1)等值演算法:先求出 G 的析取范式,然后扩充每个合取式中所缺少的命题变元, 最后利用分配律展开。 P∨..P=1 //缺少命题变元,用于最小项的扩充 Q=Q∧1=Q∧(P∨..P)=(Q∧P)∨(Q∧..P) 例3.求G=(P→Q)∧.. R 的主析取范式。 20 解: 原式=(P→Q)∧.. R =(..P∨Q)∧.. R //合取范式 =(..P∧..R)∨(Q∧..R)//第一个合取式缺少变元Q,第二个合取式缺少变元 P =(..P∧..R∧1)∨(Q∧..R∧1)//扩充最小项 =(..P∧..R∧(Q∨..Q) ∨(Q∧..R∧(P∨..P) //扩充缺少的命题变元 =(..P∧..R∧Q)∨(..P∧..R∧..Q)∨(Q∧..R∧P)∨(Q∧..R∧..P) =(..P∧..Q∧..R)∨(..P∧Q∧..R)∨(P∧Q∧..R)∨(..P∧Q∧..R)//排序