布尔逻辑

维基百科，自由的百科全书

zh-cn:布尔;zh-hk:布林逻辑(zh-cn:台湾譯布林邏輯;zh-tw:大陸譯布尔逻辑)得名于 George Boole，他是 College Cork 大学的英国数学家，他在十九世纪中叶首次定义了逻辑的代数系统。现在，布尔逻辑在电子学、计算机硬件和软件中有很多应用。在 1937 年，Claude Shannon 展示了布尔逻辑如何在电子学中使用。

使用集合代数作为介绍布尔逻辑的一种方式。还使用文氏图来展示各种布尔逻辑陈述所描述的集合联系。

[编辑] 术语

文氏图，展示 A AND B (紫罗兰色)的集合交集，A OR B (所有着色区域)的集合并集，和 A XOR B 的集合(除了紫罗兰色的所有着色区域)。方框表示"全集"。

设 X 是一个集合:

元素是一个集合的成员。表示为 $\in$ 。如果它不是这个集合的元素，表示为 $\notin$ 。

全集是集合 X，有时表示为 1。注意使用全集这个词意味着"虑及的所有元素"，同"现有的所有元素"一样不是必然的。

空集或 null 集合是没有元素的集合，表示为 $\varnothing$ ，有时表示为 0。

一元算符应用于一个单一的集合。有一个一元算符叫做逻辑非(NOT)。它的作用是采用补集。

二元算符应用于两个集合。基本的二元算符是逻辑或(OR)和逻辑与(AND)。它们进行集合的交集和并集。还有其他衍生的二元算符，比如逻辑异或(XOR)(排他的或)。

子集表示为 A $\subseteq$ B，意味这在集合 A 中所有元素都在集合 B 中。

真子集表示为 A $\subset$ B，意味着在集合 A 中的所有元素都在集合 B 中，并且两个集合不等同。

超集表示为 A $\supseteq$ B，意味着在集合 B 中的所有元素都在集合 A 中。

真超集 表示为 A $\supset$ B，意味着在集合 B 中的所有元素都在集合 A 中，并且两个集合不等同。

[编辑] 例子

设图像为集合 A 包含"全集"中所有偶数(二的倍数)，集合 B 包含"全集"中所有三的倍数。则两个集合的交集(在集合 A AND B 中所有的元素)将是"全集"中所有六的倍数。

集合 A 的补集(所有不在集合 A 中的元素)是"全集"中所有的奇数。

[编辑] 把运算连接起来

尽管在任何布尔运算中都最多有两个集合参与，从这个运算所形成的新集合可以接着与其他集合联合起来实现另外的布尔运算。使用前面的例子，我们可以定义一个新集合 C 作为"全集"中所有五的倍数的集合。所以 "集合 A AND B AND C" 将是"全集"中所有 30 的倍数。如果为了更方便，我们可以把集合 AB 当作集合 A 和 B 的交集，或者说"全集"中所有六的倍数的集合。那么我们可以称 "集合 AB AND C" 是"全集"中所有 30 的倍数的集合。我们接着进一步的把这个结果叫做集合 ABC。

[编辑] 使用圆括号

尽管任何数目的逻辑 AND(或任何数目的逻辑 OR)可以被连接在一起而没有歧义，AND 和 OR 和 NOT 的组合可以导致歧义的情况。在这种情况情况下，可以使用圆括号来分清运算的次序。永远是最内的括号内的运算先进行，随后是外层的括号以此类推，直到在所有的括号内运算都完成。接着进行括号外的运算。

[编辑] 性质

为两个主要的二元运算的符号定义为 $\land / \cap$ (逻辑与/交集)和 $\lor / \cup$ (逻辑或/并集)，把单一的一元运算的符号定义为 $\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$	de Morgan 定律
$\lnot \lnot a = a$		对合律

[编辑] 真值表

布尔逻辑只使用两个值 0 和 1，这两个值的交集和并集可以使用真值表定义如下:

$\cap$	0	1
0	0	0
1	0	1

$\cup$	0	1
0	0	1
1	1	1

也可以建立涉及多个输入和其他布尔运算的更复杂的真值表。

真值表应用在逻辑中，解释 0 为假，1 为真， $\cap$ 为与， $\cup$ 为或，而 ¬ 为非。

[编辑] 其他记号

可以使用各种样式的基本算符来表达布尔逻辑。AND(与)、OR(或)、NOT(非)是最直觉的。数学家、工程师和程序员经常使用 + 表示或， $\cdot$ 表示与(因为在某些方面这些运算类似于在其他代数结构中的加法和乘法，并且这种记号使熟悉普通代数的人易于得到积之和范式)。非也表示为在要否定的表达式顶上的一个横线。

