MHT-CET Maths · Mathematical Logic

Logical Equivalence and Algebra of Statements

Two statement patterns are logically equivalent when their last columns match, and a short list of algebra laws lets you simplify one into the other without building a table.

All Mathematical Logic notes MHT-CET Maths strategy

Why this matters

16 PYQs sit here at 31% HARD, and this is the subtopic that decides how long the rest of the chapter takes you. Every 'is equivalent to' question can be answered by an eight-row truth table, which is slow and error-prone, or by three lines of algebra, which is neither. The same laws then do the work in Switching Circuits, so the time spent here is paid back twice.

Concept 1 of 6

What Logical Equivalence Means

Intuition

Two patterns are equivalent if they can never disagree — not merely if they look similar or happen to agree in one row. The definitive test is that their final columns are identical, row for row.

Definition

$A \equiv B$ means $A$ and $B$ have the same truth value in every row of the truth table.

Equivalently, $A \leftrightarrow B$ is a tautology.
Equivalent statements may be substituted for each other anywhere, which is what makes simplification legal.
To disprove equivalence you need only ONE row where they differ — a counterexample, not a full table.

Equivalence and its test

A \equiv B \iff (A \leftrightarrow B) \text{ is a tautology} \iff A \text{ and } B \text{ share every row}

$\equiv$ logically equivalent — a claim about all rows
$\leftrightarrow$ a connective, evaluated row by row

Worked example

Show that

p \to q

and

\sim p \vee q

are logically equivalent.

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 1Mathematical LogicMODERATE

If statement I: If the work is not finished on time, the contractor is in trouble. Statement II: Either the work is finished on time or the contractor is in trouble. Then

[Q140 · 2nd May Shift 1 · 2023]

Checking one row and declaring equivalence

Agreeing in a row proves nothing; equivalence needs EVERY row. The asymmetry is worth holding onto: one row can disprove equivalence but never establish it.

Concept 2 of 6

The Algebra of Statements

Intuition

These laws are the ordinary algebra of numbers with AND behaving like multiplication and OR like addition — except that distribution works both ways round here, which ordinary arithmetic does not allow.

Definition

Simplification uses a short list of named laws. T denotes a tautology and F a contradiction:

The two that do the most work are complement and distributive.
The conditional law is what lets you remove an arrow so the others can apply.
Absorption is the one students most often fail to spot, and it collapses a whole bracket in one move.

Law	With AND	With OR
Commutative	$p \wedge q \equiv q \wedge p$	$p \vee q \equiv q \vee p$
Associative	$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$	$(p \vee q) \vee r \equiv p \vee (q \vee r)$
Distributive	$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ Both directions are legal here, unlike ordinary arithmetic where only one distribution holds.
Identity	$p \wedge T \equiv p$	$p \vee F \equiv p$
Domination	$p \wedge F \equiv F$	$p \vee T \equiv T$
Complement	$p \wedge \sim p \equiv F$	$p \vee \sim p \equiv T$ The engine of most simplifications: spot a letter meeting its own negation and a whole branch collapses to F or T.
Idempotent	$p \wedge p \equiv p$	$p \vee p \equiv p$
Absorption	$p \wedge (p \vee q) \equiv p$	$p \vee (p \wedge q) \equiv p$ The whole bracket vanishes. Worth memorising by shape: a letter outside meeting itself inside swallows the rest.
De Morgan	$\sim(p \wedge q) \equiv \;\sim p \vee \sim q$	$\sim(p \vee q) \equiv \;\sim p \wedge \sim q$
Conditional	$\sim(p \to q) \equiv p \wedge \sim q$	$p \to q \equiv \;\sim p \vee q$ Always apply this first. The other laws cannot see through an arrow.

Ten laws cover every simplification the paper sets. Complement, distributive and absorption account for most of the work.

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 2Mathematical LogicMODERATE

The proposition

(\sim p) \vee (p \wedge \sim q)

is equivalent to

[Q102 · 16th May Shift 1 · 2023]

Distributing only one way

In logic, OR distributes over AND as well:

p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)

. Students trained on ordinary algebra expect only

p \wedge (q \vee r)

to expand and miss the other half.

Drill 1 more on the algebra of statements

Concept 3 of 6

Simplifying a Statement Pattern

Intuition

