. (1.15)
1.6 一组恰当的运算
我们注意在设计我们机器人时需要的演绎逻辑的一些特性。 我们定义了四种运算，即“连接词”，可以从命题A和B开始出发定义其他命题：逻辑积或交接AB，逻辑和或并接A+B，蕴涵， 和取反.通过以各种可能的方式反复地组合这些操作，可以生成任意数量的新命题，例如
那么我们就会有很多问题了：这样产生的新命题有多少个？它是无限的，还是一个有限集合？从A和B所延伸出来命题都可以用这四个操作定义?还是需要更多的操作？甚或四个太多了,可以去掉一些？足以产生A和B的所有这些“逻辑函数”的最小的一组操作是什么？如果起始命题不止A和B而是任意个，这些操作是否仍然可以生成的所有可能的逻辑函数？
所有这些问题都很容易回答，而且其结果对于逻辑学，概率论和计算机设计都有用处。一般而言，我们正在问，从目前的高度来看，我们可以（1）增加函数的数量，（2）减少操作的数量。第一个问题可以被简化，因为注意到两个命题虽然在以（1.15）的方式写出时可能完全不同，但如果它们具有相同的真值，则从逻辑的角度来看并不是不同的命题。例如，读者可以确认（1.15）中的C在逻辑上与蕴含C =（B⇒!A）的语句相同。
因为在这个阶段，我们把注意力集中在亚里士多德命题上，所以任何逻辑函数C = f（A，B）（如（1.15））都只有两个可能的“值”，即真和假;同样，“自变量”A和B也只能取这两个值。
在这一点上，一个逻辑学家可能反对我们的符号表示方法，说符号A已经被定义为一个固定的命题，其真值不能改变;所以如果我们想考虑逻辑函数，那么我们不应该写C = f（A，B），而应该引入新的符号，并写成z = f（x，y），其中x，y，z是'陈述变量',即可替换成任何具体的陈述A，B，C。但是，如果A代表一些固定但未明确指定的命题，那么它仍然可以是真或假。对于(1.15)这样的等式,我们仅仅将其理解为对所有指定的A和B可以为真,就可以达到上述的灵活性,即我们使用一个可变的语句而不是一个语句变量。
本节人译到此
在C=f（A，B）形式的关系中，我们关注的是在离散的“空间”S上定义的逻辑函数，它由只有 = 4个点组成;即A和B分别取值为{TT，TF，FT，FF},并且在每个点上，函数f(A,B)可以独立地取两个值{T，F}中的任一个。因此，正好有个不同的逻辑函数f(A,B)。涉及n个命题的表达式是个点的空间S上的逻辑函数,而且正好有这样的函数。
对于n=1的情况,有四个逻辑函数,可以全部枚举在下面的真值表中:
| A | T | F | (A) |
|---|---|---|---|
T |
T |
(A) |
T |
F |
(A) |
F |
T |
仔细审视之后即
(1.16)
因此通过枚举可以证明和,交,反三个运算可以产生单个命题的所有逻辑函数.
对于通用情况n来说, 考虑第一个特殊函数,每个命题都为真的情况,这个函数唯一占据了空间S的一个点.对n=2,共有个函数,
| A,B | TT | TF | FT | FF |
|---|---|---|---|---|
T |
F |
F |
F |
|
F |
T |
F |
F |
|
F |
F |
T |
F |
|
F |
F |
F |
T |
仔细审查后不难发现是4个交运算,
(1.17)
现在考虑任一逻辑函数,其在S的某个点上为真,例如和定义如下
| A,B | TT | TF | FT | FF |
|---|---|---|---|---|
F |
T |
F |
T |
|
T |
F |
T |
T |
我们可以验证这些函数都是对(1.17)在S中同一个点求和的结果(这并非显而易见,读者可自行验证).因此,
(1.18)
同样有,
(1.19)
即是蕴涵操作,, 真值表如上.在S中的任一点上为真的逻辑函数f(A,B)都可以用上面的方式对(1.17)求和来得到.共有个这种函数.剩下的函数即全为假,只要取反就可以了,.
这种方法(在逻辑学中被称为"解析为正交范式")对任何n都有效.例如当n=5有个基本的交的方式,
(1.20)
有个不同的逻辑函数,这4 294 967 295都可以写成基本的交表达式的求和,除了下面的一个
(1.21)
因此,通过上面的"构造",可以验证下面的三种运算
{conjunction, disjunction, negation}, i.e. {AND, OR, NOT}, (1.22)
足以生成所有可能的逻辑函数,或者更准确的说,这三种运算构成一个"有效集".
对偶律(1.12)意味着这个集合还可以更小,对命题A与B的析取操作等价于A且B都为假的否定:
. (1.23)
因此,两个运算(AND,NOT)就可以构成演绎推理的一个合理集.这个事实在判定合情推断的合理规则集时是必不可少的,可参见第二章.
注4 请您思考:这是否意味着对于编写计算机程序而言,这两个运算是唯一的运算集合?
显然我们不能去掉任何一个运算,而只保留另一个,AND运算不能被取反运算推导出来,而且取反也不能通过对任何个数的AND运算来得到.但是,还有一种可能性是存在某个尚未找到的单一运算,可以推导出取反和AND运算,然后仅此一个运算就足以构成一个有效集.
令人惊讶的是这种运算仅存在而且有2个.运算NAND定义为对AND取反:
(1.24)
可以读为‘A NAND B’. 则有
(1.25)
因而,每一个逻辑函数都可以仅仅用NAND构造出来. 相似的,运算NOR定义为
(1.26)
同样可以构造出所有的逻辑函数:
(1.27)
One can take advantage of this in designing computer and logic circuits. A ‘logic gate’ is a circuit having, besides a common ground, two input terminals and one output. The voltage relative to ground at any of these terminals can take on only two values; say +3 volts, or ‘up’, representing ‘true’; and 0 volts or ‘down’, representing ‘false’. A NAND gate is thus one whose output is up if and only if at least one of the inputs is down; or, what is the same thing, down if and only if both inputs are up; while for a NOR gate the output is up if and only if both inputs are down.
One of the standard components of logic circuits is the ‘quad NAND gate’, an integrated circuit containing four independent NAND gates on one semiconductor chip. Given a sufficient number of these and no other circuit components, it is possible to generate any required logic function by interconnecting them in various ways.
This short excursion into deductive logic is as far as we need go for our purposes. Further developments are given in many textbooks; for example, a modern treatment of Aristotelian logic is given by Copi (1994). For non-Aristotelian forms with special emphasis on G ̈odel incompleteness, computability, decidability, Turing machines, etc., see Hamilton (1988).
We turn now to our extension of logic, which is to follow from the conditions discussed next. We call them ‘desiderata’ rather than ‘axioms’ because they do not assert that anything is ‘true’ but only state what appear to be desirable goals. Whether these goals are attainable without contradictions, and whether they determine any unique extension of logic, are matters of mathematical analysis, given in Chapter 2.
在设计计算机和逻辑电路事,我们可以利用这一点。一个“逻辑门”是一个除了公共地之外还具有两个输入端子和一个输出端子的电路。相对于接地端的电压差只能取两个值,例如为+3伏或“开”，代表逻辑“真”,而0伏或“关”代表逻辑“假”。因此，当且仅当输入端中的至少一个输入端处于关状态时，与非门(NAND)才输出端为开,反之当且仅当这两个输入端都为开则输出为关.而对于一个或非门(NOR)来说，当且仅当两个输入都为关时输出为开。
逻辑电路的标准组件之一是“四与非门”，即一个半导体芯片上集成了四个独立的与非门的集成电路。只要这种电路的数量足够多,那么不需要其他任何电路元件，就可以以不同的方式将它们连接起来而产生任何所需的逻辑功能。
目前为止,简短的对演绎逻辑的了解,就足以来达成我们的目标。许多教科书对此都有进一步的展开。例如，Copi（1994）给出了亚里士多德逻辑的现代观点下的处理。对于非亚里士多德的形式，那些强调哥德尔不完备性，可计算性，可判定性，图灵机等价的其他形式，可参见Hamilton（1988）。
现在转向我们如何对逻辑进行扩展，从接下来要讨论的因素开始。我们称其为“基础原理”而不是“公理”，因为它们并不断言任何事情为 “真”，而是对我们最终目标的声明。这些目标不应互相矛盾，而且定义了一种逻辑的扩展，这些都将在第二章中给出相应的数学分析。