离散数学课件 第一章

P
Q
0
0
0
1
1
0
1
1
P→Q 1 1 0 1
如： P:雪是黑的。
Q:太阳从东方升起 。
P → Q:如果雪是黑的，则太阳从东方升起 。
命题P→Q是假, 当且仅当P是真而Q是假。
11/20/2020
chapter1
14
1.2 联结词
条件与汉语中“如果…，就…”相类似，但有所区别: (1)自然语言中，“如果P则Q”，往往P和Q有一定的因果 关系，而条件复合命题P→Q中 P和Q 可以完全不相关。 (2)自然语言中，“如果P则Q”，当P为0、Q为1时，整个 句子真值难以确定；而条件复合命题P→Q中，当P为0时， 复合命题的真值为1。 P则Q的逻辑含义:P是Q的充分条件,的表示 命题变元——常用P、Q、R、S等大写字母或加下标的大 写字母P1, Q2, R10, ……表示来表示一个命题，称为命题 变元。 如： P:巴黎在法国。
Q:煤是白色的。
11/20/2020
chapter1
4
1.1 命题及其表示法
3、命题相关概念 简单命题（原子命题）——不能再分解的命题。 复合命题——由若干个简单命题复合而成的命题。 真值表——把组成复合命题的各命题变元的真值的所有 组合及其相对应的复合命题的真值列成表，称为真值表。
11/20/2020
chapter1
6
1.1 命题及其表示法
【例3 】求公式 (P→R)∨(Q→R)的真值表。 解：∵公式含有３个命题变元P、Q、R,
∴真值表有２3=8行。其真值表如下表 所示：
11/20/2020
chapter1
7
1.2 联结词
命题和原子命题常可通过一些联结词构成新命题, 这

3)区分“可兼或”与“不可兼或（异或，排斥或）” 析取联结词为可兼或 例如： 灯泡有故障或开关有故障。 今天下雨或打雷。 以上例句均为可兼或。
“不可兼或”表示为：▽ (异或),当P和Q均为“T”时， 则P异或Q为“F”。
P
Q
P▽Q
F
F
F
F
T
T
T
F
T
T
T
F
例： 他通过电视看杂技或到剧场看杂技。 他乘火车去北京或乘飞机去北京。
§1 命题与命题联结词
1 命题
《定义》： 具有唯一值的陈述句叫命题。 讨论定义：
(1)命题的值： 命题值可以是真的，也可以是假的，但不能同时 既为真又为假。
(2)命题的真假值表示： 命题中所有的“真”用“Ｔ ” 或“ 1”表示 命题中所有的“假”用“Ｆ ”或 “0 ”表示。
(3)命题分类： ⅰ)原子命题：一个命题，不能分解成为更简单的命题。
(2) 合取词（“合取”、 “与”运算） 1) 符号 “Λ” 设Ｐ，Ｑ为两个命题，则ＰΛＱ称Ｐ与Ｑ的合取， 读作： “Ｐ与Ｑ” “Ｐ与Ｑ的合取” “Ｐ并且Ｑ”
2) 合取运算真值表
P Q PΛ Q
FF
F
FT
F
TF
F
TT
T
QΛP F F F T
注： ①当且仅当Ｐ和Ｑ的真值均为 Ｔ ，则ＰΛＱ 的真值 为 Ｔ 。否则，其真值为 Ｆ 。
第一篇 数理逻辑
逻辑：通常指人们思考问题，从某些已知条件出发推出合 理的结论的规律。 数理逻辑：用数学方法来研究推理的规律。包括命题逻辑 和谓词逻辑。 数理逻辑研究方法：采用一套数学的符号系统来描述和处 理思维的形式和规律。
第一章 命题逻辑
§1.命题与命题联结词 §2.命题公式与真值表 §3.命题公式的翻译 §4. 等价式与蕴含式 §5.对偶与范 式 §6.命题逻辑的推理理论 §7.其他联结词

