Computer ScienceISC Class 11 · Propositional Logic and Logic Gates

Propositional Logic, Connectives and Truth Tables (ISC Class 11 Computer Science)

Updated 17 October 2026 · Fact-checked

A proposition is a statement that is either true or false. Propositional variables (p, q, r) are combined by connectives: negation (not), conjunction (and), disjunction (or), implication (if-then) and biconditional (if and only if). A truth table lists the value of a formula for every combination of values of its variables (2^n rows for n variables). A formula that is always true is a tautology (valid), always false a contradiction (unsatisfiable), and true for some interpretation, satisfiable.

Understand Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence

Propositions and connectives. A proposition is a declarative statement with a truth value (true T or false F); questions and commands are not propositions.

Connective	Symbol	Read as	True when
Negation	not p	not p	p is false
Conjunction	p AND q	p and q	both true
Disjunction	p OR q	p or q	at least one true
Implication	p -> q	if p then q	false only when p is true and q is false
Biconditional	p <-> q	p if and only if q	p and q have the same value

Truth tables (rows TT, TF, FT, FF for p, q).

p AND q: T F F F.
p OR q: T T T F.
p -> q: T F T T.
q -> p (converse): T T F T.
p <-> q: T F F T.

Implication equals (not p) OR q. The contrapositive (not q -> not p) is equivalent to p -> q.

Interpretation. One assignment of truth values to all variables. A formula with n variables has 2^n interpretations.

Classification. *Tautology (valid):* true in every interpretation (p OR not p). *Contradiction (unsatisfiable):* false in every interpretation (p AND not p). *Contingency:* neither. *Satisfiable:* true in at least one interpretation (every tautology and contingency).

Equivalences. De Morgan: not (p AND q) = (not p) OR (not q); not (p OR q) = (not p) AND (not q). Double negation: not not p = p. Distributive and commutative laws.

Word problems. Name each simple statement with a variable and join them: "You may enter if you have a ticket and are above 12 or with an adult" becomes t AND (a OR c).

Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence: key facts

Number of rows: Rows = 2^n | n = number of variables; Truth table size.
Implication: p -> q = (not p) OR q | False only for p true and q false; Equivalent form.
De Morgan: not (p AND q) = (not p) OR (not q) | not (p OR q) = (not p) AND (not q); Verify by truth table.

How to answer Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence questions

Build the truth table column by column.

1List all 2^n interpretations in a fixed order.
2Evaluate each sub-formula in its own column, innermost first.
3Read the final column: all T is a tautology, all F a contradiction.
4For equivalence, compare two final columns.

Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence in real life

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

Implication

Suppose a teacher promises: "If you score 90, you get a prize."

In which case is the promise broken?

Try it first, then show the solutionSolution

The promise p -> q is false only when p is true and q is false.
That is when a student scores 90 but gets no prize.

Answer: Only when the student scores 90 and gets no prize.

Memory hook: A promise breaks only when the condition is met but the result is not.

Tricks to remember Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence

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

Implication is false only on TF
True cannot imply false.
Use it when: p -> q.
And needs both, or needs one
AND: all true; OR: any true.
Use it when: Connectives.
2 to the n rows
3 variables give 8 rows.
Use it when: Table size.

Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

Example 1: Truth value · 1 mark · MCQBoard level

p -> q is false when:
(a) p false and q true (b) p true and q false (c) both true (d) both false

Try it first, then show the solutionSolution

Implication fails only when the premise is true and the conclusion false.

Answer: (b) p true and q false

Example 2: Evaluate · 4 marks · Short answerBoard level

For p = T, q = F, r = F evaluate: (i) p AND (q OR not r) (ii) (p -> q) OR r (iii) p <-> (q OR r) (iv) not (p AND q). (4 marks)

Try it first, then show the solutionSolution

(i) not r = T; q OR T = T; T AND T = T.
(ii) p -> q = F; F OR F = F.
(iii) q OR r = F; T <-> F = F.
(iv) p AND q = F; not F = T.

Answer: (i) T; (ii) F; (iii) F; (iv) T.

Example 3: Prove De Morgan by truth table · 6 marks · Long answerHarder board level

Using a truth table show that not (p AND q) is equivalent to (not p) OR (not q), and that p -> q is equivalent to (not p) OR q. (6 marks)

Try it first, then show the solutionSolution

Rows: p q = TT, TF, FT, FF.
not (p AND q): F, T, T, T. (not p) OR (not q): F, T, T, T. Equal in every row.
p -> q: T, F, T, T. (not p) OR q: T, F, T, T. Equal.

Answer:

p	q	p AND q	not (p AND q)	not p OR not q	p -> q	not p OR q
T	T	T	F	F	T	T
T	F	F	T	T	F	F
F	T	F	T	T	T	T
F	F	F	T	T	T	T

The columns match, so the formulas are equivalent.

