## Limits of Propositional Logic

We can use propositional logic to validate the form of an
argument that takes us from premises to a conclusion.

We cannot use propositional logic to establish the truth
of a proposition that isn't given as a premise, or which
can't be inferred by the laws of inference.

In particular, we cannot use propositional logic to reason
about propositions that obey laws (such as arithmetic laws)
beyond the logical inference system.

### Limits of Propositional Logic
in Reasoning about Relations

Consider the following "if" clause:

if (a < b) OR ( (a >= b) AND (c = d) )

We would like to know if we can simplify this "if" clause as follows:

if (a < b) OR (c = d)

More formally, we would like to establish the following
equivalence as a tautology, where we have rewritten
the relation expressions in the "if" clauses as propositional variables:

p1 OR (p2 AND p3) == p1 OR p3

We can establish whether or not this equivalence is a tautology
by showing the truth table for the expression:

p1 p2 p3 e1 e2 e1==e2
0 0 0 0 0 1
0 0 1 0 1 0
0 1 0 0 0 1
0 1 1 1 1 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1

This is NOT a tautology, even though it appears valid to substitute
the simpler boolean expression for the more complex one.

The problem is that, in performing the substitution,
we used facts about integers to draw
inferences about the propositions (such as p1 -> NOT p2)
that we could not deduce using propositional logic only.