布尔代数

布尔代数是代数的一个分支，其中的变量和常数的值正好有两个：真和假，通常分别表示为1和0。

内容
1 运算符
2 为什么布尔代数对ACSL学生很重要？
3 法则
3.1 先后次序
3.2 基本特征
4 示例问题
4.1 问题1：简化表达式
4.2 问题2：寻找解决方案
5 在线资源
5.1 网站
5.2 视频

运算符
布尔代数的基本运算符是AND, OR, 和NOT。次要的运算符是eXclusive OR（通常称为XOR）和eXclusive NOR（XNOR，有时称为等价）。它们是次要的，因为它们可以由基本运算符组成。

两个值的AND只有在两个值都是真的时候才是真的。它被写成xy或x⋅y。所有可能的输入的和的值显示在下面的真值表中。

image.png

x y xy
0 0 0
0 1 0
1 0 0
1 1 1

只要其中一个或两个值都是真的，两个值的OR就是真的。它被写成x+y。所有可能的输入的or值显示在下面的真值表中。
x y x+y
0 0 0
0 1 1
1 0 1
1 1 1

一个值的NOT是它的反面；也就是说，一个真值的NOT是假的，而一个假值的NOT是真的。它被写成x¯¯或¬x。所有可能的输入的not值显示在下面的真值表中。
x x¯¯
0 1
1 0
两个值的XOR是真的，只要这两个值是不同的。它使用⊕运算符，并且可以从基本运算符中建立。x⊕y=xy¯¯+x¯¯y 对于所有可能的输入，xor的值显示在下面的真值表中。
x y x⊕y
0 0 0
0 1 1
1 0 1
1 1 0

两个数值的XNOR在数值相同时为真。它是XOR函数的NOT。它使用⊙运算符：x⊙y=x⊕y¯。xnor可以由基本运算符建立。x⊙y= xy + x¯¯y¯¯ 对于所有可能的输入，xnor的值显示在以下真值表中。
x y x⊙y
0 0 1
0 1 0
1 0 0
1 1 1

就像代数有简化和评估表达式的基本规则一样，布尔代数也有。

为什么布尔代数对ACSL的学生很重要？
布尔代数对程序员、计算机科学家和普通人都很重要。

对于程序员来说，布尔表达式用于条件反射和循环。例如，下面这段代码对不是3的倍数的偶数进行求和，当和达到100时停止。

s = 0
x = 1
while (s < 100):
    if (x % 2 == 0) 和 (x % 3 != 0)
        else s = s + x
    x = x + 1

条件语句s < 100和布尔表达式的2个条件语句(x % 2 == 0)和(x % 3 != 0)都会评估为真或假。

对于计算机科学家来说，布尔代数是构成计算机硬件的数字电路的基础。数字电子学类别涉及一个电路的图形表示。该电路通常是最容易理解和评估的，将其转换为布尔代数表示。

一般人在互联网搜索引擎中输入搜索词时，都会使用布尔代数，而他们可能并不知道自己正在这样做。例如，搜索表达式jaguar speed -car被搜索引擎解析为布尔表达式 "jaguar "和 "car"，而不是 "speed"；它返回有关jaguar动物速度的网页，而不是jaguar汽车。

定律
布尔代数的定律是两个布尔项之间的同一性，如x+(y+z)=(x+y)+z，其中布尔项被定义为由变量、常数0和1，以及运算和、或、非、xor和xnor构成的表达式。

像普通的代数一样，小括号被用来分组术语。当 "不 "用高架横线表示时，横线下的项就隐含了一个分组。也就是说，x⋅y+z¯¯ 被评估为写成x⋅(y+z)¯¯

优先权的顺序
操作符的优先级顺序是：不是；然后是and；然后是xor和xnor；最后是or。具有相同优先级的运算符从左到右进行计算。

基本特征
交换律--两个独立项的应用顺序并不重要，x+y=y+x x⋅y=y⋅x
关联法则--在一个表达式中重新组合项并不改变表达式的值。
(x+y)+z=x+(y+z) x⋅(y⋅z)=(x⋅y)⋅z

