布尔代数

搜一下：请问布尔代数的公式是如何得到的，如分配律A+BC等于（A+B)*(A+C).

(A+B)*(A+C)=A*A+A*C+B*A+B*C=A+A*(C+B)+B*C=A*(1+C+B)+B*C=A+B*CA*(A+B)=A*A+A*B=A+A*B=A*(1+B)=A所以说都是从基本的公式推导出来的

利用真值表证明的. 也可以用技巧性的变换来证明. A+BC=(A+B)*(A+C)的证明如下： 因为A+AB =A(B+B")+AB =AB+AB"+AB =AB+AB" =A(B+B") =A,（吸收律） 所以(A+B)*(A+C) =AA+AB+AC+BC =(A+AB)+AC+BC =A+AC+BC =A+BC

利用真值表证明的. 也可以用技巧性的变换来证明. A+BC=(A+B)*(A+C)的证明如下： 因为A+AB =A(B+B")+AB =AB+AB"+AB =AB+AB" =A(B+B") =A,（吸收律） 所以(A+B)*(A+C) =AA+AB+AC+BC =(A+AB)+AC+BC =A+AC+BC =A+BC,1,

F = (AB+C)"+ B"C = (AB)"C"+ B"C = (A"+B")C"+ B"C = A"C"+ B"C"+B"C = A"C"+ B"= (A"C")"B = (A+C)B

给定一个集合：B,设它的任何两个元素X和Y,都有B中的两个元素：XY和X+Y与之对应，并满足：1）交换律：XY=YXX+Y=Y+X2)结合律：X(YZ)=(XY)ZX+(Y+Z)=X+(Y+Z)3)吸收律：X+(XY)=(X+Y)X=X4)分配律：X(Y+Z)=XY+XZX+YZ=(X+Y)(X+Z)5)互补律：B中，有元素0和1，且对应一个X，就有一个X"，满足：X+X"=1,XX"=0.此时称B为布尔代数。且X"为X的补元。B中的元素非0即1，只有两个元素。布尔代数，是英国数学家G.布尔为了研究思维规律（逻辑学、数理逻辑)于1847和1854年提出的数学模型。它由在布尔代数的元素间永远成立的关系组成，而不管具体的那个布尔代数。布尔代数起源于数学领域，是一个用于集合运算和逻辑运算的公式：〈B，∨，∧，?〉。其中B为一个非空集合，∨，∧为定义在B上的两个二元运算，?为定义在B上的一个一元运算。通过布尔代数进行集合运算可以获取到不同集合之间的交集、并集或补集，进行逻辑运算可以对不同集合进行与、或、非。 布尔代数定律：互补律：第一互补律：若A=0，则~A=1,若A=1，则~A=0 注：~A =NOT　A 第二互补律：A*~A=0 第三互补律：A+~A=1 双重互补律：/=//A=A 交换律： AND交换律：A*B=B*A OR交换律： A+B=B+A 结合律： AND结合律：A=C* OR结合律：　A+=C+ 分配律：第一分配律：　A*=+ 第二分配律：　A+=* 重言律：第一重言律： A*A=A 若A=1，则A*A=1；若A=0，则A*A=0。因此表达式简化为A 第二重言律： A+A=A 若A=1，则1+1=1；若A=0，则0+0=0。因此表达式简化为A 带常数的重言律： A+1=1 A*1=A A*0=0 A+0=A 吸收率：第一吸收率： A*=A 第二吸收率： A+=A

