Arguments and Proofs

Introduction to Proofs

Definition 30: Argument

An argument is a sequence of propositions $𝑃_{1}, 𝑃_{2}, \dots, 𝑃_{𝑛}$ such that the last proposition $𝑃_{𝑛}$ is called the conclusion of the argument, and the preceding propositions $𝑃_{1}, 𝑃_{2}, \dots, 𝑃_{𝑛 - 1}$ are called the premises of the argument.

Notation: Therefore Symbol

The conclusion of an argument can be separated from the premises by the symbol ( $∴$ ):

𝑃_{1}, 𝑃_{2}, \dots, 𝑃_{𝑛 - 1} ∴ 𝑃_{𝑛}

Definition 31: Valid and Sound Arguments

An argument is valid iff, for all truth assignments $𝜎$ , $𝜎 ⊨ 𝑃_{𝑖}$ for all premises $𝑃_{𝑖}$ implies $𝜎 ⊨ 𝑃_{𝑛}$ for the conclusion $𝑃_{𝑛}$ . Otherwise, the argument is invalid.

An argument is sound iff it is valid and all its premises are true. Otherwise, the argument is unsound.

Definition 32: Proof

A proof of a proposition $𝑃$ is a sound argument whose conclusion is $𝑃$ .

Proof Trees

To represent proofs, we can use proof trees, which are tree diagrams that represent the structure of an argument.

Remark

Proof trees are an informal extension of the sequent calculus, which will be covered later.

Notation: Proof Tree for a Valid Argument

If the conclusion $𝑃_{𝑛}$ is derived from the premises $𝑃_{1}, 𝑃_{2}, \dots, 𝑃_{𝑛 - 1}$ , then the proof tree for this argument is:

\frac{𝑃_{1} 𝑃_{2} \dots 𝑃_{𝑛 - 1}}{𝑃_{𝑛}}

We can also label the rule with a name or reasoning:

\frac{𝑃_{1} 𝑃_{2} \dots 𝑃_{𝑛 - 1}}{𝑃_{𝑛}} (Common Sense)

Methods of Proof

Definition 33: Modus Ponens

Under some truth assignment $𝜎$ , if $𝜎 ⊨ 𝑃$ and $𝜎 ⊨ (𝑃 \Rightarrow 𝑄)$ , then $𝜎 ⊨ 𝑄$ :

\frac{𝑃 \Rightarrow 𝑄 𝑃}{𝑄} (Modus Ponens)

This is often called a direct proof of $𝑄$ from $𝑃$ .

Definition 34: Modus Tollens

Under some truth assignment $𝜎$ , if $𝜎 ⊨ \neg 𝑄$ and $𝜎 ⊨ (𝑃 \Rightarrow 𝑄)$ , then $𝜎 ⊨ \neg 𝑃$ :

\frac{𝑃 \Rightarrow 𝑄 \neg 𝑄}{\neg 𝑃} (Modus Tollens)

This is often called a proof by contraposition of $\neg 𝑃$ from $\neg 𝑄$ .

Definition 35: Proof by Contradiction

Under some truth assignment $𝜎$ , if $𝜎 ⊨ (\neg 𝑃 \Rightarrow ⊥)$ , then $𝜎 ⊨ 𝑃$ :

\frac{\neg 𝑃 \Rightarrow ⊥}{𝑃} (Contradiction)

Definition 36: Weak Mathematical Induction

Under some truth assignment $𝜎$ , to prove a predicate $𝑃 (𝑛)$ for all $𝑛 > 𝑛_{0}$ , show that:

Base Case. $𝜎 ⊨ 𝑃 (𝑛_{0})$ .
Inductive Step. For all $𝑘 > 𝑛_{0}$ , if $𝜎 ⊨ 𝑃 (𝑘)$ , then $𝜎 ⊨ 𝑃 (𝑘 + 1)$ .

The rule for weak induction is as follows:

\frac{𝑃 (𝑛_{0}) \forall 𝑘 > 𝑛_{0}, 𝑃 (𝑘) \Rightarrow 𝑃 (𝑘 + 1)}{\forall 𝑛 > 𝑛_{0}, 𝑃 (𝑛)} (Ind.)

Definition 37: Strong Mathematical Induction

Under some truth assignment $𝜎$ , to prove a predicate $𝑃 (𝑛)$ for all $𝑛 > 𝑛_{0}$ , show that:

