| Boolean Algebra (logic) |
Article Index for Boolean Algebra |
Shopping Boolean |
Website Links For Algebra |
Information AboutBoolean Algebra (logic) |
|
Boolean algebra is the finitary algebra of two values. It resembles the Algebra of Real Numbers as taught in high school, but with the numeric operations of multiplication ''xy'', addition ''x'' + ''y'', and negation −''x'' replaced by the logical operations of conjunction ''x''∧''y'', disjunction ''x''∨''y'', and complement ¬''x''. The Boolean operations are these and all other operations obtainable from them by composition; equivalently, the Finitary operations on the set {0,1}. The laws of Boolean algebra can be defined Axiomatically as the equations derivable from a sufficient finite subset of those laws, such as the equations axiomatizing a complemented Distributive Lattice or a Boolean Ring , or Semantically as those equations identically true or ''valid'' over {0,1}. The axiomatic approach is Sound and Complete in the sense that it proves respectively neither more nor fewer laws than the validity-based semantic approach. VALUES Conventions Boolean algebra is the algebra of two values. These are usually taken to be 0 and 1, as we shall do here, although ⊥ and T, false and true, etc. are also in common use. For the purpose of understanding Boolean algebra any Boolean Domain of two values will do. Regardless of nomenclature the values are customarily thought of as essentially logical in character and are therefore referred to as truth values, in contrast to the natural numbers or the reals which are considered numerical values. On the other hand the algebra of the integers modulo 2, while ostensibly just as numeric as the integers themselves, was shown to constitute exactly Boolean algebra, originally by I.I. Zhegalkin in 1927 and rediscovered independently in the west by Marshall Stone in 1936. So in fact there is some ambiguity in the true nature of Boolean algebra: it can be viewed as either logical or numeric in character. More generally Boolean algebra is the algebra of values from any Boolean Algebra as a model of the laws of Boolean algebra. For example the Bit Vector s of a given length, as with say 32-bit Computer Word s, can be combined with Boolean operations in the same way as individual bits, thereby forming a 232-element Boolean algebra under those operations. Any such combination applies the same Boolean operation to all bits simultaneously. This passage from the Boolean algebra of 0 and 1 to these more general Boolean algebras is the Boolean counterpart of the passage from the algebra of the Ring Of Integers to the algebra of Commutative Ring s in general. The two-element Boolean algebra is the prototypical Boolean algebra in the same sense as the ring of integers is the prototypical commutative ring. Boolean logic as the subject matter of this article is independent of the choice of Boolean algebra (the same equations hold of every nontrivial Boolean algebra) whence there is no need here to consider any Boolean algebra other than the two-element one. Applications Boolean algebra as the calculus of two values is fundamental to digital logic, computer programming, and mathematical logic, and is also used in other areas of mathematics such as set theory and statistics. Digital Logic codes its symbols in various ways: as voltages on wires in high-speed circuits and capacitive storage devices, as orientations of a magnetic domain in ferromagnetic storage devices, as holes in punched cards or paper tape, and so on. Now it is possible to code more than two symbols in any given medium. For example one might use respectively 0, 1, 2, and 3 volts to code a four-symbol alphabet on a wire, or holes of different sizes in a punched card. In practice however the tight constraints of high speed, small size, and low power combine to make noise a major factor. This makes it hard to distinguish between symbols when there are many of them at a single site. Rather than attempting to distinguish between four voltages on one wire, digital designers have settled on two voltages per wire, high and low. To obtain four symbols one uses two wires, and so on. Programmers programming in Machine Code , Assembly Language , and other Programming Languages that expose the low-level digital structure of the Data Registers operate on whatever symbols were chosen for the hardware, invariably bit vectors in modern computers for the above reasons. Such languages support both the numeric operations of addition, multiplication, etc. performed on words interpreted as integers, as well as the logical operations of disjunction, conjunction, etc. performed bit-wise on words interpreted as bit vectors. Programmers therefore have the option of working in and applying the laws of either numeric algebra or Boolean algebra as needed. A core differentiating feature is carry propagation with the former but not the latter. Other areas where two values is a good choice are the law and mathematics. In everyday relaxed conversation, nuanced or complex answers such as "maybe" or "only on the weekend" are acceptable. In more focused situations such as a court of law or theorem-based mathematics however it is deemed advantageous to frame questions so as to admit a simple yes-or-no answer---is the defendant guilty or not guilty, is the proposition true or false---and to disallow any other answer. However much of a straitjacket this might prove in practice for the respondent, the principle of the simple yes-no question has become a central feature of both judicial and mathematical logic, making two-valued logic deserving of organization and study in its own right. A central concept of set theory is membership. Now an organization may permit multiple degrees of membership, such as novice, associate, and full. With sets however an element is either in or out. The candidates for membership in a set work just like the wires in a digital computer: each candidate is either a member or a nonmember, just as each wire is either high or low. Algebra being a fundamental tool in any area amenable to mathematical treatment, these considerations combine to make the algebra of two values of fundamental importance to computer hardware, mathematical logic, and set theory. It has not featured so prominently in law however, perhaps because mathematical methods in general have not been applied as vigorously there as in these other application areas. OPERATIONS Basic operations After values, the next ingredient of any algebraic system is its operations. Whereas elementary algebra is based on numeric operations multiplication ''xy'', addition ''x'' + ''y'', and negation −''x'', Boolean algebra is customarily based on logical counterparts to those operations, namely conjunction ''x''∧''y'' ( AND ), disjunction ''x''∨''y'' ( OR ), and complement or negation ¬''x'' ( NOT ). Conjunction is the closest of these three to its numerical counterpart, in fact on 0 and 1 it ''is'' multiplication. As a logical operation the conjunction of two propositions is true when both propositions are true, and otherwise is false. The first column of Figure 1 below tabulates the values of ''x''∧''y'' for the four possible valuations for ''x'' and ''y''; such a tabulation is traditionally called a Truth Table . Disjunction, in the second column of the figures, works almost like addition, with one exception: the disjunction of 1 and 1 is neither 2 nor 0 but 1. Thus the disjunction of two propositions is false when both propositions are false, and otherwise is true. This is just the definition of conjunction with true and false interchanged everywhere; because of this we say that disjunction is the ''dual'' of conjunction. Logical negation however does not work like numerical negation at all. Instead it corresponds to incrementation: ¬''x'' = ''x''+1 mod 2. Yet it shares in common with numerical negation the property that applying it twice returns the original value: ¬¬''x'' = ''x'', just as −(−''x'') = ''x''. An operation with this property is called an ''involution''. The set {0,1} has two Permutations , both involutary, namely the identity, no movement, corresponding to numerical negation mod 2 (since +1 = −1 mod 2), and SWAP, corresponding to logical negation. Using negation we can formalize the notion that conjunction is dual to disjunction via De Morgan's Laws , ¬(''x''∧''y'') = ¬''x'' ∨ ¬''y'' and ¬(''x''∨''y'') = ¬''x'' ∧ ¬''y''. These can also be construed as definitions of conjunction in terms of disjunction and vice versa: ''x''∧''y'' = ¬(¬''x'' ∨ ¬''y'') and ''x''∨''y'' = ¬(¬''x'' ∧ ¬''y''). Figure 2 shows the symbols used in Digital Electronics for conjunction and disjunction; the input ports are on the left and the signals flow through to the output port on the right. Inverters negating the input signals on the way in, or the output signals on the way out, are represented as circles on the port to be inverted. Derived operations Other Boolean operations are derivable from these by composition. For example implication ''x''→''y'' (IMP), in the third column of the figures, is a binary operation which is false when ''x'' is true and ''y'' is false, and true otherwise. It can be expressed as ''x''→''y'' = ¬''x''∨''y'' (the OR-gate of Figure 2 with the ''x'' input inverted), or equivalently ¬(''x''∧¬''y'') (its De Morgan equivalent in Figure 3). In logic this operation is called Material Implication , to distinguish it from related but non-Boolean logical concepts such as entailment and relevant implication. The idea is that an implication ''x''→''y'' is by default true (the weaker truth value in the sense that false implies true but not vice versa) unless its premise or antecedent ''x'' holds, in which case the truth of the implication is that of its conclusion or consequent ''y''. Although disjunction is not the exact counterpart of numerical addition, Boolean algebra nonetheless does have an exact counterpart, called exclusive-or (XOR) or parity, ''x''⊕''y''. As shown in the fourth column of the figures, the exclusive-or of two propositions is true just when exactly one of the propositions is true; equivalently when an odd number of the propositions is true, whence the name "parity". Exclusive-or is the operation of addition mod 2. The exclusive-or of any value with itself vanishes, ''x''⊕''x'' = 0, since the arguments have an even number of whatever value ''x'' has. Its digital electronics symbol is shown in Figure 2, being a hybrid of the disjunction symbol and the equality symbol. The latter reflects the fact that the negation (which is also the dual) of XOR, ¬(''x''⊕''y''), is logical equivalence, EQV, being true just when ''x'' and ''y'' are equal, either both true or both false. XOR and EQV are the only binary Boolean operations that are commutative and whose truth tables have equally many 0s and 1s. Exclusive-or together with conjunction constitute yet another complete basis for Boolean algebra, with the Boolean operations reformulated as the Zhegalkin Polynomial s. | |||||||||||||||
|
|||||||||||||||
|
|