Boolean Algebra — ISC Computer Science

01

Propositional Logic

WFFs, connectives, truth values, interpretation

Propositional logic deals with propositions — statements that are either TRUE or FALSE. We combine them using logical connectives to form compound statements called Well-Formed Formulae (WFF).

What is a Proposition?

✅ Valid Propositions

"The sky is blue" — TRUE
"2 + 2 = 5" — FALSE
"It is raining" — TRUE/FALSE
"Delhi is the capital of India" — TRUE

❌ Not Propositions

"Close the door!" (command)
"Are you ok?" (question)
"x + 2 = 5" (open sentence, value of x unknown)
"This statement is false" (paradox)

Logical Connectives (Operators)

Symbol	Name	Read As	Example	Description
~ or ¬	Negation	NOT p	~p	Reverses truth value of p
∧	Conjunction	p AND q	p ∧ q	True only when BOTH are true
∨	Disjunction	p OR q	p ∨ q	True when AT LEAST ONE is true
⇒	Implication	p implies q	p ⇒ q	False ONLY when p=T, q=F
⇔	Biconditional	p if and only if q	p ⇔ q	True when BOTH have same value

Well-Formed Formulae (WFF)

📐 Definition

A WFF is a syntactically correct expression formed using propositional variables and logical connectives following precise grammar rules.

Formation rules:

1

Atomic WFF

Any propositional variable (p, q, r, T, F) is a WFF by itself.

2

Negation Rule

If P is a WFF, then ~P is also a WFF.

3

Binary Connective Rule

If P and Q are WFFs, then (P ∧ Q), (P ∨ Q), (P ⇒ Q), (P ⇔ Q) are also WFFs.

4

Nothing Else

Only expressions formed using rules 1–3 are WFFs.

⭐ Exam Tip — WFF Examples

Valid: (p ∧ q) ⇒ r, ~(p ∨ ~q), ((p ⇒ q) ∧ (q ⇒ r))
Invalid: p ∧ ∨ q, ⇒ p q, p q ∧

Truth Tables for Basic Connectives

p	q	~p	p ∧ q	p ∨ q
T	T	F	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	F

p	q	p ⇒ q	~p ∨ q
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

⚡ Key Insight

Implication (p ⇒ q) is FALSE ONLY when the premise p is TRUE and conclusion q is FALSE. All other cases are TRUE. Note: p ⇒ q ≡ ~p ∨ q (very important for simplification!)

p	q	p ⇔ q	(p⇒q)∧(q⇒p)
T	T	T	T
T	F	F	F
F	T	F	F
F	F	T	T

⚡ Key Insight

Biconditional is TRUE when both p and q have the same truth value. It is equivalent to (p⇒q) ∧ (q⇒p).

Types of Formulae

Tautology (Valid)

A WFF that is TRUE for all possible interpretations (all rows in truth table = T).

p ∨ ~p — always TRUE (Law of Excluded Middle)

p ⇒ p — always TRUE

Contradiction (Unsatisfiable)

A WFF that is FALSE for all possible interpretations (all rows = F).

p ∧ ~p — always FALSE (Law of Contradiction)

Contingency (Satisfiable)

A WFF that is TRUE for at least one interpretation, but not all. Neither tautology nor contradiction.

p ∧ q — TRUE only when both p,q = T

Converse, Inverse, and Contrapositive

Given implication: p ⇒ q

Original

p ⇒ q

"If p, then q"

Converse

q ⇒ p

"If q, then p" — swap p and q

Inverse

~p ⇒ ~q

Negate both — equivalent to converse

Contrapositive

~q ⇒ ~p

Swap AND negate — EQUIVALENT to original!

⭐ Critical: p ⇒ q ≡ ~q ⇒ ~p (Contrapositive is logically equivalent!)

But p ⇒ q is NOT equivalent to q ⇒ p (converse) or ~p ⇒ ~q (inverse).

Chain Rule & Modus Ponens

