第2章 逻辑和证明

第二章逻辑和证明2.2 命题等价

命题演算：用真值相同的命题取代另一个 在证明时广泛使用

定义1.永真式（重言式）：真值总是真 矛盾（式）：真值总是假 可能式：真值可真也可假

真值表判定法 例1pp和pp

表2-1永真式和矛盾的例子定义2命题逻辑等价：两个复合命题在所有可能的情况下 都有相同真值 是永真式 记为真值表判定法例2证明命题 和 逻辑等价解在表2-2中构造了这两个命题的真值表，由于 和 的真值相同，它们是逻辑等价的。（接下页）

表2-2 和 的真值表例3

证明命题p∨(q∧r)和(p∨q)∧(p∨r)逻辑等价。这是析取对合取的分配律。证明：表1-11中构造了这两个命题的真值表。因为p∨(q∧r)的真值和(p∨q)∧(p∨r)的真值一样，它们是逻辑等价的。基本的逻辑等价关系（1）双重否定律：

A=A（2）等幂律：AA=A，AA=A（3）交换律：AB=BA,AB=BA（4）结合律：(AB)C=A(BC) (AB)C=A(BC)（5）分配律：(AB)C=(A

C)(BC)

(AB)C=(AC)(BC)（6）德.摩根律：(AB)=A

B(AB)=A

B（7）吸收律：A(AB)=A A(AB)=A（8）零律： AF=F AT=T（9）一律： AF=A AF=A（10）排中律：A

A=T（11）矛盾律：A

A=F（12）蕴涵等值式：A→B=AB（13）假言易位：A→B=B→A（14）等价等值式：AB=(AB)(BA)基本(p1p2…pn)(p1p2…

pn)命题逻辑等价关系与基本的集合恒等式的相似性的结合律与pqrs的含义的结合律与pqrs的含义 德摩根律的扩展 (p1p2…

pn)(p1p2…

pn)

等值演算：将复合命题中的一个子命题用与它逻辑等 价的另一个命题替换，不会改变原命题的真值，从而 得到新的逻辑等价的命题例5证明（p（pq））和pq逻辑等价证明：我们有下列等价关系

（p（pq））=p（pq） 由第二得摩根定律

=p（（p）q） 由第一得摩根定律

=p（pq） 由双非律

=（pp）（pq） 由分配律

=F（pq）

=pq

由F的恒等律例6

证明(p∧q)→(p∨q)为永真式。证明： 为证明这个命题是永真式，我们将用逻辑等价证明它逻辑上等价于T。（注意：这也可以用真值表来完成。）

(p∧q)→(p∨q)=¬(p∧q)∨(p∨q) =(¬p∨¬q)∨(p∨q) =¬(p∨p)∨(¬q∨q) =T∨T =T对偶原理：若两个命题等价，则它们的对偶命题也等价只含逻辑运算符、和的命题的对偶命题：

、

TF主析取范式和主合取范式 范式：具有某种特殊形式（结构）的命题公式 文字：命题变量或命题变量的否定（如p、p） 主析取范式：析取式，其中的每个析取项都是极小项 极小项：由文字构成的合取式，且原命题公式中的每个命题变量都在合取式中出现一次 主合取范式：合取式，其中的每个合取项都是极大项 极大项：由文字构成的析取式，且原命题公式中的每个命题变量都在析取式中出现一次任意命题公式都有与之等价的主析取范式和主析取范式从真值表构造主析取范式 对应于真值表中为真的每一行，在主析取范式中都有一个对应的合取式 行中为F的变量在相应的合取式中带有从真值表构造主合取范式 对应于真值表中为假的每一行，在主合取范式中都有一个对应的析取式 行中为T的变量在相应的合取式中带有例命题公式A= 的主析取范式与主合取范式。

真值表：主析取范式：主合取范式：习题

1.用真值表证明等价