逻辑代数

在数学和数理逻辑中，逻辑代数（有时也称开关代数、布尔代数）是代数的一个分支，其变量的值仅为真和假两种真值（通常记作 1 和 0）。初等代数中变量的值是数字，而且主要的运算是加法、乘法和乘方（以及它们的逆运算），而逻辑代数的主要运算有合取与，记为∧；析取或，记为∨；否定非，记为¬ 。因此，它是以普通代数描述数字关系相同的方式来描述逻辑关系的形式主义。

逻辑代数是乔治·布尔（George Boole）在他的第一本书《逻辑的数学分析》（1847年）中引入的，并在他的《思想规律的研究》（1854年）中更充分的提出了逻辑代数。^[1] 根据Huntington“布尔代数”这个术语，最初是由Sheffer于1913年提出。^[2]

逻辑代数一直是数字电路设计的基础，并且所有现代编程语言提供支持。它也用在集合论和统计学中。 ^[3]

逻辑代数中的几个概念

参与逻辑运算的变量叫逻辑变量，用字母A，B……表示。每个变量的取值非0 即1。 0、1不表示数的大小，而是代表两种不同的逻辑状态。

正、负逻辑规定：

正逻辑体制规定：高电平为逻辑1，低电平为逻辑0。
负逻辑体制规定：低电平为逻辑1，高电平为逻辑0。

逻辑函数：如果有若干个逻辑变量（如A、B、C、D）按与、或、非三种基本运算组合在一起，得到一个表达式L。对逻辑变量的任意一组取值（如0000、0001、0010）L有唯一的值与之对应，则称L为逻辑函数。逻辑变量A、B、C、D的逻辑函数记为：L=f(A、B、C、D)

逻辑运算

基本运算

逻辑代数的基本运算如下。

与（合取），记作 x∧y（有时记作 x AND y 或 Kxy），在 x = y = 1 情况下，满足 x∧y = 1；其他情况下 x∧y = 0。
或（析取）, 记作 x∨y（有时记作 x OR y 或 Axy），在 x = y = 0 情况下，满足 x∨y = 0；其他情况下 x∨y = 1。
非（否定）, 记作 ¬x（有时记作 NOT x, Nx 或 !x），在 x = 1 情况下，满足 ¬x = 0；而在 ¬x = 1 情况下，x = 0。

如果把真值0和1解释为整数，这些运算可以表示为普通算数运算：

{\displaystyle \begin{align} x \wedge y & = x \times y \\ x \vee y & = x + y - (x \times y) \\ \neg x & = 1 - x \end{align} }

此外可以用制作真值表来表示 x∧y, x∨y 和 ¬x 的值：

$x$	$y$	$x \wedge y$	$x \vee y$
0	0	0	0
1	0	0	1
0	1	0	1
1	1	1	1

$x$	$\neg x$
0	1
1	0

有人可能会认为，只有否定和另外两种运算之一是基本的，因为用下列性质可以用逻辑否和逻辑或来定义逻辑与，反之亦然：

{\displaystyle \begin{align} x \wedge y & = \neg(\neg x \vee \neg y) \\ x \vee y & = \neg(\neg x \wedge \neg y) \end{align} }

衍生运算

上述三个逻辑运算被称为基本的，这意味着其他逻辑运算可以以它们为基础，由他们的复合来建立，即将这些运算组合或结合。下面是由基本运算构成的运算的例子：

x \rightarrow y = \neg{x} \vee y

x \oplus y = (x \vee y) \wedge \neg{(x \wedge y)}

x \equiv y = \neg{(x \oplus y)}

这些定义产生以下真值表，其中给出了对所有四个可能的输入，这些运算的值。

$x$	$y$	$x \rightarrow y$	$x \oplus y$	$x \equiv y$
0	0	1	0	1
1	0	0	1	0
0	1	1	1	0
1	1	1	0	1

第一种运算，x → y 或 Cxy，叫做实质蕴涵。如果 x 为真，则 x → y 的值就取自 y 的值。但如果 x 为假，则 y 可以忽略；然而此运算必须返回某种真值，而且只有两种选择，所以返回蕴含较小的值，即真。（相干逻辑通过看作非真非假的假前提的蕴含来处理这件事。）

第二种运算，x ⊕ y 或 Jxy，叫做异或（通常缩写为XOR）与逻辑或的区别在于逻辑或包含其类型。它排除了 x 和 y 同时为真的情形。用算术来定义就是加和之后 mod 2，就如 1 + 1 = 0.

第三种运算，异或的互补运算，是同或或逻辑等价：x ≡ y 或 Exy，当 x 与 y 值相同时为真。因此作为其互补运算，x ⊕ y 可以理解为 x ≠ y，当 x 和 y 不同时为真。它对应的 mod 2 算术为 x + y + 1。

给定两个操作数，每个具有两个可能的值，共有 2² = 4 种可能的输入组合。由于每种输出有两种可能值，一共有 2⁴ = 16种可能的二元逻辑运算。

运算律

两个主要的二元运算的符号定义为 $\land$ (逻辑与)和 $\lor$ (逻辑或)，把单一的一元运算的符号定义为 $\lnot$ (逻辑非)。我们还使用值 0 (逻辑假)和 1 (逻辑真)。逻辑代数有下列性质:

