CBSE Class 12 Computer Science Boolean Algebra Worksheet Set 01

Boolean algebra

Boolean algebra:- a modern algebra which uses the set of numbers 0 and 1,the logic numbers used to solved logic problems.

Binary decision:-. The decision which results into yes or no. Also called logical statements or truth function.

Truth table:- a table representing all possible input-output combinations for a given logical problem/expression.

Tautology:-a Boolean expression that always results in true or 1.

Fallacy:-a Boolean expression that always results in false or 0.

Cononical expression :- a Boolean expression having all minterms or maxterms.

Minterm:-product of all the literals(with or without the bar) within the logic system.

Maxterm:-sum of all the literals(with or without the bar) within the logic system.

Karnaugh Map:- it is a graphical representation of the truth table of the given expression.

Logic Gates

Logic gates serve as the building blocks to digital logic circuits using combinational logic. We're going to consider the following gates: NOT gates (also called inverters), AND gates, OR gates, NAND gates, NOR gates, XOR gates, and XNOR gates. 

We'll also discuss the concept of gate deltay. 

Unit - IV

Chapter 13: Boolean Algebra

Boolean Algebra Theory

Boolean Algebra is a branch of mathematics dealing with the values 0 and 1, which are the logical values used for solving reasoning and decision-making problems.

A decision that only yields a yes or no outcome is called a binary decision. It is also referred to as a truth function or a logical statement.

A truth table is a structured layout that lists every possible combination of inputs and their corresponding outputs for a logical expression.

A Boolean expression that consistently yields a value of 1 or true under all conditions is known as a tautology.

A fallacy is a Boolean expression that always evaluates to 0 or false.

An expression in Boolean algebra is canonical when every single term contains all the variables of the system in either their complemented or uncomplemented form.

A minterm is the logical product of all system variables, whether inverted or not.

A maxterm represents the logical sum of all available variables in the system, with or without inversion.

A Karnaugh Map, or K-Map, serves as a visual diagram representing a truth table to simplify Boolean functions.

Logic Gates

Digital logic circuits rely on logic gates as their fundamental constructing components. In this guide, we look at several standard gates: NOT, AND, OR, NAND, NOR, XOR, and XNOR gates. Additionally, we will touch upon the concept of delay in logic gates.

NOT Gates

A NOT gate, frequently called an inverter, is characterized by having exactly one input line and one output line. Its schematic symbol features a triangle pointing to a small circle on the right side, where the bubble signifies inversion.

AND2 Gates

An AND2 gate is designed with two input bits and a single output bit. The number 2 in the subscript denotes the input count; consequently, a three-input version is called an AND3 gate. The gate produces an output of 1 if, and only if, all of its inputs are set to 1. In any other scenario, the output is 0.

OR2 Gates

OR2 gates have two bits of input and a single bit of output. The subscript, 2, indicates how many inputs this OR gate has. For example, OR3 gates have 3 inputs. The output of OR2 gate is 0 only if both inputs are 0. Otherwise, the output is 1.

Solved Questions

Question 1. State the principal of duality in Boolean algebra.
Answer: The principle of duality asserts that we can obtain a new valid Boolean equation from any existing one. This is achieved by applying three simple conversions:
(i) Swap every OR operator (+) with an AND operator (.).
(ii) Swap every AND operator (.) with an OR operator (+).
(iii) Swap all logical constants, converting 1 to 0 and 0 to 1.
In simple words: If you have a true logical formula, you can make a new true one by swapping ANDs with ORs, and 0s with 1s.

Exam Tip: Remember that duality does not mean taking the complement of variables; you only change the operators (+ and .) and identity elements (0 and 1) while keeping the literal states exactly as they are.

Question 2. Define the following terms: (a) Logical constant (b) Logical variable (c) Binary valued quantity (d) Boolean literal
Answer:
(a) Logical constant: These are the fixed logical states, representing either true (1) or false (0).
(b) Logical variable: A placeholder or symbol that is capable of holding logical values, such as true or false.
(c) Binary valued quantity: Any entity or variable that is restricted to taking exactly one of two potential outcomes, typically true or false.
(d) Boolean literal: This refers to a single variable in either its direct form (like \( X \)) or its inverted form (like \( \bar{Z} \)).
In simple words: These are the basic parts of logic. Constants are fixed values, variables hold values, binary quantities have only two choices, and literals are the variables or their opposites.