0
0
0
1
1
31
且 n=max(i,j)； (c) A=BC, 其中 B,C 的层次及 n 同(b)； (d) A=BC, 其中B,C 的层次及 n 同(b)； (e) A=BC, 其中B,C 的层次及 n 同(b). (3) 若公式A的层次为k, 则称A为k层公式.
例如 公式 A=p, B=p, C=pq, D=(pq)r,
E=((pq) r) (rs)
分别为0层，1层，2层，3层，4层公式.
16
公式赋值
定义1.8 设p1, p2, … , pn是出现在公式A中的全部命题变项, 给p1, p2, … , pn各指定一个真值, 称为对A的一个赋值或解释. 若使A为1, 则称这组值为A的成真赋值; 若使A为0, 则称这组
基本要求 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 会求复合命题的真值 深刻理解合式公式及重言式、矛盾式、可满足式等概念 熟练地求公式的真值表，并用它求公式的成真赋值与成假
赋值及判断公式类型 24
练习1
1. 将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞，他迟到了. (6) 如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞. (8) 除非交通阻塞，否则他不会迟到. (9) 他迟到当且仅当交通阻塞.
2
命题概念
例1 下列句子中那些是命题？ (1) 2是有理数. (2) 2 + 5 = 7.
(3) x + 5 > 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪.

ＰΛ（Ｐ∨Ｑ） Ｐ
（8）蕴含律： Ｐ→Ｑ¬Ｐ∨Ｑ （9）等价律：
ＰＱ（Ｐ→Ｑ）Λ（Ｑ→Ｐ） （10）零 律： Ｐ∨ＴＴ；ＰΛＦＦ （11）同一律： Ｐ∨ＦＰ；ＰΛＴＰ （12）否定律： Ｐ∨¬ＰＴ；ＰΛ¬ＰＦ （13）逆反律： Ｐ→Ｑ ¬Ｑ→ ¬Ｐ
说明： （1）证明上述１3组等价公式的方法可用真值表法。 （2） Λ、∨、 均满足结合律，则在单一用Λ、∨、
Λ¬Ｓ）→Ｐ，Ｑ→¬（Ｐ→¬Ｑ）等 所以，一个命题公式的代换实例有无限个。
3.等价置换
《定义》：给定一命题公式Ａ，Ａ’是Ａ的任何部分，若
Ａ’也是一命题公式，则称Ａ’是Ａ的子命题公式。
例：Ａ：（Ｐ∨Ｑ）→（Ｑ∨（ＲΛ¬Ｓ））
Ａ的子命题公式有： Ｐ、Ｑ、Ｒ、¬Ｓ、（Ｐ∨Ｑ）、（ＲΛ¬Ｓ）、 （Ｑ∨（ＲΛ¬Ｓ））、（Ｐ∨Ｑ）→（Ｑ∨（ＲΛ¬Ｓ））等。
（ＰΛＱ）→Ｐ为永真式。
(1) 列出真值表证明
P Q Ｐ→（Ｐ∨Ｑ） （ＰΛＱ）→Ｐ
FF T
T
FT T
T
TF T
T
TT T
T
（2）用等价公式证明 Ｐ→（Ｐ∨Ｑ） ¬Ｐ∨（Ｐ∨Ｑ） （¬Ｐ∨Ｐ）∨Ｑ T
（ＰΛＱ）→Ｐ ¬（ＰΛＱ）∨Ｐ （¬Ｐ∨¬Ｑ）∨Ｐ （¬Ｐ∨Ｐ）∨¬Ｑ T
《定理》 命题公式ＡＢ的充要条件是Ａ↔Ｂ为永真式。
《定理》：给定命题公式Ａ、Ｂ、Ｃ，若ＡＢ，且Ｂ Ｃ，则ＡＣ。 证明：∵ＡＢ，且ＢＣ， ∴（Ａ→Ｂ）Λ（Ｂ→Ｃ）为永真式， 由I6：（Ａ→Ｂ）Λ（Ｂ→Ｃ） （Ａ→Ｃ）， ∴（Ａ→Ｃ）也为永真式；即，ＡＣ成立
《定理》：给定一个命题公式Ａ、Ｂ、Ｃ，若ＡＢ, ＡＣ，则Ａ（ＢΛＣ） 证明：∵ＡＢ Λ ＡＣ， ∴（Ａ→Ｂ）Λ（Ａ→Ｃ）为永真式， 由条件，若Ａ一定为 Ｔ ，则Ｂ、Ｃ均为 Ｔ ， ∴Ａ→（ＢΛＣ）也为 Ｔ ， ∴Ａ（ＢΛＣ）为 Ｔ 。