An Example Inductive Proof
The key elements of any inductive proof:
- size
- base case
- inductive case
- applying the inductive hypothesis
If $F$ is a propositional formula that only
contains ands, ors, implications
($\wedge,\vee,\Rightarrow$) and the variables $x_1,\ldots,x_n$,
and $I$ is the interpretation in which each
$x_i = \text{true}$, then $F$ is true under interpretation
$I$.
We will prove this by induction on $n$, the number of
operators in $F$.
If $n=0$, then $F$ is a variable $x_i$, which is true under
interpretation $I$.
If $n>0$, then $F$ is one of $(A)\wedge(B)$, $(A)\vee(B)$ or
$(A)\Rightarrow(B)$.
Assume the inductive hypothesis, i.e. that formulas containing
only $\wedge,\vee\Rightarrow$ with less
than $n$ operators evaluate to true under $I$.
Since $A$ and $B$ both have
fewer than $n$ operators and only include
$\wedge,\vee,\Rightarrow$, both $A$ and $B$ evaluate to
true under $I$. So, under $I$, formula $F$ evaluates to one of
true∧true, true∨true or
true⇒true, all of which are true.
So by the principle of induction, we deduce that for any number of operators, a formula
containing only $\wedge,\vee,\Rightarrow$ evaluates to
true under interpretation $I$.