Base Case. $𝜎 ⊨ 𝑃 (𝑛_{0})$ .
Inductive Step. For all $𝑘 > 𝑛_{0}$ , if $𝜎 ⊨ 𝑃 (𝑗)$ $\forall 𝑗$ such that $𝑛_{0} < 𝑗 \leq 𝑘$ , then $𝜎 ⊨ 𝑃 (𝑘 + 1)$ .

The rule for strong induction is as follows:

\frac{𝑃 (𝑛_{0}) \forall 𝑘 > 𝑛_{0}, (⋀_{𝑗 = 𝑛_{0} + 1}^{𝑘} 𝑃 (𝑗)) \Rightarrow 𝑃 (𝑘 + 1)}{\forall 𝑛 > 𝑛_{0}, 𝑃 (𝑛)} (Str. Ind.)

Rules of Inference

Theorem 7: Rules of Inference for Conjunctions

Let $𝑃$ and $𝑄$ be propositional formulae, and $𝜎$ be a truth assignment. Then:

Introduction ( $\land_{I}$ ). If $𝜎 ⊨ 𝑃$ and $𝜎 ⊨ 𝑄$ , then $𝜎 ⊨ 𝑃 \land 𝑄$ .
Right-Elimination ( $\land_{E_{1}}$ ). If $𝜎 ⊨ 𝑃 \land 𝑄$ , then $𝜎 ⊨ 𝑃$ .
Left-Elimination ( $\land_{E_{2}}$ ). If $𝜎 ⊨ 𝑃 \land 𝑄$ , then $𝜎 ⊨ 𝑄$ .

Theorem 8: Rules of Inference for Disjunctions

Let $𝑃$ and $𝑄$ be propositional formulae, and $𝜎$ be a truth assignment. Then:

Left-Introduction ( $\lor_{I_{1}}$ ). If $𝜎 ⊨ 𝑃$ , then $𝜎 ⊨ 𝑃 \lor 𝑄$ .
Right-Introduction ( $\lor_{I_{2}}$ ). If $𝜎 ⊨ 𝑄$ , then $𝜎 ⊨ 𝑃 \lor 𝑄$ .
Elimination ( $\lor_{E}$ ). If $𝜎 ⊨ 𝑃 \lor 𝑄$ , and if $𝜎 ⊨ 𝑅$ whenever $𝜎 ⊨ 𝑃$ , and if $𝜎 ⊨ 𝑅$ whenever $𝜎 ⊨ 𝑄$ , then $𝜎 ⊨ 𝑅$ .

Theorem 9: Rules of Inference for Implications

Let $𝑃$ and $𝑄$ be propositional formulae, and $𝜎$ be a truth assignment. Then:

Introduction ( $\Rightarrow_{I}$ ). If $𝜎 (𝑄) = 𝖳$ whenever $𝜎 (𝑃) = 𝖳$ , then $𝜎 (𝑃 \Rightarrow 𝑄) = 𝖳$ .
Modus Ponens ( $\Rightarrow_{E_{1}}$ ). If $𝜎 (𝑃 \Rightarrow 𝑄) = 𝖳$ and $𝜎 (𝑃) = 𝖳$ , then $𝜎 (𝑄) = 𝖳$ .
Modus Tollens ( $\Rightarrow_{E_{2}}$ ). If $𝜎 (𝑃 \Rightarrow 𝑄) = 𝖳$ and $𝜎 (𝑄) = 𝖥$ , then $𝜎 (𝑃) = 𝖥$ .

Theorem 10: Rules of Inference for Biconditionals

Let $𝑃$ and $𝑄$ be propositional formulae, and $𝜎$ be a truth assignment. Then:

Introduction ( $\Leftrightarrow_{I}$ ). If $𝜎 (𝑃) = 𝜎 (𝑄)$ , then $𝜎 (𝑃 \Leftrightarrow 𝑄) = 𝖳$ .
Right-Elimination ( $\Leftrightarrow_{E_{1}}$ ). If $𝜎 (𝑃 \Leftrightarrow 𝑄) = 𝖳$ and $𝜎 (𝑃) = 𝖳$ , then $𝜎 (𝑄) = 𝖳$ .
Left-Elimination ( $\Leftrightarrow_{E_{2}}$ ). If $𝜎 (𝑃 \Leftrightarrow 𝑄) = 𝖳$ and $𝜎 (𝑄) = 𝖳$ , then $𝜎 (𝑃) = 𝖳$ .