Propositional Logic and Logic Gates: ISC Class 11 Notes

What Propositional Logic and Logic Gates is about

Weightage: Propositional Logic and Logic Gates is topic 3 of the ISC Class XI Computer Science syllabus, in Section A - Hardware. CISCE weights Section A at 25 of the 70 marks in Paper I (Theory). Class XI is examined by the school, so your school sets the paper within this weightage.Source: CISCE ISC Computer Science syllabus, examination year 2028, Class XI unit weightage

Key concepts

Propositions, variables and connectives

A proposition is a declarative statement that is either true (T, 1) or false (F, 0), but not both. 'Delhi is the capital of India' is a proposition; 'Close the door' and 'x + 2 = 5' (without a value of x) are not.

Propositional variables (p, q, r) stand for propositions.

Connectives:

Connective	Symbol	Read as	True when
Negation	~p	not p	p is false
Conjunction	p ∧ q	p and q	both are true
Disjunction	p ∨ q	p or q	at least one is true
Implication	p ⇒ q	if p then q	except when p is true and q is false
Equivalence	p ⇔ q	p if and only if q	p and q have the same value

Truth table of the binary connectives:

p	q	p ∧ q	p ∨ q	p ⇒ q	p ⇔ q
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T

In p ⇒ q, p is the antecedent (hypothesis) and q the consequent (conclusion). An implication with a false antecedent is true ('vacuously true').

Worked example

Let p = 'It rains' (true) and q = 'The match is cancelled' (false). Find the truth values of p ∧ q, p ∨ q, p ⇒ q and ~p ⇒ q. [2 marks]

Try it first, then show the solutionSolution

1. p ∧ q = T ∧ F = F; p ∨ q = T ∨ F = T.
2. p ⇒ q = T ⇒ F = F; ~p ⇒ q = F ⇒ F = T.

Answer: F, T, F, T.

Well-formed formulae and word problems

A well-formed formula (wff) is a string of symbols built by these rules:

1. Every propositional variable (p, q, r ...) and the constants T and F are wffs.
2. If A is a wff, then ~A is a wff.
3. If A and B are wffs, then (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) are wffs.
4. Nothing else is a wff.

So (p ∧ ~q) ⇒ r is a wff, but p ∧ ∨ q and ⇒ p q are not.

Order of precedence (when brackets are omitted): ~, then ∧, then ∨, then ⇒, then ⇔.

Representing word problems as wff:

1. Identify the simple propositions and give each a variable.
2. Translate key words: 'not' → ~; 'and', 'but' → ∧; 'or' → ∨; 'if ... then', 'implies', 'only if' → ⇒; 'if and only if' → ⇔.
3. Note: 'p only if q' means p ⇒ q; 'p unless q' means ~q ⇒ p (equivalently p ∨ q).

Example: 'If the alarm rings and Riya is awake, then she will catch the bus.' Let a = alarm rings, w = Riya is awake, b = she catches the bus: (a ∧ w) ⇒ b.

Worked example

Write as a wff: 'You can vote only if you are a citizen and you are at least 18.' Use v, c, e. [1 mark]

Try it first, then show the solutionSolution

1. 'v only if X' means v ⇒ X, where X = c ∧ e.

Answer: v ⇒ (c ∧ e).

Interpretation, truth tables; valid, satisfiable and unsatisfiable formulae

An interpretation of a wff assigns a truth value (T or F) to each of its variables; the wff then evaluates to T or F. A formula with n variables has 2ⁿ interpretations, which form the rows of its truth table.

Classification:

• Valid formula (tautology): true under every interpretation. Example: p ∨ ~p; ((p ⇒ q) ∧ p) ⇒ q.
• Unsatisfiable formula (contradiction): false under every interpretation. Example: p ∧ ~p.
• Satisfiable formula: true under at least one interpretation. Every valid formula is satisfiable; a formula that is satisfiable but not valid is a contingency (for example, p ⇒ q).

Equivalent formulae: A and B are equivalent if they have the same truth value in every interpretation, i.e. A ⇔ B is valid. Useful equivalences: p ⇒ q ≡ ~p ∨ q; De Morgan: ~(p ∧ q) ≡ ~p ∨ ~q and ~(p ∨ q) ≡ ~p ∧ ~q; contrapositive: p ⇒ q ≡ ~q ⇒ ~p.

The program below prints the table of p ⇒ q beside ~p ∨ q (showing they are equivalent) and tests the modus ponens formula over all interpretations.

// Prints the truth table of (p => q) and (~p v q), and classifies ((p => q) ^ p) => q.
public class TruthTable
{
    static boolean implies(boolean x, boolean y) { return !x || y; }

