Computer ScienceISC Class 12 · Boolean Algebra

Propositional Logic, wff and Equivalence Laws (ISC Class 12 Computer Science)

Updated 17 October 2026 · Draft, not yet fact-checked

A well formed formula (wff) is a statement built from propositional variables with the connectives ~, ∧, ∨, ⇒ and ⇔. Its truth table decides whether it is valid (always true), unsatisfiable (always false) or satisfiable. Equivalence laws such as p ⇒ q ≡ ~p ∨ q and De Morgan's laws let you simplify a wff without a table.

Valid and contingency formulas are both satisfiable; an unsatisfiable formula like p ∧ ~p is false in every row of its truth table.

Illustration drawn for QuestionBuddy.

Understand Propositional Logic, Well Formed Formulae and Equivalence Laws

Propositional variables and connectives. A propositional variable (p, q, r) stands for a statement that is either true or false. The connectives are ~ (not, negation), ∧ (and, conjunction), ∨ (or, disjunction), ⇒ (implication) and ⇔ (biconditional).

wff. A single variable, or true/false, is a wff. If A and B are wffs then ~A, (A ∧ B), (A ∨ B), (A ⇒ B) and (A ⇔ B) are wffs. Nothing else is. So p ∧ ⇒ q is not a wff, but (p ∧ q) ⇒ ~r is.

Interpretation and truth table. An interpretation gives every variable a truth value. A wff with n variables has 2^n interpretations, and the truth table lists the value of the wff for each.

p	q	p ⇒ q	p ⇔ q
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

p ⇒ q is false in exactly one case: p true and q false. p ⇔ q is true when p and q have the same value.

Classifying a wff. Valid (tautology): true under every interpretation. Unsatisfiable (contradiction): false under every interpretation. Satisfiable: true under at least one interpretation. A satisfiable wff that is not valid is a contingency.

Equivalence laws. Commutative and associative laws for ∧ and ∨; distributive laws; De Morgan: ~(p ∧ q) ≡ ~p ∨ ~q and ~(p ∨ q) ≡ ~p ∧ ~q; implication: p ⇒ q ≡ ~p ∨ q; biconditional: (p ⇔ q) ≡ (p ⇒ q) ∧ (q ⇒ p); negation: ~(~p) ≡ p; excluded middle: p ∨ ~p ≡ true; contradiction: p ∧ ~p ≡ false. Simplification rules: p ∧ true ≡ p, p ∧ false ≡ false, p ∨ true ≡ true, p ∨ false ≡ p.

Related implications. For p ⇒ q: converse is q ⇒ p; inverse is ~p ⇒ ~q; contrapositive is ~q ⇒ ~p. Only the contrapositive is equivalent to the original.

Inference rules. Modus ponens: from p ⇒ q and p, conclude q. Chain rule (hypothetical syllogism): from p ⇒ q and q ⇒ r, conclude p ⇒ r.

Boolean theorems, SOP/POS and Karnaugh maps are a separate topic.

Propositional Logic, Well Formed Formulae and Equivalence Laws: key facts

Implication law: p ⇒ q ≡ ~p ∨ q
False only when p is true and q is false
Contrapositive ~q ⇒ ~p is equivalent; Use it to remove ⇒ before simplifying.
Biconditional law: (p ⇔ q) ≡ (p ⇒ q) ∧ (q ⇒ p) | True when p and q have the same value; Expand it when simplifying.
De Morgan's laws: ~(p ∧ q) ≡ ~p ∨ ~q
~(p ∨ q) ≡ ~p ∧ ~q
Change the connective and negate each part; Negation of a compound statement.
Classification of a wff: Valid true in every row
Unsatisfiable false in every row
Satisfiable true in at least one row
Contingency satisfiable but not valid; Needs 2^n rows for n variables.

Valid	true in every row
Unsatisfiable	false in every row
Satisfiable	true in at least one row
Contingency	satisfiable but not valid

How to answer Propositional Logic, Well Formed Formulae and Equivalence Laws questions

Use this routine for truth-table and simplification questions.

1Write the wff fully bracketed and list the variables; the table has 2^n rows.
2Add a column for each sub-formula, working from the innermost brackets outwards.
3Read the last column: all T means valid, all F means unsatisfiable, otherwise a contingency.
4To simplify, first replace ⇒ and ⇔ by ~, ∧, ∨ using the implication and biconditional laws.
5Then apply De Morgan, distribution, p ∧ ~p ≡ false and p ∨ ~p ≡ true, naming the law at each step.
6For word problems, define the variables (p: ..., q: ...) before writing the wff.

Propositional Logic, Well Formed Formulae and Equivalence Laws 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.

Rule for a door-access system

