第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 ❑例子 ❖ 判断¬¬pp
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 ¬pq p→q ¬pq 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 ¬pq
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 等值式 ❑否定律 ❖双重否定律 ¬¬pp ❖德摩根律 • ¬ (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，经多次置换，所得到的新公式 与原公式等价。 ❖称由已知的等值式推演出另外一些等值式的过程 为等值演算