数理逻辑与集合论：1 命题逻辑的基本概念.ppt

引言
现代科学技术的各个领域，都提出了大量离散结构的科学问题。例如：
计算机科学
程序设计
计算机网络
信息论与编码
通信理论
现代密码学
数字信号处理
形式语言
等……
它们都与离散数学密切相关。
引言
离散数学
是联结词及真值表
1. 否定词
定义: 设 P 是一个命题, 构造一个新命题是原命题的否定, 称该命题是命题 P 的取否命题, 表示成“P ”.
规定:
P 为真当且仅当P为假
例如:
P : 今天下雨.
 P : 今天不下雨.
自然语言中用到的联结词: 非 , 不 , 并非
P
 P
F T
T
F
真值表——
公式在所有赋值下的取值情况列成的表
联结词
2. 合取词
定义: 设命题 P 和 Q 是两个命题,构造一个新命题“ P 与 Q ”,称作命题 P 和 Q 的合取,表示成“PQ ”.
规定——
当且仅当 P 和 Q 都为真时, P Q 为真.
自然语言中用到的联结词:
“和”，“与” , “并且”
“既...又...” “不仅...而且...”
“虽然...但是...
P Q
PQ
F F
F T
T F
T T
F
F
F
T
例: 将下列命题符号化
P:李平聪明. Q:李平用功.
(1) 李平既聪明又用功.
(2) 李平虽然聪明但不用功.
(3) 李平不但聪明而且用功.
(4) 李平不是不聪明而是不用功.
P  Q
P  Q
P  Q
(P)  Q
例: P:今天下雨. Q: 3+3=6
今天下雨与3+3=6. 可表示为:P Q
“” 可以连接两个完全没有联系的命题.
联结词
3. 析取词∨
定义:设命题 P 和 Q 是两个命题, 构造一个新命题“ P 或Q ”, 称作命题 P 和 Q 的析取, 表示成“PQ”.
规定——
P∨Q为假当且仅当 P 与 Q 同时为假.
当且仅当 P 和 Q 中至少一个为真时,
P  Q 为真.
P Q
P∨Q
F F
F T
T F
T T
F
T
T
T
联结词
例如：
P: 灯泡有故障. Q: 开关有故障.
灯泡有故障或开关有故障.
(可能同时发生)
应表示为 P  Q
注意: 析取词表示的是“可兼或”.
例如:
P: 小李正在家里看书. Q: 小李正在剧场看戏.
小李正在家里看书或正在剧场看戏.
（不可能同时发生）
表示为： (P  Q)  ( P Q)
=P  Q
P Q
P  Q
F F
F T
T F
T T
F
T
T
F
—
—
P Q
P∨Q
F F
F T
T F
T T
F
T
T
T
4. 蕴涵词
定义: 设 P,Q为二命题，复合命题 “如果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Q
P是Q 的充分条件
P是Q 的必要条件。
（1）只要不下雨，我就骑自行车上班。
（2）只有不下雨，我才骑自行车上班。
设：P：天下雨。Q：我骑自行车上班。
(1) 等价为：除非我骑自行车上班，否则天下雨。
 P Q
（2）等价为：除非不下雨，我才骑自行车上班。
Q   P
注意：P Q 中的 P 和 Q 不一定有内在联系。
例: 将下列命题符号化
联结词
规定
PQ为假当且仅当P为真Q为假.
当 P 为假时，PQ 为真
说明——
如：P:“天气好” Q:“我去接你”
则P Q ：“若天气好，则我去接你”
当天气好时，
我去接了你，此时， P Q 真
我没去接你，此时， P Q 假
当天气不好时，
我无论去或不去接你均未食言，此时认定P Q 为真是适当的
P Q
P  Q
F F
F T
T F
T T
T
T
F
T
PQ=  P  Q
联结词
5. 双条件词
定义：设P，Q为二命题， “P当且仅当Q”称作 P 与 Q 的等价