Ch 6. Boolean Algebra and Combinatorial Circuits
6.2 Boolean Algebras
Note on Variable Naming
In Boolean algebra, variables such as [latex]x[/latex], [latex]y[/latex], [latex]z[/latex], [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], and [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] are all used interchangeably to represent Boolean values. Each variable denotes a logical condition or signal that can take on one of two values: 0 (false) or 1 (true). These symbols are chosen for clarity and context, and all follow the same Boolean laws and principles.
Boolean algebra is a mathematical structure that captures the logic of binary variables, which have values that are either true (1) or false (0). It is not just a set of rules, but a formal system with defined operations, identities, and laws. Understanding Boolean algebra allows IT professionals to design efficient circuits, optimize code, and reason about logical conditions in software and hardware.
A Boolean algebra is a set equipped with two binary operations, a unary operation, and two distinguished elements. This is typically a set [latex]B[/latex] equipped with the binary operations [latex]+[/latex] and [latex]\cdot[/latex], the unary operation [latex]\bar{\ }[/latex] or [latex]\neg[/latex], and the two distinguished elements [latex]0[/latex] and [latex]1[/latex]. They must satisfy the following Boolean axioms.
Axiom 6.1: Laws of Boolean Algebra
In any Boolean algebra, the following identities hold:
- Closure: For all [latex]a, b \in B[/latex], both [latex]a + b[/latex] and [latex]a \cdot b[/latex] are in [latex]B[/latex].
- Commutativity:
- [latex]a + b = b + a[/latex]
- [latex]a \cdot b = b \cdot a[/latex]
- Associativity:
- [latex]a + (b + c) = (a + b) + c[/latex]
- [latex]a \cdot (b \cdot c) = (a \cdot b) \cdot c[/latex]
- Distributivity:
- [latex]a \cdot (b + c) = (a \cdot b) + (a \cdot c)[/latex]
- [latex]a + (b \cdot c) = (a + b) \cdot (a + c)[/latex]
- Identity Elements:
- [latex]a + 0 = a[/latex]
- [latex]a \cdot 1 = a[/latex]
- Complement:
- [latex]a + \bar{a} = 1[/latex]
- [latex]a \cdot \bar{a} = 0[/latex]
In a Boolean algebra [latex]B[/latex], the lattice order is the relation [latex]\leq[/latex] on [latex]B[/latex] defined by
[latex]x \leq y[/latex] if and only if [latex]x = x \cdot y[/latex]
This order makes each element comparable with respect to how it behaves under the two binary operations.
This definition is used in the proof of the following theorem, which shows that the element [latex]\bar{a}[/latex] in Axiom 6.1 f) is unique.
Theorem 6.3: The Complement of an Element in a Boolean Algebra is Unique
Let [latex]a[/latex] be an element in a Boolean algebra. Then there exists a unique element [latex]\bar{a}[/latex] such that
- [latex]a + \bar{a} = 1[/latex]
- [latex]a \cdot \bar{a} = 0[/latex]
Proof
First, note that by the definition of [latex]\\ \bar{\ }[/latex], the element exists.
Next, we prove uniqueness. Let [latex]a[/latex] be an element in a Boolean algebra, and suppose there are two elements [latex]x[/latex] and [latex]y[/latex] such that
[latex]a + x = 1[/latex] and [latex]a \cdot x = 0 \quad[/latex]Assumption 1
[latex]a + y = 1[/latex] and [latex]a \cdot y = 0 \quad[/latex]Assumption 2
We want to show that [latex]x = y[/latex]. From Axiom 6.1 e) ii, Assumption 2, Axiom 6.1 d) i, Assumption, and Axiom 6.1 e) i:
[latex]x = x \cdot 1 = x \cdot (a + y) = x \cdot a + x \cdot y = 0 + x \cdot y = x \cdot y[/latex]
Thus, by the lattice order of the Boolean algebra, [latex]x \leq y[/latex]. Similarly,
[latex]y = y \cdot 1 = y \cdot (a + x) = y \cdot a + y \cdot x = 0 + y \cdot x = y \cdot x[/latex]
Thus, [latex]y \leq x[/latex]. Since [latex]x \leq y[/latex] and [latex]y \leq x[/latex], it follows that [latex]x = y[/latex]. Therefore, the complement [latex]\bar{a}[/latex] is unique.
[latex]\square[/latex]
Boolean algebra refers to the element [latex]\bar{a}[/latex] as the complement of [latex]a[/latex]. It also includes several useful identities that simplify expressions, as shown in the following theorem. These laws are essential for simplifying logic circuits and expressions.
Theorem 6.4
In any Boolean algebra, the following identities hold:
- Idempotent Laws:
- [latex]a + a = a[/latex]
- [latex]a \cdot a = a[/latex]
- Domination Laws:
- [latex]a + 1 = 1[/latex]
- [latex]a \cdot 0 = 0[/latex]
- Absorption Laws:
- [latex]a + (a \cdot b) = a[/latex]
- [latex]a \cdot (a + b) = a[/latex]
- Double Negation: [latex]\bar{\bar{a}} = a[/latex]
- 0 and 1 Laws:
- [latex]\bar{0} = 1[/latex]
- [latex]\bar{1} = 0[/latex]
- De Morgan’s Laws:
- [latex]\overline{a \cdot b} = \bar{a} + \bar{b}[/latex]
- [latex]\overline{a + b} = \bar{a} \cdot \bar{b}[/latex]
Proof
All these laws can be proved using Axiom 6.1.
[latex]\square[/latex]
Example 6.7
Simplify the Boolean expression [latex](a + b) \cdot (a + \bar{b}) \cdot (\bar{a} + b)[/latex].
Group the first two terms and do the following using Axioms 6.1 d) ii, 6.1 f) ii, and 6.1 e) i:
[latex](a + b) \cdot (a + \bar{b}) = a + (b \cdot \bar{b}) = a + 0 = a[/latex]
Group this result with the third term and do the following using Axioms 6.1 d) i, 6.1 f) ii, and 6.1 e) i:
[latex]a \cdot (\bar{a} + b) = a \cdot \bar{a} + a \cdot b = 0 + a \cdot b = a \cdot b[/latex]
Boolean algebra is closely related to set theory (see Section 4.1) as the following table shows:
| Boolean Algebra | Set Theory |
|---|---|
| [latex]a + b[/latex] | [latex]A \cup B[/latex] (union) |
| [latex]a \cdot b[/latex] | [latex]A \cap B[/latex] (intersection) |
| [latex]\bar{a}[/latex] | [latex]A^{c}[/latex] (complement) |
| [latex]0[/latex] | [latex]\emptyset[/latex] (empty set) |
| [latex]1[/latex] | [latex]U[/latex] (universal set) |
This analogy helps visualize Boolean operations using Venn diagrams and supports reasoning about logic in terms of sets.
The dual of a Boolean expression is formed by replacing AND ([latex]\cdot[/latex]) with OR ([latex]+[/latex]), OR ([latex]+[/latex]) with AND ([latex]\cdot[/latex]), [latex]0[/latex] with [latex]1[/latex], and [latex]1[/latex] with [latex]0[/latex].
Example 6.8
Consider the expression [latex](a + 0) \cdot 1 = a[/latex].
The dual of this expression is [latex](a \cdot 1) + 0 = a[/latex].
Finding the dual of Boolean expressions allows us to discover new theorems from previously proven ones. This is stated in the following theorem.
Theorem 6.5: Dual of a Boolean Theorem is Also a Theorem
If a Boolean identity is a theorem, then its dual is also a theorem.
Example 6.9
Consider the distributive law Axiom 6.1 d) i, which is
[latex]a \cdot (b + c) = (a \cdot b) + (a \cdot c)[/latex]
To form the dual, we replace [latex]\cdot[/latex] with [latex]+[/latex] and [latex]+[/latex] with [latex]\cdot[/latex] to obtain
[latex]a + (b \cdot c) = (a + b) \cdot (a + c)[/latex]
This is also a valid Boolean identity known as the dual distributive law.
Real-World Example 6.2: Access Control in a Smart Building
Imagine a smart building that controls access to different areas based on two conditions:
[latex]A[/latex]: The person has a valid access card.
[latex]B[/latex]: The person is on the approved guest list.
The system uses a Boolean expression to determine whether to unlock the door:
[latex](A + B) \cdot (A + \bar{B})[/latex]
This expression checks whether the person has a valid card or is on the guest list. It supports the following cases:
Case 1: A person has a valid card and is on the guest list
[latex]A = 1, B = 1 \rightarrow (1 + 1) \cdot (1 + 0) = 1 \cdot 1 = 1 \rightarrow[/latex] Access granted
Case 2: A person has a valid card but is not on the guest list
[latex]A = 1, B = 0 \rightarrow (1 + 0) \cdot (1 + 1) = 1 \cdot 1 = 1 \rightarrow[/latex] Access granted
Case 3: A person does not have a valid card but is on the guest list
[latex]A = 0, B = 1 \rightarrow (0 + 1) \cdot (0 + 0) = 1 \cdot 0 = 0 \rightarrow[/latex] Access denied
Case 4: A person has neither a valid card nor is on the guest list
[latex]A = 0, B = 0 \rightarrow (0 + 0) \cdot (0 + 1) = 0 \cdot 1 = 1 \rightarrow[/latex] Access denied
This Boolean expression ensures that only people with valid access cards are allowed in, regardless of guest status. It uses Boolean algebra to efficiently enforce security logic.
