Boolean algebra deals with binary variables and logic operations.
Binary Variables: Variables that can take only two values: 0 (false) or 1 (true).
Logical Operations:
AND (·): Output is 1 only if all inputs are 1. Alternatively, output is 0 if any of the inputs is 0.
OR (+): Output is 1 if any of the inputs is 1. Alternatively, output is 0 only iff all inputs are 0.
NOT ('): Output is the complement of the input.
AND, OR, NOT are the basic functions, but not the only functions. There are others such as NAND, NOR, Exclusive OR (XOR) and XNOR to name a few. For two variables there can be 16 different functions as listed at the end of this article.
A Boolean expression is a combination of Boolean variables and logic operations. Goal is to simplify these expressions to make digital circuits that are (1) chaper and (2) power efficient. Following Boolean algebra identities are used to simplify the expressions.
+--------+---------------+
| LAW |EXPRESSION |
+--------+---------------+
|Identity| x+0=x |
| | x·1=x |
+--------+---------------+
|Null | x+1=1 |
| | x·0=0 |
+--------+---------------+
|Idempot-| x+x=x |
|ent | x·x=x |
+--------+---------------+
|Complem-|x+x'=1 |
|ent |x·x'=0 |
+--------+---------------+
|Associa-|(x+y)+z=x+(y+z)|
|tive |(x·y)·z=x·(y·z)|
+--------+-----+---------+
|Distrib-|x(y+z)=xy+xz |
|utive |x+yz=(x+y)(x+z)|
+--------+-----+---------+
|De Morg-|(x+y)'=x'·y' |
|an |(xy)'=x'+y' |
+--------+---------------+
Simplify following Boolean expressions using Boolean algebra:
xy + xy′
(x + y)(x + y′)
zx + zx′y
xy + xy'
= x(y + y'); Complement
= x.1 ; Null
= x
(x + y)(x + y')
= xx + xy' + xy + yy'; Idempotent, complement
= x + x(y' + y) + 0 ; Complement
= x + x ; Idempotent
= x
zx + zx′y
= z(x + x'y)
= z(x + x')(x + y)
= z (1)(x + y)
= z (x + y)
In Boolean algebra we can check function output for all possible inputs. A truth table lists all inputs of a Boolean expression and evaluates its output. The truth table is the unique representation of a Boolean function. This is the procedure to make a truth table:ps to Write a Truth Table:
Determine the number of input variables in the Boolean function. n
There will be 2n possible input combinations for n variables.
Create a table with columns for each input variable. List all possible combinations of 0s and 1s for these variables.
Add a column for the output of the Boolean function. For each input combination, compute the output based on the given Boolean expression.
Example: Create truth table for the Boolean function: F(A, B) = A'+ A ⋅ B
Solution:
+---+---+---+---+-----+
|Sr.|A B| A'|A.B|AB+A'|
+---+---+---+---+-----+
| 0 |0 0| 1 | 0 | 1 |
| 1 |0 1| 1 | 0 | 1 |
| 2 |1 0| 0 | 0 | 0 |
| 3 |1 1| 0 | 1 | 1 |
+---+---+---+---+-----+
The above truth table can be summarized in one of the two ways:
List input combinations for which function value is 1: F(A, B) = ∑m(0, 1, 3)
List input combinations for which function value is 0: F(A, B) = ΠM(2)
Waveforms are graphs that show how signals change over time. Think that A and B are two switches that can be either ON (1) or OFF (0).
A: Starts OFF, turns ON at time 1, OFF at time 3, ON at time 5, and so on.
B: Alternates between ON and OFF every 1 unit of time.
A: ___|‾‾‾|___|‾‾‾|___|‾‾
B: _|‾|_|‾|_|‾|_|‾|_|‾|_|
Time: 0 1 2 3 4 5 6 7 8 9 10
A.B: _____|‾|_____|‾|_____|
A+B: _|‾‾‾‾‾|_|‾‾‾‾‾|_|‾‾‾‾
NAND: ‾‾‾‾‾|_|‾‾‾‾‾|_|‾‾‾‾‾|
NOR: ‾|_____|‾|_____|‾|____
XOR: _|‾‾‾|___|‾‾‾|___|‾‾‾|_
The AND gate waveform is ON (1) only when both A and B are ON. Otherwise, it’s OFF.
At time 2-3: Both A=1 and B=1 → Output is ON.
At time 6-7: Both A=1 and B=1 → Output is ON.
All other times: Either A or B is OFF → Output is OFF.
Figure out the correctness of OR, NAND, NOR and XOR waveforms in above figure.
Logic diagram is graphical representation of Boolean algebra functions. Writing Boolean expression from a logic diagram involves translating the gates into a mathematical expression. We follow these steps for this translation:
Locate the input variables (e.g. A, B, C) and the final output (e.g. F) of the circuit.
Start from the inputs and trace the path through each gate towards the output.
Write intermediate Boolean expressions for each gate. Use Boolean identities to simplify if possile.
Substitute the intermediate expressions into the final output expression.
Write Boolean expression for following logic diagram.
|\
A --| O--|‾‾\
|/ |AND)--+
B--------|__/ |
+-\‾‾‾\
)OR )-- F
+-/___/
C --|‾‾\ |
|AND)-------+
D --|__/
Inputs: A, B, C, D
Output: F
NOT gate input: A
NOT gate output: A'
Top AND gate inputs: A' and B
Top AND gate output: A'B
Lower AND gate inputs: C and D
Lower AND gate output: CD
OR gate inputs: A'B and CD
OR gate output: A'B + CD
Here is the labeled diagram showing the expression at each step:
|\ A'
A --| O--|‾‾\ A'B
|/ |AND)--+
B--------|__/ | F=A'B+CD
+-\‾‾\ |
)OR)-+
+-/__/
C --|‾‾\ CD |
|AND)-------+
D --|__/
Canonical forms are standard ways of writing Boolean functions. They are useful for analysis and simplification.
Sum of Products (SOP) form represents a Boolean function as sum of products. Alternatively, it is OR of AND terms.
Example: F(A, B, C) = A'B'C + BC' + AB'C
Canonical or Standard Sum of Products (SSOP) form is a special SOP where no input variable is missing in any of the product terms.
Example: F(A, B, C) = A'B'C + ABC' + AB'C
Product of Sums (POS) form represents a Boolean function as a product of sums. Alternatively, it is AND of OR terms.
Example: F(A, B, C) = (A + B + C') · (A' + B) · (A' + B' + C)
Canonical or Standard Product of Sums (SPOS) form is a special SOP where no input variable is missing in any of the sum terms.
Example: F(A, B, C) = (A + B + C') · (A' + B+C') · (A' + B' + C)
Identify the Variables: Determine all the variables used in the given Boolean expression.
Expand each term to ensure that each product term contains all the variables in either complemented or uncomplemented form.
Add missing variables in a term by using the identity X = X ⋅ (Y + Y’) to introduce the missing variable.
Distribute and expand the terms using Boolean algebra to ensure each term contains all the variables.
Write multiple entries only once due to identity X = X+X.
Express the final result as a sum of minterms. Each product term should match a minterm in the truth table.
Given SOP expression F(A, B) = A + B, convert it to Standard SOP form.
The variables are A and B.
A is missing B, expand to: A = A (B + B') → AB + AB'
B is missing A, expand to: B = B (A + A') → AB + A'B
Substitute back to original function: F (A, B) = (AB + AB') + (AB + A'B)
Final canonical form after removing duplicates: F (A, B) = AB + AB' + A'B
The expression is now in canonical form, where each term contains all variables.
Identify the Variables: Determine all the variables used in the given Boolean expression.
Expand each sum term to ensure that it contains all the variables in either complemented or uncomplemented form.
Add missing variables: Use the identity X ⋅ X' = 0 to introduce the missing variable in a term.
Distribute and expand: Apply Boolean algebra rules to ensure each sum term includes all variables.
Write multiple entries only once: Avoid redundant expressions using the identity X = X ⋅ X.
Express the final result as a product of maxterms: Each sum term should match a maxterm in the truth table.
Given the POS expression F (A, B) = A ⋅ B, write it in canonical form.
The variables are A and B.
A is missing B, expand to: A = A + B⋅B' → (A+B)(A+B')
B is missing A, expand to: B = B+AA' → (A+B)(A'+B)
Substitute back to original function: F (A, B) = (A+B)(A+B')(A+B)(A'+B)
Final canonical form after removing duplicates: F (A, B) = (A+B)(A+B')(A'+B)
Now, each term contains all variables, making it a canonical POS form.
A minterm is a product term in which each variable appears once, either complemented or uncomplemented.
A minterm is a special Boolean function.
It is 1 for one combination of inputs and 0 for all other combinations.
For n variables, there can be 2^n different minterms.
A truth table can be written in compact form as sum of minterms.
Following are 4 minterms for two variable function F(A, B):
|A B | m0 | m1| m2|m3 |
| |A'B'|A'B|AB'|AB |
+----+----------------+
|0 0 | 1 | 0 | 0 | 0 |
|0 1 | 0 | 1 | 0 | 0 |
|1 0 | 0 | 0 | 1 | 0 |
|1 1 | 0 | 0 | 0 | 1 |
Write following function as sum of minterms:
|A B | F |
+----+---+
|0 0 | 1 |
|0 1 | 0 |
|1 0 | 1 |
|1 1 | 0 |
F(A, B) = m0 + m2
Also written as,
F(A, B) = ∑m(0, 2)
Or as,
F(A, B) = A'B' + AB'
A maxterm is a sum term in which each variable appears once, either complemented or uncomplemented.
Each maxterm corresponds to a unique combination of inputs that makes the function output 0.
A truth table can be written in compact form as product of Maxterms.
Following are 4 maxterms for a two variable function F (A, B):
|A B |M0 | M1 | M2 | M3 |
| |A+B|A+B'|A'+B|A'+B'|
+----+---+----+----+-----+
|0 0 | 0 | 1 | 1 | 1 |
|0 1 | 1 | 0 | 1 | 1 |
|1 0 | 1 | 1 | 0 | 1 |
|1 1 | 1 | 1 | 1 | 0 |
Write following function as product of maxterms:
|A B | F |
+----+---+
|0 0 | 1 |
|0 1 | 0 |
|1 0 | 1 |
|1 1 | 0 |
F(A, B) = M1 · M3
Often written as,
F(A, B) = ΠM(1, 3)
Or as,
F(A, B) = (A+B')(A'+B')
Minterms and maxterms are complementary.
The minterms that are not present in the SOP form correspond to the maxterms in the POS form, and vice versa.
Example:
POS: F(A, B) = m1 + m3 = A'B + AB
SOP: F(A, B) = M0 · M2 = (A + B)(A' + B)
Express the Boolean function F(A, B, C) = Σm(1, 3, 5, 7) as product of maxterms.
The maxterms are the input combinations where the function outputs 0. Since there are 2ⁿ possible combinations for n variables, the maxterms are those not included in the minterms. If the minterms are 1, 3, 5, 7, the maxterms are 0, 2, 4, 6.
Each maxterm number corresponds to a binary representation. For example, for 3 variables (A, B, C):
Maxterm 0 → 000
Maxterm 2 → 010
Maxterm 4 → 100
Maxterm 6 → 110
For each maxterm, write the corresponding Boolean expression:
If the binary digit is 0, write the variable as it is (e.g., A).
If the binary digit is 1, write the complement of the variable (e.g., A').
Combine the variables with OR (+) operators.
Combine the Maxterms with AND (·) Operators. The final expression is the product (AND) of all the maxterms.
Here is the final expression for given example:
[0 0 0][0 1 0][1 0 0][1 1 0]
F = (A+B+C)(A+B'+C)(A'+B+C)(A'+B'+C)
For two variables there can be 24 = 16 different Boolean functions.
|AB|F0F1F2 F3F4F5 F6F7F8|
+--+--------------------+
|00|0 0 0 0 0 0 0 0 1 |
|01|0 0 0 0 1 1 1 1 0 |
|10|0 0 1 1 0 0 1 1 0 |
|11|0 1 0 1 0 1 0 1 0 |
|AB|F9 F10F11F12 F13F14F15|
+--+--------------------- +
|00|1 1 1 1 1 1 1 |
|01|0 0 0 1 1 1 1 |
|10|0 1 1 0 0 1 1 |
|11|1 0 1 0 1 0 1 |
F0: Constant 0
Output is always 0.
Expression: F(A, B) = 0
F1: AND
Output is 1 only if both A and B are 1.
Expression: F(A, B) = A · B
F2: Inhibition (A and not B)
Output is 1 if A is 1 and B is 0.
Expression: F(A, B) = A · B'
F3: A
Output is the same as A.
Expression: F(A, B) = A
F4: Inhibition (B and not A)
Output is 1 if B is 1 and A is 0.
Expression: F(A, B) = A' · B.
F5: B
Output is the same as B.
Expression: F(A, B) = B.
F6: XOR (Exclusive OR)
Output is 1 if A and B are different.
Expression: F(A, B) = A ⊕ B = A'B + AB'.
F7: OR
Output is 1 if at least one of A or B is 1.
Expression: F(A, B) = A + B.
F8: NOR (Not OR)
Output is 1 only if both A and B are 0.
Expression: F(A, B) = (A + B)'.
F9: XNOR (Equivalence)
Output is 1 if A and B are the same.
Expression: F(A, B) = A ⊙ B = A'B' + AB.
F10: NOT B
Output is the complement of B.
Expression: F(A, B) = B'.
F11: Implication (B implies A)
Output is 1 unless B is 1 and A is 0.
Expression: F(A, B) = B' + A.
F12: NOT A
Output is the complement of A.
Expression: F(A, B) = A' .
F13: Implication (A implies B)
Output is 1 unless A is 1 and B is 0.
Expression: F(A, B) = A' + B.
F14: NAND (Not AND)
Output is 1 unless both A and B are 1.
Expression: F(A, B) = (A · B)' .
F15: Constant 1
Output is always 1.
Expression: F(A, B) = 1.
Simplify using Boolean algbra: a) (A + B)′(A′ + B′)′ ; (b) y(wz′ + wz) + xy
Obtain the truth table of the function: F = xy + xy′ + y′ z
Use Boolean algebra to simplify following expression: a) ABC + A′B′C + A′BC + ABC′ + A′B′C′; b) (A + C + D)(A + C + D′)(A + C + D)(A + B′)
Given the Boolean function F = xy + x′y′ + y′z. Implement it using a) AND, OR, NOT; b) OR, NOT; c) AND, NOT
Express the function F(A, B, C) = (A' + B)(B' + C) as: (a) Sum of minterms; (b) Product of Maxterms.
Digital Circuit Design: Simplifying Boolean expressions reduces the number of logic gates required.
Boolean algebra provides a framework for analyzing and simplifying logical expressions.
Minterms and maxterms are essential for representing Boolean functions in canonical forms.
Understanding these concepts is crucial for designing efficient digital systems.