【离散数学】命题逻辑

发布于:2022-11-09 ⋅ 阅读:(9) ⋅ 点赞:(0) ⋅ 评论:(0)

目录

1. 命题

2. 联结词 

3. 真值表                                                     

4. 等价公式 

5. 蕴含式

6. 对偶式

7. 范式

8. 推理理论 


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的真值表
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)是成立的