There is a reliable order: clear the arrows, push the negations in, then look for a letter meeting its own negation. Almost every 'is equivalent to' question on this paper collapses within three or four lines if you work in that order.

Definition

The standard simplification order:

Clear arrows with the conditional law, so only $\sim, \wedge, \vee$ remain.
Push negations inwards with De Morgan, cancelling double negations as they appear.
Distribute or factor to bring like letters together.
Collapse with complement, absorption, identity and domination.

Stop as soon as the expression matches an option — you do not have to reach the simplest possible form.

Worked example

Simplify

[p \wedge (q \vee r)] \vee [\sim r \wedge \sim q \wedge p]

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 3Mathematical LogicHARD

The logical statement

(\sim(\sim p\vee q)\vee(p\wedge r))\wedge(\sim q\wedge r)

is equivalent to

[Q140 · 11th May Shift 2 · 2024]

Simplifying around an arrow instead of clearing it

De Morgan, distribution and absorption are stated for

\wedge

and

\vee

only. Leaving a

\to

in place and trying to distribute across it produces confident nonsense. Clear every arrow first.

Drill 6 more on simplifying a statement pattern

Concept 4 of 6

Tautology, Contradiction and Contingency

Intuition

Once you have the last column, the classification is just a glance: all T is a tautology, all F is a contradiction, and anything with a mix is a contingency. Most exam patterns simplify to T or F long before the table is finished.

Definition

Classify a statement pattern by its final column:

Tautology — true in every row. It simplifies to $T$ .
Contradiction — false in every row. It simplifies to $F$ .
Contingency — at least one T and at least one F. It simplifies to something still containing a letter.

The fastest route is almost always to simplify with the algebra laws and see whether a bare $T$ or $F$ falls out.

Classification by last column

\text{tautology} \Rightarrow \text{all } T \qquad \text{contradiction} \Rightarrow \text{all } F \qquad \text{contingency} \Rightarrow \text{mixed}

$p \vee \sim p$ the standard tautology
$p \wedge \sim p$ the standard contradiction

Worked example

Classify

(p \wedge \sim q) \wedge (\sim p \wedge q)

as a tautology, contradiction or contingency.

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 4Mathematical LogicMODERATE

p

and

q

are statements, then which of the following is a contingency.

[Q107 · 3rd May 2nd Shift · 2023]

Calling a contingency a tautology after checking two rows

A pattern that comes out T in the rows you happened to try may still be F elsewhere. Either simplify all the way to a bare

T

, or check every row — a partial table cannot establish a tautology.

Drill 3 more on tautology, contradiction and contingency

Concept 5 of 6

The Dual of a Statement Pattern

Intuition

The dual is a mechanical mirror: swap every AND with OR and every T with F, and leave the letters completely alone. It looks like a negation at a glance, and that resemblance is exactly what the paper tests.

Definition

The dual of a statement pattern is obtained by interchanging:

$\wedge$ with $\vee$ , and
$T$ with $F$ .

The statement letters and every $\sim$ stay exactly as they are. A conditional must be written in $\sim, \wedge, \vee$ form before a dual can be taken. The dual of the dual returns the original, and the laws in the table above come in dual pairs — which is why they are listed in two columns.

Dual versus negation

\text{dual}(p \wedge \sim q) = p \vee \sim q \qquad \sim(p \wedge \sim q) \equiv\; \sim p \vee q

dualswap the connectives only — letters untouched
$\sim$ negation — swaps connectives AND negates every letter

Worked example

Write the dual of

[\sim q \wedge (p \vee \sim q) \wedge \sim r] \vee p

Practice this conceptself-check · 4 quick reps

Negating the letters when asked for a dual

The dual of

p \wedge \sim q

p \vee \sim q

, NOT

\sim p \vee q

. The second is the negation. Duals touch connectives and constants only, and the two operations produce different statements that both appear in the option list.

Concept 6 of 6

Finding the Statement That Makes a Pattern a Tautology

Intuition

A recurring stem says 'this pattern is a tautology — what must r be?'. Turn it round: a conditional is a tautology exactly when its consequent is true in every row where the antecedent is. So simplify the antecedent first and read off what it forces.

Definition

For $X \to r$ to be a tautology, $r$ must be true in every row where $X$ is true.

