Boolean Algebra and Propositional Logic: ISC Class 12 Computer Science

What Boolean Algebra is about

Weightage: CISCE publishes no chapter or unit weightage for ISC Computer Science. Boolean Algebra is part of Section A, 1 of the 2027 syllabus and can be asked anywhere in the 70-mark Paper 1 (Part I compulsory: ten 1-mark items and a 10-mark short-answer question; Part II: two of three 10-mark questions in each of Sections A and B, and two of three 5-mark questions in Section C).Source: CISCE ISC Computer Science (868) syllabus, examination year 2027; latest Paper 1 specimen (2025) and the 2025 board paper

Key concepts

Propositional logic: wffs, truth tables, tautology, contradiction, contingency

A proposition is a statement that is either true (1) or false (0). Propositional variables (p, q, r) stand for propositions. Connectives:

• ~p (negation): true when p is false.
• p ∧ q (conjunction): true only when both are true.
• p ∨ q (disjunction): false only when both are false.
• p ⇒ q (implication, 'if p then q'): false only when p is true and q is false. p is the antecedent, q the consequent.
• p ⇔ q (biconditional, 'p if and only if q'): true when p and q have the same value.

A well-formed formula (wff) is built correctly from variables, connectives and brackets (for example (p ∧ q) ⇒ ~r). An interpretation assigns truth values to the variables; the truth table lists every interpretation.

• Tautology (valid formula): true in every row, e.g. p ∨ ~p.
• Contradiction (unsatisfiable): false in every row, e.g. p ∧ ~p.
• Contingency: true in some rows and false in others, e.g. p ⇒ q.
• Satisfiable: true in at least one row (tautologies and contingencies).

Useful equivalences: law of implication p ⇒ q ≡ ~p ∨ q; law of biconditional (p ⇔ q) ≡ (p ⇒ q) ∧ (q ⇒ p); law of negation ~(~p) ≡ p; excluded middle p ∨ ~p ≡ true; contradiction p ∧ ~p ≡ false; De Morgan ~(p ∨ q) ≡ ~p ∧ ~q.

Rules of inference: modus ponens ((p ⇒ q) ∧ p) ⇒ q; chain rule (hypothetical syllogism) ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r). Both are tautologies.

Worked example

[3] Using a truth table, show whether ((p ⇒ q) ∧ ~q) ⇒ ~p is a tautology, a contradiction or a contingency. (Apply)

Try it first, then show the solutionSolution

1. Columns: p, q, p⇒q, ~q, (p⇒q)∧~q, ~p, final - 1 mark.

   p	q	p⇒q	~q	(p⇒q)∧~q	~p	final
   0	0	1	1	1	1	1
   0	1	1	0	0	1	1
   1	0	0	1	0	0	1
   1	1	1	0	0	0	1

2. Intermediate columns correct (an implication is 0 only when the left side is 1 and the right side 0) - 1 mark.
3. Final column is 1 in every row, so the formula is a tautology - 1 mark.

Answer: The final column is all 1s, so ((p ⇒ q) ∧ ~q) ⇒ ~p is a tautology (this rule is called modus tollens).

Converse, inverse and contrapositive

For the conditional p ⇒ q:

• Converse: q ⇒ p (antecedent and consequent interchanged).
• Inverse: ~p ⇒ ~q (both negated, order kept).
• Contrapositive: ~q ⇒ ~p (interchanged and negated).

Key facts:
1. A conditional is logically equivalent to its contrapositive: p ⇒ q ≡ ~q ⇒ ~p.
2. The converse and the inverse are equivalent to each other, but not to the original.
3. The contrapositive is the converse of the inverse (or the inverse of the converse).

Example: p = 'it rains', q = 'the match is cancelled'.
Statement: if it rains, the match is cancelled (p ⇒ q).
Converse: if the match is cancelled, it rains (q ⇒ p).
Inverse: if it does not rain, the match is not cancelled (~p ⇒ ~q).
Contrapositive: if the match is not cancelled, it does not rain (~q ⇒ ~p).

When the original statement itself has a negation, apply the rules mechanically: for ~p ⇒ q the converse is q ⇒ ~p, the inverse is p ⇒ ~q, and the contrapositive is ~q ⇒ p.

Worked example

[2] p: 'A number is divisible by 4'; q: 'A number is even'. Write the converse and the contrapositive of p ⇒ q in symbols and words. (Apply)

Try it first, then show the solutionSolution

1. Converse q ⇒ p: if a number is even, it is divisible by 4 - 1 mark.
2. Contrapositive ~q ⇒ ~p: if a number is not even, it is not divisible by 4 - 1 mark.