$a \lor (b \lor c) = (a \lor b) \lor c$	$a \land (b \land c) = (a \land b) \land c$	结合律
$a \lor b = b \lor a$	$a \land b = b \land a$	交换律
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	吸收律
$a \lor (b \land c) = (a \lor b) \land (a \lor c)$	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	分配律
$a \lor \lnot a = 1$	$a \land \lnot a = 0$	互补律
$a \lor a = a$	$a \land a = a$	幂等律
$a \lor 0 = a$	$a \land 1 = a$	有界律
$a \lor 1 = 1$	$a \land 0 = 0$	有界律
$\lnot 0 = 1$	$\lnot 1 = 0$	0 和 1 是互补的
$\lnot (a \lor b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \lor \lnot b$	对偶律
$\lnot \lnot a = a$		对合律

逻辑代数的基本规则

代入规则

任何一个含有变量 X 的等式，如果将所有出现 X 的位置，都代之以一个逻辑函数 F，此等式仍然成立。

对偶规则

设 F 是一个逻辑函数式，如果将 F 中的所有的 * 变成 +，+ 变成 *，0 变成 1，1 变成 0，而变量保持不变。那么就的得到了一个逻辑函数式 F'，这个 F' 就称为 F 的对偶式。如果两个逻辑函数 F 和 G 相等，则它们各自的对偶式 F' 和 G' 也相等。

反演规则

当已知一个逻辑函数 F，要求 ¬F 时，只要把 F 中的所有 * 变成 +，+ 变成 *，0 变成 1，1 变成 0，原变量变成反变量，反变量变成原变量，即得 ¬F。使用反演规则时要注意保持原函数中逻辑运算的优先顺序。

逻辑函数的标准形式

逻辑变量的逻辑与运算叫做与项，与项的逻辑或运算构成了逻辑函数的与或式，也叫做积之和式(SP form)。

逻辑变量的逻辑或运算叫做或项，或项的逻辑与运算构成了逻辑函数的或与式，也叫做和之积式(PS form)。

最小项

对于 n 个变量的逻辑函数而言，它的与项如果包含全部 n 个变量，即每个变量以原变量或反变量的形式出现一次且只出现一次，那么这个与项就称为该逻辑函数的最小项。

最大项

对于 n 个变量的逻辑函数而言，它的或项如果包含全部n 个变量，即每个变量以原变量或反变量的形式出现一次且只出现一次，那么这个或项就称为该逻辑函数的最大项。

逻辑函数的化简

运用逻辑代数的基本公式及规则可以对逻辑函数进行变换，从而得到表达式的最简形式。这里所谓的最简形式是指最简与或式或者是最简或与式，它们的判别标准有两条：(1)项数最少；(2)在项数最少的条件下，项内的文字最少。

卡诺图是遵循一定规律构成的。由于这些规律，使逻辑代数的许多特性在图形上得到形象而直观的体现，从而使它成为公式证明、函数化简的有力工具。

应用

计算机

20世纪早期，一些电子工程师领悟到逻辑代数很像某种电子电路的行为。香农在它1937年的论文中证明了这种行为与逻辑代数等价。

几乎所有现代通用计算机都用二值布尔逻辑做运算；也就是说它们的电路是二值布尔逻辑的物理表示。几种表示方式：导线上电压的高低，磁性存储设备中磁畴的方向，打孔卡或纸带上的洞，等等（但有些早期的计算机用了十进制电路或者机械，而不是二值逻辑电路）

当然，也可能在任意介质中编码进2个以上的符号。比如在导线上用0，1，2，3伏特去编码一种有4个符号的字符集，或者利用打孔卡的洞的不同大小。但实践上，在一个很小的、高速的、低功耗的电路中噪声是个关键因素。它使分辨多个可能出现的符号变得困难。所以电路设计者们选择了高、低2种电压而不是4种。

由于上面的原因计算机使用二值逻辑电路。最常见的计算机架构使用32或64个叫做比特的布尔值序列，比如01101000110101100101010101001011。当使用机器语言、汇编语言和某些高级语言时，程序员可以操作寄存器的数字结构。在寄存器中0电压表示逻辑0，参考电压（通常是+5伏或+3.3伏^[4]）表示逻辑1。这些语言同时支持数值操作和逻辑操作。这里的“数值操作”指计算机把比特序列当作二进制数字进行加减乘除等运算。“逻辑操作”指2个比特序列之间的与或非运算，序列中每一位都与另一序列中对应位进行运算。这两种操作之间的关键不同是前者有进位而后者没有。

参见

参考文献

↑ Boole, George. An Investigation of the Laws of Thought. Prometheus Books. 2003 [1854]. ISBN 978-1-59102-089-9.
↑ "The name Boolean algebra (or Boolean 'algebras') for the calculus originated by Boole, extended by Schröder, and perfected by Whitehead seems to have been first suggested by Sheffer, in 1913." E. V. Huntington, "New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia mathematica ", in Trans. Amer. Math. Soc. 35 (1933), 274-304; footnote, page 278.
↑ Givant, Steven; Halmos, Paul. Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer. 2009. ISBN 978-0-387-40293-2.
↑ Logic Levels - learn.sparkfun.com. learn.sparkfun.com. [2016-12-12].

[1] Boole, George. An Investigation of the Laws of Thought. Prometheus Books. 2003 [1854]. ISBN 978-1-59102-089-9.

[2] "The name Boolean algebra (or Boolean 'algebras') for the calculus originated by Boole, extended by Schröder, and perfected by Whitehead seems to have been first suggested by Sheffer, in 1913." E. V. Huntington, "New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia mathematica ", in Trans. Amer. Math. Soc. 35 (1933), 274-304; footnote, page 278.

[givhal-3] Givant, Steven; Halmos, Paul. Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer. 2009. ISBN 978-0-387-40293-2.

[4] Logic Levels - learn.sparkfun.com. learn.sparkfun.com. [2016-12-12].

[1]

[2]

[3]

[4]