《概率论沉思录》翻译1.6节
推荐豆瓣的TEX公式插件：http://www.douban.com/note/146062725/
以及Chrome插件math everywhere: https://www.douban.com/note/154867225/ =====================
时隔N年的继续翻译。前篇请见：
《概率论沉思录》翻译（4） --------------------------------------------下面是翻译的分割线---------------------------------- 1.6 适合运算的集合 我们注意到演绎逻辑的一些特点，这些特点这样生成的新条件的类有多大？它是无限的吗，还是关于这些运算的有限闭集？每个由A和B定义的条件都可以这样表示吗，还是需要一些其他的运算？或者这四种运算是互相重复的，所以可以去除一些？能够生成这些A和B的“逻辑函数”的最小操作的集合是什么？如果初始条件不是A和B，而是任意数量的${A_1,A_2,…,A_n}$，这些运算还能生成所有关于${A_1,A_2,…,A_n}$的逻辑函数吗？ 这些问题都很容易回答，而它们的答案对于逻辑学、概率论和计算机设计都很有用。广义地说，我们问的是，从我们当前有利的位置出发，我们是否可以：1） 增加函数的数量；2）减少运算的数量。第一个问题可以作如下简化：我们注意到，两个条件以(1.15)的形式写出来可能截然不同，但从逻辑角度来讲，如果它们的值都为真的话，它们并非不同的条件。例如，留待读者证明，(1.15)中的$C$和隐含条件$C=(B\Longrightarrow \bar{A})$在逻辑上是相同的陈述。 由于我们在这一阶段，仅将我们的注意力限制在亚里士多德条件上，亦即任何诸如（1.15）的逻辑函数$C=f(A,B)$只有两个可能“值”，真或假；同样的，“独立变量”$A$和$B$也只能取这两个值。 此时，一个逻辑学家可能会反对我们的定义，认为符号$A$的定义代表某些固定条件，其值不能改变；如果我们希望考虑逻辑函数，那么与其写成$C=f(A,B)$，我们应该引入新的符号并写成$z=f(x,y)$，其中$x,y,z$是“陈述变量”，用以替代不同特定的陈述$A,B,C$。但是如果$A$代表某些固定的但不特定的条件，那么它仍然可以为真或假。我们能够理解，不管怎么定义$A,B$，类似于（1.15）的式子采取某些灵活性，因此可以采取一定的灵活性；例如，与其采取陈述变量，我们使用变量陈述。 和形式$C=f(A,B)$联系起来，我们关注定义在离散空间$S$上的逻辑函数，该空间只有$2^2=4$个点；相应的，$A$和$B$在这些点上各自取值$\{TT,TF,FT,FF\}$；并且在每点上，函数$f(A,B)$只能独立地取两个值$\{T,F\}$。因此，只有确切的$2^4=16$种不同的逻辑函数$f(A,B)$，再无其他。包含$n$个条件的表达式$B=f(A_1,...,A_n)$是$M=2^n$个点构成的空间$S$的逻辑函数；该空间上确切只有$2^M$个函数。 当$n=1$时，有4个逻辑函数$\{f_1(A),f_2(A),f_3(A),f_4(A)\}$，我们可以用列举定义，在真值表中写岀它们所有可能的值： --------------------------------- A | T | F $f_1(A)$ | $T$ | $T$ $f_2(A)$ | $T$ | $F$ $f_3(A)$ | $F$ | $T$ $f_4(A)$ | $F$ | $F$ -------------------------------------- 但很显然，上表只不过是： $f_1(A)=A+\bar{A}$ $f_2(A)=A \qquad (1.16)$ $f_3(A)=\bar{A}$ $f_4(A)=A\bar{A}$ 因此我们通过列举证明，这三种操作：与，或和非足够对单一条件产生所有的逻辑函数。 对于一般情况$n$来说，首先考虑特殊函数，每个都在S的一点且仅在一点上为真。对于$n=2$有$2^n=4$个函数 -------------------------------------------------------------------------------------------------- $A,B$ | $TT$ | TF | FT | FF $f_1(A,B)$ | $T$ | $F$ | $F$ | $F$ $f_2(A,B)$ | $F$ | $T$ | $F$ | $F$ $f_3(A,B)$ | $F$ | $F$ | $T$ | $F$ $f_4(A,B)$ | $F$ | $F$ | $F$ | $T$ ------------------------------------------------------------------------------------------------------- 显然这些也只是如下四种基本与运算 $$f_1(A,B)=AB$$ $f_2(A,B)=A\bar{B} \qquad (1.17)$ $f_3(A,B)=\bar{A}B$ $f_4(A,B)=\bar{A}\bar{B}$ 考虑任意逻辑函数，其在S上某些特定点取真值；例如，$f_5(A,B)$和$f_6(A,B)$,定义为 -------------------------------------------------------------------------------------------------- $A,B$ | $TT$ | TF | FT | FF $f_5(A,B)$ | $F$ | $T$ | $F$ | $T$ $f_6(A,B)$ | $T$ | $F$ | $T$ | $T$ ------------------------------------------------------------------------------------------------------- 我们断言以上函数都是（1.17）中在同样点上取真值的与操作的逻辑和（这并不显然；读者们应当仔细证明）。这样 $f_5(A,B)=f_2(A,B)+f_4(A,B)=A\bar{B}+\bar{A}\bar{B}=(A+\bar{A})\bar{B}=\bar{B}$ (1.18) 类似的 $f_6(A,B)=f_1(A,B)+f_3(A,B)+f_4(A,B)=AB+\bar{A}B+\bar{A}\bar{B}=B+\bar{A}\bar{B}=\bar{A}+B$ (1.19) 个，$f_6(A,B)$即隐含$f_6(A,B)=(A\Longrightarrow B)$，其真值表已在上面讨论过。任何在S上至少一点取真值的逻辑函数$f(A,B)$可以由这种方式重建，作为（1.17）的基本与操作的逻辑和。这样有$2^4-1=15$种函数。对于剩下的一个函数，在所有点上都是假的，只用取反就可以了，$f_{16}(A,B)\equiv A\bar{A}$。 这种方法（在逻辑教材中称为“归约析取范式”——是这样翻译吗？）对许多$n$生效。例如，当$n=5$时，有$2^5=32$种基本与运算： $\{ABCDE,ABCD\bar{E},ABC\bar{D}E,...,\bar{A}\bar{B}\bar{C}\bar{D}\bar{E}\}$ (1.20) 以及$2^32=4294967296$种逻辑函数$f_i(A,B,C,D,E)$；其中4294967295种可以被写成基本与运算的逻辑和形式，剩下唯一的反运算： $f_{4294967296}(A,B,C,D,E)=A\bar{A}$ (1.21) 这样我们可以通过“思维构造”来确认这三种运算 {与，或，非} {AND, OR, NOT} (1.22) 足以生成所有的逻辑函数；或者，更为精确的，它们构成一个充分集。 对偶性质（1.12）表明一个较小的集合已经足够；A和B的与运算和否认它们都为假的性质一样： $A+B=\bar{\bar{A}\bar{B}}$ (1.23) 因此，（AND,NOT）这两个运算足以为推演逻辑构成一个充分集。等到我们未来决定，我们关于合理质疑的规则是否构成一个充分集时，这个事实将会很重要；请见第2章。 很显然我们并不能丢掉这些运算的其中之一，然后只保留另一个；比如，“AND”操作并不能被简化为“逻辑非”；而逻辑非并不能被任意数量的“AND”操作所构成。但这仍然有疑问，即“逻辑与”和“逻辑非”都有可能被简化为某种尚未引入的他类运算，这样一个单纯的逻辑运算便可构成一个充分集。
令人惊奇而愉悦的是，这种操作不但存在，而且还存在两个。“与非（NAND）”操作被定义为“AND”操作的非：
$$A\uparrow B\equiv \overline{AB}=\overline{A}+\overline{B}$$ (1.24)
我们可以把它读成“A与非B”。但我们立即就有了：
$$\overline{A}=A\uparrow A$$
$$AB=(A\uparrow B)\uparrow (A\uparrow B)$$
$$A+B=(A\uparrow B)\uparrow(B\uparrow B)$$ (1.25)
因此，每个逻辑函数可以单独被“与非”操作构造。类似的，逻辑“或非”可以被定义成：
$$A\downarrow B\equiv \overline{A+B}=\overline{A}\overline{B}$$ (1.26)
且“或非”操作足够强大，可以定义其他所有的逻辑函数：
$$\overline{A}=A\downarrow A$$
$$A+B=(A\downarrow B)\downarrow (A\downarrow B)$$
$$AB=(A\downarrow B)\downarrow (B\downarrow B)$$ (1.27)
我们可以利用这种优势来设计计算机和逻辑电路。一个“逻辑门”是一个电路，它除了公共回路（common ground）之外，还有两个接入端口和一个输出端口。和任何一个回路端口相关的电压只能有两个值：+3伏特，或者“向上”，代表“真”；以及0伏特或者“向下”，代表“假”。一个“与非”门就是这样一个逻辑门，它的输出端口为“向上”当且仅当至少一个输入端口为“向下”；或者，换个说法，输出端口为“向下”，当且仅当两个输入端口同时为“向上”；而“或非”门输出为“向上”，当且仅当两个输入端口同时为“向下”。
逻辑电路的一个标准元件为“四路与非门（quad NAND）”，一个有四个独立与非门的半导体集成芯片电路。只要这种元件的数量足够，不需要其它电路元件，就可以利用它们不同的连接方式，来产生任意需要的逻辑函数。
以上对演绎逻辑（deductive logic）的简单介绍，足以满足本书需要了。深入理论可以在许多教科书中找到：比如，Copi对于亚里士多德逻辑的现代演绎（1994）。对于非亚里士多德形式，比如关于哥德尔完备性、可计算性（computability）、决定论（decidability）、图灵机，等等，可见Hamilton（1988）。
接下来我们谈论一些条件，以此为基础扩展逻辑。我们把这些条件称之为“必备（desiderata）”而不是公理，因为它们并不能决定哪些东西是“真”，而仅仅是陈述哪些看起来像是可追求的目标。至于这些目标是否可以达成（且找不到反例），以及它们是否能决定某种特殊形式的逻辑延展，则是数学分析的范畴了，详见第二章。
