2.2 用0和1与逻辑表达计算
2.2.1 基本逻辑运算：与、或、非、异或
符号化计算化示例：逻辑
生活中处处体现着逻辑。所谓逻辑是指事物因果之间所遵循的规律，是现实中普适的思维方式。逻辑的基本表现形式是命题与推理。命题由语句表述，即由一语句表达的内容为“真”或为“假”的一个判断！
例如：
命题1——罗素不是一位小说家。
命题2——罗素是哲学家。
命题3——罗素不是一位小说家并且罗素是哲学家。
推理即依据由简单命题的判断推导得出复杂命题的判断结论的过程。
命题与推理也可以符号化。例如，如果命题1用符号X表示，命题2用符号Y表示，X和Y为两个基本命题，则Z = (X AND Y) OR ((NOT X) AND (NOT Y))便是结果亦为“真”或“假”的一个复杂的命题。复杂命题的推理可被认为是关于命题的一组逻辑运算的过程。示例中出现的逻辑运算定义如下：
一个命题由X,Y,Z等表示，其值可能为“真”（符号化为TRUE）或为“假”（符号化为FALSE）。两个命题X,Y之间可以进行X AND Y,X OR Y,NOT X,X XOR Y等运算，分别称为“与”“或”“非”“异或 ”运算。运算规则如下。
AND：当X和Y都为真时，X AND Y也为真；其他情况，X AND Y均为假。
OR：当X和Y都为假时，X OR Y也为假；其他情况，X OR Y均为真。
NOT：当X为真时，NOT X为假；当X为假时，NOT X为真。
XOR：当X和Y都为真或都为假时，X XOR Y为假；否则，X XOR Y为真。
表2.2中列出了4种逻辑运算的结果。
表2.2 4种逻辑运算的运算结果对比表
下面再看一个利用逻辑运算推理的示例。
示例11 在一次学生测验中，有3位老师做了预测：A.有人及格；B.有人不及格；C.全班都不及格。在考试后证明只有一位老师的预测是对的，请问谁对谁错？
解：该题有3个命题，需要通过3个命题的关系来判断命题的真假。
命题A——“有人及格”。
命题B——“有人不及格”。
命题C——“全班都不及格”。
从3个命题的关系中，可获得如下命题（结果是可以确定的）。
（1）如果A真，则C假；如果C真，则A假；二者有一成立。
（2）如果B真，而A和 C可能有一个为真（由（1）给出），则与题只有一个为真矛盾。
（3）如果B假，则“全班都及格”为真，即C为假。
由上推断：A为真。
上述示例也可以进行符号化求解，如下所示。
已知：
((A AND (NOT C)) OR ((NOT A) AND C)) = TRUE
(NOT B) AND ((A AND (NOT C)) OR ((NOT A) AND C))) = TRUE
(NOT B) AND (NOT C) = TRUE
组合A,B,C形成所有可能解：
{<A= TRUE, B=FALSE, C= FALSE >,
<A= FALSE, B= TRUE, C= FALSE >,
<A= FALSE, B= FALSE, C= TRUE > }
将上述可能解分别代入已知条件，能够使所有已知条件都满足的便是问题的解。不难得出结果，问题的解为<A= TRUE, B= FALSE, C= FALSE >。
2.2.2 基于0和1表达的逻辑运算
现实中的命题判断与推理（真/假）以及数学中的逻辑均可以用0和1来表达与处理。
如0表示“假”,1表示“真”，则前述各种逻辑运算可转变为0和1之间的逻辑运算，如图2.7所示。既然0和1能表示逻辑运算，那么逻辑推理也就能被计算机处理。
简单记忆如下：假设X和Y都是1位的二进制数。
AND：有0为0，全1为1。即两个操作数X、Y只要有0出现，则X AND Y结果为0；两个操作数X、Y全为1，则X AND Y结果为1。
OR：有1为1，全0为0。即两个操作数X、Y只要有1出现，则X OR Y结果为1；两个操作数X、Y全为0，则X OR Y结果为0。
图2.7 0和1表达的逻辑运算示意
NOT：非1为0，非0为1。即当X为1时，NOT X为0；当X为0时，NOT X为1。
XOR：相同为0，不同为1。即两个操作数X、Y相同时，则X XOR Y结果为0；两个操作数X、Y不同时，则X XOR Y结果为1。
示例12 按位操作的逻辑运算示例。
按位操作的逻辑运算示例如图2.8所示。能看出它们有什么作用吗？请在2.2.3小节中找答案。
图2.8 按位操作的逻辑运算示例
2.2.3 习与练：应用逻辑运算表达复杂计算关系
示例13 一家商店被盗，经调查可以肯定是甲、乙、丙、丁中的某一个人所为。审讯中，甲说：“我不是罪犯。”乙说：“丁是罪犯。”丙说：“乙是罪犯。”丁说：“我不是罪犯。”
经调查证实4个人中只有一个说的是真话。问：罪犯是谁，谁说了真话。
解：分4步进行求解。
（1）符号化。用A、B、C、D表示甲、乙、丙、丁4个人，如果值为1，表示其是罪犯，值为0，则表示其不是罪犯。按已知条件，4个人中有一人是罪犯，因此 ABCD的可能解为{1000,0100,0010,0001}。
（2）用逻辑运算式表达4个人说的是真话还是假话。
如果甲说的是真话，则表达为(NOT A)，甲说的是假话，则表达为(NOT (NOT A))；
如果乙说的是真话，则表达为D，乙说的是假话，则表达为(NOT D)；
如果丙说的是真话，则表达为B，丙说的是假话，则表达为(NOT B)；
如果丁说的是真话，则表达为(NOT D)，丁说的是假话，则表达为(NOT (NOT D))。
（3）再用逻辑运算式表达“4个人中只有一个说的是真话”，因为只有一人说的是真话，所以如果该人说的是真话，则其他人说的就是假话。表达出来则是：
(NOT A) AND (NOT D) AND (NOT B) AND (NOT (NOT D)) = 1；
D AND (NOT (NOT A)) AND (NOT B) AND (NOT(NOT D)) = 1；
B AND (NOT (NOT A)) AND (NOT D) AND (NOT (NOT D)) = 1；
(NOT D) AND (NOT (NOT A)) AND (NOT D) AND (NOT B) = 1；
按已知条件，以上4个表达式只有一个成立。
（4）将ABCD的可能解一一代入上面4个表达式，如表2.3所示。
表2.3 示例13 ABCD的可能解代入结果
可以看出，当ABCD=1000时，满足只有一个表达式成立的条件。
故可知，甲是罪犯，丁说的是真话，其他人说的是假话。
示例14 示例13中，如果经调查证实4个人中只有一个说的是假话。问：罪犯是谁，谁说了假话。
解：（1）再用逻辑运算式表达“4个人中只有一个说的是假话”，因为只有一人说的是假话，所以如果该人说的是假话，则其他人说的就是真话。表达出来则是：
(NOT (NOT A)) AND D AND B AND (NOT D) = 1；
(NOT A) AND (NOT D) AND B AND (NOT D) = 1；
(NOT A) AND D AND (NOT B) AND (NOT D) = 1；
(NOT A) AND D AND B AND (NOT (NOT D)) = 1；
按已知条件，只有一个表达式成立。
（2）将ABCD的可能解一一代入上面4个表达式，如表2.4所示。
表2.4 示例14 ABCD的可能解代入结果
可以看出，当ABCD=0100时，满足①～④只有一个表达式成立的条件。
故可知，乙是罪犯，B说的是假话，其他人说的是真话。
示例15 如何判断一个字节中第i位为1或0？假设该字节信息为10001111，如何判断第4位（自右向左）是1还是0？
答：此时可将该字节信息和一个00001000进行与运算，如果结果是全0（逻辑“假”），则该位为0，否则该位为1，如图2.9所示。
图2.9 示例15判断方法
小知识
在计算机中，有两种类型的逻辑运算需要区分：“位操作形式的逻辑运算”和“值操作形式的逻辑运算”。如何理解呢？这取决于如何表示“真”“假”。如果X是一个m位的二进制数，X的m位全0时为假，而X的m位非全0时则为真，此时是以X的值来表示真或假。假设X和Y都是以值来表示真或假，则X和Y可在值的层面运用逻辑运算，此时可被认为是值操作形式的逻辑运算。如果X和Y是两个m位的二进制数，分别将X和Y的m位逐位应用逻辑运算得到运算结果，则此时可被认为是位操作形式的逻辑运算。
示例16 如何将一个字节中第i位设为1或设为0？假设该字节信息为10001111，如何将第4位（自右向左）设为1或者设为0？
答：此时可将该字节信息和一个00001000进行“或”运算，便可将该字节的第4位设为1。而如果将该字节信息和一个11110111进行“与”运算，便可将该字节的第4位设为0，如图2.10所示。
图2.10 示例16求解方法
示例17 如何将一个字节中的多位设为1或设为0？假设该字节信息为10001111，如何将第4位（自右向左）和第8设为1或者设为0？
答：此时可将该字节信息和一个10001000进行“或”运算，便可将该字节的第4位和第8位设为1。而如果将该字节信息和一个01110111进行“与”运算，便可将该字节的第4位和第8位设为0，如图2.11所示。
图2.11 示例17求解方法
示例18 证明 X XOR Y = ((NOT X) AND Y) OR (X AND (NOT Y))。
证明：本题可用“穷举法”证明。将X,Y的所有可能组合出的输入分别代入到左右两边的式子中，如果得到完全相同的输出，则说明两边是等价的。可作一个表，如表2.5所示，这是能填写出来的。由表2.5可以看出左式和右式是等价的。
表2.5 用穷举法证明X XOR Y = ((NOT X) AND Y) OR (X AND (NOTY))
小知识
古希腊哲学家 Aristotle（亚里士多德，公元前384年—322年）提出了关于逻辑的一些基本规律，如矛盾律、排中律、统一律和充足理由律等，其最著名的理论是“三段论法”和“演绎法”，即最基本的形式逻辑。德国数学家Leibnitz（莱布尼茨，1646年—1716年）把形式逻辑符号化，从而能对人的思维进行运算和推理，引出了数理逻辑。英国数学家Boole（布尔，1815年—1864年）提出了布尔代数——一种基于二进制逻辑的代数系统，现在通常所说的布尔量、布尔值、布尔运算、布尔操作等，均是为了纪念他所做的伟大贡献。目前，关于逻辑的研究有很多，如时序逻辑（Temporal Logics）、模态逻辑（Modal Logics）、归纳逻辑（Inductive Logics）、模糊逻辑（Fuzzy Logics）、粗糙逻辑（Rough Logics）、非单调逻辑等。这些内容，读者可查阅相关资料学习。