👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Number Systems & Logic
Study mode

Boolean algebra

Study Practice Revise 🔒 Test

Introduction to Boolean Algebra

Boolean algebra is a branch of mathematics that deals with variables having only two possible values: 0 and 1. These values represent false and true respectively, and form the foundation of digital logic used in computers, calculators, and many electronic devices.

Understanding Boolean algebra is essential for computer aptitude tests and competitive exams because it helps simplify complex logical expressions and design efficient digital circuits. This simplification reduces hardware costs and improves performance in real-world applications.

In this chapter, we will explore Boolean variables, operations, logic gates, fundamental laws, simplification techniques, and practical applications. By the end, you will be able to analyze and simplify Boolean expressions confidently and translate them into logic circuits.

Boolean Variables and Operations

A Boolean variable is a variable that can take one of two values: 0 or 1. These values correspond to false and true respectively.

There are three basic Boolean operations:

  • AND (·): The output is 1 only if both inputs are 1.
  • OR (+): The output is 1 if at least one input is 1.
  • NOT (‾): The output is the complement (opposite) of the input.

These operations are denoted symbolically as follows:

  • AND: \( A \cdot B \) or simply \( AB \)
  • OR: \( A + B \)
  • NOT: \( \overline{A} \)

Let's see the truth tables for these operations, which show all possible input combinations and their corresponding outputs.

Truth Tables for Basic Boolean Operations
ABA · B (AND)A + B (OR)‾A (NOT A)
00001
01011
10010
11110

Why these operations matter: In digital circuits, 1 and 0 correspond to voltage levels (e.g., 5V and 0V). The AND operation models situations where all conditions must be true, OR models situations where any condition suffices, and NOT flips the state.

Logic Gates and Symbols

Logic gates are physical devices that implement Boolean operations. Each gate has one or more inputs and a single output based on the Boolean operation it performs.

Here are the common logic gates, their symbols, and truth tables:

AND Output = A·B OR Output = A + B Output = ‾A NAND Output = ‾(A·B) NOR Output = ‾(A + B) XOR Output = A ⊕ B XNOR Output = ‾(A ⊕ B)

Summary of gates:

  • AND gate: Output is 1 only if both inputs are 1.
  • OR gate: Output is 1 if any input is 1.
  • NOT gate: Output is the inverse of input.
  • NAND gate: Output is the complement of AND.
  • NOR gate: Output is the complement of OR.
  • XOR gate: Output is 1 if inputs are different.
  • XNOR gate: Output is 1 if inputs are the same.

Boolean Laws and Theorems

Boolean algebra follows specific laws and theorems that help simplify expressions. These laws are similar to arithmetic laws but adapted for Boolean variables.

1. Commutative Law

The order of variables does not affect the result:

\[ A + B = B + A; \quad A \cdot B = B \cdot A \]

2. Associative Law

The grouping of variables does not affect the result:

\[ (A + B) + C = A + (B + C); \quad (A \cdot B) \cdot C = A \cdot (B \cdot C) \]

3. Distributive Law

AND distributes over OR and vice versa:

\[ A \cdot (B + C) = (A \cdot B) + (A \cdot C); \quad A + (B \cdot C) = (A + B) \cdot (A + C) \]

4. Identity Law

0 is the identity for OR, and 1 is the identity for AND:

\[ A + 0 = A; \quad A \cdot 1 = A \]

5. Null Law

1 is the null for OR, and 0 is the null for AND:

\[ A + 1 = 1; \quad A \cdot 0 = 0 \]

6. Complement Law

A variable ORed with its complement is 1; ANDed with its complement is 0:

\[ A + \overline{A} = 1; \quad A \cdot \overline{A} = 0 \]

7. De Morgan's Theorems

These theorems relate complements of AND and OR operations:

\[ \overline{A \cdot B} = \overline{A} + \overline{B}; \quad \overline{A + B} = \overline{A} \cdot \overline{B} \]

Why these laws are important: They allow us to rewrite and simplify complex Boolean expressions, making digital circuits easier to design and understand.

