2.

BOOLEAN ALGEBRA
1) Long ago Aristotle [Father of logic] constructed a complete system of formal logic and wrote six famous
works on the subject, contributing greatly to the organization of man’s reasoning.
2) George Boole is considered the ‘father of symbolic logic’/ ‘father of Boolean Algebra’
3) Books revolutionary paper “An investigation of the laws of the though’ was published in 1854 which led
to the development of new system the algebra of logic ‘BOOLEAN ALGEBRA’.
4) He developed logic as an abstract mathematical system consisting of defined terms, operations and rules
for using the operations.
5) Boolean algebra is useful in designing logic circuits used by processors of computer system.
6) Boolean Algebra had no practical applications until 1938, when Claude Shannon of Bell telephone
Laboratories used it to analyze telephone switching circuits.
7) Shannon wrote a paper titled ‘A Symbolic Analysis of Relay Switching Circuits’.
8) In this paper he applied Boolean Algebra to solve relay problems.
9) Boolean algrbra is also called as ‘switching Algebra’.

Important terms with definitions:

1) Logic: Logic refers to the science that studies the principles of correct reasoning. Logic comes from the
Greek word ‘Logos’ which means ‘sentence’, ‘reason’, ‘rule’, ‘ratio’.
2) Boolean Algebra: It is an algebra which deals with binary number system ( O &1) used for designing
logic circuits used by processors of computer system.
3) Logical statements / Truth functions : Statements or functions which can be determined to be true or
false are called logical statements or truth functions.
4) Truth values : Values true (1) or False ( D) are called truth values.
5) Logical variables/ binary valued variables: The variables which can store these truth values (i.e. O
(false) or (false) are called logical variables or binary valued variables.
6) Binary decisions: The decision which results into either true (1) or false (o) is called as binary decision.
7) Algebraic expressions: Algebraic variables like a,b,c, x, etc., are combined with the help of mathematical
operators like +, +, x, % to form algebraic expressions. Ex : 2xA + b/3 etc.,
8) Logical operations : Specific operations that can be applied on truth functions are called as logical
operations
9) Logical function/Compound statement : Logical statement or truth functions are combined with the help
of logical operators like AND, OR and NOT to form a compound statement or logical function.
Ex : X NOT Y AND Z

LOGICAL OPERATORS
1) Truth Table : It is a table which represents all the possible values of logical variables / statements
along with all possible results for the given combination of values.
2) Tautology : If result of any logical statement or expression is always TRUE or 1, is called
Tautology.
3) Fallacy : If result of any logical statement or expression is always FALSE or O, is called Fallacy.
4) Postulates of Boolean Algebra: The fundamental laws of Boolean Algebra are called as the
Postualtes of Boolean Algebra.

5) Principle of duality: It states that, replacing of

(i) Each OR sign(+) with an AND sign (.)
(ii) Each AND sign(.) with an OR sign (+)
(iii) Each 0 with 1 and 1 with 0
Boolean Algebra Rules

5)Proof by perfect induction: It is method of proving Boolean theorems by substituting all possible
values of the varaibles.
6) DeMorgan’s Theorem: a) ̅̅̅̅̅̅̅̅
𝑿 + 𝒀=𝑿. ̅𝒀
̅ b) ̅̅̅̅̅
𝑿. 𝒀=𝑿̅ +𝒀
̅
Applications: (i) De Morgan;s theorem is useful in implementation of basic gate operations with
NAND and NOR gates which are viable in IC form.
(ii) It is used in simplification of Boolean expressions.
(iii) These laws are applied to text searching using operators like AND, OR and NOT.
(iv) It is generally used for mathematical duality.

Derivation of Boolean Expressions

1) Literal: It is a single variable within a term which may or may not be complemented.
2) Minterms(m): It is product of all the literals with or without the bar within the logic system.
Ex: X.Y
3) Maxterm(M): It is the sum of all the literals with or without bar within the logic system. Ex: X+Y
4) Two types of standard forms of expressions/Canonical expression: (a) Sum of Products (SOP)
(b) Product of Sum (POS)
5) Canonical Expression: Boolean Expression composed either of minterms or maxterms is refereed
as Canonical expression.
6) Canonical SOP form(Ʃ): Boolean expression is represented purely as sum of minterms, it said to be
̅.Z)
in canonical SOP form. Ex: (X.Y.Z)+(X.𝒀
7) Canonical POS form (Π): Boolean expression is represented purely as product of maxterms, it said to
̅+Z)
be in Canonical POS form. Ex: (X+Y+Z).(X+𝒀
8) Karnaugh Map (K-Map): It is a graphical display of the fundamental product in a truth table.
9) Map Rolling: Its rolling the map so that its left edges are touching right edges and top edges are
touching bottom edges.
10) 2,3,4 variables general SOP K-Map
2 varaible K-Map 3 varaible K-Map