每个布尔代数 (A,<math>land</math>,<math>lor</math>) 都引出一个环 (A,+,*)，通过定义 a + b = (a <math>land</math> &not;b) <math>lor</math> (b <math>land</math> &not;a) (这个运算在集合论中叫做对称差在逻辑中叫做XOR(异或)) 和 a * b = a <math>land</math> b。这个环的零元素符合布尔代数的 0；环的乘法单位元素是布尔代数的 1。这个环有对于 A 中的所有的 a 保持 a * a = a 的性质；有这种性质的环叫做布尔环。反过来，如果给出布尔环A，我们可以把它转换成布尔代数，通过定义 x <math>lor</math> y = x + y + xy 和 x <math>land</math> y = xy。因为这两个运算是互逆的，我们可以说每个布尔环引发一个布尔代数，或反之。此外，映射 f : A → B 是布尔代数的同态，当且仅当它是布尔环的同态。布尔环和代数的范畴是等价的。布尔代数 A 的理想是一个子集 I，对于在 I 中的所有 x,y 我们有 x <math>lor</math> y 在 I 中，并且对于在 A 中的所有 a 我们有 a <math>land</math> x 在 I 中。理想的概念符合在布尔环 A中环理想的概念。A 的理想 I 叫做素理想，如果 I ≠ A；并且如果 a <math>land</math> b 在 I 中总是蕴涵 a 在 I 中或 b 在 I 中。A 的理想 I 叫做极大理想，如果 I ≠ A 并且真正包含 I 的唯一的理想是 A 自身。这些概念符合布尔环A 中的素理想和极大理想的环理论概念。理想的对偶是滤子。布尔代数 A 的滤子是子集 p，对于在 p 中的所有 x,y 我们有 x <math>land</math> y 在 p 中，并且对于在 A 中的所有 a，如果 a <math>lor</math> x = a 则 a 在 p 中。 可以证实所有的有限的布尔代数都同构于这个有限集合的所有子集的布尔代数。此外，所有的有限的布尔代数的元素数目都是二的幂。Stone 的著名的布尔代数的表示定理陈述了所有的布尔代数 A 都在某个(紧凑的完全不连通的 Hausdorff)拓扑空间中同构于所有闭开集的布尔代数。 在 1933 年，美国数学家 Edward Vermilye Huntington (1874-1952) 展示了对布尔代数的如下公理化：交换律： x + y = y + x。结合律： (x + y) + z = x + (y + z)。Huntington等式： n(n(x) + y) + n(n(x) + n(y)) = x。一元函数符号 n 可以读做"补"。Herbert Robbins 接着摆出下列问题： Huntington等式能否缩短为下述的等式，并且这个新等式与结合律和交换律一起成为布尔代数的基础? 通过一组叫做 Robbins 代数的公理，问题就变成了： 是否所有的 Robbins 代数都是布尔代数?Robbins 代数的公理化：交换律： x + y = y + x。结合律： (x + y) + z = x + (y + z)。Robbins等式： n(n(x + y") + n(x + n(y))) = x。这个问题自从 1930 年代一直是公开的，并成为 Alfred Tarski 和他的学生最喜好的问题。在 1996 年，William McCune 在 Argonne 国家实验室，建造在 Larry Wos、Steve Winker 和 Bob Veroff 的工作之上，肯定的回答了这个长期存在的问题： 所有的 Robbins 代数都是布尔代数。这项工作是使用 McCune 的自动推理程序 EQP 完成的。 代入法则 它可描述为逻辑代数式中的任何变量A，都可用另一个函数Z代替，等式仍然成立。对偶法则 它可描述为对任何一个逻辑表达式F，如果将其中的“+”换成“*”，“*”换成“+”，“1”换成“0”，“0”换成“1”，仍保持原来的逻辑优先级，则可得到原函数F的对偶式G，而且F与G互为对偶式。我们可以看出基本公式是成对出现的，二都互为对偶式。反演法则 有原函数求反函数就称为反演（利用摩根定律），我们可以把反演法则这样描述：将原函数F中的“*”换成“+”，“+”换成“*”，“0”换成“1”，“1”换成“0”；原变量换成反变量，反变量换成原变量，长非号即两个或两个以上变量的非号不变，就得到原函数的反函数。 互补律：第一互补律：若A=0，则~A=1,若A=1，则~A=0 注：~A =NOT　A第二互补律：A*~A=0第三互补律：A+~A=1双重互补律：/<~A>=//A=A交换律：AND交换律：A*B=B*AOR交换律： A+B=B+A结合律：AND结合律：A<B*C>=C*<A*B>OR结合律：　A+<B+C>=C+<A+B>分配律：第一分配律：　A*<B+C>=<A*B>+<A*C>第二分配律：　A+<B*C>=<A+B>*<A+C>重言律：第一重言律： A*A=A 若A=1，则A*A=1；若A=0，则A*A=0。因此表达式简化为A第二重言律： A+A=A 若A=1，则1+1=1；若A=0，则0+0=0。因此表达式简化为A带常数的重言律：A+1=1A*1=AA*0=0A+0=A吸收率：第一吸收率： A*<A+B>=A第二吸收率： A+<A*B>=A 在k元素集合X上有k个n元运算f: X→X，因此在{0,1}上有2个n元运算。所以得出所有布尔代数，不论大小都两个常量或“零元”运算，四个一元运算，16个二元运算，256个三元运算，以此类推，它们叫做给定布尔代数的布尔运算。只有一个例外就是一个元素的布尔代数，它叫做退化的或平凡的（被一些早期作者禁用），布尔代数的所有运算可以被证明是独特的。（在退化情况下，给定元数的所有运算都是同样的运算因为对所有输入都返回同样结果。）在{0,1}上的运算可以用真值表展出，选取0和1为真值假和真。它们可以按统一和不依赖应用的方式列出，允许我们命名或至少单独列出它们。这些名字对布尔运算提供方便的简写。n元运算的名字是2位的二进制数。有2个这种运算，你不能得到更简明的命名法了!下面展示元数从0到2的所有运算的这种格局和关联的名字。直到2元的布尔运算的真值表常量 f0 f1 0 1 一元运算 x0 　f0 f1 f2 f3 0 　0 1 0 1 1 　0 0 1 1 二元运算 x0 x1 　f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 0 0 　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 　0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 　0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 　0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 这些表格继续到更高元数上，对n元有2行，每个行给出n个变量x0,…xn−1的一个求值或绑定，而每列都有表头fi，它们给出第i个n元运算fi(x0,…,xn−1)在这个求值下的值。运算包括变量本身，例如f2是x0而f10是x0 (作为它的一元对应者的两个复件)而f12是x1 (没有一元对应者)。否定或补¬x0出现为f1再次出现为f5，连同f3 (¬x1在1元时没有出现)，析取或并x0∨x1出现为f14，合取或交x0∧x1出现为f8，蕴涵x0→x1出现为f13，异或或对称差x0⊕x1出现为f6，差集x0−x1出现为f2等等。对布尔函数的其他命名或表示可参见零阶逻辑。作为关于它的形式而非内容的次要详情，一个代数的运算传统上组织为一个列表。我们这里通过在{0,1}上有限运算索引了布尔代数的运算，上述真值表表示的排序首先按元数，其次为每个元数运算的列出表格。给定元数的列表次序是如下两个规则确定的。 (i)表格左半部分的第i行是i的二进制表示，最低有效位或第0位在最左（“小端”次序，最初由艾伦·图灵提议，所以可不无合理的叫做图灵序）。 (ii)表格的右半部分的第j列是j的二进制表示，还是按小端次序。在效果上运算的下标就是这个运算的真值表。