Close

Part 6: Boolean Algebra

A project log for ALUMinimum

Learn deep logic optimization by implementing the fastest ALU West of the Pecos River, using no specialized arithmetic chip

Squonk42Squonk42 07/20/2017 at 11:050 Comments

If we try to summarize what we have seen so far:

  1. Arithmetic operations on arbitrary analog values are better performed using digital numbers to get a repeatable accuracy
  2. Unsigned integer digital numbers are represented as base 2 (binary) numbers using only 0 and 1 values, using a positional notation with enough binary digits (bits). Using only 2 values offers the simplest and most effective design to store digital numbers in a physical device
  3. Signed integer digital numbers are represented using a 2's complement notation but otherwise follow the same arithmetic rules as unsigned integer digital numbers
  4. Non-integer numbers can be represented using:
    1. a fixed-point notation where the decimal point position is implicit and a given number of bits right of it are used to hold the fractional part of the number, following the same arithmetic rules as integer digital numbers
    2. a floating point notation where the decimal point position is given by an integer exponent, and the remaining bits hold the fractional part of the number as the mantissa. Both the exponent and mantissa parts still follow the same arithmetic rules as integer digital numbers
  5. Arithmetic operations on digital numbers can be reduced to subtraction operations
  6. Subtraction operation can be implemented using the basic logic operations from the Boolean algebra, although adding the addition operation does not cost much, and having positional shift or rotation operations helps implementing multiplication and division operations more efficiently, which would otherwise require complex specific hardware
  7. Simple as well as bitwise (i.e., performed on a set of bits that can be used equivalently to store a digital number) logic conditions  can of course be implemented using the same basic logic operations from the Boolean algebra

Thus, digital computers can perform all arithmetic and logic operations only using Boolean algebra values, operations and laws, which will be described below in details, using simple undergraduate maths.

It is thus a formalism for describing logical relations in the same way that ordinary algebra describes numeric relations.

Values

Unlike elementary algebra which deals with an infinite set of numbers, Boolean algebra is using a finite set of only 2 elements. These 2 values can be indifferently called true and falseT and F0 and 1, or any other couple of symbols, but they are generally represented with the bits (binary digits) 0 and 1, as the XOR (exclusive-or) and AND (conjunction) operations (see below) plays the role of the addition (+) and multiplication (x) operations in integer arithmetic modulo 2, for which 1 + 1 = 0, but unlike common arithmetic, where 1 + 1 = 2. The OR operation (inclusive-or or disjunction) is then defined as x + y + xy.

Manipulating only 2 values is very nice, since it enables using the method of proof of perfect induction or proof by exhaustion, i.e., the verification for all possible cases for demonstrating theorems, as the number of cases is very small.

Operations

Boolean operations are functions having zero or more Boolean input values (in the set {0, 1}) to a single Boolean output value.

The number of operands is the arity of the operation. An operation of arity zero, or 0-ary operation is a constant, and the Boolean algebra only deals with unary operations (with arity 1) and binary operations (with arity 2).

Unary Operations

If we consider all possible calculations from 1 binary input value p to an output value, there are only 2 ^ 2 = 4 unary operations:

Unary Boolean Operations

OperationName SymbolValue
FALSELogicalfalse⊥, OpThe output value is always false, regardless of the input value of p.
IDENTLogical identitypLogical identity is an operation on one input value p, for which the output value remains p.
NOTLogical negation¬p, ~p, Np, FpLogical negation is an operation on one logical value p, or which the output value is true if its input value is false and its value is false if its input value is true.
TRUELogical true⊤, VpThe output value is always true, regardless of the input value of p.

Binary Operations

For calculations from 2 binary inputs p and q to an output values, each inputs with two possible values, there are 2 ^ 2 = 4 possible combinations of inputs. Because each output can have two possible values, there are 2 ^ 4 = 16 possible binary operations:

Binary Boolean Operations

Here are enumerated all possible operations, and their equivalent representations:

