Review: Boolean Algebra, Truth Tables, Gates
Boolean Algebra Axioms
1. Binary field: 𝐵 = 0 𝑖𝑓 𝐵 ≠ 1 𝑎𝑛𝑑 𝐵 = 1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
2. NOT (denoted by ¬/ −): �̅� = 0 𝑖𝑓 𝑋 = 1 𝑎𝑛𝑑 �̅� = 1 𝑖𝑓 𝑋 = 1
3. AND (𝐝𝐞𝐧𝐨𝐭𝐞𝐝 𝐛𝐲 ∙/∗) : 𝑋 ∙ 𝑌 = 1 𝑖𝑓 𝑋 = 𝑌 = 1 𝑎𝑛𝑑 𝑋 ∙ 𝑌 = 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
4. OR (denoted by +): 𝑋 + 𝑌 = 0 𝑖𝑓 𝑋 = 𝑌 = 0 𝑎𝑛𝑑 𝑋 + 𝑌 = 1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
Notes:
The operators AND, OR, NOT are universal or functionally complete in that they can be used to
express all Boolean functions
Order of precedence is NOT, AND, OR.
The symbols used to denote these operations (e.g. + for OR) are not universally standard. You
may see some different notations such as ∨ for OR and ^ for AND
Principle of Duality
If 0 and 1 and the operators ∙ (AND) and +(OR) are interchanged, the resulting statement is correct and
equivalent to the original.
Theorems
Name OR (+) Version AND (∙) Version
Idempotent 𝐴 + 𝐴 = 𝐴 𝐴 ∙ 𝐴 = 𝐴
Commutative 𝐴 + 𝐵 = 𝐵 + 𝐴 𝐴 ∙ 𝐵 = 𝐵 ∙ 𝐴
Associative (𝐴 + 𝐵) + 𝐶 = 𝐴 + (𝐵 + 𝐶) (𝐴 ∙ 𝐵) ∙ 𝐶 = 𝐴 ∙ (𝐵 ∙ 𝐶)
Distributive 𝐴 + (𝐵 ∙ 𝐶) = (𝐴 + 𝐵) ∙ (𝐴 + 𝐶) 𝐴 ∙ (𝐵 + 𝐶) = (𝐴 ∙ 𝐵) + (𝐴 ∙ 𝐶)
Identity 𝐴 + 0 = 𝐴 𝐴 ∙ 1 = 𝐴
Null 𝐴 + 1 = 1 𝐴 ∙ 0 = 0
Complement 𝐴 + �̅� = 1 𝐴 ∙ �̅� = 0
Double
Negation/Involution
(�̅�)̅̅ ̅̅̅ = 𝐴
Covering 𝐴 + (𝐴 ∙ 𝐵) = 𝐴 𝐴 ∙ (𝐴 + 𝐵) = 𝐴
Combining (𝐴 + 𝐵) ∙ (𝐴 + �̅�) = 𝐴 (𝐴 ∙ 𝐵) + (𝐴 ∙ �̅�) = 𝐴
Consensus (𝐴 + 𝐵) ∙ (�̅� + 𝐶) ∙ (𝐵 + 𝐶)
= (𝐴 + 𝐵) ∙ (�̅� + 𝐶)
(𝐴 ∙ 𝐵) + (�̅� ∙ 𝐶) + (𝐵 ∙ 𝐶)
= (𝐴 ∙ 𝐵) + (�̅� ∙ 𝐶)
DeMorgan’s (𝐴 + 𝐵̅̅ ̅̅ ̅̅ ̅̅ ̅) = �̅� ∙ �̅� (𝐴 ∙ 𝐵̅̅ ̅̅ ̅̅ ̅) = �̅� + �̅�
Truth Tables and Gates
Boolean functions can be evaluated with a truth table. Given a truth table, we can translate a Boolean
function to gates.
AND
A
B
OR
A
B
NOT
A
NAND
A
B
NOR
A
B
XOR
A
B
Notes:
By convention, a true state is also called on or 1 and a false state is also called off or 0 .
To Prove a Boolean Function:
1. Directly through theorems of Boolean algebra
2. Exhaustively by a truth table
X
X
X
X
X
X