    public static void main(String[] args)
    {
        boolean[] tf = {true, false};
        boolean valid = true, satisfiable = false;
        System.out.println("p     q     | p=>q  ~p v q");
        for (boolean p : tf)
            for (boolean q : tf)
            {
                boolean f1 = implies(p, q);
                boolean f2 = !p || q;
                System.out.printf("%-5s %-5s | %-5s %-5s%n", p, q, f1, f2);
                boolean mp = implies(implies(p, q) && p, q);   // modus ponens formula
                valid = valid && mp;
                satisfiable = satisfiable || mp;
            }
        System.out.println("((p=>q) ^ p) => q valid? " + valid + ", satisfiable? " + satisfiable);
    }
}

Output:

p     q     | p=>q  ~p v q
true  true  | true  true 
true  false | false false
false true  | true  true 
false false | true  true 
((p=>q) ^ p) => q valid? true, satisfiable? true

Worked example

Using a truth table, classify (p ⇒ q) ⇒ (q ⇒ p). [2 marks]

Try it first, then show the solutionSolution

1. Rows (p, q): TT: T ⇒ T = T; TF: F ⇒ T = T; FT: T ⇒ F = F; FF: T ⇒ T = T.
2. True in some rows and false in one: satisfiable but not valid (a contingency).

Answer: Satisfiable but not valid (false only when p is false and q is true).

Logic gates: AND, OR, NOT and the other gates

A logic gate is an electronic circuit that produces a binary output from one or more binary inputs according to a logical rule. 1 = true (high voltage), 0 = false (low).

Gate	Expression	Output is 1 when
NOT	X = A'	A = 0
AND	X = A · B	all inputs are 1
OR	X = A + B	at least one input is 1
NAND	X = (A · B)'	not all inputs are 1
NOR	X = (A + B)'	all inputs are 0
XOR	X = A ⊕ B = A'B + AB'	inputs differ
XNOR	X = (A ⊕ B)' = AB + A'B'	inputs are equal

Truth table (two inputs):

A	B	AND	OR	NAND	NOR	XOR	XNOR
0	0	0	0	1	1	0	1
0	1	0	1	1	0	1	0
1	0	0	1	1	0	1	0
1	1	1	1	0	0	0	1

Link with propositional logic: NOT ↔ ~, AND ↔ ∧, OR ↔ ∨, XNOR ↔ ⇔, and p ⇒ q is built as A' + B.

Universality: AND, OR and NOT together form a functionally complete set: any Boolean function can be built from them. NAND alone and NOR alone are also complete, so they are called universal gates:

• NOT from NAND: (A · A)' = A'.
• AND from NAND: ((A · B)')' (NAND followed by a NAND used as NOT).
• OR from NAND: (A' · B')' = A + B (De Morgan).
• Similarly with NOR: NOT = (A + A)'; OR = ((A + B)')'; AND = (A' + B')' = A · B.

Worked example

Show that OR can be made from three NAND gates. [2 marks]

Try it first, then show the solutionSolution

1. Gate 1: A NAND A = A'; gate 2: B NAND B = B'.
2. Gate 3: A' NAND B' = (A' · B')' = A + B by De Morgan's law.

Answer: NAND each input with itself to get A' and B', then NAND these: (A'B')' = A + B.

Half adder

A half adder adds two bits A and B and produces a Sum (S) and a Carry (C).

A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Expressions: S = A ⊕ B = A'B + AB'; C = A · B.

Circuit: one XOR gate for the sum and one AND gate for the carry.

Limitation: it cannot add a carry coming in from a previous column, so it suits only the least significant bit position.

Worked example

Give the half-adder outputs for A = 1, B = 1, and explain them in binary arithmetic. [1 mark]

Try it first, then show the solutionSolution

1. S = 1 ⊕ 1 = 0; C = 1 · 1 = 1.

Answer: S = 0, C = 1: 1 + 1 = 10₂.

Full adder and combining gates for arithmetic

A full adder adds three bits: A, B and a carry-in (Cin) from the previous column, producing Sum and Carry-out (Cout).

Expressions: Sum = A ⊕ B ⊕ Cin; Cout = A·B + Cin·(A ⊕ B) (equivalently A·B + B·Cin + A·Cin).

Construction: two half adders and an OR gate. The first half adder adds A and B (sum S1, carry C1); the second adds S1 and Cin (sum = final Sum, carry C2); Cout = C1 + C2.

The Java program below simulates this circuit with bitwise operators and prints its truth table.

// Simulates a full adder built from two half adders and an OR gate, and prints its truth table.
public class FullAdder
{
    static int and(int a, int b) { return a & b; }
    static int or(int a, int b)  { return a | b; }
    static int xor(int a, int b) { return a ^ b; }