OperationNameSymbolValue
FALSEContradictionfalse, ⊥, OpqThe output value is always false, regardless of the input values of p and q.
NORLogical negation of logical disjunction, Peirce's arrow, Quine's dagger, ampheck, neither-norp ↓ q,  XpqThe output value of true if both of input values p and q are false. In other words, it produces a value of false if at least one of its input values is true.
NBUTConverse nonimplicationp ↚ q, MpqThe output value is true if p is false (NOT pBUT q is true.
NOTLLeft negation¬p, ~p, Np, FpqThe output value is true if the LEFT input value p is NOT true.
BUTNMaterial nonimplication p ↛ qp ⊅ q, LpqThe output value is true if p is true BUT q is false (NOT q).
NOTRRight negation¬q, ~q, Nq, GpqThe output value is true if the RIGHT input value q is NOT true.
XORExclusive disjunctionp ⊕ q, p ⊻ q, p ↮ q, p ≢ q, JpqThe output value is true whenever the inputs values differ.
NANDLogical negation of logical conjunction, Sheffer strokep ↑ q, p | q, DpqThe output value is true, if and only if, at least one of the input value is false.
ANDLogical conjunction∧ q, p ᛫ qp * qpq, KpqThe output value is true if both of input values are true.
XNORLogical equality, logical biconditionalp ↔qp ≡ qp = q, EpqThe output value is true if and only if both input values are false or both input values are true.
RIGHTProjection functionq, HpqThe output value is the same as the right input value q.
THENMaterial implication, material conditionalp → qp ⊃ qp ⇒ q, CpqIf p is true, THEN the output value is the same as the input value q and true otherwise.
LEFTProjection functionp ,IpqThe output value is the same as the left input value p.
IFConverse implicationp ← qp ⊂ q, BpqThe output value is the same as input value p IF the input value q is true and true otherwise.
ORLogical disjunctionp ∨ qp + q, ApqThe output value is true if at least one of input values is true.
TRUETautologytrue, ⊤, VpqThe output value is always true, regardless of the input values of p and q.

Basis

The operations need not be all explicitly stated. A basis is any set from which the remaining operations can be obtained by composition. A Boolean algebra may be defined from any of several different bases. There are three bases for Boolean algebra that are in common use:

Laws

If we assume the lattice basis, the Boolean algebra satisfies a set of identities between two Boolean terms, where a Boolean term is defined as an expression built up from variables, the underlying set of constants 0 and 1 and using the 3 basic operations ( [AND, OR, NOT]) . These identities are called laws, which can conveniently be proven using the method of proof of perfect induction, given the small number of cases.

Monotone Axioms

If we use the symbols commonly used for analyzing digital circuits ( or implicit for AND, + for OR and ~ for NOT), the following axioms hold:

(a)(b)
x + 0 = xx ‧ 1 = xidentity(II)
x + y = y + xxy = yxcommutativity(III)
x + yz = (x + y) (x + z)
x(y + z) = xy + xz
distributivity
(IV)

All of the laws above use only AND and OR operations. These operations have the property that changing either argument either leaves the output unchanged or the output changes in the same way as the input. Equivalently, changing any variable from 0 to 1 never results in the output changing from 1 to 0. Operations with this property are said to be monotone.

Nonmonotone Axioms

Nonmonotonicity enters via complement operation NOT as follows:

(a)(b)
x + ~x = 1                   x ‧ ~x = 0            complements(V)

The above axioms (Ia) to (Va) and their dual (Ib) to (Vb) are the ones introduced by Edward V. Huntington in his paper "Sets of Independent Postulates for the Algebra of Logic" pp 293-293 in 1904 as postulates bearing the same reference numbers in its first set of postulates (his postulates Ia, Ib and VI are provided by the lattice basis and the fact that the set of Boolean values contains 2 distinct elements, {0, 1}).

These axioms are sufficient to prove all the other laws below:

Monotone Laws

More monotonous laws were introduced by Huntington:

(a)(b)
If x + y = x for all x, then y = 0
If x ‧ y = x for all x then y = 1
unique identity(VII)
x + x = x
x ‧ x = x
idempotence(VIII)
x + 1 = 1
x ‧ 0 = 0
annihilation(IX)
x + xy = xx (x + y) = xabsorption(X)
x + (by + z) = (x + y) + zx (yz) = (xy)zassociativity (XIII)

Nonmonotone Laws

And one more nonmonotonous law was also described in Huntington's paper (lawn XIV is not):

If x + y = 1 and x ‧ y = 0, then y = ~x
unique negation(XI)
~(~x) = xdouble negation(XIV)

De Morgan's Laws

However, whereas ordinary algebra satisfies the 2 laws:

(-x)+(-y) = -(x + y)
(-x)(-y) = xy

Boolean algebra satisfies De Morgan's laws:

(a)(b)
~x + ~y = ~(xy)~x ‧ ~y= ~(x + y)De Morgan's laws
(XII)

These are the 2 last laws from Huntington's paper, and not surprisingly, form an indispensable tool when simplifying digital circuits involving AND, OR and NOT operations ("gates").

Other Nonmonotone Laws

Some other laws can be proven (make sure to display the "Proven properties" panel):

(1)(2)
x + (~x + y) = 1
x ‧ (~x ‧ y) = 0
(a)
(x + y) + (~x ‧ ~y) = 1
(x ‧ y) ‧ (~x + ~y) = 0
(b)
(x + y) ‧ (~x ‧ ~y) = 0(x ‧ y) + (~x + ~y) = 1(c)
(x + (y + z)) + ~x = 1
(x‧(y‧z)) ‧ ~x = 0
(d)
y ‧ (x + (y + z)) = y
y + (x‧(y‧z)) = y(e)(e)
(x + (y + z)) + ~y = 1(x‧(y‧z)) ‧ ~y = 0(f)
(x + (y + z)) + ~z = 1(x‧(y‧z)) ‧ ~z = 0(g)
~((x + y) + z) ‧ x = 0~((x‧y)‧z) + x = 1(h)
~((x + y) + z) ‧ y = 0~((x‧y)‧z) + y = 1(i)
~((x + y) + z) ‧ z = 0~((x‧y)‧z) + z = 1(j)
(x + (y + z)) + ~((x + y) + z) = 1(x ‧ (y ‧ z)) ‧ ~((x ‧ y) ‧ z) = 0(k)
(x + (y + z)) ‧ ~((x + y) + z) = 0(x + (y + z)) ‧ ~((x + y) + z) = 0(l)

Discussions