4 varaible K-Map
11) 2,3,4 variables general POS K-Map 3 varaible K-Map
2 varaible K-Map

4 varaible K-Map

ASSIGNMENT

One mark questions

1. What is another name of Boolean algebra?
2. What do you understand by the term truth value?
3. What do you understand by the term truth function?
4. What do you meant by binary valued variables?
5. What do you understand by logic function?
6. Give examples for logic function.
7. What is meant by tautology and fallacy?
8. Prove the 1+Y is a tautology and 0.Y is a fallacy.
9. Name the three logical operators.
10. What is a truth table? What is its significance?
11. What is NOT operator?
12. Write Venn diagram for NOT operator.
13. Write the truth table for NOT operator.
14. What is OR operator?
15. Write Venn diagram for OR operator.
16. Write the truth table for OR operator.
17. What is AND operator.
18. Write Venn diagram for AND operator.
19. Write the truth table for AND operator.
20. State indempotence law.
21. Prove indempotence law using truth table.
22. Draw logic diagram to represent indempotence law.
23. State Involution law.
24. Prove Involution law using truth table.
25. Draw logic diagram to represent Involution law.
26. State Complementarity law.
27. Prove Complementarity law using truth table.
28. Draw logic diagram to represent Complementarity law.
29. State Commutative law.
30. Prove Commutative law using truth table.
31. Draw logic diagram to represent Commutative law..
32. State Associative law.
33. Prove Associative law using truth table.
34. Draw logic diagram to represent Associative law.
35. State Distributive law.
36. Prove Distributive law using truth table.
37. Draw logic diagram to represent Distributive law.
38. Prove that X+XY =X (Absorption law)
39. Prove that X(X+Y)=X (Absorption law)
40. Draw logic diagram to represent Absorption law.
41. Prove that XY + XY ̅=X
42. Prove that (X+Y) (X+Y ̅) = X
43. Prove that X+X ̅ Y = X+Y
44. What is minterm?
45. Find the minterm for XY +Z.
46. What is a maxterm?
47. Find the maxterm for X+Y ̅+Z.
48. What is the canonical form of Boolean expression?
49. Give an example for a Boolean expression in the sum of minterms form.
50. Give an example for a Boolean expression in the product of minterms form.

Two marks questions

