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.