逻辑代数

维基百科,自由的百科全书
跳转至: 导航搜索

数学数理逻辑中,逻辑代数(有时也称开关代数布尔代数)是变量的值仅为两种真值(通常记作 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)

逻辑运算与性质[编辑]

两个主要的二元运算的符号定义为 \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)在项数最少的条件下,项内的文字最少。

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

参见[编辑]

参考文献[编辑]

  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.
  3. ^ Givant, Steven; Halmos, Paul. Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer. 2009. ISBN 978-0-387-40293-2.