同位素定律--一个与自身或'或'和'的项等于该项。
消灭定律--与1相接的项为1；与0相接的项为0。
相同法则--一个被0或与1相配的项总是等于该项。
补码法则--一个被补码的项等于1，一个被补码的项等于0。
吸收法 - 复杂的表达式可以通过吸收同类项而简化为简单的表达式。
x+xy=x

x+x¯¯y=x+y

x(x+y)=x

分布式定律--可以用乘法或因数--来计算。
分布式定律--将一个表达式相乘或因式分解是可以的。
x⋅(y+z)=xy+xz

(x+y)⋅(p+q)=xp+xq+yp+yq

(x+y)(x+z)=x+yz

DeMorgan定律--一个被否定的或（和）表达式等于每个项的否定的和（或）。
x+y¯¯=x¯¯⋅y¯¯ x⋅y¯¯=x¯¯+y¯¯

双重否定--被颠倒两次的项等于原来的项。x¯ ¯=x
XOR和XNOR的关系 x⊙y=x⊕y¯ =x⊕y¯¯=x¯¯⊕y

样本问题
这类问题的典型形式是 "给定一个布尔表达式，尽可能地简化它 "或 "给定一个布尔表达式，找出所有可能的输入值，使表达式为真"。简化意味着用最少的运算符写出一个等价的表达式。

问题1：简化表达式
问题：尽可能地简化以下表达式。
A(A+B)¯¯¯+BA¯¯¯

解决方案。

简化的过程如下。

A(A+B)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯+BA¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
=(A(A+B)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯)⋅(BA¯¯¯¯¯¯¯¯¯¯¯¯) (德摩根法则)
=(A(A+B))⋅(B¯¯¯¯+A¯¯¯¯¯¯¯¯) (双重否定；DeMorgan定律)
=A⋅(B¯¯¯¯+A)(吸收；双重否定)
=A(吸收)
问题2：寻找解决方案
问题：找出使下列表达式为真的所有顺序对（A,B）：(A+B)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯+A¯¯¯¯B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

解决方案。

通常有两种方法来解决这类问题。一种方法是尽可能地简化表达式，直到显而易见地找到解决方案。另一种方法是为所有可能的输入创建一个真值表，并为每个子表达式设置列。

简化的方法如下。

(A+B)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯+A¯¯¯¯B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
=A+B¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯⋅A¯¯¯¯B¯¯¯¯¯¯¯¯
=(A+B)⋅(A¯¯¯¯¯¯¯¯+B¯¯¯¯)
=(A+B)⋅(A+B¯¯¯¯)
=AA+AB¯¯¯¯+BA+BB¯¯¯¯
=A+A(B¯¯¯¯+B)+0
=A+A(1)
=A+A
=A
这意味着只要A为真，所有输入都有效：(1,0)和(1,1)

真值表的方法如下。每一列是对另外两列进行基本运算的结果。

1 #2 #3 #4 #5 #6 #7 #8

第1列、第2列的OR 第3列的NOT 第1列的ADD 第1列、第2列的OR 第4列、第6列的NOT 第7列的OR
a b a+b a+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯ a¯¯¯¯ a¯¯¯¯b a+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯+a¯¯¯¯b a+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯+a¯¯¯¯b¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
0 0 0 1 1 0 1 0
0 1 1 0 1 1 1 0
1 0 1 0 0 0 0 1
1 1 1 0 0 0 0 1
最右边的一列是我们要解决的表达式；对于第3和第4行，输入是(1,0)和(1,1)，它是真的。

在线资源
网站
Ryan's Tutorials的一部分是关于布尔代数的一个很好的在线教程。有许多在线布尔计算器。这个给出了真值表的计算器。这个有广告的链接也简化了NOT计算器，并使用了！。

视频
下面的YouTube视频显示了ACSL的学生和顾问在解决以前的一些问题。要访问带有视频的YouTube页面，请点击图标中的视频标题。(你也可以通过点击图片中间的箭头直接播放视频；但是，你可能想在更大的范围内观看视频，因为它包含在白板上的书写。) 有些视频包含广告；ACSL对这些广告不负责任，也不接受任何形式的广告补偿。