Name: Password: Sign in

[Lecture 2] 命题的等价

1 永真式,矛盾与可能式

  • 永真式 :如果无论逻辑变元真值如何复合命题都为真,例如 p¬p
  • 矛盾 :如果无论逻辑变元真值如何复合命题都为假,例如 p¬p
  • 可能式 : 复合命题真假取决于逻辑变元,例如 ¬p

2 逻辑等价

如果 pq 为永真式,那么命题 pq 等价,即 pq (注意符号 不是逻辑运算符,它不产生新的复合命题)

例如对于 pq¬pq,有:

p q ¬p pq ¬pq (pq)(¬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

从而

pq¬pq

又例如 De Morgan 定律,它指出了两组等价的复合命题:

¬(pq)¬p¬q

¬(pq)¬p¬q

利用真值表证明,如下所示:

p q ¬p ¬q pq ¬(pq) pq ¬(pq) ¬p¬q ¬p¬q
F F T T F T T F T T
F T T F F T T F T F
T F F T F T T F T F
T T F F T F F T F F

注意到第 6 列与第 9 列相同(¬(pq)¬p¬q 永真),第 8 列与第 10 列相同(¬(pq)¬p¬q 永真)

同样,可以证明析取结合律 p(qr)(pq)r 与和取结合律 p(qr)(pq)r。这说明,同为析取(或和取)的情况下逻辑表达式的值与运算顺序无关,pqrpqr 有定义。扩展这一结论有 p1p2...pnp1p2...pn 有定义,进而 De Morgan 定律可以扩展为:

¬(p1p2...pn)(¬p1¬p2...¬pn)

¬(p1p2...pn)(¬p1¬p2...¬pn)

De Morgan 定律表明,析取的否定为各分命题的和取,和取的否定为各分命题的析取,这一点在后续有广泛的运用。

3 构造新的逻辑等价式

3.1 逻辑等价式的替换

pqpq 总是有同样的值,因而可以相互替换而不改变表达式的逻辑。

例如证明 (pq)(pq) 为永真式,由 2.2 中讨论,pq¬pq,有:

(pq)(pq)¬(pq)(pq)

由 De Morgan 定律:

(pq)(pq)(¬p¬q)(pq)

由析取结合律和交换律有:

(pq)(pq)(¬pp)(¬qq)

从而:

(pq)(pq)TTT

利用这样的特性,我们使用通用的方法构造新表达式。

3.2 构造新表达式

假设我们想构造一个由命题变元 pq 构成的复合命题 c,满足下面的真值条件:

p q c
F F T
F T F
T F T
T T T

当然这样的简单问题可以直接观察得出(qp)。如果我们想用更为通用的方法来解答这类问题,我们可以构造一些复合命题构成的变元,再由这些变元析取得到与 c 等价的命题,过程如下:

  • 找到所有 c 为 T 的行,由此时 pq 的值构成一个和取式使得该和取式当且仅当 pq 为当前值时为真。例如上例中我们可以构造这样几组和取式:¬p¬qp¬qpq

  • 析取这几组和取式得到 (¬p¬q)(p¬q)(pq)

  • 上述和取式与 c 等价

当然证明也并不困难,由分配律有:

(¬p¬q)(p¬q)(pq)(¬pp)¬q(pq)¬q(pq)

¬q(pq)(¬qp)(¬qq)¬qpqpc

从而

(¬p¬q)(p¬q)(pq)c

3.3 析取范式

将以上方法推广,对于含有任意个变量的复合命题,要使其满足真值表要求。

  • 大项:如果每个合取式中每个变量出现且仅出现一次,我们称该合取式为大项 Mi

注意到对于给定的逻辑变元 p1p2pn,需要满足真值表中对应值为真的时候,我们都可以将它们析取起来构造大项 Mi,使得 Mi 当且仅当该给定变元组的时候为真(例如 2.3.2 中的 ¬p¬q 只有在第一行才为真)。

  • 合取范式:若干大项析取得到 M1M2...Mn,我们称其为 析取范式

由于析取范式中只要有一个大项为 T 则为 T,因而显然它满足了真值表中值为 T 所在行的要求;又对于真值表中所在行为 F 时,注意到所有的大项此时都是 F (构造大项的时候采用了和取)从而析取范式为 F,满足真值表的要求。

Copyright (c) 2014-2016 Kyles Light.
Powered by Tornado.
鄂 ICP 备 15003296 号