PROOF 25

Prove.

Only the contrapositive is equivalent to the original statement

In propositional logic.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

For a statement p → q, the statement q → p is its converse, ¬p → ¬q its inverse, and ¬q → ¬p its contrapositive.

Proof.

These three names refer only to form; they say nothing about truth or falsity.convention

∎

Definition D2

A rectangle whose four sides all have equal length is called a square.

Proof.

Every square is a rectangle, and a rectangle whose width and height differ is not a square.convention

∎

Lemma L1

¬(p → q) is equivalent to p ∧ ¬q.

Proof.

(1)¬(p → q) ⟺ ¬(¬p ∨ q)A1, E

(2)¬(¬p ∨ q) ⟺ ¬¬p ∧ ¬qA3

(3)¬¬p ⟺ pA2

(4)¬(p → q) ⟺ p ∧ ¬q(1), (2), (3), E

∎

Theorem T1

p → q and its contrapositive ¬q → ¬p are equivalent.

Proof.

(1)p → q ⟺ ¬p ∨ qA1

(2)¬q → ¬p ⟺ ¬¬q ∨ ¬pA1, D1

(3)¬¬q ⟺ qA2

(4)¬q → ¬p ⟺ q ∨ ¬p(2), (3), E

(5)q ∨ ¬p ⟺ ¬p ∨ qA4

(6)¬q → ¬p ⟺ ¬p ∨ q(4), (5), E

(7)p → q ⟺ ¬q → ¬p(1), (6), E

∎

Theorem T2

The converse and the inverse are not equivalent to the original statement.

Proof.

(1)Let R be a rectangle of width 2 and height 1.assumption

(2)Let p be “R is a square” and q be “R is a rectangle.”convention

(3)The four sides of R are not all equal, so p is false and q is true.(1), (2), D2

(4)p → q ⟺ ¬p ∨ q ⟺ true ∨ true ⟺ true(3), A1, A6, A5

(5)q → p ⟺ ¬q ∨ p ⟺ false ∨ false ⟺ false(3), A1, A6, A5, D1

(6)¬p → ¬q ⟺ ¬¬p ∨ ¬q ⟺ false ∨ false ⟺ false(3), A1, A6, A5, D1

(7)That the converse is false means that q ∧ ¬p is true.(5), L1

(8)Indeed R is a rectangle and not a square. This is a counterexample to the converse.(3), (7)

(9)The original statement is true, while the converse and the inverse are false.(4), (5), (6)

(10)Therefore the converse and the inverse are not equivalent to the original statement.(9)

∎

Remark

Can A2 be removed from this proof?

Double negation elimination sits in an inconspicuous place. Check which lines lose their justification when it is removed.