Answer: Converse: q ⇒ p, 'If a number is even, then it is divisible by 4' (false in general, e.g. 6). Contrapositive: ~q ⇒ ~p, 'If a number is not even, then it is not divisible by 4' (true, like the original).

Laws and theorems of Boolean algebra; duality and complement

Postulates: 0 · 0 = 0, 1 · 1 = 1, 0 + 0 = 0, 1 + 1 = 1, 0' = 1, 1' = 0; a variable is either 0 or 1.

Law	AND form	OR form
Identity (0 and 1)	A · 1 = A, A · 0 = 0	A + 0 = A, A + 1 = 1
Idempotence	A · A = A	A + A = A
Complement	A · A' = 0	A + A' = 1
Involution	(A')' = A	(A')' = A
Commutative	A · B = B · A	A + B = B + A
Associative	(A · B) · C = A · (B · C)	(A + B) + C = A + (B + C)
Distributive	A · (B + C) = A · B + A · C	A + B · C = (A + B) · (A + C)
Absorption	A · (A + B) = A	A + A · B = A
De Morgan	(A · B)' = A' + B'	(A + B)' = A' · B'

Also useful: A + A'B = A + B and A(A' + B) = AB; consensus AB + A'C + BC = AB + A'C.

Principle of duality: every valid Boolean identity remains valid if you interchange AND with OR and 0 with 1, leaving the variables and their complements unchanged. Dual of A + A'B = A + B is A · (A' + B) = A · B.

Complement of an expression: apply De Morgan's theorem: interchange AND and OR, 0 and 1, AND complement every variable. Complement of A + B'C is A'(B + C'). The difference from the dual is that the complement also complements each literal.

Worked example

[2] Write (a) the dual and (b) the complement of X · Y' + 1 · Z. (Apply)

Try it first, then show the solutionSolution