    public static void main(String[] args)
    {
        System.out.println("A B Cin | Sum Cout");
        for (int a = 0; a <= 1; a++)
            for (int b = 0; b <= 1; b++)
                for (int cin = 0; cin <= 1; cin++)
                {
                    int s1 = xor(a, b);          // first half adder: sum
                    int c1 = and(a, b);          // first half adder: carry
                    int sum = xor(s1, cin);      // second half adder: sum
                    int c2 = and(s1, cin);       // second half adder: carry
                    int cout = or(c1, c2);       // either carry gives Cout
                    System.out.println(a + " " + b + "  " + cin + "  |  " + sum + "    " + cout);
                }
    }
}

Output:

A B Cin | Sum Cout
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

Combining adders for arithmetic: to add two n-bit numbers, connect n full adders in a chain (a ripple-carry adder): each Cout feeds the next Cin; the first stage can be a half adder (or a full adder with Cin = 0). For example, a 4-bit adder adds 0110 + 0111: column sums give 1101 (6 + 7 = 13). Subtraction uses the same adder with 2's complement (invert B and set the first Cin to 1).

Worked example

For a full adder with A = 1, B = 0, Cin = 1, find Sum and Cout using the expressions. [2 marks]

Try it first, then show the solutionSolution

1. Sum = 1 ⊕ 0 ⊕ 1 = 1 ⊕ 1 = 0.
2. Cout = 1·0 + 1·(1 ⊕ 0) = 0 + 1 = 1.

Answer: Sum = 0, Cout = 1 (1 + 0 + 1 = 10₂).

Propositional Logic and Logic Gates 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

• Logic Gates, the Half Adder and the Full Adder
• Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence

Propositional Logic and Logic Gates: syntax and key facts

Implication

p ⇒ q ≡ ~p ∨ q ≡ ~q ⇒ ~p (contrapositive)

De Morgan's laws

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

Number of interpretations

Rows in a truth table = 2ⁿ for n variables

Half adder

S = A ⊕ B = A'B + AB'; C = A · B

Full adder

Sum = A ⊕ B ⊕ Cin; Cout = AB + Cin(A ⊕ B)

XOR and XNOR

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

Propositional Logic and Logic Gates: diagrams to practise

Practise each one on paper: draw it from the checklist, then tick off every label.

How the school exam asks Propositional Logic and Logic Gates

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

Tricks to remember Propositional Logic and Logic Gates

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

• Implication: only T ⇒ F is F

  A promise is broken only when the condition happens and the result does not.

  Use it when: Truth value of p ⇒ q.

• Valid ⊂ satisfiable

  Always true (valid) is a special case of sometimes true (satisfiable); never true is unsatisfiable.

  Use it when: Classifying formulae.

• Bubble = NOT

  NAND = AND + bubble; NOR = OR + bubble; XNOR = XOR + bubble.

  Use it when: Gate symbols.

• Full adder = 2 half adders + OR

  Sum: XOR of all three; carry: any two are 1.

  Use it when: Full adder.

Propositional Logic and Logic Gates: exam-level solved questions

Ordered from exam 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 a school exam set on the board pattern this is a 5-mark question split into 2 + 1 + 2 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 Propositional Logic and Logic Gates

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

• ✗Mistake: Taking F ⇒ T as false

  An implication is false only when the antecedent is true and the consequent false.

  ✓Do this: Remember the single F row: T ⇒ F.

  Usually costs: 1-2 marks.

• ✗Mistake: Confusing satisfiable with valid

  Satisfiable needs one true row; valid needs all rows true.

  ✓Do this: Check every row before calling a formula valid.

  Usually costs: 1 mark.

• ✗Mistake: Translating 'p only if q' as q ⇒ p

  'Only if' introduces the necessary condition: p ⇒ q.

  ✓Do this: 'Only if' points to the consequent.

  Usually costs: 1 mark.

• ✗Mistake: Drawing NAND or NOR without the output bubble

  The bubble is what makes them inverted gates.

  ✓Do this: Always add the bubble.

  Usually costs: ½-1 mark.

Practice questions on Propositional Logic and Logic Gates

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 · MCQExam level

   Which of the following is NOT a proposition?
   (a) 7 is a prime number.
   (b) Please shut the window.
   (c) The Earth is flat.
   (d) 2 + 3 = 6.

   Hint

   Commands have no truth value.

   Answer

   (b) Please shut the window.

2. Q2 · 1 mark · Very short answerExam level

   State the output of an XNOR gate for inputs A = 1, B = 0.

   Hint

   Equal inputs give 1.

   Answer

   0, because the inputs differ.