Example 4: Classify formulas · 6 marks · Long answerHarder board level

Classify as tautology, contradiction or contingency by truth table: (a) p OR not p (b) p AND not p (c) p -> not p (d) (p -> q) AND p -> q. Also state which are satisfiable. (6 marks)

Try it first, then show the solutionSolution

(a) T, T: tautology.
(b) F, F: contradiction.
(c) p = T gives T -> F = F; p = F gives F -> T = T: contingency (true when p is false).
(d) If p -> q and p are true, q is true: always true: tautology (modus ponens).
Satisfiable: (a), (c), (d); (b) is unsatisfiable.

Answer: (a) tautology; (b) contradiction; (c) contingency; (d) tautology. Satisfiable: a, c, d.

Example 5: Word problem · 6 marks · Long answerHOTS / competency

Write the formula for the rule "A visitor may enter if the visitor has a ticket (t) and is either above 12 years (a) or accompanied by an adult (c)". Evaluate it for t = T, a = F, c = T and for t = F, a = T, c = T, and give the number of interpretations. Write the negation of the rule using De Morgan. (6 marks)

Try it first, then show the solutionSolution

Formula: t AND (a OR c).
t = T, a = F, c = T: a OR c = T; T AND T = T: may enter.
t = F, a = T, c = T: F AND T = F: may not enter.
3 variables: 2^3 = 8 interpretations.
Negation: not t OR not (a OR c) = not t OR (not a AND not c): no ticket, or neither above 12 nor accompanied.

Answer: t AND (a OR c); first case T, second F; 8 interpretations; negation is (not t) OR ((not a) AND (not c)).

Where students lose marks in Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence

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

Mistake: Treating p -> q as false when p is false
Everyday meaning.
Wrong working
F -> T = F
Right working
F -> T = T
Do this: False premise gives true implication.
Usually costs: 2 marks.
Mistake: Wrong number of rows
Counting variables.
Wrong working
3 variables, 6 rows
Right working
8 rows
Do this: 2^n.
Usually costs: 1-2 marks.
Mistake: Distributing not without changing the connective
De Morgan slip.
Wrong working
not (p AND q) = not p AND not q
Right working
not p OR not q
Do this: Swap AND and OR.
Usually costs: 2 marks.

Exam tips

Always list rows in the order TT, TF, FT, FF.
Use one column per sub-formula.
Define each variable in a word problem.

Practice questions on Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence

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

Q1 · 1 mark · MCQBoard level
A formula that is true for every interpretation is called a:
(a) contradiction (b) tautology (c) contingency (d) proposition
Hint
Valid.
Answer
(b) tautology
Q2 · 3 marks · Short answerBoard level
Write the truth table of p <-> q and of (p -> q) AND (q -> p), and state the relation. (3 marks)
Hint
Rows TT, TF, FT, FF.
Answer
p <-> q: T, F, F, T. (p -> q) AND (q -> p): (T AND T) = T, (F AND T) = F, (T AND F) = F, (T AND T) = T. The columns are identical: the biconditional is the conjunction of the two implications.
Q3 · 4 marks · Short answerHarder board level
Construct the truth table of (p OR q) AND not (p AND q) and name the operation it represents. (4 marks)
Hint
Exactly one is true.
Answer
Rows TT, TF, FT, FF give F, T, T, F. It is true when exactly one of p and q is true: the exclusive OR (XOR).
Q4 · 6 marks · Long answerHarder board level
Construct the truth table of (p -> q) AND (q -> r) -> (p -> r) with 8 rows and decide whether it is a tautology. (6 marks)
Hint
If premise is true, conclusion must be.
Answer
The premise (p -> q) AND (q -> r) is true only if no row has p true with q false, or q true with r false. In each such row, p -> r is true, so the whole formula is true in all 8 rows: it is a tautology (hypothetical syllogism).
Q5 · 4 marks · Short answerHOTS / competency
Translate "If the server is down or the network is slow, then the page does not load; the page loads; therefore the server is not down." Name the variables, write the argument as a formula and say whether it is valid. (4 marks)
Hint
((d OR s) -> not l) AND l -> not d.
Answer
d: the server is down; s: the network is slow; l: the page loads. Formula: ((d OR s) -> not l) AND l -> not d. If l is true, then not l is false, so (d OR s) must be false, which makes d false: not d. The formula is a tautology: the argument is valid.

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.Rows for 3 variables?Show answer
8.
2.p -> q false when?Show answer
p true and q false.
3.De Morgan for AND?Show answer
Not p OR not q.
4.Tautology?Show answer
True in every interpretation.
5.Contradiction?Show answer
False in every interpretation.

Propositional Logic: Connectives, Truth Tables, Tautology and Equivalence: frequently asked questions

Is a question a proposition?

No.

What is satisfiable?

True for at least one interpretation.

What is the converse of p -> q?

q -> p.

What is the contrapositive?

not q -> not p.