Suppose a lab door rule says: if the card is valid (p) then the door opens (q).

The door did not open. What can you conclude about the card, and which law gives it?

Try it first, then show the solutionSolution

The rule is p ⇒ q and ~q is observed.
The contrapositive ~q ⇒ ~p is equivalent to the rule, so modus ponens on it gives ~p.

Answer: The card was not valid (contrapositive with modus ponens).

Memory hook: No effect means no cause, if the rule is the only way.

Negating a notification setting

Suppose an app sends an alert when the battery is low (p) or the storage is full (q).

When does the app send no alert? Write it as a wff.

Try it first, then show the solutionSolution

Alert is p ∨ q, so no alert is ~(p ∨ q).
De Morgan gives ~p ∧ ~q.

Answer: ~p ∧ ~q: battery not low and storage not full.

Memory hook: No "or" means neither one.

Tricks to remember Propositional Logic, Well Formed Formulae and Equivalence Laws

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

Promise broken
p ⇒ q is a promise: it is broken (false) only when p happens and q does not.
Use it when: Filling the implication column.
Same or different
p ⇔ q is true when the two values are the same.
Use it when: Biconditional column.
Only the contrapositive
Flip and negate (~q ⇒ ~p) keeps the meaning; flip alone (converse) or negate alone (inverse) does not.
Use it when: Converse, inverse, contrapositive questions.
Break the bar, change the sign
De Morgan: negating a bracket changes ∧ to ∨ and ∨ to ∧.
Use it when: Negating compound statements.

Propositional Logic, Well Formed Formulae and Equivalence Laws: solved examples

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

Example 1: Implication as OR · 1 mark · MCQBoard level

Which wff is equivalent to p ⇒ q?
(a) p ∨ ~q (b) ~p ∨ q (c) ~p ∧ q (d) q ⇒ p

Try it first, then show the solutionSolution

The implication law gives p ⇒ q ≡ ~p ∨ q.
Check row p = T, q = F: ~p ∨ q = F ∨ F = F, matching p ⇒ q = F.

Answer: (b) ~p ∨ q

Example 2: Classify with a truth table · 3 marks · Short answerHarder board level

Construct the truth table of (p ∨ q) ⇒ (p ∧ q) and state whether it is valid, unsatisfiable or satisfiable.

Try it first, then show the solutionSolution

Rows (p, q): TT gives p ∨ q = T, p ∧ q = T, result T. (1 mark)
TF gives T and F, result F. FT gives T and F, result F. FF gives F and F, result T. (1 mark)
The column is T, F, F, T: true in some rows, false in others. (1 mark)

Answer: Satisfiable but not valid (a contingency); it is true exactly when p and q have the same value.

Example 3: Simplify using laws · 3 marks · Short answerHarder board level

Simplify (p ⇒ q) ∧ (p ⇒ ~q), naming the law used at each step.

Try it first, then show the solutionSolution

Implication law: (~p ∨ q) ∧ (~p ∨ ~q). (1 mark)
Distributive law: ~p ∨ (q ∧ ~q). (1 mark)
Contradiction law q ∧ ~q ≡ false, then p ∨ false rule: ~p. (1 mark)

Answer: ~p

Example 4: Converse, inverse, contrapositive · 3 marks · Short answerHarder board level

Write the converse, inverse and contrapositive of: "If a number ends in 0, then it is divisible by 10". Which one is logically equivalent to the original?

Try it first, then show the solutionSolution

p: the number ends in 0; q: it is divisible by 10; the original is p ⇒ q.
Converse q ⇒ p: if a number is divisible by 10 then it ends in 0. Inverse ~p ⇒ ~q: if it does not end in 0 then it is not divisible by 10. Contrapositive ~q ⇒ ~p: if it is not divisible by 10 then it does not end in 0.
Only the contrapositive is equivalent.

Answer: The contrapositive is equivalent; the converse and inverse are equivalent to each other, not to the original.

Example 5: Case: report server · 4 marks · Case-basedHOTS / competency

Suppose a system obeys these rules. p: the server is up; q: the backup runs; r: the report is sent.
Rule 1: if the server is up then the backup runs. Rule 2: if the backup runs then the report is sent. Fact: the server is up.
(i) Write the rules as wffs. (1 mark)
(ii) Name the rule that gives p ⇒ r. (1 mark)
(iii) Show that r follows. (2 marks)

Try it first, then show the solutionSolution

(i) p ⇒ q and q ⇒ r, with the fact p.
(ii) The chain rule on p ⇒ q and q ⇒ r gives p ⇒ r.
(iii) Modus ponens on p ⇒ r and p gives r. Equivalently: p true makes q true, and q true makes r true.

