目录
1. 命题
(1)只有具有确定真值的陈述句才是命题,一切没有判断内容的句子,无所谓是非的句子,如感叹句、疑问句、祈使句等都不能作为命题。
(2)命题分为两种类型:
① 原子命题:不能分解为更简单的陈述语句。
② 复合命题:由联结词,标点符号和原子命题复合构成的命题,称为复合命题。
【注】所有这些命题都应该具有确定的真值。
2. 联结词
(1)否定(﹁)
P | ﹁P |
T | F |
F | T |
(2)合取(∧)
P | Q | P∧Q |
T | T | T |
T | F | F |
F | T | F |
F | F | F |
(3)析取(∨)
P | Q | P∨Q |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
(4)条件(→)
P | Q | P→Q |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
(5)双条件(⇄)
P | Q | P⇄Q |
T | T | T |
T | F | F |
F | T | F |
F | F | T |
3. 真值表
P | Q | P∧Q | ﹁P | (P∧Q)∧﹁P |
T | T | T | F | F |
T | F | F | F | F |
F | T | F | T | F |
F | F | F | T | F |
4. 等价公式
序号 | 表达式 | 命题定律 |
1 | ﹁﹁P=P | 对合律 |
2 | P∨P⇔P,P∧P⇔P | 幂等律 |
3 | (P∨Q)∨R⇔P∨(Q∨R) (P∧Q)∧R⇔P∧(Q∧R) |
结合律 |
4 | P∨Q⇔Q∨P P∧Q⇔Q∧P |
交换律 |
5 | P∨(Q∧R)⇔(P∨Q)∧(P∨R) P∧(Q∨R)⇔(P∧Q)∨(P∧R) |
分配律 |
6 | P∨(P∧Q)⇔P P∧(P∨Q)⇔P |
吸收律 |
7 | ﹁(P∨Q)⇔﹁P∧﹁Q ﹁(P∧Q)⇔﹁P∨﹁Q |
德摩根律 |
8 | P∨F⇔P,P∧T⇔P | 同一律 |
9 | P∨T⇔T,P∧F⇔F | 零律 |
10 | P∨﹁P⇔T,P∧﹁P⇔F | 否定律 |
5. 蕴含式
(1)重言式:就是永真公式,真值永远为T
(2)蕴含式:当P→Q是个重言式,则P蕴含Q,记作P⇒Q
(3)对于P→Q:
① 逆换式:Q→P
② 反换式:﹁P→﹁Q
③ 逆反式:﹁Q→﹁P
1 | P∧Q⇒P |
2 | P∧Q⇒Q |
3 | P⇒P∨Q |
4 | ﹁P⇒P→Q |
5 | Q⇒P→Q |
6 | ﹁(P→Q)⇒P |
7 | ﹁(P→Q)⇒﹁Q |
8 | P∧(P→Q)⇒Q |
9 | ﹁Q∧(P→Q)⇒﹁P |
10 | ﹁P∧(P∨Q)⇒Q |
11 | (P→Q)∧(Q→R)⇒(P→R) |
12 | (P∨Q)∧(P→R)∧(Q→R)⇒R |
简单来说,蕴含式(P⇒Q)的意思就是前者(P)永远为真时,必定会有后者(Q)发生(想要得到前者(P),后者(Q)必须是其中一个条件)
6. 对偶式
简单来说,就是把命题公式中联结词∨换成∧,将∧换成∨,若有特殊变元F和T亦可相互取代
例如:(P∧Q)∨T
对偶式为:(P∨Q)∧F
7. 范式
(1)合取范式:A1∧A2∧A3∧…∧An (An是析取式)
求法:
① 将公式中的联结词化归为∧,∨,﹁(去掉→)
② 利用德摩根律将否定符号﹁移到各个命题变元之前
③ 利用分配律、结合律将公式归约为合取范式
大项:
① 任意两个不同大项的析取式永真
② 全体大项的合取式为永假
主合取范式:
对于命题公式,如果有一个等价公式由全体大项的合取组成,则为主合取范式
求法:
① 化归为合取范式
② 除去合取范式中所有永真的合取项
③ 将合取范式中重复出现的析取项和相同的变元合并
④ 对析取项补入没有出现的命题变元,即添加(P∧﹁P),利用分配律展开公式即可
注:也可以画真值表,找真值为F的指派所对应大项,这些大项的合取就是主合取范式
(2)析取范式:A1∨A2∨A3∨…∨An (An是合取式)
求法:
① 将公式中的联结词化归为∧,∨,﹁(去掉→)
② 利用德摩根律将否定符号﹁移到各个命题变元之前
③ 利用分配律、结合律将公式归约为析取范式
小项:
① n个命题变元共有2^n个小项
② 任意两个不同小项的合取式永假
③ 全体小项的析取式为永真
主析取范式:
对于命题公式,如果有一个等价公式由全体小项的析取组成,则为主析取范式
求法:
① 化归为析取范式
② 除去析取范式中所有永假的析取项
③ 将析取范式中重复出现的合取项和相同的变元合并
④ 对合取项补入没有出现的命题变元,即添加(P∨﹁P),利用分配律展开公式即可
注:也可以画真值表,找真值为T的指派所对应小项,这些小项的析取就是主析取范式
8. 推理理论
简单来说,就是利用蕴含式和等价式进行推理证明,我们通过两个个例子来讲解:
(1)直接证明
证明:(P∨Q)∧(P→R)∧(Q→S)⇒S∨R
(1) P∨Q P
(2) ﹁P→Q T(1)E
(3) Q→S P
(4) ﹁P→S T(2),(3)I
(5) ﹁S→P T(4)E
(6) P→R P
(7) ﹁S→R T(5),(6)I
(8) S∨R T(7)E
(2)间接证明
证明:A→B,﹁(B∨C) 可逻辑推出﹁A
(1) A→B P
(2) A P(附加前提) 注:间接证明就是假设﹁(﹁A)是成立的
(3) ﹁(B∨C) P
(4) ﹁B∧﹁C T(3)E
(5) B T(1),(2)I
(6) ﹁B T(4)I
(7) B∧﹁B(矛盾) T(5),(6)I 矛盾说明(﹁A)是成立的