1 Boolean Algebra and digital Logic

1.2 Boolean Algebra

For the treatment of mathematical problems as they occur in the solution of mathematical equations aids exist that are summarized under the term "algebra".
In digital design, too, complex problems need to be treated using appropriate mathematical methods

However, digital design reduces the number of possible states of information on exactly two. Although different names for these conditions are common, such as 0/1, true / false, etc., a strong similarity can be seen with another area of mathematics, the "formal logic".

Fortunately, there is a logic which was developed for two element information system presented here. It is an algebraic structure that was developed by the English mathematician George Boole and described in his famous publication, "An Investigation of the Laws of Thought".

This algebra is now named after George Boole as "Boolean algebra". Its importance is based on its various possibilities. It is suitable for the treatment of problems related to set theory, for algebraic representation of propositional logic, and algebraic manipulation and description of electronic circuits.

Boolean algebra can now be divided into four areas:

However, only the first three areas are of importance to digital design:

• the set theory,
• the propositional logic,
• the circuit algebra.
  

George Boole's work was complemented by other mathematicians, in particular, Hamilton, de Morgan, and Shannon should be mentioned.

The merit of Claude E. Shannon is to recognize the possible application of Boolean algebra in the treatment of switching networks. He showed that the main characteristics of switches and relays connected in series or in parallel can be described particularly well with the two-element logic.

The special subject area within the boolean algebra dealt with by Claude Shannon is basically described today as "switching algebra".

1.2.1 Basics of Boolean Algebra

At this point the Boolean algebra shall be introduced in simplified form as a system of rules (postulates and theorems) in which the functional treatment of binary information is described. The underlying operations are algebraically expressed by the so-called "Boolean Functions".

These Boolean functions have (by definition) two significant properties:

• Every function argument (every operand) can accept only the value "0" or "1",
• The function value, (i. e. the result which is obtained after applying the function to the operands) can accept also only the value "0" or "1".
  

Observation:

• The idea of the Boolean Function must be carefully distinguished from the idea of the binary operation or the binary function:
• An function defined without restrictions can have any number of arguments (operands) n.
  
• Has the function n = 1 operands, it is referred to as "unary operation". The best known example of a unary operation is the sign operation ("+ ""-").
• Has the function n = 2 operands, it is referred to as a "binary operation". Examples are the operations "addition", "subtraction" etc.
  

The same term "Binary operation" is often used when the arguments may accept only binary values (0/1). Because at this point also operations should be treated which can accept any number of binary operands, a conflict of concepts apparently originates.

In order to avoid this ambiguity the term Boolean function will be used for all n-digit functions (n = 1, 2, ...) whose arguments and results are binary entities.

1.2.2 Set Theory and Presentation in Boolean Algebra

To introduce more clearly the rules of the Boolean Algebra, presentation forms from Set Theory can be used. Especially suitable are graphic descriptions applying so-called set diagrams.

Definition of the term Set:

A set is a unit in which certain, differentiable objects are collected. These differentiable objects are called set elements.
As set can be defined through the enumeration of its elements.

Examples of sets:

• Set of Decimal Numbers: A = {0,1,2,3,4,5,6,7,8,9}
• Set of Binary Numbers: B = {0,1}
• Set of binary 2-Tuples: C = {[0,0],[0,1],[1,0],[1,1]}
• Set of Truth Values: D = {true,false}