离散习题讲解（2）

她来听我的演唱会......

问题：

掌握德摩根定律

使用德摩根定律（De Morgan’s Laws）对以下语句取反，并给出解释。

a) Kwame will take a job in industry or go to graduate school.
b) Carlos will bicycle or run tomorrow.
c) Yoshiko knows Java and calculus.
d) James is young and strong.
e) Rita will move to Oregon or Washington.

解答：

德摩根定律的内容是：

  • 对于命题“P 或 Q”的否定：¬(P ∨ Q) ≡ ¬P ∧ ¬Q
  • 对于命题“P 且 Q”的否定：¬(P ∧ Q) ≡ ¬P ∨ ¬Q

这些规则可以帮助我们将原始语句的否定转换为更简单的形式。

解释和答案：

a) Kwame will take a job in industry or go to graduate school.
原命题是“Kwame将要做一份工业工作或上研究生”。这可以表示为“P ∨ Q”，其中P表示“Kwame将做工业工作”，Q表示“Kwame将上研究生”。

根据德摩根定律，否定为：
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
因此，答案是：
Kwame will not take a job in industry and will not go to graduate school.

b) Carlos will bicycle or run tomorrow.
原命题是“Carlos明天要么骑自行车，要么跑步”。这也是一个“P ∨ Q”形式。

根据德摩根定律，否定为：
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
因此，答案是：
Carlos will not bicycle tomorrow, and Carlos will not run tomorrow.

c) Yoshiko knows Java and calculus.
原命题是“Yoshiko知道Java和微积分”。这是一个“P ∧ Q”形式，其中P表示“Yoshiko知道Java”，Q表示“Yoshiko知道微积分”。

根据德摩根定律，否定为：
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
因此，答案是：
Yoshiko does not know Java or does not know calculus.

d) James is young and strong.
原命题是“James年轻且强壮”。这是一个“P ∧ Q”形式，其中P表示“James年轻”，Q表示“James强壮”。

根据德摩根定律，否定为：
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
因此，答案是：
James is not young, or he is not strong.

e) Rita will move to Oregon or Washington.
原命题是“Rita将要搬到俄勒冈或华盛顿”。这也是一个“P ∨ Q”形式。

根据德摩根定律，否定为：
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
因此，答案是：
Rita will not move to Oregon and will not move to Washington.

总结：

  • a) Kwame will not take a job in industry and will not go to graduate school.
  • b) Carlos will not bicycle tomorrow, and Carlos will not run tomorrow.
  • c) Yoshiko does not know Java or does not know calculus.
  • d) James is not young, or he is not strong.
  • e) Rita will not move to Oregon and will not move to Washington.

问题：

Q2: Show that $ p (q r) $ and $ q (p r) $ are logically equivalent.

Q3: Show that $ (p r) (q r) $ and $ (p q) r $ are logically equivalent.

Q4: Show that $ (q (p q)) p $ is a tautology.

解答和解释：

Q2: $ p (q r) $ 和 $ q (p r) $ 是否逻辑等价？

首先将两个命题分别用逻辑表达式转换并简化。我们需要证明它们是逻辑等价的，即它们的真值表相同。

  1. 命题 1：$ p (q r) $
    • $ p (q r) $ 等价于 $ (p) (q r) $
    • $ (p) p \(，所以有：\) p (q r) $
    • $ q r $ 等价于 $ q r \(，因此：\) p (q r) $
    • 进一步合并： $ p q r $
    • 这就是简化后的第一个命题。
  2. 命题 2：$ q (p r) $
    • $ q (p r) $ 等价于 $ q (p r) $
    • 所以，第二个命题是： $ q p r $
    • 注意到 $ p q r $ 和 $ q p r $ 是等价的（这两者只是顺序不同），因此这两个命题是逻辑等价的。

结论： $ p (q r) q (p r) $

Q3: $ (p r) (q r) $ 和 $ (p q) r $ 是否逻辑等价？

我们将两个命题的表达式分别转换，并简化：

  1. 命题 1：$ (p r) (q r) $
    • $ p r $ 等价于 $ p r $
    • $ q r $ 等价于 $ q r $
    • 所以： $ (p r) (q r) $
    • 使用分配律进行展开： $ (r p) (r q) $
    • 进一步合并： $ r (p q) $
    • 所以，命题 1 简化为： $ r (p q) $
  2. 命题 2：$ (p q) r $
    • $ (p q) r $ 等价于 $ (p q) r $
    • 这与命题 1 简化后的形式是等价的，因为 $ (p q) p q $。
    • 所以： $ (p q) r r (p q) $

结论： $ (p r) (q r) (p q) r $

Q4: $ (q (p q)) p $ 是否为重言式（tautology）？

我们将证明该命题在所有可能的情况下都为真。

  1. 命题：$ (q (p q)) p $
    • $ p q $ 等价于 $ p q $
    • 所以命题变为： $ (q (p q)) p $
    • 展开 $ q (p q) \(：\) (q p) (q q) $
    • $ q q $ 为假，因此剩下的是： $ q p $
    • 于是整个命题变为： $ (q p) p $
    • 由于 $ q p $ 包含 $ p $，所以无论 $ q $ 是否为真，命题始终为真。

结论： $ (q (p q)) p $

总结：

  • Q2: $ p (q r) $ 和 $ q (p r) $ 是逻辑等价的。
  • Q3: $ (p r) (q r) $ 和 $ (p q) r $ 是逻辑等价的。
  • Q4: $ (q (p q)) p $ 是一个重言式（始终为真）。