高中數學擴充套件/邏輯/習題集/解答

高中數學擴充套件

---

補充章節 — 素數和模算術 — 邏輯

數學證明 — 集合論和無限過程 — 計數和生成函式 — 離散機率

矩陣 — 進一步模算術 — 數學規劃 — 馬爾可夫鏈

邏輯習題集練習

1.

$x'\Rightarrow y'=x+y'$

$y\Rightarrow x=y'+x=x+y'$

因此，這些陳述是相同的

2.

$(x\Leftrightarrow y)\Rightarrow z=$

$(x\Leftrightarrow y)'+z=$

$(x'+y)'+z=$

$xy'+z$

3.

a. $(\forall x)(x^{2}=9\Rightarrow x^{2}-6x-3=0)$

x² = 9 表示 x 可以是 3

3² - 6*3 - 3 = 0 為假

因此該句子為假

b.$(\exists x)((x^{2}=9)\times (x^{2}-6x-3=0))$

為了使該方程為假，我們需要一個 x 使 x²=9 和 x² - 6x - 3 = 0 同時為假。

使 x²=9 為真的 x 值為 x=3 和 x=-3

使 x² - 6x - 3 = 0 為真的 x 值為 $x=2{\sqrt {3}}+3{\mbox{ and }}x=-2{\sqrt {3}}+3$

由於所有 x 值都不相同，因此不存在任何使該語句為真的數字。

4. (該解決方案來自湯姆·蘭姆)。令 (x+y)w+z = a NAND b，其中 a 和 b 可以是 x、y、w、z 中的任何一個，或者另一個 NAND 運算子。

$(x+y)w+z=(ab)'$

$(x+y)w+z=a'+b'$

因此 $a=[(x+y)w]'$ 和 $b=z'$，都需要進一步的 NAND 運算子。令 a = c NAND d，並令 b = e NAND f。

$(x+y)w+z={(cd)'}^{'}+{(ef)'}^{'}$

$(x+y)w+z=cd+ef$

因此 d=w, e=f=z,c=x+y。令 c = g NAND h。

$x+y=(gh)'$

$x+y=g'+h'$

現在 g=x' 且 h=y'，我們仍然需要更多 NAND 運算子。令 g = i NAND j 並令 h = k NAND l。

$(ij)'=x'$ $x=ij$ $(kl)'=y'$ $kl=y$

因此， i=j=x 且 k=l=y。

現在將所有變數代回，你應該得到: (x+y)w+z={[(x NAND x) NAND (y NAND y)] NAND w} NAND (z NAND z)

另一種方法 AND、OR 和 NOT 都可以用 NAND 表示。因此，任何布林表示式都可以完全用 NAND 表示。這種性質被稱為 NAND 的普遍性。請記住 x NAND y = (xy)'

首先，

NOT x = x' = x'x' = (xx)' = x NAND x

同樣，

x OR y = x + y = (x'y')' = (x NAND x) NAND (y NAND y)

還有

x AND y = xy = (xy)' ' = (x NAND y) NAND (x NAND y)

現在

(x + y)w = ((x NAND x) NAND (y NAND y)) NAND w

所以

(x + y)w + z = ((((x NAND x) NAND (y NAND y)) NAND w) NAND (((x NAND x) NAND (y NAND y)) NAND w)) NAND (z NAND z)