Modus Ponens (Law of Detachment)

Premise 1: p ⇒ q

Premise 2: p (p is TRUE)

──────────

Conclusion: q

If "if p then q" is true, and p is true, we can conclude q is true.

Chain Rule (Hypothetical Syllogism)

Premise 1: p ⇒ q

Premise 2: q ⇒ r

──────────

Conclusion: p ⇒ r

If p implies q, and q implies r, then p implies r (transitivity of implication).

02

Equivalence Laws

All laws for simplifying WFFs — must memorise every one!

Two WFFs P and Q are logically equivalent (P ≡ Q) if they have identical truth values for all interpretations. These laws let us simplify and transform expressions.

Complete List of Equivalence Laws

1. Identity Laws

p ∧ T ≡ p p ∨ F ≡ p

AND with TRUE and OR with FALSE leave the variable unchanged.

2. Domination Laws (Null / Annihilation)

p ∨ T ≡ T p ∧ F ≡ F

OR with TRUE always gives TRUE; AND with FALSE always gives FALSE.

3. Idempotent Laws

p ∧ p ≡ p p ∨ p ≡ p

4. Commutative Laws

p ∧ q ≡ q ∧ p

p ∨ q ≡ q ∨ p

Order of operands doesn't matter for AND and OR.

5. Associative Laws

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

6. Distributive Laws

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) — AND distributes over OR

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) — OR distributes over AND

7. De Morgan's Laws ⭐ (Most Important!)

~(p ∧ q) ≡ ~p ∨ ~q — NOT of AND = OR of NOTs

~(p ∨ q) ≡ ~p ∧ ~q — NOT of OR = AND of NOTs

Memory trick: "Break the bar, change the operator" — negate each variable and flip AND↔OR.

8. Law of Implication

p ⇒ q ≡ ~p ∨ q

Used to convert implications to OR form for simplification.

9. Law of Biconditional

p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p)

p ⇔ q ≡ (p ∧ q) ∨ (~p ∧ ~q)

10. Law of Negation (Double Negation / Involution)

~(~p) ≡ p

11. Law of Excluded Middle (Tautology)

p ∨ ~p ≡ T — Always TRUE

12. Law of Contradiction

p ∧ ~p ≡ F — Always FALSE

13. Absorption Laws

p ∨ (p ∧ q) ≡ p

p ∧ (p ∨ q) ≡ p

14. Simplification Rules (for AND)

p ∧ T ≡ p p ∧ F ≡ F p ∧ p ≡ p p ∧ ~p ≡ F

15. Simplification Rules (for OR)

p ∨ T ≡ T p ∨ F ≡ p p ∨ p ≡ p p ∨ ~p ≡ T

Worked Example: Simplify a WFF

Simplify: ~(p ∨ ~q) ∨ (p ∧ q)

Step 1: Apply De Morgan's to ~(p ∨ ~q)

= (~p ∧ ~~q) ∨ (p ∧ q)

Step 2: Apply Double Negation (~~q = q)

= (~p ∧ q) ∨ (p ∧ q)

Step 3: Factor out q (Distributive Law)

= q ∧ (~p ∨ p)

Step 4: Apply Law of Excluded Middle (~p ∨ p = T)

= q ∧ T

Step 5: Apply Identity Law

= q

03

Boolean Algebra

Binary values, basic postulates, AND / OR / NOT

Boolean algebra is a mathematical system dealing with binary values — 0 (FALSE) and 1 (TRUE) — and the operations performed on them. It is the foundation of digital circuits and computing.

Binary-Valued Quantities

Value 0 (FALSE)

Switch is OFF
Voltage is LOW
Condition is False
Represented as 0

Value 1 (TRUE)

Switch is ON
Voltage is HIGH
Condition is True
Represented as 1

Basic Postulates of Boolean Algebra

AND with 0

0 · 0 = 0 1 · 0 = 0

AND with 1

0 · 1 = 0 1 · 1 = 1

OR with 0

