Boolean algebra is an algebra that deals with binary variables and logic operations.
A truth table is a table of all possible combinations of the variables, showing the relation between the values that the variables may take and the result of the operation.
There are three basic logical operations:
-
AND \((\cdot)\): This operation is represented by a dot \((\cdot)\) or by the absence of an operator.
Truth table for AND operation,
\(x\) \(y\) \(x \cdot y\) \(0\) \(0\) \(0\) \(0\) \(1\) \(0\) \(1\) \(0\) \(0\) \(1\) \(1\) \(1\) -
OR \((+)\): This operation is represented by a plus \((+)\) sign.
Truth table for OR operation,
\(x\) \(y\) \(x + y\) \(0\) \(0\) \(0\) \(0\) \(1\) \(1\) \(1\) \(0\) \(1\) \(1\) \(1\) \(1\) -
NOT \(({}^{\prime})\): This operation is represented by a prime \(({}^{\prime})\) or an overline \((\overline{})\), also referred to as the complement operation, since it changes a \(1\) to \(0\) and a \(0\) to \(1\).
Truth table for NOT operation,
\(x\) \(x^{\,\prime}\) \(0\) \(1\) \(1\) \(0\)
For the operator precedence, expressions inside parentheses must be evaluated before all other operations. The next operation that holds precedence is the complement or NOT \((')\), and then follows the AND \((\cdot)\), and finally, the OR \((+)\).
Postulates and Theorems of Boolean Algebra
The Duality principle states that every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged. The dual of a Boolean algebraic expression is obtained by interchanging AND \((\cdot)\) and OR \((+)\) operators while complementing \(1\)’s and \(0\)’s.
| Postulates | Duality | |
|---|---|---|
| 1 | \(\displaystyle 0 \cdot 0 = 0\) | \(\displaystyle 1 + 1 = 1\) |
| 2 | \(\displaystyle 0 \cdot 1 = 0\) | \(\displaystyle 1 + 0 = 1\) |
| 3 | \(\displaystyle 1 \cdot 0 = 0\) | \(\displaystyle 0 + 1 = 1\) |
| 4 | \(\displaystyle 1 \cdot 1 = 1\) | \(\displaystyle 0 + 0 = 0\) |
| 5 | \(\displaystyle 0^{\prime} = 1\) | \(\displaystyle 1^{\prime} = 0\) |
| Theorems | Duality | |
|---|---|---|
| Associative | \(\displaystyle x + (y + z) = (x + y) + z\) | \(\displaystyle x \cdot (y \cdot z) = (x \cdot y) \cdot z\) |
| Commutative | \(\displaystyle x + y = y + x\) | \(\displaystyle x \cdot y = y \cdot x\) |
| Distributive | \(\displaystyle x \cdot (y + z) = x \cdot y + x \cdot z\) | \(\displaystyle x + (y \cdot z) = (x + y) \cdot (x + z)\) |
| Identity | \(\displaystyle x + 0 = x\) | \(\displaystyle x \cdot 1 = x\) |
| Annihilator | \(\displaystyle x + 1 = 1\) | \(\displaystyle x \cdot 0 = 0\) |
| Idempotence | \(\displaystyle x + x = x\) | \(\displaystyle x \cdot x = x\) |
| Absorption | \(\displaystyle x + x \cdot y = x\) | \(\displaystyle x \cdot (x + y) = x\) |
| Involution | \(\displaystyle \left(x^{\,\prime}\right)^{\prime} = x\) | |
| Complementation | \(\displaystyle x + x^{\,\prime} = 1\) | \(\displaystyle x \cdot x^{\,\prime} = 0\) |
| De Morgan | \(\displaystyle (x + y)^{\prime} = x^{\,\prime} \cdot y^{\,\prime}\) | \(\displaystyle \left(x \cdot y\right)^{\prime} = x^{\,\prime} + y^{\,\prime}\) |
| Consensus | \(\displaystyle x \cdot y + x^{\,\prime} \cdot z + y \cdot z = x \cdot y + x^{\,\prime} \cdot z\) | \(\displaystyle (x + y) \cdot \left(x^{\,\prime} + z\right) \cdot (y + z) = (x + y) \cdot \left(x^{\,\prime} + z\right)\) |
| Transposition | \(\displaystyle x \cdot y + x^{\,\prime} \cdot z = (x + z) \cdot \left(x^{\,\prime} + y\right)\) | \(\displaystyle (x + y) \cdot \left(x^{\,\prime} + z\right) = x \cdot z + x^{\,\prime} \cdot y\) |
| \(\displaystyle x + x^{\,\prime} \cdot y = x + y\) | \(\displaystyle x \cdot \left(x^{\,\prime} + y\right) = x \cdot y\) | |
| \(\displaystyle x \cdot y + x \cdot y^{\,\prime} = x\) | \(\displaystyle (x + y) \cdot \left(x + y^{\,\prime}\right) = x\) | |
| \(\displaystyle x \cdot y + x^{\,\prime} \cdot y \cdot z = x \cdot y + y \cdot z\) | \(\displaystyle (x + y) \cdot \left(x^{\,\prime} + y + z\right) = (x + y) \cdot (y + z)\) | |
| \(\displaystyle x \cdot F\left(x,\,x^{\,\prime},\,y,\,z,\,\dots\right) = x \cdot F\left(1,\,0,\,y,\,z,\,\dots\right)\) | \(\displaystyle x + F\left(x,\,x^{\,\prime},\,y,\,z,\,\dots\right) = x + F\left(0,\,1,\,y,\,z,\,\dots\right)\) | |
| \(\displaystyle x^{\,\prime} \cdot F\left(x,\,x^{\,\prime},\,y,\,z,\,\dots\right) = x^{\,\prime} \cdot F\left(0,\,1,\,y,\,z,\,\dots\right)\) | \(\displaystyle x^{\,\prime} + F\left(x,\,x^{\,\prime},\,y,\,z,\,\dots\right) = x^{\,\prime} + F\left(1,\,0,\,y,\,z,\,\dots\right)\) | |
| \(\displaystyle F\left(x,\,x^{\,\prime},\,y,\,z,\,\dots\right) = x \cdot F\left(1,\,0,\,y,\,z,\,\dots\right) + x^{\,\prime} \cdot F\left(0,\,1,\,y,\,z,\,\dots\right)\) | \(\displaystyle F\left(x,\,x^{\,\prime},\,y,\,z,\,\dots\right) = \left[x + F\left(0,\,1,\,y,\,z,\,\dots\right)\right] \cdot \left[x^{\,\prime} + F\left(1,\,0,\,y,\,z,\,\dots\right)\right]\) |
Boolean Functions
A Boolean function \(F\) described by an algebraic expression consists of binary variables, the constants \(0\) and \(1\), and the logic operation symbols. For a given value of the binary variables, the function can be equal to either \(1\) or \(0\).
A Boolean function \(F\) can be represented in a truth table. The number of rows in the truth table is \(2^n\), where \(n\) is the number of variables in the function. The binary combinations for the truth table are obtained from the binary numbers by counting from \(0\) through \(2^n - 1\).
For example, a Boolean function \(\displaystyle F = x + y^{\,\prime} \cdot z\)
\(F\) is equal to \(1\) if \(x\) is equal to \(1\) or if both \(y^{\,\prime}\) and \(z\) are equal to \(1\). \(F\) is equal to \(0\) otherwise. The complement operation dictates that when \(y^{\,\prime} = 0\), \(y = 1\).
The truth table for function \(F\),
\(x\) \(y\) \(z\) \(\displaystyle F = x + y^{\,\prime}z\) \(0\) \(0\) \(0\) \(0\) \(0\) \(0\) \(1\) \(1\) \(0\) \(1\) \(0\) \(0\) \(0\) \(1\) \(1\) \(0\) \(1\) \(0\) \(0\) \(1\) \(1\) \(0\) \(1\) \(1\) \(1\) \(1\) \(0\) \(1\) \(1\) \(1\) \(1\) \(1\)
When a Boolean expression is implemented with logic gates, each term requires a gate and each variable within the term designates an input to the gate. A literal is a single variable within a term, in complemented or uncomplemented form.
There is only one way that a Boolean function can be represented in a truth table. However, when the function is in algebraic form, it can be expressed in a variety of ways, all of which have equivalent logic.
By manipulating a Boolean expression according to the rules of Boolean algebra, it is sometimes possible to obtain a simpler expression for the same function and thus reduce the number of gates in the circuit and the number of inputs to the gate.
Complement of a Function
The complement of a function \(F\) is \(F^{\prime}\) and is obtained from an interchange of \(0\)’s for \(1\)’s and \(1\)’s for \(0\)’s in the value of \(F\). The complement of a function may be derived algebraically through De Morgan’s theorems.
De Morgan’s theorems can be extended to \(n\) variables,
\(\boxed{\left(A_1 + A_2 + A_3 + \cdots + A_n\right)^{\prime} = A_{1}^{\prime} \cdot A_{2}^{\prime} \cdot A_{3}^{\prime} \cdots A_{n}^{\prime}}\)
By applying the duality principle,
\(\boxed{\left(A_1 \cdot A_2 \cdot A_3 \cdots A_n\right)^{\prime} = A_{1}^{\prime} + A_{2}^{\prime} + A_{3}^{\prime} + \cdots + A_{n}^{\prime}}\)
The generalized form of De Morgan’s theorems states that the complement of a function \(F\) is obtained by interchanging AND \((\cdot)\) and OR \((+)\) operators and complementing \(({}^{\prime})\) each literal. In other words, take the dual of the function \(F\) and complement each literal.
For example, find the complement of function \(\displaystyle F = x^{\,\prime} \cdot y \cdot z^{\,\prime} + x^{\,\prime} \cdot y^{\,\prime} \cdot z\)
By applying the duality principle,
The dual of \(F\) is \(\displaystyle \left(x^{\,\prime} + y + z^{\,\prime}\right) \cdot \left(x^{\,\prime} + y^{\,\prime} + z\right)\)
Then complement each literal,
\(\displaystyle F^{\prime} = \left(x + y^{\,\prime} + z\right) \cdot \left(x + y + z^{\,\prime}\right)\)