东南大学：《离散数学》课程教学资源（PPT课件讲稿）第二章 命题逻辑等值演算

第2章命题逻辑等值演算 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式,主析取范式与主合取 范式 联结词完备集 可满足性问题与消解法

1 第2章 命题逻辑等值演算 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式，主析取范式与主合取 范式 联结词完备集 可满足性问题与消解法

2.1等值式 口等值式:公式A,B的等价式A<B为永 真式 △符号:A台B,也称A逻辑恒等于B

2 2.1 等值式 ❑等值式：公式A，B的等价式A↔B为永 真式 ❖符号：ＡＢ，也称A逻辑恒等于B

2.1等值式 口例子 令判断→p台→p D pFT TF Ld TT 3

3 2.1 等值式 p ¬p ¬¬p ¬¬p  p F T F T T F T T ❑例子 ❖ 判断¬¬pp

2.1等值式 口例子 令判断Pq台一pVq Pq卩>q pvg p-q收"pvq FFT FTI T TF F TTFT TTFT TTTT TITF 4

4 2.1 等值式 p q ¬p p→q ¬pq p→q  ¬pq F F T T T T F T T T T T T F F F F T T T F T T T ❑例子 ❖ 判断 p→q  ¬pq

2.1等值式 口否定律 令双重否定律→p→p ◆德摩根律 (pVq分-p∧-q (p∧q)分→pV=q 口幂等律pp兮p,卩∧p分p 口交换律 ☆pVq冷qVp ☆卩∧q分q∧p ☆卩q分qP 5

5 2.1 等值式 ❑否定律 ❖双重否定律 ¬¬pp ❖德摩根律 • ¬ (p  q)  ¬ p  ¬q • ¬ (p  q)  ¬p  ¬q ❑幂等律 p  p  p， p  p  p ❑交换律 ❖p  q  q  p ❖p  q  q  p ； ❖p  q  q  p

2.1等值式 口结合律 ☆(pVq)Vr分pV(qv门 ☆(p∧q)∧r冷DA(q∧门 ☆(p分q)分「冷卩分(q冂 口分配律 ☆p∧(q分(D∧qV(D∧门 pV(q∧分(PVq)∧(pv门

6 2.1 等值式 ❑结合律 ❖(p  q)  r  p  (q  r) ❖(p  q)  r  p  (q  r) ❖(p  q)  r  p  (q  r) ❑分配律 ❖p  (q  r)  (p  q)  (p  r) ❖p  (q  r)  (p  q)  (p  r)

2.1等值式 口吸收律 ☆pV印D∧q冷卩 ☆p∧(pVq)冷p 口常元律 令零律:pT兮T,p∧F分F 同一律:pvF台p,P∧T台p 排中律:pv=p兮T 令矛盾律:p∧→p分F

7 2.1 等值式 ❑吸收律 ❖p  (p  q)  p ❖p (p  q)  p ❑常元律 ❖零律: p  T  T， p  F  F ❖同一律: p  F  p， p  T  p ❖排中律: p  ¬ p  T ❖矛盾律: p  ¬ p  F

2.1等值式 口蕴含等值式卩→q分pvq 口等价等值式pq兮(p→q)∧(q→p) 口假言易位p→q分q→→p 口等价否定等值式Pq兮一q 口归缪律(p→q)∧(→q)分p

8 2.1 等值式 ❑蕴含等值式 p → q  ¬ p  q ❑等价等值式 p  q (p → q)  (q → p) ❑假言易位 p → q  ¬ q → ¬ p ❑等价否定等值式 p  q  ¬ p  ¬ q ❑归缪律 (p → q )  (p → ¬ q )  ¬ p

2.1等值式 说明: (1)16组等值模式都可以给出无穷多个同类型的具 体的等值式 (2)证明上述16组等值式的代入实例方法可用真值 表法,把分改为<所得的命题公式为永真式,则 分成立

9 2.1 等值式 说明： (1)16组等值模式都可以给出无穷多个同类型的具 体的等值式。 (2)证明上述16组等值式的代入实例方法可用真值 表法，把改为所得的命题公式为永真式，则 成立

2.1等值式 口置换规则:设q(A是含公式A的命题公式, q(B是用公式B置换了q(A)中所有A后得到的 命题公式,若AB,则q(A)分φ(B)。 口说明: ◆等值演算过程中遵循的重要规则。 一个命题公式A,经多次置换,所得到的新公式 与原公式等价。 称由已知的等值式推演出另外一些等值式的过程 为等值演算。 10

10 2.1 等值式 ❑置换规则：设φ(A)是含公式A的命题公式， φ(B)是用公式B置换了φ(A)中所有A后得到的 命题公式，若ＡB ，则φ(A)  φ(B) 。 ❑说明： ❖等值演算过程中遵循的重要规则。 ❖一个命题公式A，经多次置换，所得到的新公式 与原公式等价。 ❖称由已知的等值式推演出另外一些等值式的过程 为等值演算