Answer: (i) p ⇒ q, q ⇒ r, p (ii) chain rule (iii) r: the report is sent, by modus ponens

Where students lose marks in Propositional Logic, Well Formed Formulae and Equivalence Laws

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

Mistake: Treating the converse as equivalent
Only the contrapositive keeps the meaning of p ⇒ q.
Wrong working
p ⇒ q ≡ q ⇒ p
Right working
p ⇒ q ≡ ~q ⇒ ~p
Do this: Flip and negate together.
Usually costs: 1 mark
Mistake: Wrong row for implication
p ⇒ q is false only for p true and q false, not whenever q is false.
Wrong working
p = F, q = F gives p ⇒ q = F
Right working
p = F, q = F gives p ⇒ q = T
Do this: A false p always gives a true implication.
Usually costs: 1 mark
Mistake: Half De Morgan
The connective must change as well as the signs.
Wrong working
~(p ∧ q) ≡ ~p ∧ ~q
Right working
~(p ∧ q) ≡ ~p ∨ ~q
Do this: Change ∧ to ∨ and negate each part.
Usually costs: 1 mark

Exam tips

Always write 2^n rows in the standard order TT, TF, FT, FF.
Show one column for every sub-formula; the examiner awards marks per column.
Name the law in the right-hand margin at each simplification step.
State the classification in words (valid, unsatisfiable or satisfiable) after the table.
In a word problem, define each variable before writing the wff.

Practice questions on Propositional Logic, Well Formed Formulae and Equivalence Laws

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
Which of these is unsatisfiable?
(a) p ∨ ~p (b) p ∧ ~p (c) p ⇒ p (d) p ⇔ p
Hint
It must be false in every row.
Answer
(b) p ∧ ~p (law of contradiction); the others are valid.
Q2 · 2 marks · Short answerBoard level
Use De Morgan's law to write the negation of: "The user has a card or a coupon".
Hint
Negate an "or".
Answer
With p: has a card, q: has a coupon, ~(p ∨ q) ≡ ~p ∧ ~q: the user has no card and no coupon.
Q3 · 3 marks · Short answerHarder board level
Show by a truth table that ((p ⇒ q) ∧ p) ⇒ q is valid. Name the rule it expresses.
Hint
Four rows.
Answer
TT: (T ∧ T) ⇒ T = T. TF: (F ∧ T) = F, F ⇒ F = T. FT: (T ∧ F) = F, F ⇒ T = T. FF: (T ∧ F) = F, F ⇒ F = T. All T, so it is valid. It is modus ponens.
Q4 · 3 marks · Short answerHarder board level
Simplify p ∨ (p ∧ q) using the equivalence laws and confirm with a truth table.
Hint
Write p as p ∧ true.
Answer
p ∨ (p ∧ q) ≡ (p ∧ true) ∨ (p ∧ q) ≡ p ∧ (true ∨ q) ≡ p ∧ true ≡ p. Table (p, q): TT gives T, TF gives T, FT gives F, FF gives F, the same as p.
Q5 · 3 marks · Case-basedHOTS / competency
Rule: "If the alarm is on (p) then the door is locked (q)". The door is not locked. (i) State what follows. (ii) Show why a student who says "the door is locked, so the alarm is on" is wrong.
Hint
One is the contrapositive, the other the converse.
Answer
(i) ~q with p ⇒ q gives ~p by the contrapositive and modus ponens: the alarm is not on. (ii) That is the converse q ⇒ p, which is not equivalent: with p = F and q = T, p ⇒ q is true but q ⇒ p is false.

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.When is p ⇒ q false?Show answer
Only when p is true and q is false.
2.When is p ⇔ q true?Show answer
When p and q have the same truth value.
3.What is a valid formula?Show answer
One that is true under every interpretation.
4.What is the contrapositive of p ⇒ q?Show answer
~q ⇒ ~p.
5.State modus ponens.Show answer
From p ⇒ q and p, conclude q.
6.State the chain rule.Show answer
From p ⇒ q and q ⇒ r, conclude p ⇒ r.

Propositional Logic, Well Formed Formulae and Equivalence Laws: frequently asked questions

What is a wff in propositional logic?

A well formed formula built from propositional variables and the connectives ~, ∧, ∨, ⇒ and ⇔ by the formation rules, with correct bracketing.

What is the difference between satisfiable and valid?

Satisfiable means true for at least one interpretation; valid means true for all of them. Every valid formula is satisfiable but not the other way round.

How many rows does a truth table have?

2^n rows for n propositional variables, so 4 rows for two variables and 8 for three.

Is the inverse of an implication equivalent to it?

No. The inverse ~p ⇒ ~q is equivalent to the converse q ⇒ p, not to the original p ⇒ q.