离散数学(2) 逻辑等价

逻辑等价

我们学习了怎么样用真值表来判断一个命题的真假,这是一种万无一失的判断方法。它的弊端也很明显:太过复杂。我们知道真值表的行数是$2^n$行,其中n为命题的数量。我们不妨看看函数图,横坐标是命题的数量,纵坐标是真值表的行数。当命题越来越多的时候,它的真值表行数会增长更快!

36

这节课我们学习另一种求真值的办法 – 逻辑等价。一种通过将命题简化,从而达到最简表达式并能找出可能真值的方法。

命题可满足性

所谓命题可满足性,即当原子命题的真值能够使复合命题为真所具备的条件。比如说 (A \vee B) \wedge C

当A, B任何一个命题为真,C也为真的时候整个复合命题就是真的。我们就说这个复合命题具有命题可满足性。

逻辑等价

逻辑学的历史悠久,很多人在反复的推导中发现了一些逻辑等价的规律。运用这些规律我们可以将一个复合命题简化再判断其是否具有命题可满足性。下表为所有本课需要学的逻辑等价。

Logic Equivalence Cheat sheet

看起来有点多,加以练习之后我们会很快上手的。我们先观察一个复合命题 (P \wedge Q) \vee (P \wedge \neg Q)

如果我们用真值表来判断这个逻辑表达式的命题可满足性的话我们首先要列$2^2$行表格,然后再画若干列来写出所有可能性。这么做没有问题,但却复杂。

根据上面的表,我们可以证明:

  1. (P \wedge Q) \vee (P \wedge \neg Q)

  2. \equiv P \vee (Q \wedge \neg Q) Distributive Laws

  3. \equiv P \vee T Cancellation Law

从第二步到第三步用了一个Cancellation Law, 它没有出现在表格中。但是很好理解, 我们知道逻辑与 \wedge 是当所有原子命题为真的时候复合命题才为真。如果Q的真值为真,那么 (Q \wedge \neg Q) 里面 \neg Q 的真值就为假,反之亦然。所以整个 (Q \wedge \neg Q) 部分是一个矛盾式。

可以看到,通过逻辑等价,我们不但简化了一条复合命题到简单命题真值表也随之简单很多了。

除此之外,我们还有一个逻辑包含表(也在上面的链接中),它可以帮助我们找出逻辑表达式之间的关系。我们会在稍后的证明中用到它。

课后练习

利用逻辑等价证明下列逻辑表达式等价

  1. Q \rightarrow (P \vee (P \wedge Q)) \equiv Q \rightarrow P

  2. P \rightarrow (P \rightarrow Q)) \equiv \neg Q \rightarrow \neg P

  3. A \leftrightarrow B \equiv (A \wedge B) \vee (\neg A \wedge \neg B)

证明下列个命题公式为永真式:

  1. P \rightarrow (P \vee Q)

  2. \neg P \rightarrow (P \rightarrow Q)

1 个赞