1. Prove algebraically that (X+Y) (X+Z) = X+YZ
2. ̅Y = X+Y
Prove algebraically that X+X
3. ̅ B = A+B
Use duality theorem to derive another Boolean relation from: A+A
4. What would be complement of the following:
 ̅ (𝐁𝐂̅ + 𝐁
(a) 𝐀 ̅ 𝐂)
(b) 𝐀𝐁̅ + 𝐂̅ 𝐃
̅
(c) XY +𝐘̅Z + Z𝐙̅
(d) X+ 𝐗̅Y + 𝐗̅ 𝐙̅
5. What are the fundamental products for each of the input words. ABCD = 0010, ABCD=
110, ABCD = 1110. Write SOP expression.
6. A truth table has output 1 for each of these inputs.
7. Construct a Boolean function of three variables X, Y and Z that has an output1 when
exactly two of X, Y and Z are having values 0, and an output 0 in all other cases.
8. Construct a truth able for three variables A,B and C that will have an output 1 when XYZ=
100, XYZ = 101, XYZ = 110 and XYZ = 111. Write the Boolean expression for logic network
in SOP form.
9. Convert the following expressions to canonical Product –of-Sum form:
(a) (A+C) (C+D)
(b) A(B+C) (C̅+D ̅)
(c) (X+Y) (Y+Z) (X+Z)
10. Convert the following expressions to canonical Sum of Product form:
(a) (X+ ̅
XY +X̅ Z̅)
(b) YZ + ̅
XY
(c) AB ̅ +C̅)
̅ (B
11. Draw Karnaugh maps for the following expressions:
12. Draw a general K-map for four variables A,B, C and D.
13. Give the expression in four variables, draw the K-map for the function:
(a) m2+m3+m5+m7+m9+m11+m13
(b) m0+m2+m4+m8+m9+m10+m11+m12+m13
14. Draw the K- map for the function in three variables given below.
(a) m0+m2+m3+m5+m7
(b) m1+m2+m3+m5+m7
15. Write S-O-P expression corresponding to the function F in the following truth table and
draw the logic gate diagram (use OR and AND gates)

A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
Three marks questions
1. State and prove any three theorems of Boolean algebra.
2. State and prove associative law of addition and multiplication.
3. State and prove De Morgam’s theorems by the method perfect induction.
4. Obtain the minterm expression for the Boolean function F= A+B ̅C.
5. Explain with an example how to express a Boolean function in its sum-of- products form.
6. Explain with an example how to express a Boolean function in its product –of- sum form.
7. Construct a truth table for minterms and maxterms for three variables and designate the
terms.
8. Using basic gates, construct a logic circuit for the Boolean expression
̅ +Y), (X+Z), (Y+Z)
(𝐗
9. Simplify the following Boolean expressions and draw logic circuit diagrams of the
simplified expressions using only NAND gates.
̅ BC+𝐀
(a) 𝐀 ̅ B 𝐂̅ +A 𝐁 ̅ 𝐂̅ + A𝐁
̅C
̅ C+ 𝐀
(b) 𝐀 ̅ B+ A 𝐁̅ 𝐂̅ + BC
(c) (𝐀𝐁𝐂). (𝐀𝐁𝐂̅) + 𝐀 ̅ BC
̅ BC+A𝐁
(d) 𝐀 ̅ 𝐂̅+ABC+AB𝐂̅
(e) (A+B+C) (A+𝐁 ̅ + 𝐂̅)(A+𝐁 ̅ +C)
10. For a four variable map in w,x,y and z draw the subcubes for
(a) WX𝐘 ̅ (b) WX (c) XY𝐙̅ (d) Y
11. Convert the following product-of-sums form into its corresponding sum-of-products
form using write the truth table.. F(x,y,z) = π (2,46,7)
̅̅̅̅̅̅̅̅̅̅̅̅
(a) Reduce the following Boolean expression to the simplest form : [B+C. (𝐀𝐁 + 𝐀𝐂)]
(b) Given : F(x,y,z) =(1, 3,7) then prove that F’ (x,y,z) = π(0,2,4,5,6)

Five marks questions

1. Using maps, simplify the following expressions in four variables W, X, Y and Z.
a. m1+m3+m5+m6+m7+m9+m11+m13
b. m0+m2+m4+m8+m9+m10+m11+m12+m13
2. For the Boolean function F and F’ in the truth table, find the following:
a. List the minterms of the functions F and F’
b. Express F and F’ in sum of minterms in algebraic form.
c. Simplify the functions to an expression with a minimum number of literals.
A B C F F’
0 0 0 0 1
0 0 1 0 1
0 1 0 1 0
0 1 1 1 0
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 0
3. State and prove De Morgan’s theorems algebraically.
4. Find the compliment of F = X+YZ, then show F.F’ =0 and F+F’=1.
5. (a) State the two Absorption laws of Boolean algebra. Verify using truth table.
 (b) Simplify using laws of Boolean algebra. At each step state clearly the law used for
simplification. F(x,y,z)=x.y+x.z+x.y.z
6. Given the Boolean function F(x,y,z) = (0, 2, 4, 5, 6). Reduce it using Karnuagh map
method.
7. (a) State the two complement properties of Boolean algebra. Verify using the truth
tables. (b) X (y̅z̅ +yz)
8. Given the Boolean function F(A,B, C, D) =(5,6,7,8,9,10,14). Use Karnagugh’s map to
reduce the function F using SOP form. Write a logic gate diagram for the reduced SOP
expression.
9. Given: F(A,B,C,D) = (0, 2, 4,6, 8,10, 14). Use Karnaugh map to reduce the function F
using POS form. Write a logic gate diagram for the reduced POS expression.
10. Use Karnaugh map to reduce the given function using SOP form. Draw the logic gate
diagrams for the reduced SOP expression. You may use gates with more than two
inputs. Assume that the variables and their complements are available as inputs.
11. Given the Boolean function F(A,B,C,D) = (0,4,8,9,10,11,12,13,15).
Reduce it by using Karnaugh map.