0 + 0 = 0 1 + 0 = 1

OR with 1

0 + 1 = 1 1 + 1 = 1

NOT (Complement)

0̄ = 1 1̄ = 0

Note

· = AND, + = OR, overbar = NOT

Truth Tables for Basic Boolean Operations

AND Gate (·)

A	B	A · B
0	0	0
0	1	0
1	0	0
1	1	1

OR Gate (+)

A	B	A + B
0	0	0
0	1	1
1	0	1
1	1	1

NOT Gate (overbar)

A	Ā (NOT A)
0	1
1	0

04

Theorems of Boolean Algebra

All theorems with proofs — duality, idempotence, De Morgan's, absorption...

Principle of Duality

📐 Duality Principle

Every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators AND and OR are interchanged and the identity elements 0 and 1 are interchanged.

Original

A + 0 = A

Dual

A · 1 = A

Original

A + A = A

Dual

A · A = A

Complete Theorem Reference

1. Identity Theorems

A + 0 = A A · 1 = A

A + 1 = 1 A · 0 = 0

Proof (A + 0 = A): When A=0: 0+0=0 ✓; When A=1: 1+0=1 ✓

2. Idempotent Laws

A + A = A A · A = A

Proof: OR table: 0+0=0=0, 1+1=1=1 ✓ | AND table: 0·0=0, 1·1=1 ✓

3. Commutative Laws

A + B = B + A

A · B = B · A

4. Associative Laws

A + (B + C) = (A + B) + C

A · (B · C) = (A · B) · C

5. Distributive Laws

A · (B + C) = A·B + A·C — AND distributes over OR

A + (B · C) = (A + B) · (A + C) — OR distributes over AND

⭐ Note: Second law has NO analogy in ordinary algebra!

In normal algebra, a + (b·c) ≠ (a+b)·(a+c), but in Boolean algebra it is valid.

6. Complement Laws (Operations with 0 and 1)

A + Ā = 1 — Complement OR = 1 (Tautology)

A · Ā = 0 — Complement AND = 0 (Contradiction)

Ā̄ = A — Double complement = original (Involution)

7. Absorption Laws

A + A·B = A

A · (A + B) = A

Proof of A + A·B = A:
= A·1 + A·B        (Identity: A = A·1)
= A·(1 + B)        (Distributive)
= A·1               (1 + B = 1)
= A                 (Identity) ✓

8. De Morgan's Theorems ⭐⭐⭐

̄(A·B) = Ā + B̄ — NOT(A AND B) = NOTA OR NOTB

̄(A+B) = Ā · B̄ — NOT(A OR B) = NOTA AND NOTB

Proof by Truth Table: ̄(A·B) = Ā + B̄

A	B	A·B	̄(A·B)	Ā	B̄	Ā + B̄	Same?
0	0	0	1	1	1	1	✓
0	1	0	1	1	0	1	✓
1	0	0	1	0	1	1	✓
1	1	1	0	0	0	0	✓

05

SOP, POS, Minterms & Maxterms

Canonical & cardinal forms, sum of products, product of sums

Minterms and Maxterms

Minterm (mₙ)

A product (AND) term containing all n variables in true or complemented form. Evaluates to 1 for exactly one input combination.

For 2 variables A, B:

m₀ = Ā·B̄ (when A=0, B=0)

m₁ = Ā·B (when A=0, B=1)

m₂ = A·B̄ (when A=1, B=0)

m₃ = A·B (when A=1, B=1)

Maxterm (Mₙ)

A sum (OR) term containing all n variables. Evaluates to 0 for exactly one input combination.

For 2 variables A, B:

M₀ = A+B (0 when A=0, B=0)

M₁ = A+B̄ (0 when A=0, B=1)

M₂ = Ā+B (0 when A=1, B=0)

M₃ = Ā+B̄ (0 when A=1, B=1)

⚡ Key Relationship: Mₙ = complement of mₙ

