Download presentation
Presentation is loading. Please wait.
1
第2章 命题逻辑 2.1 命题逻辑的基本概念 命题与真值 简单命题与复合命题 命题符号化 五个联结词 命题常项、命题变项与合式公式
2.1 命题逻辑的基本概念 命题与真值 简单命题与复合命题 命题符号化 五个联结词 命题常项、命题变项与合式公式 公式的赋值 真值表 命题公式的分类 —— 重言式、 矛盾式、可满足式
2
1、命题与真值 命题: 是具有确定真值的陈述句（判断结果惟一的陈述句）。 命题的真值: 判断的结果。 真值的取值: 真或假。
真——用T或1表示；假——用F或0表示。 真命题: 真值为真的命题。 假命题: 真值为假的命题。 注意: 感叹句、祈使句、疑问句都不是命题。 陈述句中的悖论以及判断结果不惟一确定的也不是命题。
3
例 下列句子中那些是命题？ (1) 是无理数. (2) ＝8. (3) x + 5 ＞ 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话. (8) 如果太阳从西边升起，那么2是奇数. 真命题 假命题 真值不确定 疑问句 感叹句 祈使句 悖论 真命题 (3)~(7)都不是命题
4
2、命题的分类 简单命题(原子命题)： 简单陈述句构成的命题。 复合命题： 由简单命题通过联结词按一定规则联结而成的命题。
5
3、命题符号化 用小写英文字母 p, q, r, … ,pi,qi,ri (i≥1）表示简单命题。 用“1”表示真，用“0”表示假。
例如，令 p： 是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1 r：明天是晴天。
6
4、五个联结词 （1）否定式 定义 设p为命题，复合命题 “非p”（或 “p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p 为真当且仅当p为假。 说明：“”属一元运算符； 真值表： p p 1
7
自然语言中的“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”都可以符号化为∧，但“…和…”、“…与…”视情况而定。
（2）合取式 记 p∧q，∧称作合取联结词， 规定 p∧q为真当且仅当p与q同时为真。 说明：“∧”属二元运算符； 真值表： p q p∧q 1 自然语言中的“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”都可以符号化为∧，但“…和…”、“…与…”视情况而定。
8
例 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 王晓不是不聪明，而是不用功. (5) 张辉与王丽都是三好生. (6) 张辉与王丽是同学. 解 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) q ∧ p (4) ( q )∧ p
9
例 (续) 令 r : 张辉是三好学生，s :王丽是三好学生 (5) r∧s. (6) 令 t : 张辉与王丽是同学，t 是简单命题 .
说明: (1)~(5)说明描述合取式的灵活性与多样性. (6) 中“与”联结的是句子的主语成分，因而(6) 中句子是简单命题.
10
（3）析取式 记 p∨q，∨称作析取联结词， 并规 定 p∨q为假当且仅当p与q同时为假。 说明：“∨”属二元运算符； 真值表： 例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) ab=0，即a=0或b=0. (4) 小元元只能拿一个苹果或一个梨.
11
(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 , 为什么?
12
（4）蕴涵式 自然语言中的“或”具有二义性， 相容或：允许 p、q 同为真. 排斥或： p、q 中恰有一个成立(不能同时为真).
(1), (2), (3) 均为相容或，而 (4)~(7) 为排斥或. （4）蕴涵式 记 pq，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，pq为假当且仅当 p 为真 q 为假.
13
真值表： pq 的逻辑关系：q 为 p 的必要条件。 “如果 p，则 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 除非 q, 否则非 p 与自然语言的不同：前件与后件可以没有任何内在联系。 当前件 p 为F时，无论q 为何值，pq 均为T，即为“善意推定”。 如：如果 ≠ 4 ，则太阳从西边升起. T
14
注意： pq 与 q p 等值（真值相同）
将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候. pq pq pq qp qp pq qp qp 注意： pq 与 q p 等值（真值相同）
15
（5）等价式 记 pq，称作等价联结词. 规定 pq为真当且仅当p与q同时为真或同时为假. 说明: (1) 真值表： (2) pq 的逻辑关系：p与q互为充分必要条件。 等价于 (pq) ∧(qp). (3) 区分： p 仅当 q pq p 当 q qp p 当且仅当 q pq
16
例 求下列复合命题的真值 (1) ＝ 4 当且仅当 ＝ 6. (2) ＝ 4 当且仅当 3 是偶数. (3) ＝ 4 当且仅当 太阳从东方升起. (4) ＝ 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在x0 可导的充要条件是它在 x0 连续. 它们的真值分别为 1，0，1，0，0.
17
规定： ① 联结词的优先顺序为：( ),, , , , ; ② 如果联结词同级，则按从左到右的顺序运算，否则要加上括号。 例 分析运算次序：
18
5、命题变项与合式公式 命题常项(命题常元)：表示有确定真值的简单命题. 命题变项(命题变元)：真值可以变化的陈述句.
合式公式 (命题公式, 公式) ： 递归定义： 例 判断下列自符串中哪些是命题公式。 (1) p(qr) (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) 不是。
19
公式的层次 例如 公式((pq) r)(rs) 的层次。 p 0层 p 1层 pq 2层 (pq)r 3层
A C B 联结词 n=max(i,j) n+1 层 i 层 j 层 定义 例如 公式((pq) r)(rs) 的层次。 p 层 p 层 pq 层 (pq)r 层 ((pq) r)(rs) 层
20
6、公式的赋值 定义 给公式A中的命题变项 p1, p2, … , pn指定一组真值称为对A的一个赋值或解释。 成真赋值： 成假赋值：
含n个变项的公式有2n个赋值. 例 公式 ( p q ) r 001是一组成真赋值，110是一组成假赋值。
21
7、真值表 真值表: 公式A在所有赋值下的取值情况列成的表。 构造真值表的步骤： 例 给出公式的真值表。
例 给出公式的真值表。 （1）A= (qp) qp 的真值表 p q qp (qp) q (qp) qp 0 0 0 1 1 0 1 1 1
22
（2）B= (pq) r 的真值表 p q r pq r (pq)r 0 0 0 0 0 1 0 1 0 0 1 1
1
23
(1) p (pq) (2) (p q) ( pq) (3) (pq) r (4) (pq) q
（3）C = (pq) q 的真值表 p q p pq (pq) (pq) q 0 0 0 1 1 0 1 1 1 练习：给出公式的真值表。 (1) p (pq) (2) (p q) ( pq) (3) (pq) r (4) (pq) q
24
8、命题公式的分类 定义 设A为一个命题公式 (1) 若A无成假赋值，则称A为重言式(也称永真式)
注意：① 重言式是可满足式，但反之不真。即可满足式是至少存在一组成假赋值。 ② 可用真值表来判断公式的类型。 上例中A为重言式，B为可满足式，C为矛盾式
25
((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
26
2.2 命题逻辑等值演算 等值式 基本等值式 置换规则、 等值演算 真值函数 复合联结词 —— 与非式、或非式、排斥或 联结词的完备集
27
1、等值式 定义 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式。
说明：(1) 不是逻辑联结词，区分 与 ； (2) 判断两个公式A与B是否等值的方法 —— 真值表法、等值演算法。 用真值表可验证两个公式是否等值 请验证：p(qr) (pq) r p(qr) (pq) r
28
2、基本等值式 共16组： 德摩根律: (AB)AB (AB)AB 蕴涵等值式: ABAB
等价等值式: AB(AB)(BA) 注意: A,B,C代表任意的命题公式。 牢记这些等值式是继续学习的基础。
29
3、等值演算 等值演算: 由已知的等值式推演出新的等值式的过程。 置换规则：若AB, 则(B)(A)
例 q(p(pq)) qp 因为 p(pq) p 等值演算的基础： (1) 等值关系的性质：自反、对称、传递 (2) 基本的等值式 (3) 置换规则
30
例1 证明 p(qr) (pq)r 证 p(qr) p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq) r （蕴涵等值式，置换规则） 说明：也可以从右边开始演算（请做一遍）； 因为每一步都用置换规则，故可不写出； 熟练后，基本等值式也可以不写出。
31
例2 证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假. 方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左边的 成真赋值，是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观察.
32
例3 用等值演算法判断下列公式的类型。 (1) q(pq) 解 q(pq) q(pq) q(pq) p(qq) p0 0 该式为矛盾式. (2) (pq)(qp) 解 (pq)(qp) (pq)(qp) (pq)(pq) 1 该式为重言式. 问：最后一步为什么等值于1？
33
(3) ((pq)(pq))r) 解 ((pq)(pq))r (p(qq))r p1r pr 该式为可满足式. 如101是它的成真赋值,000是它的成假赋值. 说明：演算步骤不惟一,应尽量使演算短些。
34
(2) (pq)(pq) (pq)(pq)
例4 化简下程序段。 if (A) { if (B) x; else y; } else 执行 x的条件： (AB)(AB) (AA)B B if (B) x; else y; 化简为 练习 证明：(1) (pq) (pr) p(qr) (2) (pq)(pq) (pq)(pq)
35
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元真值函数.
36
说明： ① 对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表。 ② 等值的公式对应的真值函数相同。 ③ 如 P32表2.6给出所有2元真值函数对应的真值表, 每一个含2个命题变项的公式的真值表都可以在下表中找到。 例如：pq, pq, (pq)((pq)q) 等都对应 表中的
37
5、复合联结词 排斥或： pq(pq)(pq) 与非式： pq(pq) 或非式： pq(pq)
38
6、联结词的完备集 定义 设S是一个联结词集合，如果任何n(n1) 元 真值函数都可以由仅含S中的联结词构成的公式表
说明： 若S是联结词完备集，则任何命题公式都可用S 中的联结词表示. 若S1, S2是两个联结词集合，且S1 S2. 若S1是完备集，则S2也是完备集.
39
联结词的完备集实例 (1) S1={, , } (2) S2={, , , } (3) S3={, , , , }
而{},{ }等则不是联结词全功能集.
40
作业： P60 2(2,4,6)、4(2,4,6)、 5(2,4,6)、9(2，4)、 12(2,4)、20、22
Similar presentations
![1-5重言式与蕴含式 1-5.1重言式（tautology） 定义1-5.1 [重言式]:](/62/11581745/big_thumb.jpg "1-5重言式与蕴含式 1-5.1重言式（tautology） 定义1-5.1 [重言式]:>")
