0

suppose $\theta$ is a function using only the binary connectives "and" and "or" and a single propositional variable $p$. Show by induction on length of $\theta$ that the formula $p \implies \theta$ is a tautology

I know for basic step that $n=0$ and I need to show $p \implies p$ is a tautology induction I have to assume $p$ implies $\psi$ is a tautology where $\psi$ is less than/equal to $n$ . I am not sure what else to do or how to do it. I also know that $(p \implies \psi) \land (p \implies \psi)$ is a tautology.

Mauro ALLEGRANZA
  • 94,169
ABUG
  • 1

1 Answers1

0

As you already mentioned, you need general well-founded induction to prove this. So we consider a formula $p \to \theta$, and we assume that the property holds for all formulas $p \to \theta'$, where $\theta'$ has fewer symbols than $\theta$.

Since $\theta$ consists only of $\land$, $\lor$, and $p$, we have to consider three cases:

Case 1: $\theta = p$. Then the formula is $p \to p$, and that is obviously a tautology.

Case 2: $\theta = \theta' \lor \theta''$, and both $\theta'$ and $\theta''$ consist only of $\land$, $\lor$, and $p$. Obviously, $\theta'$ and $\theta''$ have fewer symbols than $\theta$, so we may apply the induction hypothesis. By induction, $p \to \theta'$ and $p \to \theta''$ are tautologies. That means in particular that every truth assignment $v$ that maps $p$ to true must also map $\theta'$ and $\theta''$ to true. Now consider an arbitrary truth assignment $v$. If $v$ maps $p$ to false, then it maps $p \to \theta$ to true. If $v$ maps $p$ to true, then it maps by induction $\theta'$ and $\theta''$ to true, therefore it maps $\theta' \lor \theta''$ to true, and therefore it maps $p \to (\theta' \lor \theta'')$ to true. Combining both subcases, we see that every truth assignment $v$ maps $p \to \theta$ to true, as required.

Case 3: $\theta = \theta' \land \theta''$, and both $\theta'$ and $\theta''$ consist only of $\land$, $\lor$, and $p$. This case is handled analogously to case 2.

Uwe
  • 298