Simplify Boolean Expression Using Laws

Example 1: Simplify Expression Using Boolean Laws Easy
Simplify the Boolean expression \( A + A \cdot B \).

Step 1: Apply the Absorption Law which states \( A + A \cdot B = A \).

Explanation: If \( A = 1 \), the expression is 1 regardless of \( B \). If \( A = 0 \), then \( A \cdot B = 0 \), so the expression is 0. Hence, the expression simplifies to \( A \).

Answer: \( A + A \cdot B = A \)

Truth Tables

A truth table lists all possible input combinations of Boolean variables and shows the output of a Boolean expression for each combination. It is a fundamental tool to analyze and verify logic expressions and circuits.

Let's construct a truth table for the expression \( (A + B) \cdot C \):

Truth Table for \( (A + B) \cdot C \)
ABCA + B(A + B) · C
00000
00100
01010
01111
10010
10111
11010
11111

How to read the table: For each row, calculate \( A + B \) first, then multiply by \( C \). The output column shows the final result.

Karnaugh Map (K-map)

A Karnaugh map (K-map) is a graphical tool to simplify Boolean expressions with 2 to 4 variables by grouping adjacent 1s in a grid. It helps minimize the number of terms and variables in the expression, making circuit design easier.

Each cell in a K-map corresponds to a minterm (a unique combination of variable values). Adjacent cells differ by only one variable, allowing grouping in powers of two (1, 2, 4, 8...).

Here is a 4-variable K-map layout with variables \( A, B, C, D \):

00 01 11 10 00 01 11 10

How to group: Group adjacent 1s in rectangles of size 1, 2, 4, 8, etc. Groups can wrap around edges. Each group corresponds to a simplified product term.

Simplify Boolean Expression Using K-map

Example 3: Simplify Using K-map Medium
Simplify the Boolean function \( F(A,B,C,D) = \sum m(0,2,5,7,8,10,13,15) \) using a 4-variable K-map.

Step 1: Plot the minterms on the 4-variable K-map by marking 1s in the corresponding cells.

Step 2: Group the adjacent 1s in the largest possible groups (powers of two). For example, group minterms (0,2,8,10) and (5,7,13,15).

Step 3: Derive the simplified expression from each group:

  • Group 1 (0,2,8,10): \( \overline{B} \cdot \overline{D} \)
  • Group 2 (5,7,13,15): \( B \cdot D \)

Step 4: Write the simplified Boolean expression:

\[ F = \overline{B} \cdot \overline{D} + B \cdot D \]

Answer: \( F = \overline{B} \cdot \overline{D} + B \cdot D \)

Derive Logic Circuit from Boolean Expression

Example 5: Draw Logic Circuit from Boolean Expression Hard
Draw the logic circuit for the simplified Boolean expression \( A \cdot B + \overline{C} \).

Step 1: Identify the operations:

  • AND operation between \( A \) and \( B \)
  • NOT operation on \( C \)
  • OR operation between \( A \cdot B \) and \( \overline{C} \)

Step 2: Draw the circuit stepwise:

  • Use an AND gate with inputs \( A \) and \( B \).
  • Use a NOT gate with input \( C \) to get \( \overline{C} \).
  • Use an OR gate with inputs from the AND gate output and the NOT gate output.

Step 3: Connect the gates accordingly.

A B C AND NOT OR Output

Answer: The circuit consists of an AND gate for \( A \cdot B \), a NOT gate for \( \overline{C} \), and an OR gate combining both outputs.

Formula Bank