For the same index n: Mₙ = m̄ₙ. Example: m₀ = Ā·B̄, so M₀ = A+B ✓

SOP — Sum of Products

A Boolean expression where product (AND) terms are summed (OR). The Canonical SOP uses only minterms.

Example: f(A,B,C) = ∑m(1,4,7) = m₁ + m₄ + m₇

= Ā·B̄·C + A·B̄·C̄ + A·B·C

✅ How to find SOP from a truth table

1. Find all rows where output = 1
2. Write the minterm for each (0→complement, 1→true variable)
3. OR all the minterms together

POS — Product of Sums

A Boolean expression where sum (OR) terms are multiplied (AND). The Canonical POS uses only maxterms.

Example: f(A,B,C) = ΠM(0,2,3,5,6) = M₀·M₂·M₃·M₅·M₆

= (A+B+C)·(A+B̄+C)·(A+B̄+C̄)·(Ā+B+C̄)·(Ā+B̄+C)

✅ How to find POS from a truth table

1. Find all rows where output = 0
2. Write the maxterm for each (0→true variable, 1→complement)
3. AND all the maxterms together

Complete Example: 3-variable Function

Truth table for f(A,B,C)

Row	A	B	C	f	Minterm	Maxterm
0	0	0	0	0	m₀=Ā·B̄·C̄	M₀=A+B+C ←POS
1	0	0	1	1	m₁=Ā·B̄·C ←SOP	M₁=A+B+C̄
2	0	1	0	0	m₂=Ā·B·C̄	M₂=A+B̄+C ←POS
3	0	1	1	1	m₃=Ā·B·C ←SOP	M₃=A+B̄+C̄
4	1	0	0	1	m₄=A·B̄·C̄ ←SOP	M₄=Ā+B+C
5	1	0	1	0	m₅=A·B̄·C	M₅=Ā+B+C̄ ←POS
6	1	1	0	0	m₆=A·B·C̄	M₆=Ā+B̄+C ←POS
7	1	1	1	1	m₇=A·B·C ←SOP	M₇=Ā+B̄+C̄

Canonical SOP (output=1 rows: 1,3,4,7):

f = ∑m(1,3,4,7) = Ā·B̄·C + Ā·B·C + A·B̄·C̄ + A·B·C

Canonical POS (output=0 rows: 0,2,5,6):

f = ΠM(0,2,5,6) = (A+B+C)·(A+B̄+C)·(Ā+B+C̄)·(Ā+B̄+C)

06

Karnaugh Maps (K-Maps)

Systematic minimisation — 2, 3, and 4 variable maps

A Karnaugh Map is a graphical method for simplifying Boolean expressions. Adjacent cells differ by exactly one variable (Gray code ordering), allowing visual identification of groupings.

Rules for Grouping (Implicants)

Group only 1s (for SOP minimisation) or only 0s (for POS minimisation)
Group sizes must be powers of 2: 1, 2, 4, 8, 16...
Groups must be rectangular (including wrapping around edges)
Make groups as large as possible (larger groups = fewer literals)
Each group eliminates one variable per doubling in size
Every 1 must be covered by at least one group
Overlapping groups are allowed (same 1 can be in multiple groups)
Corners wrap around (top-bottom and left-right)

2-Variable K-Map

f(A,B) — Layout

1

0

1

0

Group of 2 → f = B̄

3-Variable K-Map

⚡ Important: Column order in 3/4-variable K-Maps

Columns/rows must follow Gray code order: 00, 01, 11, 10 (NOT 00, 01, 10, 11). This ensures adjacent cells differ by only one bit.

3-variable K-Map (A, BC)

0

1

0

1

0

1

Green group (4 cells) → Ā·C ... wait: Ā·(B... )

Amber group: A·B̄ (wraps left-right corners)

4-Variable K-Map — Detailed Example

f(A,B,C,D) = ∑m(0,1,4,5,6,7,8,9,14,15)

4-variable K-Map (AB rows, CD columns)

1

0

1

0

1