3. Q3 · 2 marks · Short answerExam level

   Draw the truth table of p ∧ (q ∨ ~p) and classify it.

   Hint

   Four rows.

   Answer

   Rows (p, q): TT → T ∧ T = T; TF → T ∧ F = F; FT → F; FF → F. True in one row only: satisfiable but not valid (it is equivalent to p ∧ q).

4. Q4 · 2 marks · Short answerHarder exam level

   Show that (p ∧ q) ⇒ p is valid.

   Hint

   When can the antecedent be true?

   Answer

   The antecedent p ∧ q is true only in row TT, where p is also true, so the implication is never 'T ⇒ F'. Rows: TT → T, TF → (F ⇒ T) T, FT → (F ⇒ F) T, FF → T. True in all rows: valid.

5. Q5 · 2 marks · Short answerHarder exam level

   Show that ~(p ∨ q) ∧ p is unsatisfiable.

   Hint

   De Morgan.

   Answer

   ~(p ∨ q) ≡ ~p ∧ ~q, so the formula is ~p ∧ ~q ∧ p, which contains p ∧ ~p and is false in every row (TT F, TF F, FT F, FF F): unsatisfiable.

6. Q6 · 5 marks · Short answerHarder exam level

   Construct AND and NOT gates using only NOR gates, with expressions.

   Hint

   Tie inputs; De Morgan.

   Answer

   NOT: tie both inputs of a NOR: (A + A)' = A'. AND: invert A and B with two NOR-as-NOT gates to get A' and B', then NOR them: (A' + B')' = A·B (De Morgan). Three NOR gates in all.

7. Q7 · 2 marks · Short answerHarder exam level

   For a half adder, write the expressions and explain why it cannot be used for the second bit of a multi-bit addition.

   Hint

   Carry in.

   Answer

   S = A ⊕ B, C = A·B. The second and later bits must also add the carry from the previous column, but a half adder has only two inputs, so a full adder (three inputs) is needed.

8. Q8 · 5 marks · Short answerHOTS / competency

   Translate and classify: 'If it is a holiday then the school is closed, and it is a holiday, and the school is not closed.'

   Hint

   h, c.

   Answer

   Let h = holiday, c = school closed: (h ⇒ c) ∧ h ∧ ~c. Rows: TT → (T) ∧ T ∧ F = F; TF → (F) ∧ ... = F; FT → T ∧ F ∧ F = F; FF → T ∧ F ∧ T = F. False in every row: unsatisfiable (the statements contradict each other).

9. Q9 · 5 marks · Short answerHOTS / competency

   A circuit has output X = (A ⊕ B) · C. Draw its truth table and state when X = 1.

   Hint

   Eight rows.

   Answer

   Rows ABC: 000 0; 001 0; 010 0; 011 1; 100 0; 101 1; 110 0; 111 0. X = 1 when C = 1 and exactly one of A, B is 1 (rows 011 and 101).

10. Q10 · 10 marks · Long answerHOTS / competency

    Explain the universality of NAND and NOR gates, and why manufacturers prefer them.

    Hint

    Build NOT, AND, OR from each; cost.

    Answer

    A set of gates is universal (functionally complete) if every Boolean function can be built from it. AND, OR and NOT are complete, since any truth table can be written as an OR of AND terms. NAND alone is complete: NOT = (A·A)'; AND = ((A·B)')' (two gates); OR = (A'·B')' (three gates). NOR alone is complete: NOT = (A + A)'; OR = ((A + B)')'; AND = (A' + B')'. Since NOT, AND and OR can be made, any circuit can be built entirely from NANDs or entirely from NORs. Manufacturers prefer them because a chip of one gate type is cheaper to design and produce, NAND and NOR are simple and fast in transistor technology, and stock of a single gate type simplifies building and repairing circuits.

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.When is p ⇒ q false?Show answer

   Only when p is true and q is false.

2. 2.Valid formula?Show answer

   True under every interpretation (tautology).

3. 3.Rows for 3 variables?Show answer

   2³ = 8.

4. 4.Universal gates?Show answer

   NAND and NOR.

5. 5.Half adder outputs?Show answer

   S = A ⊕ B, C = AB.

6. 6.Full adder sum?Show answer

   A ⊕ B ⊕ Cin.

Quick revision checklist

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

• ☐Connectives: ~, ∧, ∨, ⇒ (false only T ⇒ F), ⇔ (same values).
• ☐wff: variables; ~A; (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B).
• ☐Valid: all T; unsatisfiable: all F; satisfiable: at least one T.
• ☐p ⇒ q ≡ ~p ∨ q ≡ ~q ⇒ ~p.
• ☐Gates: AND, OR, NOT (complete set); NAND, NOR universal; XOR = differ, XNOR = equal.
• ☐Half adder: S = A ⊕ B, C = AB; full adder: Sum = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B).

Propositional Logic and Logic Gates: frequently asked questions