Commutative Law
\[ A + B = B + A; \quad A \cdot B = B \cdot A \]
where: \( A, B \) are Boolean variables (0 or 1)
Associative Law
\[ (A + B) + C = A + (B + C); \quad (A \cdot B) \cdot C = A \cdot (B \cdot C) \]
where: \( A, B, C \) are Boolean variables
Distributive Law
\[ A \cdot (B + C) = (A \cdot B) + (A \cdot C); \quad A + (B \cdot C) = (A + B) \cdot (A + C) \]
where: \( A, B, C \) are Boolean variables
Identity Law
\[ A + 0 = A; \quad A \cdot 1 = A \]
where: \( A \) is a Boolean variable
Null Law
\[ A + 1 = 1; \quad A \cdot 0 = 0 \]
where: \( A \) is a Boolean variable
Complement Law
\[ A + \overline{A} = 1; \quad A \cdot \overline{A} = 0 \]
where: \( A \) is a Boolean variable; \( \overline{A} \) is complement of \( A \)
De Morgan's Theorems
\[ \overline{A \cdot B} = \overline{A} + \overline{B}; \quad \overline{A + B} = \overline{A} \cdot \overline{B} \]
where: \( A, B \) are Boolean variables
Example 2: Construct Truth Table Easy
Create a truth table for the Boolean expression \( (A + B) \cdot C \).

Step 1: List all possible combinations of inputs \( A, B, C \). Since each can be 0 or 1, there are \( 2^3 = 8 \) combinations.

Step 2: Calculate \( A + B \) for each combination.

Step 3: Multiply the result of \( A + B \) by \( C \) (AND operation).

Step 4: Fill the output column accordingly.

ABCA + B(A + B) · C
00000
00100
01010
01111
10010
10111
11010
11111

Answer: The truth table above correctly represents the expression \( (A + B) \cdot C \).

Example 4: Apply De Morgan's Theorem Medium
Simplify the complement of the expression \( A + B \cdot C \), i.e., simplify \( \overline{A + B \cdot C} \).

Step 1: Apply De Morgan's theorem to the complement of a sum:

\[ \overline{A + B \cdot C} = \overline{A} \cdot \overline{B \cdot C} \]

Step 2: Apply De Morgan's theorem again to \( \overline{B \cdot C} \):

\[ \overline{B \cdot C} = \overline{B} + \overline{C} \]

Step 3: Substitute back:

\[ \overline{A + B \cdot C} = \overline{A} \cdot (\overline{B} + \overline{C}) \]

Answer: \( \overline{A + B \cdot C} = \overline{A} \cdot (\overline{B} + \overline{C}) \)

Tips & Tricks

Tip: Use De Morgan's Theorems to simplify complements quickly.

When to use: When dealing with complements of AND/OR expressions.

Tip: Group 1s in K-map in powers of two (1, 2, 4, 8) for optimal simplification.

When to use: While simplifying Boolean expressions using Karnaugh maps.

Tip: Remember that \( A + A \cdot B = A \) to reduce expressions faster.

When to use: When you see terms with a variable ORed with its AND combination.

Tip: Construct truth tables systematically to avoid missing input combinations.

When to use: When verifying or simplifying Boolean expressions.

Tip: Practice drawing logic gates alongside expressions to strengthen conceptual understanding.

When to use: When converting Boolean expressions to circuits.

Common Mistakes to Avoid

❌ Confusing AND and OR operations in expressions.
✓ Remember AND requires all inputs to be 1; OR requires at least one input to be 1.
Why: Students often mix up the conditions for AND and OR due to symbolic similarity.
❌ Incorrectly applying De Morgan's theorem by missing complement signs.
✓ Carefully complement each variable and change the operator from AND to OR or vice versa.
Why: Rushing through simplification leads to missing negations.
❌ Grouping invalid cells in K-map (non-adjacent 1s).
✓ Only group adjacent 1s in powers of two; adjacency includes wrap-around edges.
Why: Lack of understanding of adjacency rules in K-maps.
❌ Omitting variables during simplification, leading to incorrect expressions.
✓ Ensure all variables are accounted for after grouping in K-maps or applying laws.
Why: Students sometimes drop variables to oversimplify.
❌ Mixing up logic gate symbols when drawing circuits.
✓ Memorize standard symbols and verify connections carefully.
Why: Similar-looking symbols cause confusion under exam pressure.
Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Boolean algebra · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.