0

1

0

Group 1 (4 cells rows 00,01 cols 00,01): B̄·D̄

Group 2 (4 cells rows 01,11 cols 11): B·C

Group 3 (row 10 cols 00,01): A·B̄·D̄ ... wrap check

⭐ Step-by-step K-Map solving process

1. Plot all 1s in the K-Map from the minterm list or truth table
2. Identify all essential prime implicants (1s covered by only one group)
3. Form the largest possible groups (prefer 8 > 4 > 2 > 1)
4. Cover all 1s using minimum number of groups
5. Write one term per group (variables that don't change within a group are eliminated)
6. OR all the terms together (SOP form)

How to Read a Group (Extract the Term)

For each group of 1s, look at which variables stay constant across all cells in the group:

If variable stays at 0 throughout the group → include it complemented (e.g., Ā)
If variable stays at 1 throughout the group → include it true (e.g., A)
If variable changes (0 and 1 both appear) → eliminate that variable

Group of 4 spanning all values of D, but A=0, B=0, C=1:

Result = Ā · B̄ · C (D is eliminated)

07

Digital Circuits

Half adder, full adder, majority circuit — SOP realization

Half Adder

📐 Definition

A Half Adder adds two 1-bit binary numbers A and B, producing a Sum (S) and a Carry (C). It cannot accept a carry-in from a previous stage.

Half Adder Truth Table

A	B	Sum (S)	Carry (C)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Boolean Expressions

Sum (S) — XOR

S = A ⊕ B = Ā·B + A·B̄

Carry (C) — AND

C = A · B

⭐ Logic gates needed

Sum: 1 XOR gate (or 2 AND + 1 OR + 2 NOT)
Carry: 1 AND gate

Full Adder

📐 Definition

A Full Adder adds three 1-bit inputs: A, B, and Carry-in (Cᵢₙ), producing Sum (S) and Carry-out (Cₒᵤₜ). It can be cascaded to add multi-bit numbers.

Full Adder Truth Table

A	B	Cᵢₙ	Sum (S)	Carry-out (Cₒᵤₜ)
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

SOP Expressions

Sum (S) = ∑m(1,2,4,7)

S = Ā·B̄·Cᵢₙ + Ā·B·C̄ᵢₙ + A·B̄·C̄ᵢₙ + A·B·Cᵢₙ

S = A ⊕ B ⊕ Cᵢₙ (simplified)

Carry-out = ∑m(3,5,6,7)

Cₒᵤₜ = A·B + B·Cᵢₙ + A·Cᵢₙ

= A·B + Cᵢₙ·(A ⊕ B)

Implementation

A Full Adder can be built using:

2 Half Adders + 1 OR gate (most common)
Direct gate implementation using SOP

Using two half adders:

HA1: S₁ = A ⊕ B, C₁ = A·B

HA2: S = S₁ ⊕ Cᵢₙ

Cₒᵤₜ = C₁ + (S₁ · Cᵢₙ)

Majority Circuit

📐 Definition

A Majority circuit outputs 1 when the majority of inputs are 1. For 3 inputs (A, B, C), output is 1 when 2 or more inputs are 1.

Majority Circuit (3-input)

A	B	C	Output (M)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

SOP Expression & Simplification

Canonical SOP (minterms 3,5,6,7):

M = Ā·B·C + A·B̄·C + A·B·C̄ + A·B·C

After K-Map simplification:

M = A·B + B·C + A·C

The simplified form needs only 3 AND gates and 1 three-input OR gate.

08

Quick Quiz

Test yourself — ISC exam-level questions

Score 0 / 0

Q1. Which of the following is logically equivalent to p ⇒ q?

Law of Implication: p ⇒ q ≡ ~p ∨ q. This is a fundamental equivalence used in simplification.

Q2. De Morgan's theorem states: ~(A + B) = ?

~(A + B) = Ā · B̄. De Morgan's: NOT of OR = AND of NOTs. "Break the bar, change the operator."

Q3. Which type of formula is TRUE for ALL possible interpretations?

A Tautology is a WFF that is TRUE under all interpretations. Example: p ∨ ~p. A Contradiction is always FALSE. A Contingency can be either.

Q4. The canonical SOP of f(A,B) with minterms {1,3} is:

m₁ = Ā·B (A=0,B=1), m₃ = A·B (A=1,B=1). f = Ā·B + A·B = B·(Ā + A) = B·1 = B.

Q5. In a Half Adder, what are the Boolean expressions for Sum (S) and Carry (C)?

Sum = A XOR B = A⊕B = Ā·B + A·B̄ (output 1 when inputs differ). Carry = A AND B (output 1 only when both inputs are 1).

Q6. Which law states: A + A·B = A?

A + A·B = A is the Absorption Law. Proof: A·1 + A·B = A·(1+B) = A·1 = A. The "absorbed" term A·B disappears because A alone already captures it.

⚡

Master Cheat Sheet

All key formulas at a glance — print and revise!

Boolean Algebra — All Laws in One Place

Identity

A+0=A A·1=A

Null/Domination

A+1=1 A·0=0

Idempotent

A+A=A A·A=A

Complement

A+Ā=1 A·Ā=0

Involution

Ā̄ = A

Commutative

A+B=B+A A·B=B·A

Associative

(A+B)+C=A+(B+C)

Distributive

A·(B+C)=A·B+A·C

De Morgan 1

̄(A·B) = Ā+B̄

De Morgan 2

̄(A+B) = Ā·B̄

Absorption 1

A+A·B = A

Absorption 2

A·(A+B) = A

Implication

p⇒q ≡ ~p∨q

Contrapositive

p⇒q ≡ ~q⇒~p

Biconditional

p⇔q ≡ (p⇒q)∧(q⇒p)

Chain Rule

p⇒q, q⇒r ⊢ p⇒r

🎯 Top 5 Things That Appear Most in ISC Exams

1. De Morgan's theorem — simplification problems and truth table proofs
2. K-Map simplification — always include grouping visualization
3. SOP from truth table — construct canonical form then simplify
4. Full adder truth table + expressions — circuit design questions
5. WFF simplification using equivalence laws step-by-step

Boolean AlgebraComplete Theory

✅ Valid Propositions

❌ Not Propositions

Tautology (Valid)

Contradiction (Unsatisfiable)

Contingency (Satisfiable)

Modus Ponens (Law of Detachment)

Chain Rule (Hypothetical Syllogism)

1. Identity Laws

2. Domination Laws (Null / Annihilation)

3. Idempotent Laws

4. Commutative Laws

5. Associative Laws

6. Distributive Laws

7. De Morgan's Laws ⭐ (Most Important!)

8. Law of Implication

9. Law of Biconditional

10. Law of Negation (Double Negation / Involution)

11. Law of Excluded Middle (Tautology)

12. Law of Contradiction

13. Absorption Laws

14. Simplification Rules (for AND)

15. Simplification Rules (for OR)

Simplify: ~(p ∨ ~q) ∨ (p ∧ q)

Value 0 (FALSE)

Value 1 (TRUE)

AND Gate (·)

OR Gate (+)

NOT Gate (overbar)

1. Identity Theorems

2. Idempotent Laws

3. Commutative Laws

4. Associative Laws

5. Distributive Laws

6. Complement Laws (Operations with 0 and 1)

7. Absorption Laws

8. De Morgan's Theorems ⭐⭐⭐

Minterm (mₙ)

Maxterm (Mₙ)

Truth table for f(A,B,C)

f(A,B,C,D) = ∑m(0,1,4,5,6,7,8,9,14,15)

Half Adder Truth Table

Boolean Expressions

Full Adder Truth Table

SOP Expressions

Implementation

Majority Circuit (3-input)

SOP Expression & Simplification

Boolean Algebra — All Laws in One Place

Boolean Algebra
Complete Theory