Exam Tip: When defining a literal, always emphasize that it includes both the variable itself and its complement, as students often forget to mention the complemented state.

Question 3. State Demorgan’s laws.
Answer: De Morgan's First Law states that the complement of a sum is equal to the product of the complements: \[ \overline{X + Y} = \overline{X} \cdot \overline{Y} \] De Morgan's Second Law states that the complement of a product is equal to the sum of the complements: \[ \overline{X \cdot Y} = \overline{X} + \overline{Y} \]
In simple words: De Morgan's laws show how to break a negation bar over an addition or multiplication. Adding flips to multiplying, and multiplying flips to adding, when you break the bar.

Exam Tip: To easily remember De Morgan's laws, use the phrase: 'break the line, change the sign'. This prevents mix-ups with signs during algebraic simplification.

Question 4. Why are AND and NOR gates called Universal Gates?
Answer: NAND and NOR gates are highly cost-effective and simpler to manufacture. Furthermore, any standard logical operation, such as AND, OR, and NOT, can be fully constructed using only these gates. For this reason, NAND and NOR gates are known as universal gates.
In simple words: NAND and NOR gates are called universal because you can build any other kind of logic gate using only them.

Exam Tip: Even if the question contains a typo (like AND instead of NAND), answer it correctly by referring to NAND and NOR gates as the universal logic blocks.

Question 5. Given the following truth table, derive a sum of product (SOP) and product of sum (POS) form of Boolean expression from it:

Answer: In SOP form, we identify the rows where the output is 1: \[ F = \sum(1,2,5,7) = \overline{X}\overline{Y}Z + \overline{X}Y\overline{Z} + X\overline{Y}Z + XYZ \] In POS form, we identify the rows where the output is 0: \[ F = \prod(0,3,4,6) = (X+Y+Z)(X+\overline{Y}+\overline{Z})(\overline{X}+Y+Z)(\overline{X}+\overline{Y}+Z) \]
In simple words: For Sum of Products (SOP), look at the rows where output is 1 and write them with ANDs. For Product of Sums (POS), look at the rows where output is 0 and write them with ORs.

Exam Tip: In SOP, a 0 is written as a complemented variable (e.g., \bar{X}) and 1 is uncomplemented. In POS, it is the exact opposite: 0 is uncomplemented and 1 is complemented.

Question 6. Prove that X.(X+Y)=X by truth table method.
Answer: We construct the truth table as follows:

From this truth table, the column for \( X \) and the column for \( X \cdot (X+Y) \) have identical values for all input combinations. This verifies that \( X \cdot (X+Y) = X \).
In simple words: By making a table of all combinations, we see that the output column for X.(X+Y) matches the column for X exactly.

Exam Tip: Always state a clear concluding sentence after drawing the truth table, explaining that the columns are identical, to secure full marks.

Question 7. Prove that X.(X+Y)=X by algebric method
Answer: We start with the Left-Hand Side (LHS) of the expression: \[ \text{LHS} = X \cdot (X + Y) \] Applying the distributive law: \[ = X \cdot X + X \cdot Y \] Since \( X \cdot X = X \) (Idempotent Law): \[ = X + X \cdot Y \] Factoring out \( X \) using the distributive property: \[ = X \cdot (1 + Y) \] Since \( 1 + Y = 1 \) (Dominance Law): \[ = X \cdot 1 \] Since \( X \cdot 1 = X \) (Identity Law): \[ = X = \text{RHS} \] Hence proved.
In simple words: We multiply X into the parentheses to get X.X + X.Y. Since X.X is just X, we get X + X.Y. Factoring out X leaves X.(1 + Y), and since 1 + Y is 1, the final answer is X.

Exam Tip: When proving identities algebraically, write the name of the law used (such as Idempotent or Distributive Law) next to each step so the examiner knows your reasoning.

Question 8. State the distributive laws of Boolean algebra. How are they different from distributive laws of ordinary algebra.
Answer: The distributive laws of Boolean algebra are given by:
(i) \( X \cdot (Y + Z) = X \cdot Y + X \cdot Z \)
(ii) \( X + (Y \cdot Z) = (X + Y) \cdot (X + Z) \)