另一种记号使用"交"表示与使用"并"表示或。但是这会导致混淆，因为术语"并"也经常用于合并集合的另一个布尔运算，它包括了与和或二者。

[编辑] 布尔术语的基本数学使用

在联立方程的情况下，它们是用暗含的逻辑与连接的:

x + y = 2

AND

x - y = 2

同样适用于联立不等式:

x + y < 2

AND

x - y < 2

大于等于号( $\ge$ )和小于等于号( $\le$ )可以假定包含了一个逻辑或:

X < 2

X = 2

加/减号( $\pm$ )，在平方根的解的情况下，可以被看作是逻辑或:

WIDTH = 3

WIDTH = -3

[编辑] 布尔术语的英语使用

在把英语句子转换成形式的布尔语句的时候要小心。很多英语词语有不精确的意义可能导致多种意思，例如词 NOT(非):

"所有闪光的东西不是金子。"

它可以意味着 "没有闪光的东西是金子" 或者 "有些闪光的东西不是金子"。AND(与)和 OR(或)在英语中在特定情况下是可以互换使用的:

"在下雨与下雪的时候我总是带伞。"

"在下雨或下雪的时候我总是带伞。"

还要注意在英语中词 OR(或)可以对应于逻辑或(OR)异或逻辑异或(XOR)，依赖于上下文:

"我在潮湿或高温的时候出汗。" (逻辑或)

"我午饭打算吃鸡肉或牛肉。" (逻辑异或)

在规定计算机程序或者电子电路时使用英语描述它们的功能的时候这是个重要问题。例如，语句"程序应该校验申请者已经选择取了男性或女性单选框"，应当被当作一个异或，并增加一个检查来确保其中一个且只有一个被选择了。在其他情况下，英语的解释可能更少确定性，规定的作者可能需要探讨它们的真正意图。

[编辑] 应用

[编辑] 数字电子电路设计

布尔逻辑还在电子工程中的电路设计中使用；这里的 0 和 1 表示在数字电路中某一个位的不同状态，典型的是高和低电压。使用包含变量的表达式描述电路，并且对于这些变量的所有的值两个这种表达式是等价的，当且仅当对应的电路有相同的输入-输入行为。进一步的说，每种可能的输入-输出行为都被建模为适合的布尔表达式。

基本的逻辑门比如与门、或门、非门可以单独使用，或者联合成与非门、或非门和异或门来控制数字电子和电路。这些门的串联或并联控制了运算的优先级。

[编辑] 数据库应用

关系数据库使用 SQL 语言，或者其他特定于数据库的语言，来进行查询，它可以包含布尔逻辑。对于这种应用，在表中每个记录都可以被当作"集合"的"元素"。例如，在 SQL 中，下列 SELECT 语句被用来从在数据库中的表格中检索数据:

SELECT * FROM EMPLOYEES WHERE LAST_NAME = 'Smith' AND FIRST_NAME = 'John' ;

SELECT * FROM EMPLOYEES WHERE LAST_NAME = 'Smith' OR FIRST_NAME = 'John' ;

SELECT * FROM EMPLOYEES WHERE NOT LAST_NAME = 'Smith' ;

在有多个运算出现的时候，可以使用圆括号来明确的指定布尔运算发生的次序:

SELECT * FROM EMPLOYEES WHERE (NOT LAST_NAME = 'Smith') AND (FIRST_NAME = 'John' OR FIRST_NAME = 'Mary') ;

在需要的时候可以使用嵌套的圆括号。

联合两个(或更多)表格的任何布尔运算在关系数据库术语中都被称为连接。

[编辑] 搜索引擎查询

Wikibooks How to search has more about this subject:

Boolean Logic

对于这种应用，在互联网上的每个 web 页面都被当作是"集合"的"元素"。各种在线搜索引擎使用各自不同的语法。下面描述 Google 使用的语法。

逻辑与不使用符号。所以，它是连接两个搜索项的缺省方式:

"搜索项1" "搜索项2"

使用关键字 OR 表示逻辑或:

"搜索项1" OR "搜索项2"

使用减号表示逻辑非:

-"搜索项1"

不支持使用圆括号来明确指定运算的次序。

[编辑] 参见

[编辑] 外部链接

逻辑的演算, George Boole 著, Cambridge and Dublin Mathematical Journal Vol. III (1848), pp. 183-98.

来自“http://zh.wikipedia.org../../../%E5%B8%83/%E5%B0%94/%E9%80%BB/%E5%B8%83%E5%B0%94%E9%80%BB%E8%BE%91.html”

页面分类: 邏輯 | 布尔代数