高中数学扩展/逻辑/习题集/解答

高中数学扩展

---

补充章节 — 素数和模算术 — 逻辑

数学证明 — 集合论和无限过程 — 计数和生成函数 — 离散概率

矩阵 — 进一步模算术 — 数学规划 — 马尔可夫链

逻辑习题集练习

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)