Site Overlay

离散数学笔记:1.3:命题等价

命题等价

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.

逻辑等价(Logical Equivalences)

如果 $f(p,q,\cdots)$ 的真值与变量的关系永远对应于 $g(p,q,\cdots)$,那么$f,g$ 就是逻辑等价的。

【例子】德摩根律:

$$
\begin{aligned}&\neg(p \wedge q) \equiv \neg p \vee \neg q\\&\neg(p \vee q) \equiv \neg p \wedge \neg q\end{aligned}
$$

这个经常写代码的人应该秒懂吧……

【例子】证明 $p\to q$ 逻辑等价 $\neg p \or q$ (条件析取等价)

$p\to q$$p$ 真,$q$ 假时为真,这个好像从定义上就是等价的,不知道为啥书上还要用个表格证明?

image-20200407121556941

【例子】证明 $\neg (p\or (\neg p \and q))\equiv \neg p \and \neg q$

解:

    !(p || (!p && q))
=== !p && !(!p && q)
=== !p && (p || !q)
=== (!p && p) || (!p && !q)
=== F || !p && !q

注意:括号不能随便丢弃!!p && !(!p && q) !== !p && p || !q

同义反复(tautology)——永真式

【例子】证明 $(p\and q) \to (p \or q)$ 是同义反复。

解:

    (p && q)->(p || q)
=== !(p && q) || (p || q)
=== !p || !q || p || q
=== !p || p || !q || q
=== true || true
=== true

矛盾(contradiction )——永假式

可满足 (Satisfiability)

如果存在赋值使得 $f(p,q,\cdots) = T$ 那么 $f$ 就是可满足的。

【例子】Determine whether each of the compound propositions

  1. $(p ∨ ¬q) ∧ (q ∨ ¬r) ∧(r ∨ ¬p)$,

  2. $(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)$, and

  3. $(p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)$ is satisfiable.

  4. $p,q,r$ 真时命题为真,因此可满足。

  5. 当 p 真, q 假时为真,因此可满足。

  6. 由于两个分命题($(p ∨ ¬q) ∧ (q ∨ ¬r) ∧(r ∨ ¬p)$$(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)$)不能同时为真,所以不可满足。

【例子】N 皇后问题:$n\times n$ 棋盘上,是否存在 $n$ 个皇后棋子都能分布在不同行、列和对角线的解?

image-20200407135242194

至于解法可以用回溯递归,这里不展开了。

逻辑运算符扩展

异或 XOR

异或判断输入和输出是否相同。相同输出 1,不同输出 0.

A B ${\displaystyle Y=A\oplus B}$
0 0 0
0 1 1
1 0 1
1 1 0

与非 NAND

与非就是合取串上非。所以,它起到的作用就是判断是否输入两个 1,是则输出 0,不是则输出 1.

发表评论

电子邮件地址不会被公开。 必填项已用*标注