Boolean Logic System

Jump to navigation Jump to search

A Boolean Logic System is a Deductive Logic System that involves Boolean Logic Operations.



a ∨ (bc) = (ab) ∨ c a ∧ (bc) = (ab) ∧ c associativity
ab = ba ab = ba commutativity
a ∨ 0 = a a ∧ 1 = a identity
a ∨ (bc) = (ab) ∧ (ac)   a ∧ (bc) = (ab) ∨ (ac)   distributivity
a ∨ ¬a = 1 a ∧ ¬a = 0 complements
    • A Boolean algebra with only one element is called a trivial Boolean algebra or a degenerate Boolean algebra. (Some authors require 0 and 1 to be distinct elements in order to exclude this case.)

      It follows from the last three pairs of axioms above (identity, distributivity and complements) that

a = ba     if and only if     ab = b.
    • The relation ≤ defined by ab if and only if the above equivalent conditions hold, is a partial order with least element 0 and greatest element 1. The meet ab and the join ab of two elements coincide with their infimum and supremum, respectively, with respect to ≤.

      As in every bounded lattice, the relations ∧ and ∨ satisfy the first three pairs of axioms above; the fourth pair is just distributivity. Since the complements in a distributive lattice are unique, to define the involution ¬ it suffices to define ¬a as the complement of a.

      The set of axioms is self-dual in the sense that if one exchanges ∨ with ∧ and 0 with 1 in an axiom, the result is again an axiom. Therefore by applying this operation to a Boolean algebra (or Boolean lattice), one obtains another Boolean algebra with the same elements; it is called its dual.

    • The basic operations of Boolean algebra are the following ones:
      • And (conjunction), denoted xy (sometimes x AND y or Kxy), satisfies xy = 1 if x = y = 1 and xy = 0 otherwise.
      • Or (disjunction), denoted xy (sometimes x OR y or Axy), satisfies xy = 0 if x = y = 0 and xy = 1 otherwise.
      • Not (negation), denoted ¬x (sometimes NOT x, Nx or !x), satisfies ¬x = 0 if x = 1 and ¬x = 1 if x = 0.
    • If the truth values 0 and 1 are interpreted as integers, these operation may be expressed with the ordinary operations of the arithmetic:
      • xy = xy,
      • xy = x + y - xy,
      • ¬x = 1 - x.
    • Alternatively the values of xy, xy, and ¬x can be expressed by tabulating their values with truth tables as follows.
x y xy xy
0 0 0 0
1 0 0 1
0 1 0 1
1 1 1 1
x ¬x
0 1
1 0
Figure 1. Truth tables


  • (Wikipedia, 2009) ⇒
    • Boolean logic is a complete system for logical operations. It was named after George Boole, who first defined an algebraic system of logic in the mid 19th century. Boolean logic has many applications in electronics, computer hardware and software, and is the base of digital electronics. In 1938, Claude Shannon showed how electric circuits with relays were a model for Boolean logic. This fact soon proved enormously consequential with the emergence of the electronic computer.
    • Using the algebra of sets, this article contains a basic introduction to sets, Boolean operations, Venn diagrams, truth tables, and Boolean applications. The Boolean algebra article discusses a type of algebraic structure that satisfies the axioms of Boolean logic. The binary arithmetic article discusses the use of binary numbers in computer systems.
    • Terms: Let X be a set:
      • An element is one member of a set. This is denoted by \in. If it's not an element of the set, this is denoted by \notin.
      • The universe is the set X, sometimes denoted by 1. Note that this use of the word universe means "all elements being considered", which are not necessarily the same as "all elements there are".
      • The empty set or null set is the set of no elements, denoted by \varnothing and sometimes 0.
      • A unary operator applies to a single set. There is one unary operator, called logical NOT. It works by taking the complement.
      • A binary operator applies to two sets. The basic binary operators are logical OR and logical AND. They perform the union and intersection of sets. There are also other derived binary operators, such as XOR (exclusive OR).
      • A subset is denoted by A \subseteq B and means every element in set A is also in set B.
      • A superset is denoted by A \supseteq B and means every element in set B is also in set A.
      • The identity or equivalence of two sets is denoted by A \equiv B and means that every element in set A is also in set B and every element in set B is also in set A.
      • A proper subset is denoted by A \subset B and means every element in set A is also in set B and the two sets are not identical.
      • A proper superset is denoted by A \supset B and means every element in set B is also in set A and the two sets are not identical.