第2章 命题逻辑 2.1 命题逻辑的基本概念 命题与真值 简单命题与复合命题 命题符号化 五个联结词 命题常项、命题变项与合式公式 2.1 命题逻辑的基本概念 命题与真值 简单命题与复合命题 命题符号化 五个联结词 命题常项、命题变项与合式公式 公式的赋值 真值表 命题公式的分类 —— 重言式、 矛盾式、可满足式

1、命题与真值 命题: 是具有确定真值的陈述句（判断结果惟一的陈述句）。 命题的真值: 判断的结果。 真值的取值: 真或假。 真——用T或1表示；假——用F或0表示。 真命题: 真值为真的命题。 假命题: 真值为假的命题。 注意: 感叹句、祈使句、疑问句都不是命题。 陈述句中的悖论以及判断结果不惟一确定的也不是命题。

例 下列句子中那些是命题？ (1) 是无理数. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话. (8) 如果太阳从西边升起，那么2是奇数. 真命题 假命题 真值不确定 疑问句 感叹句 祈使句 悖论 真命题 (3)~(7)都不是命题

2、命题的分类 简单命题(原子命题)： 简单陈述句构成的命题。 复合命题： 由简单命题通过联结词按一定规则联结而成的命题。

3、命题符号化 用小写英文字母 p, q, r, … ,pi,qi,ri (i≥1）表示简单命题。 用“1”表示真，用“0”表示假。 例如，令 p： 是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1 r：明天是晴天。

4、五个联结词 （1）否定式 定义 设p为命题，复合命题 “非p”（或 “p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p 为真当且仅当p为假。 说明：“”属一元运算符； 真值表： p p 1

自然语言中的“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”都可以符号化为∧，但“…和…”、“…与…”视情况而定。 （2）合取式 记 p∧q，∧称作合取联结词， 规定 p∧q为真当且仅当p与q同时为真。 说明：“∧”属二元运算符； 真值表： p q p∧q 1 自然语言中的“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”都可以符号化为∧，但“…和…”、“…与…”视情况而定。

例 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 王晓不是不聪明，而是不用功. (5) 张辉与王丽都是三好生. (6) 张辉与王丽是同学. 解 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) q ∧  p (4)  ( q )∧  p

例 (续) 令 r : 张辉是三好学生，s :王丽是三好学生 (5) r∧s. (6) 令 t : 张辉与王丽是同学，t 是简单命题 . 说明: (1)~(5)说明描述合取式的灵活性与多样性. (6) 中“与”联结的是句子的主语成分，因而(6) 中句子是简单命题.

（3）析取式 记 p∨q，∨称作析取联结词， 并规 定 p∨q为假当且仅当p与q同时为假。 说明：“∨”属二元运算符； 真值表： 例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) ab=0，即a=0或b=0. (4) 小元元只能拿一个苹果或一个梨.

(5) 人固有一死，或重于泰山或轻于鸿毛. (6) 王晓红生于1975年或1976年. (7) 张晓静是江西人或安徽人. 解：令 p:2是素数，q:3是素数，r:4是素数 则 (1), (2)分别符号化为: p∨r , p∨q 它们的真值分别为 1, 1. 令 t :小元元拿一个苹果，u:小元元拿一个梨， 则 (4) 符号化为 (t∧u) ∨(t∧u). 令v :王晓红生于1975年,w:王晓红生于1976年,则 (6) 既可符号化为 (v∧w)∨(v∧w), 又可符号化为 v∨w , 为什么?

（4）蕴涵式 自然语言中的“或”具有二义性， 相容或：允许 p、q 同为真. 排斥或： p、q 中恰有一个成立(不能同时为真). (1), (2), (3) 均为相容或，而 (4)~(7) 为排斥或. （4）蕴涵式 记 pq，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，pq为假当且仅当 p 为真 q 为假.

真值表： pq 的逻辑关系：q 为 p 的必要条件。 “如果 p，则 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 除非 q, 否则非 p 与自然语言的不同：前件与后件可以没有任何内在联系。 当前件 p 为F时，无论q 为何值，pq 均为T，即为“善意推定”。 如：如果 2 + 2 ≠ 4 ，则太阳从西边升起. T

注意： pq 与  q  p 等值（真值相同） 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候. pq pq pq qp qp pq qp qp 注意： pq 与  q  p 等值（真值相同）

（5）等价式 记 pq，称作等价联结词. 规定 pq为真当且仅当p与q同时为真或同时为假. 说明: (1) 真值表： (2) pq 的逻辑关系：p与q互为充分必要条件。 等价于 (pq) ∧(qp). (3) 区分： p 仅当 q pq p 当 q qp p 当且仅当 q pq