In ordinary algebra, only the first law \( X(Y+Z) = XY + XZ \) is valid for all real numbers. The second law, \( X + YZ = (X+Y)(X+Z) \), does not hold true in standard arithmetic, but is valid in Boolean algebra where variables are restricted to the binary values 0 and 1.
In simple words: Boolean algebra has two distributive rules. The first one is just like normal math, but the second one is special to logic and does not work in standard math.

Exam Tip: Be prepared to prove the second distributive law using a truth table, as it is a common follow-up question in exams due to how unique it is to Boolean algebra.

Question 9. In Boolean algebra, verify using truth table that (X + Y)’ = X’ Y’ for each X, Y in (0, 1).
Answer: We verify this with the following truth table:

The columns representing \( (X + Y)' \) and \( X' \cdot Y' \) have identical values. Thus, De Morgan's first theorem is verified.
In simple words: We can build a table with columns for both sides of the equation. Since the columns for (X+Y)' and X'Y' match perfectly, the statement is true.

Exam Tip: Make sure to clearly label each intermediate column (like X+Y, X', and Y') to show the examiner step-by-step how you constructed the final columns.

Question. State Demorgan’s laws. Verify one of the Demorgan’s laws using truth tables.
Answer: De Morgan's laws are:
1. First Law: \( \overline{X + Y} = \overline{X} \cdot \overline{Y} \)
2. Second Law: \( \overline{X \cdot Y} = \overline{X} + \overline{Y} \)

Let us verify the second law using a truth table:

Since the columns for \( (X \cdot Y)' \) and \( X' + Y' \) are identical, the second law is verified.
In simple words: De Morgan's laws show that the complement of a product is the sum of complements, and vice versa. The table confirms this by showing identical outputs.

Exam Tip: When verifying, highlight the two columns you are comparing to make the verification obvious to the examiner.

Question 10. Why are AND and NOR gates called Universal gates?
Answer: NAND and NOR gates are known as universal gates because they are easier to design and more economical to construct. Crucially, any other basic logic gates (such as NOT, AND, or OR) can be implemented using combinations of only NAND or only NOR gates.
In simple words: NAND and NOR gates are called universal gates because they can be used to make any other logic gates.

Exam Tip: Even if the question has a typo, ensure you explain that it is NAND and NOR gates that possess the universal property.

Question 11. By means of truth table, demonstrate the validity of the following Postulates / Laws of Boolean algebra: (a) Commulative law (b) Absorption law (c) Idempotent law
Answer: We verify each law step-by-step:

(a) Commutative Law:
(i) \( X + Y = Y + X \)

Since the columns for \( X+Y \) and \( Y+X \) are identical, \( X+Y = Y+X \) is proved.

(ii) \( X \cdot Y = Y \cdot X \)

Since the columns for \( X \cdot Y \) and \( Y \cdot X \) are identical, \( X \cdot Y = Y \cdot X \) is proved.

(b) Absorption Law:
(i) \( X + X \cdot Y = X \)

The columns for \( X \) and \( X + X \cdot Y \) are identical. Hence, \( X + X \cdot Y = X \) is proved.

(ii) \( X \cdot (X + Y) = X \)

The columns for \( X \) and \( X \cdot (X + Y) \) are identical. Hence proved.

(c) Idempotent Law:
(i) \( X + X = X \)

The columns for \( X \) and \( X + X \) are identical. Hence proved.

(ii) \( X \cdot X = X \)

The columns for \( X \) and \( X \cdot X \) are identical. Hence proved.
In simple words: By making truth tables for all three laws, we see that the output columns match the input columns exactly in every case, confirming that these rules are correct.

Exam Tip: When displaying proofs for laws like absorption or idempotency, do not skip rows even if they seem trivial. Drawing the full table guarantees you receive full marks.

Question 12. Obtain the simplified form of a boolean expression using Karnaugh map. F(u,v,w,x) = ∑ (0, 3, 4, 5, 7, 11, 13, 15)
Answer: Let the variables be \( u, v, w, x \). The K-map cell values are:

From this map, we can form:
1. Quad 1: Combining cells \( \{m_3, m_7, m_{11}, m_{15}\} \). This group reduces to \( wx \).
2. Quad 2: Combining cells \( \{m_5, m_7, m_{13}, m_{15}\} \). This group reduces to \( vx \).
3. Pair 1: Combining cells \( \{m_0, m_4\} \). This group reduces to \( \bar{u}\bar{w}\bar{x} \).

Summing these terms gives the simplified Boolean expression: \[ F = wx + vx + \bar{u}\bar{w}\bar{x} \]
In simple words: We place 1s in the K-map grid for the given numbers. We group these 1s into blocks of four (quads) and pairs to simplify the formula into a much shorter version.

Exam Tip: Always state the binary and literal labels for rows and columns clearly on the K-map to avoid grouping mistakes.

Question 13. Draw the logic circuit diagram for the following expression : Y = a b + b c + c a
Answer: The digital circuit diagram is constructed using three separate 2-input AND gates to compute the terms \( ab \), \( bc \), and \( ca \). The outputs of these three gates are then combined into a single 3-input OR gate to produce the final sum expression \( Y \).

In simple words: We draw three AND gates to multiply the pairs of letters together, and then connect their outputs to an OR gate that adds them up.

Exam Tip: Ensure that connection points (nodes) where lines branch off are marked with a small solid dot to indicate a proper electrical connection.

Question 14. Prepare a truth table for X Y Z + X Y
Answer: We construct the truth table for the given expression \( \overline{X}Y\overline{Z} + X\overline{Y} \):

In simple words: We list all eight combinations of 0s and 1s for X, Y, and Z. Then we find the values for their opposites and individual terms before adding them together.

Exam Tip: Double-check each step of inversion and product operations carefully. A single arithmetic error in one row can cost you full marks for the entire truth table.

Question 15. Write the equivalent expression for the following logic circuit :
Answer: The given logic circuit consists of three parallel branches whose outputs are combined using an OR gate:
1. The top AND-NOT gate combination processes inputs \( A \) and \( C \), producing \( (AC)' \).
2. The middle AND-NOT gate combination processes inputs \( B \) and \( A \), producing \( (BA)' \).
3. The bottom AND-NOT gate combination processes inputs \( B \) and \( C \), producing \( (BC)' \).

Summing these terms at the final OR gate gives: \[ F = (AC)' + (BA)' + (BC)' \]
In simple words: Each pair of inputs goes through a multiplication and an inversion, and then the three results are added together at the end.

Exam Tip: When tracing logic circuits, write down the intermediate expression at the output of each individual gate to avoid making mistakes in the final expression.

Question 16. Draw the circuit diagram for F = AB’C + C’B using NAND to NAND logic only.
Answer: By applying De Morgan's theorem double negation, we can transform the SOP expression \( AB'C + C'B \) into an all-NAND structure: \[ F = \overline{\overline{AB'C} \cdot \overline{C'B}} \] This translates directly to a first-level stage of two NAND gates (one 3-input gate and one 2-input gate) feeding their outputs into a final 2-input NAND gate.

In simple words: To use only NAND gates, we double-invert the equation. This allows us to build the circuit using two NAND gates at the start, connected to a third NAND gate at the end.

Exam Tip: Remember that a NAND gate is represented by an AND gate shape with a small bubble (inversion circle) at its output. Leaving out the bubble turns it into an AND gate, which will cause you to lose marks.

Question 17. Write the Sum of Products form of the function G(U,V,W). Truth table representation of G is as follows:

Answer: From the given truth table, we can express the function \( G(U,V,W) \) in both SOP and POS forms.

1. Sum of Products (SOP) Form: We select the rows where the output \( G \) is 1 (m2, m4, m6, m7): \[ G(U,V,W) = \overline{U}V\overline{W} + U\overline{V}\overline{W} + UV\overline{W} + UVW \]
2. Product of Sums (POS) Form: We select the rows where the output \( G \) is 0 (M0, M1, M3, M5) and write them as maxterms: \[ G(U,V,W) = (U + V + W)(U + V + W')(U + V' + W')(U' + V + W') \]
In simple words: For Sum of Products (SOP), we combine rows where the output is 1 using ANDs and add them. For Product of Sums (POS), we combine rows where the output is 0 using ORs and multiply them.

Exam Tip: Pay close attention to whether the question asks for SOP or POS. If it asks for SOP, use the 1s in the output column; if it asks for POS, use the 0s.

High Order Thinking Skills(HOTS)

Q1. State the principle of duality in Boolean Algebra and give the dual of the Boolean expression (X + Y) . (X' + Z') . (Y + Z)
Answer: The Principle of Duality states that any valid Boolean relation remains valid if we swap all AND (.) and OR (+) operators, and swap all 0 and 1 identity elements.

Applying this to the given expression: Original: \( (X + Y) \cdot (X' + Z') \cdot (Y + Z) \)
Dual: \( (X \cdot Y) + (X' \cdot Z') + (Y \cdot Z) \) (or simply \( XY + X'Z' + YZ \))
In simple words: The duality rule says we can find a sister expression by changing every plus to a dot, and every dot to a plus.

Exam Tip: Remember that variables themselves (including complements like X') are never inverted when finding the dual. Only the operators and constants change.

Question 2. Seven inverters are cascaded one after another. What is the output if the input is 1?
Answer: The output will be 0.

An odd number of cascaded inverters always negates the initial input value. Since seven is an odd number, the input of 1 is inverted seven times, resulting in a final output of 0.
In simple words: Each inverter flips the signal. If you flip a 1 seven times, it ends up as 0 because flipping an odd number of times always changes the starting value.

Exam Tip: For any number of cascaded inverters \( n \), if \( n \) is odd, the output is \( \bar{\text{input}} \); if \( n \) is even, the output is equal to the input.

Question 3. Why are NAND and NOR gates called Universal Gates?
Answer: These gates are termed universal because any digital circuit or basic logical function (such as NOT, AND, and OR) can be fully realized using only NAND gates or only NOR gates. Additionally, they are highly economical and easier to manufacture.
In simple words: NAND and NOR gates are called universal because you can build any other gate using only them, which makes designing circuits simpler and cheaper.

Exam Tip: Always specify that both NAND and NOR gates can individually implement the three basic operations (AND, OR, NOT) to fully justify why they are universal.

Question 4. Obtain a simplified form for the following Boolean expression using Karnaugh's Map: F(a, b, c, d) = ∑(0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 14).
Answer: The 4-variable K-map for \( F(a,b,c,d) \) is shown below:

Grouping of 1s:
1. Quad 1: Combined cells \( \{m_8, m_9, m_{10}, m_{11}\} \) in the bottom row. This reduces to \( a\bar{b} \).
2. Quad 2: Combined cells \( \{m_0, m_1, m_4, m_5\} \) in the top-left. This reduces to \( \bar{a}\bar{c} \).
3. Corner Quad: Combined corner cells \( \{m_0, m_2, m_8, m_{10}\} \). This reduces to \( \bar{b}\bar{d} \).
4. Pair 1: Combined cells \( \{m_5, m_7\} \). This reduces to \( \bar{a}bd \).
5. Pair 2: Combined cells \( \{m_{10}, m_{14}\} \). This reduces to \( ac\bar{d} \).

The fully simplified Boolean expression is: \[ F = a\bar{b} + \bar{a}\bar{c} + \bar{b}\bar{d} + \bar{a}bd + ac\bar{d} \]
In simple words: We draw the grid and place 1s in the cells corresponding to our numbers. We then group these 1s into the largest possible blocks of 4 and 2 to find the simplest algebraic terms.

Exam Tip: Don't forget to look for corner groups! Combining the four corner cells into a quad often yields a simpler result than using multiple pairs.

Q5. Prove XY+YZ+YZ’=Y algebraically.
Answer: We start with the Left-Hand Side (LHS) of the expression: \[ \text{LHS} = XY + YZ + YZ' \] Factor out \( Y \) from the second and third terms: \[ = XY + Y(Z + Z') \] Since \( Z + Z' = 1 \) (Complement Law): \[ = XY + Y(1) \] \[ = XY + Y \] Now, factor out \( Y \) from both remaining terms: \[ = Y(X + 1) \] Since \( X + 1 = 1 \) (Dominance Law): \[ = Y(1) \] \[ = Y = \text{RHS} \] Hence proved.
In simple words: First, combine YZ and YZ' to get Y(Z + Z'). Since Z + Z' is 1, this simplifies to Y. Then, XY + Y becomes Y(X + 1), which simplifies directly to Y.

Exam Tip: Always state which Boolean laws (such as Complement or Dominance) are applied at each step of your algebraic proof to secure full credit.

Q6. Simplified AB’CD’+AB’CD+ABCD’+ABCD.
Answer: We start with the given expression: \[ E = AB'CD' + AB'CD + ABCD' + ABCD \] Group the first two terms and the last two terms, then factor out common variables: \[ = AB'C(D' + D) + ABC(D' + D) \] Since \( D' + D = 1 \): \[ = AB'C(1) + ABC(1) \] \[ = AB'C + ABC \] Now, factor out \( AC \) from both terms: \[ = AC(B' + B) \] Since \( B' + B = 1 \): \[ = AC(1) \] \[ = AC \] The simplified expression is \( AC \).
In simple words: We group the terms that are nearly identical and factor out the opposites (like D and D'). Since any variable plus its opposite equals 1, they cancel out, leaving just AC.

Exam Tip: Look for pairs of terms that differ by only a single complemented variable, as they can always be simplified together using the distributive and complement laws.

Q7. Draw the diagram of digital circuit for F(a,b,c)= AB+BC+CD using NAND-to- NAND logic.
Answer: Using double negation and applying De Morgan's Law, we can express the logic sum as a series of NAND operations: \[ F = \overline{\overline{AB} \cdot \overline{BC} \cdot \overline{CD}} \] This design is implemented using three initial 2-input NAND gates to compute \( \overline{AB} \), \( \overline{BC} \), and \( \overline{CD} \), which then feed into a final 3-input NAND gate to produce the output \( F \).

In simple words: We multiply the pairs using three NAND gates, and then connect their outputs into a final NAND gate to finish the design.

Exam Tip: When drawing NAND-to-NAND logic, remember that the final OR gate with inverted inputs is logically identical to a NAND gate.

Q8. Prepare a truth table for X'Y' + X'Y
Answer: We construct the truth table for the Boolean expression \( X'Y' + X'Y \):

In simple words: We write down all combinations of X and Y, compute their inverted values, calculate the products, and add them up to find the final results.

Exam Tip: Note that \( X'Y' + X'Y \) simplifies algebraically to \( X'(Y' + Y) = X'(1) = X' \). You can use this to quickly check if your final truth table column matches the \( X' \) column.

Q9. Convert X+Y into minterms.
Answer: To expand the expression \( X + Y \) into its canonical minterm form, we multiply each term by the sum of the missing variable and its complement: \[ X + Y = X \cdot 1 + Y \cdot 1 \] \[ = X(Y + Y') + Y(X + X') \] \[ = XY + XY' + YX + X'Y \] Since \( YX = XY \) (Commutative Law) and \( XY + XY = XY \) (Idempotent Law): \[ = XY + XY' + X'Y \] Thus, the canonical minterm expression is \( XY + XY' + X'Y \).
In simple words: To write this in minterms, we expand each letter by multiplying it by 1, written as (Y + Y') or (X + X'), so every term in the final answer contains both letters.

Exam Tip: Always remember to remove duplicate terms (like XY) using the Idempotent Law \( A + A = A \) to write the final simplified canonical SOP expression.

Q10. Convert the following function into canonical product of sums form F(X,Y,Z)=𝚷(0,2,4,5).
Answer: The given product-of-sums (POS) representation can be expanded using maxterms: \[ F(X,Y,Z) = \prod(0,2,4,5) = M_0 \cdot M_2 \cdot M_4 \cdot M_5 \] We define each maxterm based on its binary code (where a binary 1 corresponds to a complemented variable and a binary 0 to an uncomplemented variable):
- For \( M_0 \) (000): \( X + Y + Z \)
- For \( M_2 \) (010): \( X + Y' + Z \)
- For \( M_4 \) (100): \( X' + Y + Z \)
- For \( M_5 \) (101): \( X' + Y + Z' \)

Multiplying these maxterms together yields the canonical product of sums form: \[ F = (X + Y + Z)(X + Y' + Z)(X' + Y + Z)(X' + Y + Z') \]
In simple words: We find the sum terms for each number in the list. For each term, a 1 means we use the primed letter and a 0 means we use the plain letter, then we multiply them all.

Exam Tip: In maxterm representation, remember that a binary value of 1 corresponds to a complemented variable (e.g., X') and a 0 corresponds to an uncomplemented variable (e.g., X). This is the exact opposite of the minterm rule.