A circular argument
Consider the following argument:
I, Professor Brown, always tell the truth. That must be true because
It is a USNA rule that faculty members must always tell the truth
and I follow all USNA rules. You know I follow all the rules because
I stated that I follow all USNA rules, and if I state something you
know it is true because I, Professor Brown, always tell the
truth.
Hopefully you recognize that there's something wrong with this
argument. This is what's called a circular
argument - an argument that assumes the truth of the very
thing it is supposed to prove.
Circular arguments are not
logically valid, because following them leads you in an
infinite loop ... it's
turtles
all the way down.
A question
One of our main results about propositional logic was that every
boolean function has a defining propositional formula ... in
fact, has a defining propositional formula that only uses ands,
ors and nots. It's interesting to ask whether there are other
small sets of propositional operators that suffice to define
every boolean function. For example: Can all boolean functions
be defined by formulas that use only ands, ors and implications?
Do we think this is true?
Consider the following statement:
Proposition: 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$.
If this proposition is true, it's interesting because it would
imply that there
are boolean functions that can't be defined by formulas that use
only ands, ors and implications (in contrast to ands/ors/nots),
specifically, any boolean function that has "false" in the
output column of the row with all inputs "true".
So let's consider whether we can prove this proposition.
A new kind of proof
Do you think above proposition is true? Explain why you think it's true?
What would it take to *prove* this to you? I.e. convince you
to the point at which you'd bet your life that it's true?
How about this for a proof:
Proof attempt I:
By our givens,
$F$ is one of $(A)\wedge(B)$, $(A)\vee(B)$ or
$(A)\Rightarrow(B)$.
Also by our givens, $A$ and $B$ can only contain
ands, ors, implications and variables, so
therefore they
are both true under interpretation $I$.
So under interpretation $I$ formula $F$ evaluates as one of
true∧true, true∨true or
true⇒true, all of which are true. QED.
Is this convincing? Isn't this circular?
We are trying to prove that a formula with only
$\wedge/\vee/\Rightarrow$ eval's to true when all the variables
are all true, and in that proof we just assume that $A$ and $B$
both evaluate to true when the variables are all true because
they only contain $\wedge/\vee\Rightarrow$.
There we are
assuming the truth of the very thing we are supposed to be proving!
So how can we fix this argument (which is somehow compelling
despite its flaws)
so that it's no longer circular?
Proof attempt II:
Let $F$ be an $n$-operator formula.
By our givens $F$ is one of $(A)\wedge(B)$, $(A)\vee(B)$ or
$(A)\Rightarrow(B)$.
Also by our givens, $A$ and $B$ can only contain
ands, ors, implications and variables,
and both $A$ and $B$
contain fewer
than $n$ operators, so
therefore they
are both true under interpretation $I$.
So under interpretation $I$ formula $F$ evaluates as one of
true∧true, true∨true or
true⇒true, all of which are true. QED.
This breaks the circularity, because we are assuming the
result holds for A and B with fewer operators!
In other words, we are saying $n$-operator formulas evaluate to
true under $I$ because formulas with fewer than $n$ operators
evaluate to true under $I$.
If we
tease this apart level-by-level, we eventually come to the case
of zero operators, which we haven't addressed!
However, it's easy. When $n = 0$, $F$ is a variable, and all
variables evaluate to true under interpretation $I$.
So now instead of a
circular argument, we have an
argument that
spirals ... spirals downward until it
eventually reaches zero.
So when we put all these elements together, do we feel like we
have a convincing argument that works for any formula
$F$ whose only operators are ands, ors and nots no matter how
many operators are in the formula?
I think that we should accept this as convincing proof
because what it's really doing is showing us how, for a
formula $F$ of size $n$, we could build up a proof for $F$
from proofs for formulas of smaller size. And since we have a
concrete proof for $n=0$, the smallest size, there's a
foundation for all these proofs to build on.
Note: Our third and final proof attempt is
our actual (complete and correct!) proof, which you see under
the theorem statement below. It puts together all the pieces
we discussed so far.
|
$n=2$: $x_1 \wedge x_2 \Rightarrow x_3$
|
$n = 1$: $x_1 \wedge x_2$
|
$n= 0$: $x_i$
|
|
$F$ is $(A) \Rightarrow (B)$, both $A$ and $B$ are true under
interpretation $I$ (see $n=1$ and $n=0$), so $F$ is
$\text{true} \Rightarrow \text{true}$ which evaluates to true.
|
$F$ is $(A) \wedge (B)$, both $A$ and $B$ are true under
interpretation $I$ (see $n=0$), so $F$ is
$\text{true} \wedge \text{true}$ which evaluates to true.
|
$F$ is a variable, and $I$ maps all variables to true.
|
Proof by (strong) induction
We will now make a concious decision to accept the kind of
argument we developed in the previous section. Here are the
essential features of that kind of argument.
-
There is some collection of objects, and we are trying to
prove that some property $P$ is satisfied by all objects in the
collection.
In our example, the collection of objects is "all
propositional formulas that contain only ands, ors and
implications", and the property is "evaluates to true under
interpretation $I$", recalling that $I$ is the
interpretation in which all variables are assigned the value
"true".
-
There is a non-negative integer "size" for each object in
the collection.
In our example, the size is "the number of propositional
operators in the formula".
-
The argument then goes like this:
-
We prove that property $P$ holds for all
objects of size 0.
[Note: this is called the "base case".]
In our example above, the "base case" was $n=0$,
i.e. formulas with no operators, which means the formula is
a variable.
-
We prove that, for any size $n > 0$:
($P$ holds for all objects of size less than
$n$) $\Rightarrow$ ($P$ holds for all objects of size $n$).
[Note: this is called the "inductive case", and
the left-hand side of the implicationis called the inductive
hypothesis.]
In our example the inductive case is when $F$ contains a
non-zero number of operators. The inductive hypthothesis is
that any formula with less than $n$ operators evaluates to
true under interpretation $I$. We assume the inductive
hypothesis, and prove that any formula of size $n$ evaluates to
true under $I$. As we saw in propositional and first-order
logic, if we prove $Y$ using $X$ as an assumption, we can
"close the assumption" and deduce $X \Rightarrow Y$. So
in this case, closing the assumption gives us
"any formula with less than $n$ operators evaluates to
true under interpretation $I$" $\Rightarrow$
"any formula of size $n$ evaluates to
true under $I$".
-
We deduce that property $P$ holds for objects of all sizes.
We call such
proofs
inductive proofs or
proof by induction.
It is important to understand that we have a to make the
philosophical decision to accept this new kind of deduction rule
that says that if we know (1) the base case holds, and we know
(2) the inductive case holds, then we deduce (3) that the
property holds for objets of all sizes.
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)$.*
Note: we would normally never write this in our
proofs, but just to show you the connection to the
description of induction from above, this is what we just
proved in Point 2:
$\forall n > 0 \left[
\left(
\begin{array}{c}
\text{all formulas containing} \\
\text{only $\wedge,\vee\Rightarrow$ with less}\\
\text{than $n$ operators}\\
\text{evaluate to true under $I$}
\end{array}
\right)
\Rightarrow
\left(
\begin{array}{c}
\text{all $n$-operator formulas}\\
\text{containing only $\wedge,\vee\Rightarrow$}\\
\text{evaluate to true under $I$}
\end{array}
\right)
\right]
$
Assume the inductive hypothesis, i.e. that all formulas containing
only $\wedge,\vee\Rightarrow$ with less
than $n$ operators evaluate to true under $I$.
Then $A$ and $B$, which both have
fewer than $n$ operators and only include
$\wedge,\vee,\Rightarrow$, both 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.
-
By induction, deduce that for any number of operators, a formula
containing only $\wedge,\vee,\Rightarrow$ evaluates to
true under interpretation $I$.
* To clarify what we mean by
"$F$ is one of $(A)\wedge(B)$, $(A)\vee(B)$ or
$(A)\Rightarrow(B)$": when $n > 0$, the formula
$F$ has one or more operators, so
its expression tree has top node labeled with one of
$\wedge$/$\vee$/$\Rightarrow$. The left subtree under that top
node is the formula we call "A", and the right
subtree under that top node is the formula we call "B".