Simplify $X$ first — it usually collapses to something small.
Read off the rows where the simplified $X$ holds.
The answer is the option that is true in all of those rows; it need not be true everywhere else.

A useful simplification: $(p \to q) \wedge \sim q \equiv \;\sim p \wedge \sim q$ , the modus tollens pattern.

Tautology condition and modus tollens

(X \to r) \text{ is a tautology} \iff X = T \Rightarrow r = T \qquad (p \to q) \wedge \sim q \equiv\; \sim p \wedge \sim q

Xthe antecedent — simplify this before anything else
rthe statement being solved for

Worked example

The statement pattern

[(p \to q) \wedge \sim q] \to r

is a tautology. What must

r

be equivalent to?

Practice this conceptself-check · 4 quick reps

From the bank · past-year question

Example 6Mathematical LogicMODERATE

The statement pattern

\lbrack(p\rightarrow q) \land -q\rbrack \rightarrow r

is a tautology when r is equivalent to

[Q109 · 19 April Shift I · 2025]

Looking for an r that is true everywhere

r

only has to hold in the rows where the ANTECEDENT is true — it may be false elsewhere without harming the tautology. Hunting for a universally true

r

rules out the correct option, which is usually a plain

\sim p

\sim q

Drill 1 more on finding the statement that makes a pattern a tautology

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Formulas (4)

What Logical Equivalence Means
Equivalence and its test
$A \equiv B \iff (A \leftrightarrow B) \text{ is a tautology} \iff A \text{ and } B \text{ share every row}$
Tautology, Contradiction and Contingency
Classification by last column
$\text{tautology} \Rightarrow \text{all } T \qquad \text{contradiction} \Rightarrow \text{all } F \qquad \text{contingency} \Rightarrow \text{mixed}$
The Dual of a Statement Pattern
Dual versus negation
$\text{dual}(p \wedge \sim q) = p \vee \sim q \qquad \sim(p \wedge \sim q) \equiv\; \sim p \vee q$
Finding the Statement That Makes a Pattern a Tautology
Tautology condition and modus tollens
$(X \to r) \text{ is a tautology} \iff X = T \Rightarrow r = T \qquad (p \to q) \wedge \sim q \equiv\; \sim p \wedge \sim q$

Reference tables (1)

The Algebra of Statements10 rows

Law	With AND	With OR
Commutative	$p \wedge q \equiv q \wedge p$	$p \vee q \equiv q \vee p$
Associative	$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$	$(p \vee q) \vee r \equiv p \vee (q \vee r)$
Distributive	$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ Both directions are legal here, unlike ordinary arithmetic where only one distribution holds.
Identity	$p \wedge T \equiv p$	$p \vee F \equiv p$
Domination	$p \wedge F \equiv F$	$p \vee T \equiv T$
Complement	$p \wedge \sim p \equiv F$	$p \vee \sim p \equiv T$ The engine of most simplifications: spot a letter meeting its own negation and a whole branch collapses to F or T.
Idempotent	$p \wedge p \equiv p$	$p \vee p \equiv p$
Absorption	$p \wedge (p \vee q) \equiv p$	$p \vee (p \wedge q) \equiv p$ The whole bracket vanishes. Worth memorising by shape: a letter outside meeting itself inside swallows the rest.
De Morgan	$\sim(p \wedge q) \equiv \;\sim p \vee \sim q$	$\sim(p \vee q) \equiv \;\sim p \wedge \sim q$
Conditional	$\sim(p \to q) \equiv p \wedge \sim q$	$p \to q \equiv \;\sim p \vee q$ Always apply this first. The other laws cannot see through an arrow.

Ten laws cover every simplification the paper sets. Complement, distributive and absorption account for most of the work.

Watch out for (6)

Checking one row and declaring equivalence
→ What Logical Equivalence Means
Distributing only one way
→ The Algebra of Statements
Simplifying around an arrow instead of clearing it
→ Simplifying a Statement Pattern
Calling a contingency a tautology after checking two rows
→ Tautology, Contradiction and Contingency
Negating the letters when asked for a dual
→ The Dual of a Statement Pattern
Looking for an r that is true everywhere
→ Finding the Statement That Makes a Pattern a Tautology

Drill every past-year question on this subtopic

16 questions from the bank — paginated, with cart and Word-export support.

Drill the 16 questions

Drill every past-year question on this subtopic

Related notes