例 求下列复合命题的真值 (1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6. (2) 2 + 2 ＝ 4 当且仅当 3 是偶数. (3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起. (4) 2 + 2 ＝ 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在x0 可导的充要条件是它在 x0 连续. 它们的真值分别为 1，0，1，0，0.

规定： ① 联结词的优先顺序为：( ),, , , , ; ② 如果联结词同级，则按从左到右的顺序运算，否则要加上括号。 例 分析运算次序：

5、命题变项与合式公式 命题常项(命题常元)：表示有确定真值的简单命题. 命题变项(命题变元)：真值可以变化的陈述句. 合式公式 (命题公式, 公式) ： 递归定义： 例 判断下列自符串中哪些是命题公式。 (1) p(qr) (2) p(q  r) (3) p (4) q (5) pq r (6) p r (7) p (q r) (8) (p w) q) 解：(1)(2)(3)(4)(7)是公式，(5)(6)(8) 不是。

公式的层次 例如 公式((pq) r)(rs) 的层次。 p 0层 p 1层 pq 2层 (pq)r 3层 A C B 联结词 n=max(i,j) n+1 层 i 层 j 层 定义 例如 公式((pq) r)(rs) 的层次。 p 0层 p 1层 pq 2层 (pq)r 3层 ((pq) r)(rs) 4层

6、公式的赋值 定义 给公式A中的命题变项 p1, p2, … , pn指定一组真值称为对A的一个赋值或解释。 成真赋值： 成假赋值： 含n个变项的公式有2n个赋值. 例 公式 ( p q ) r 001是一组成真赋值，110是一组成假赋值。

7、真值表 真值表: 公式A在所有赋值下的取值情况列成的表。 构造真值表的步骤： 例 给出公式的真值表。 例 给出公式的真值表。 （1）A= (qp) qp 的真值表 p q qp (qp) q (qp) qp 0 0 0 1 1 0 1 1 1

（2）B= (pq) r 的真值表 p q r pq r (pq)r 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1

(1) p (pq) (2) (p  q)  ( pq) (3) (pq)  r (4) (pq) q （3）C =  (pq) q 的真值表 p q p pq  (pq)  (pq) q 0 0 0 1 1 0 1 1 1 练习：给出公式的真值表。 (1) p (pq) (2) (p  q)  ( pq) (3) (pq)  r (4) (pq) q

8、命题公式的分类 定义 设A为一个命题公式 (1) 若A无成假赋值，则称A为重言式(也称永真式) 注意：① 重言式是可满足式，但反之不真。即可满足式是至少存在一组成假赋值。 ② 可用真值表来判断公式的类型。 上例中A为重言式，B为可满足式，C为矛盾式

((c (a  b))  ( c (a  b))) a  b   c 张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎。现在问：这三人中到底谁说的是真话，谁说的是假话？ ((a   b)  ( a  b))  ((b   c)  ( b  c)) ((c (a  b))  ( c (a  b))) a  b   c

2.2 命题逻辑等值演算 等值式 基本等值式 置换规则、 等值演算 真值函数 复合联结词 —— 与非式、或非式、排斥或 联结词的完备集

1、等值式 定义 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式。 说明：(1)  不是逻辑联结词，区分 与 ； (2) 判断两个公式A与B是否等值的方法 —— 真值表法、等值演算法。 用真值表可验证两个公式是否等值 请验证：p(qr)  (pq) r p(qr) (pq) r

2、基本等值式 共16组： 德摩根律: (AB)AB (AB)AB 蕴涵等值式: ABAB 等价等值式: AB(AB)(BA) 注意: A,B,C代表任意的命题公式。 牢记这些等值式是继续学习的基础。

3、等值演算 等值演算: 由已知的等值式推演出新的等值式的过程。 置换规则：若AB, 则(B)(A) 例 q(p(pq))  qp 因为 p(pq)  p 等值演算的基础： (1) 等值关系的性质：自反、对称、传递 (2) 基本的等值式 (3) 置换规则

例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 用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假. 方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左边的 成真赋值，是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观察.

例3 用等值演算法判断下列公式的类型。 (1) q(pq) 解 q(pq)  q(pq)  q(pq)  p(qq)  p0  0 该式为矛盾式. (2) (pq)(qp) 解 (pq)(qp)  (pq)(qp)  (pq)(pq)  1 该式为重言式. 问：最后一步为什么等值于1？

(3) ((pq)(pq))r) 解 ((pq)(pq))r  (p(qq))r  p1r  pr 该式为可满足式. 如101是它的成真赋值,000是它的成假赋值. 说明：演算步骤不惟一,应尽量使演算短些。

(2) (pq)(pq)  (pq)(pq) 例4 化简下程序段。 if (A) { if (B) x; else y; } else 执行 x的条件： (AB)(AB)  (AA)B B if (B) x; else y; 化简为 练习 证明：(1) (pq) (pr)  p(qr) (2) (pq)(pq)  (pq)(pq)

4、真值函数 问题：含n个命题变项的所有公式共产生多少个互 不相同的真值表？ 答案为 个，为什么？ n元真值函数 答案为 个，为什么？ n元真值函数 定义 F: {0,1}n{0,1} 共有 个n元真值函数。 例如 F:{0,1}2{0,1}，且F(00)=F(01)=F(11)=0， F(10)=1，则F为一个确定的2元真值函数.

说明： ① 对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表。 ② 等值的公式对应的真值函数相同。 ③ 如 P32表2.6给出所有2元真值函数对应的真值表, 每一个含2个命题变项的公式的真值表都可以在下表中找到。 例如：pq, pq, (pq)((pq)q) 等都对应 表中的

5、复合联结词 排斥或： pq(pq)(pq) 与非式： pq(pq) 或非式： pq(pq)

6、联结词的完备集 定义 设S是一个联结词集合，如果任何n(n1) 元 真值函数都可以由仅含S中的联结词构成的公式表 说明： 若S是联结词完备集，则任何命题公式都可用S 中的联结词表示. 若S1, S2是两个联结词集合，且S1  S2. 若S1是完备集，则S2也是完备集.

联结词的完备集实例 (1) S1={, , } (2) S2={, , , } (3) S3={, , , , } 而{},{ }等则不是联结词全功能集.

作业： P60 2(2,4,6)、4(2,4,6)、 5(2,4,6)、9(2，4)、 12(2,4)、20、22