1. (a) Dual: interchange · and +, and 1 with 0; keep literals: (X + Y') · (0 + Z) - 1 mark.
2. (b) Complement: also complement each literal: (X' + Y) · (0 + Z') which simplifies to (X' + Y) · Z' - 1 mark.

Answer: (a) Dual: (X + Y') · (0 + Z). (b) Complement: (X' + Y) · (0 + Z') = (X' + Y) · Z'.

SOP and POS; minterms, maxterms; canonical and cardinal forms

Sum of products (SOP): OR of AND terms, e.g. A'B + BC'.
Product of sums (POS): AND of OR terms, e.g. (A + B)(A' + C).

Minterm: an AND term containing every variable once (complemented or not); it is 1 for exactly one row. For row values 0 write the variable complemented, for 1 uncomplemented. Row 011 of F(A, B, C) gives minterm A'BC = m3.
Maxterm: an OR term containing every variable once; it is 0 for exactly one row. For row values 0 write the variable uncomplemented, for 1 complemented. Row 010 gives maxterm A + B' + C = M2.

Canonical form: the expression written with full minterms or maxterms, e.g. F(A, B, C) = A'BC' + A'BC + ABC'.
Cardinal (shorthand) form: the list of decimal row numbers: F = Σ(2, 3, 6) for SOP, or F = π(0, 1, 4, 5, 7) for the same function as POS.

Relationship: the minterm list and the maxterm list of a function together contain every row number exactly once. So if F = Σ(2, 3, 6) for three variables, F = π(0, 1, 4, 5, 7).

From a truth table: SOP uses rows where the output is 1; POS uses rows where the output is 0.

Variable order matters: in F(A, B, C, D), A is the most significant bit (weight 8) and D the least (weight 1).

Worked example

[2] For F(A, B, C, D), write m5 and M9 in canonical form. (Apply)

Try it first, then show the solutionSolution

1. m5: 5 = 0101 → A'BC'D (0 → complemented in a minterm) - 1 mark.
2. M9: 9 = 1001 → A' + B + C + D' (1 → complemented in a maxterm) - 1 mark.

Answer: m5 = A'·B·C'·D and M9 = A' + B + C + D'.

Karnaugh maps up to four variables

A Karnaugh map arranges the rows of a truth table so that neighbouring cells differ in exactly one variable (Gray-code order 00, 01, 11, 10). For F(A, B, C, D) put AB on the rows and CD on the columns; the cell numbers are:

AB \ CD	00	01	11	10
00	0	1	3	2
01	4	5	7	6
11	12	13	15	14
10	8	9	11	10

Rules:
1. For SOP, enter 1s (minterms) and group 1s; for POS, enter 0s (maxterms) and group 0s.
2. Groups must be rectangles of 1, 2, 4, 8 or 16 cells (single, pair, quad, octet).
3. Make each group as large as possible; the map wraps round: the top row is adjacent to the bottom row and the left column to the right (map rolling), so the four corners form a quad.
4. Use as few groups as possible; every 1 (or 0) must be covered; groups may overlap; drop any group whose cells are all covered by other groups (a redundant group).
5. Reading a group: keep only the variables that do not change within it. In SOP a variable that is 1 is written plain and 0 complemented; in POS a variable that is 0 is written plain and 1 complemented.

An octet eliminates three variables, a quad two, a pair one.

Example: F(A, B, C, D) = Σ(0, 2, 5, 7, 8, 10, 13, 15). The four corners (0, 2, 8, 10) form a quad where B = 0 and D = 0 → B'D'. The centre cells (5, 7, 13, 15) form a quad where B = 1 and D = 1 → BD. So F = B'D' + BD (B XNOR D). Verified by truth table.

Worked example

[4] Reduce F(A, B, C, D) = π(0, 1, 2, 3, 5, 7, 8, 10, 12, 14) using a K-map, showing the groups. (Apply)

Try it first, then show the solutionSolution

1. Enter 0s in cells 0, 1, 2, 3, 5, 7, 8, 10, 12, 14 - 1 mark.
2. Quad 1, 3, 5, 7 (A = 0, D = 1) → (A + D'); quad 8, 10, 12, 14 (A = 1, D = 0) → (A' + D) - 1 mark.
3. Cells 0 and 2 still need covering: quad 0, 2, 8, 10 (B = 0, D = 0) → (B + D), or quad 0, 1, 2, 3 (A = 0, B = 0) → (A + B) - 1 mark.
4. F = (A + D')(A' + D)(B + D), equally (A + D')(A' + D)(A + B); both checked against the truth table - 1 mark.

Answer: F = (A + D')·(A' + D)·(B + D) (an equally minimal answer is (A + D')·(A' + D)·(A + B)).

From word problem to circuit: truth table, SOP, K-map, gates

The standard 10-mark Section A question gives conditions in words and four inputs.

Method:
1. Write each condition as a product of inputs: 'X and not Y and Z' → XY'Z.
2. Draw the 16-row truth table in binary order (0000 to 1111) with the inputs in the order given in F(...). For each row, set output 1 if any condition is satisfied.
3. SOP: Σ of rows with output 1 (canonical form: write each minterm). POS: π of rows with output 0.
4. K-map: group and reduce.
5. Logic diagram: SOP → AND gates feeding one OR gate; POS → OR gates feeding one AND gate. NAND-only: AND-OR becomes NAND-NAND. NOR-only: OR-AND becomes NOR-NOR.

Special circuits in the syllabus:

• Majority circuit (3 inputs): output 1 when at least two inputs are 1: F = AB + BC + CA = Σ(3, 5, 6, 7).
• Half adder: Sum = A'B + AB' = A ⊕ B; Carry = AB.
• Full adder: Sum = A ⊕ B ⊕ C; Carry = AB + BC + CA (the majority function).

Worked example

[2] A three-member committee approves a proposal when at least two members vote yes (inputs A, B, C; 1 = yes). Write the output in cardinal and reduced SOP form. (Apply)

Try it first, then show the solutionSolution

1. Rows with two or more 1s: 011, 101, 110, 111 → F = Σ(3, 5, 6, 7) - 1 mark.
2. K-map pairs (3, 7) → BC, (5, 7) → AC, (6, 7) → AB → F = AB + BC + CA - 1 mark.

Answer: F = Σ(3, 5, 6, 7) = AB + BC + CA (the majority circuit).

Boolean Algebra in real life

Each concept, met in an everyday situation. Read the situation, answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Topics in this chapter

• Boolean Theorems, SOP and POS Forms and Karnaugh Maps
• Propositional Logic, Well Formed Formulae and Equivalence Laws

Boolean Algebra: syntax and key facts

Implication and biconditional

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

In Boolean form p ⇔ q = pq + p'q'.

Converse / inverse / contrapositive of p ⇒ q

q ⇒ p / ~p ⇒ ~q / ~q ⇒ ~p

Only the contrapositive is equivalent to the original.

De Morgan

(A · B)' = A' + B'; (A + B)' = A' · B'

Basis of complements and universal-gate circuits.

Absorption and redundancy

A + AB = A; A(A + B) = A; A + A'B = A + B

Most common simplifications.

K-map reading

Pair removes 1 variable, quad 2, octet 3

SOP: 1 → plain, 0 → complemented. POS: 0 → plain, 1 → complemented.

Minterm and maxterm

1. 1.m_i: 1 in row i only (0
2. 2.complemented); M_i: 0 in row i only (1
3. 3.complemented)

Σ list and π list together cover all rows.

How the board asks Boolean Algebra

The question patterns to expect, and the method that works for each.

Tricks to remember Boolean Algebra

Short memory aids. Say each one aloud once, then use it on a question the same day.

• Dual versus complement

  Dual: swap the operators only. Complement: swap the operators AND flip every letter.

  Use it when: The most-tested one-mark distinction.

• Minterm 0 → dash, maxterm 1 → dash

  In a minterm a 0 gets a dash (complement); in a maxterm a 1 gets a dash.

  Use it when: Canonical form from cardinal numbers.

• Contrapositive = CIN

  Contrapositive = Converse of the INverse: swap and negate.

  Use it when: Converse, inverse and contrapositive.

Boolean Algebra: board-level solved questions

Ordered from board level to HOTS. Cover the solution, write your own, then compare step by step.

Case-study practice (Section D style)

Read the situation, then answer every part. In the board paper this is a 6-mark question split into 2 + 1 + 2 + 1 marks.

Where the marks are

How a typical answer is split into step marks. Show every step: a right final answer alone rarely earns full marks.

Where students lose marks in Boolean Algebra

The slips examiners see most often, and what to write instead.

• ✗Mistake: Confusing the dual with the complement

  CISCE examiners' comments, 2024 and 2025: candidates 'Confused complement with dual', 'Changed the complements while forming the dual' and 'Could not apply complementation and De Morgan's law correctly'.

  Wrong working

  Dual of (A + B')·(A + 1) = A + B' written as (A'·B) + (A'·0) = A'·B.

  Right working

  Dual: (A·B') + (A·0) = A·B' (literals unchanged).

  ✓Do this: For the dual swap only + and ·, 0 and 1. For the complement also flip every literal.

  Usually costs: 1 mark.

• ✗Mistake: Mixing up converse, inverse, antecedent and consequent

  CISCE examiners' comments: 2024 candidates 'Confused converse and inverse'; 2025 candidates were 'Unsure of the difference between antecedent and consequent'.

  ✓Do this: Antecedent is the 'if' part. Converse swaps; inverse negates; contrapositive swaps and negates.

  Usually costs: 1 mark.

• ✗Mistake: Canonical versus cardinal, and wrong number of variables

  CISCE examiners' comments, 2024: candidates 'Used three variables instead of four', 'Interchanged 0 and 1' and 'Wrote binary 0011/0101 instead of the canonical term'; others were 'Unsure of difference between cardinal and canonical form'.

  ✓Do this: Cardinal = numbers (Σ or π list); canonical = full terms with every variable. Minterm: 0 → complement; maxterm: 1 → complement.

  Usually costs: 1-2 marks.

• ✗Mistake: K-map errors: pairs instead of quads, redundant groups, wrong headings, SOP for POS

  CISCE examiners' comments, 2024 and 2025: candidates 'Took pair instead of quad because map rolling not clear', 'Included redundant group', 'Interchanged headings', 'Took SOP instead of POS' and 'Used 1's output (minterms) instead of 0's for POS'.

  ✓Do this: Use Gray-code headings (00, 01, 11, 10); look for wrap-round groups; delete any group whose cells are covered elsewhere; POS groups 0s.

  Usually costs: 2-4 marks.

• ✗Mistake: No conclusion in a validity question

  CISCE examiners' comments, 2024 and 2025: candidates 'Did not write the conclusion' or 'Did not state the conclusion', and some 'Proved using laws instead of a truth table'.

  ✓Do this: When a truth table is asked, use one, show every column and end with 'Hence it is a tautology / valid'.

  Usually costs: 1 mark.

Practice questions on Boolean Algebra

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · Very short answerBoard level

   Which law states A + A · B = A?

   Hint

   One term swallows the other.

   Answer

   Absorption law.

2. Q2 · 1 mark · Very short answerBoard level

   Write the canonical POS form of F(A, B) = A ⇒ B.

   Hint

   An implication is 0 in one row only.

   Answer

   F = A' + B (= π(2)): the only 0-row is A = 1, B = 0.

3. Q3 · 1 mark · Very short answerBoard level

   Write the inverse of 'If a shape is a square, then it has four sides.'

   Hint

   Negate both, same order.

   Answer

   If a shape is not a square, then it does not have four sides.

4. Q4 · 1 mark · MCQHarder board level

   The complement of (A + B') · (C' + D) is:
   (a) A' · B + C · D'
   (b) (A' + B) · (C + D')
   (c) A · B' + C' · D
   (d) (A + B') + (C' + D)

   Hint

   De Morgan twice.

   Answer

   (a) A' · B + C · D'.

5. Q5 · 2 marks · Short answerHarder board level

   [2] Prove AB + A'C + BC = AB + A'C using Boolean laws.

   Hint

   Multiply BC by (A + A').

   Answer

   BC = BC(A + A') = ABC + A'BC. So LHS = AB + A'C + ABC + A'BC = AB(1 + C) + A'C(1 + B) = AB + A'C.

6. Q6 · 5 marks · Long answerHarder board level

   [5] Reduce F(P, Q, R, S) = Σ(0, 2, 5, 7, 8, 10, 13, 15) using a K-map and draw the circuit using NOR gates only.

   Hint

   Corners and centre.

   Answer

   Quad of corners 0, 2, 8, 10 → Q'S'; quad 5, 7, 13, 15 → QS. F = Q'S' + QS. For NOR-only, write F as POS: F = (Q + S')(Q' + S) (equal to the SOP by truth table); NOR(Q, S') and NOR(Q', S) feed a third NOR gate, whose output is ((Q + S')' + (Q' + S)')' = (Q + S')(Q' + S) = F (OR-AND becomes NOR-NOR).

7. Q7 · 5 marks · Long answerHOTS / competency

   [5] Reduce F(A, B, C, D) = π(1, 3, 5, 7, 13, 15) using a K-map and draw the logic diagram.

   Hint

   Look for a quad in the first two rows and a quad in the D-columns.

   Answer

   0s at 1, 3, 5, 7 (A = 0, D = 1) → (A + D'); 0s at 5, 7, 13, 15 (B = 1, D = 1) → (B' + D'). F = (A + D')(B' + D'), verified by truth table (F is 0 exactly at 1, 3, 5, 7, 13, 15). Circuit: two OR gates feeding an AND gate.

8. Q8 · 10 marks · Long answerHOTS / competency

   [10] A laboratory door opens when (i) a staff card is shown (C) during working hours (W); or (ii) a visitor pass (V) is shown during working hours with the alarm off (L' where L = alarm on); or (iii) the master key (K) is used when the alarm is off. Inputs C, V, W, L, K would need five variables, so assume no visitor passes are issued (V = 0) and take X(C, W, L, K). (a) Truth table and SOP. [5] (b) K-map and logic diagram. [5]

   Hint

   With V = 0, condition (ii) disappears; X = CW + KL'.

   Answer

   (a) With V = 0: X = 1 when C = W = 1, or K = 1 and L = 0. Rows (C W L K): 0001 (1), 0101 (5), 1001 (9), 1100 (12), 1101 (13), 1110 (14), 1111 (15). X = Σ(1, 5, 9, 12, 13, 14, 15). (b) Quad 12, 13, 14, 15 → CW; quad 1, 5, 9, 13 (L = 0, K = 1) → L'K. X = CW + L'K (verified). Circuit: AND(C, W) and AND(L', K) into an OR gate.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.p ⇒ q is false when?Show answer

   Only when p is true and q is false.

2. 2.Which is equivalent to p ⇒ q: converse, inverse or contrapositive?Show answer

   The contrapositive ~q ⇒ ~p.

3. 3.Maxterm for row 110 of F(A, B, C)?Show answer

   A' + B' + C (M6).

4. 4.What does a quad eliminate in a 4-variable K-map?Show answer

   Two variables.

5. 5.Majority function of three inputs?Show answer

   AB + BC + CA.

Quick revision checklist

The night before the exam: can you do each of these without looking?

• ☐p ⇒ q ≡ ~p ∨ q; false only for 1 ⇒ 0.
• ☐Converse q⇒p; inverse ~p⇒~q; contrapositive ~q⇒~p (equivalent).
• ☐Tautology all 1; contradiction all 0; contingency mixed.
• ☐Dual: swap +/· and 0/1. Complement: also flip literals (De Morgan).
• ☐Minterm: 0 → A'; maxterm: 1 → A'. Σ and π lists are complementary.
• ☐K-map: Gray code, wrap round, largest groups, no redundancy; SOP groups 1s, POS groups 0s.
• ☐Majority / full-adder carry = AB + BC + CA; half adder sum A ⊕ B, carry AB.

Boolean Algebra: frequently asked questions