布尔逻辑
布尔逻辑(英语:Boolean algebra)得名于乔治·布尔,他是爱尔兰科克的皇后学院的英国数学家,他在十九世纪中叶首次定义了逻辑的代数系统。现在,布尔逻辑在电子学、计算机硬件和软件中有很多应用。在1937年,克劳德·艾尔伍德·香农展示了布尔逻辑如何在电子学中使用。
“布尔逻辑”的各地常用别名 | |
---|---|
中国大陆 | 布尔逻辑 |
港台 | 布林运算 |
使用集合代数作为介绍布尔逻辑的一种方式。还使用文氏图来展示各种布尔逻辑陈述所描述的集合联系。
术语
设X是一个集合:
- 元素是一个集合的成员。表示为 。如果它不是这个集合的元素,表示为 。
- 全集是集合X,有时表示为1。注意使用全集这个词意味着“虑及的所有元素”,不必然的同“现有的所有元素”一样。
- 空集或null集合是没有元素的集合,表示为 ,有时表示为0。
- 一元算符应用于一个单一的集合。有一个一元算符叫做逻辑非(NOT)。它的作用是采用补集。
- 子集表示为A B,意味这在集合A中所有元素都在集合B中。
- 真子集表示为A B,意味着在集合A中的所有元素都在集合B中,并且两个集合不等同。
- 超集表示为A B,意味着在集合B中的所有元素都在集合A中。
- 真超集表示为A 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的组合可以导致歧义的情况。在这种情况下,可以使用圆括号来分清运算的次序。永远是最内的括号内的运算先进行,随后是外层的括号以此类推,直到在所有的括号内运算都完成。接着进行括号外的运算。
性质
为两个主要的二元运算的符号定义为 (逻辑与/交集)和 (逻辑或/并集),把单一的一元运算的符号定义为 / ~(逻辑非/补集)。我们还使用值0(逻辑假/空集)和1(逻辑真/全集)。下列性质适用于布尔代数和布尔逻辑二者:
真值表
布尔逻辑只使用两个值0和1,这两个值的交集和并集可以使用真值表定义如下:
|
|
- 也可以创建涉及多个输入和其他布尔运算的更复杂的真值表。
- 真值表应用在逻辑中,解释0为假,1为真, 为与, 为或,而¬为非。
其他记号
可以使用各种样式的基本算符来表达布尔逻辑。AND(与)、OR(或)、NOT(非)是最直觉的。数学家、工程师和程序员经常使用 +表示或, 表示与(因为在某些方面这些运算类似于在其他代数结构中的加法和乘法,并且这种记号使熟悉普通代数的人易于得到积之和范式)。非也表示为在要否定的表达式顶上的一个横线。
另一种记号使用"交"表示与使用"并"表示或。但是这会导致混淆,因为术语"并"也经常用于合并集合的另一个布尔运算,它包括了与和或二者。
布尔术语的基本数学使用
- 在联立方程的情况下,被联立的方程暗含逻辑与:
- x + y = 2
- AND
- x - y = 2
同样适用于联立不等式:
- x + y < 2
- AND
- x - y < 2
- 大于等于号( )和小于等于号( ),可以认为是暗含逻辑或的一对等式与不等式的联立:
- X < 2
- OR
- X = 2
- 加/减号( ),在表示“平方根的解”情况下,可以被看作暗含逻辑或的一对联立等式:
- WIDTH = 3
- OR
- 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');
在需要的时候可以使用嵌套的圆括号。
联合两个(或更多)表格的任何布尔运算在关系数据库术语中都被称为连接。
搜索引擎查询
对于这种应用,在互联网上的每个web页面都被当作是"集合"的"元素"。各种在线搜索引擎使用各自不同的语法。下面描述Google使用的语法。
- 逻辑与不使用符号。所以,它是连接两个搜索项的缺省方式:
- "搜索项1" "搜索项2"
- 使用关键字OR表示逻辑或:
- "搜索项1" OR "搜索项2"
- 使用减号表示逻辑非:
- -"搜索项1"
- 不支持使用圆括号来明确指定运算的次序。
参见
外部链接
- 逻辑的演算 (页面存档备份,存于互联网档案馆), George Boole著, Cambridge and Dublin Mathematical Journal Vol. III (1848), pp. 183-98.
- Logical Formula Evaluator (页面存档备份,存于互联网档案馆)(for Windows), a software which calculates all possible values of a logical formula
- How Stuff Works - Boolean Logic (页面存档备份,存于互联网档案馆)
- Maiki & Boaz BDD-PROJECT, a Web Application for BDD reduction and visualization.