If a formula $φ$ contains at most one occurrence of any sentence letter, then $φ$ is not a tautology. The only connectives in my system are $→$ and $¬$. I think I should attempt this by induction on the complexity of $φ$ (the number of connectives). Then we have two cases to consider: either $φ = ¬ψ$, or $φ = ψ→ξ$, where $ψ$, $ξ$ satisfy the induction hypothesis. I'm stuck here, as I cannot find a property of sentences that contain at most one occurrence of any sentence letter to exploit.
Asked
Active
Viewed 414 times
1
-
A → A contains two occurences of the sentence letter A, so it does not satisfy the hypothesis of my question. – BogIch Feb 01 '16 at 23:15
-
Formatting tips here. – Em. Feb 01 '16 at 23:36
1 Answers
6
By induction on the complexity of formulas $\phi$, we prove the stronger statement:
If $\phi$ contains at most one occurrence of any propositional variable, then $\phi$ is neither a tautology nor a contradiction.
Suppose $\phi$ contains at most one occurrence of any propositional variable.
If $\phi$ is atomic, then it's just a propositional variable, so it's not a tautology and not a contradiction, as there are assignments of values to its variable that give the formula the value False, and others that give it the value True.
If $\phi$ is $\neg \psi$ and the result holds for $\psi$, then clearly it holds for $\phi$ as well.
Now suppose $\phi$ is $\psi\to\theta$. As shown in this related answer, if $\psi \to \theta$ is a tautology, then there is a propositional variable that occurs in both $\psi$ and $\theta$. So $\phi$ isn't a tautology. If $\phi$ were a contradiction, then $\neg\phi \equiv (\psi\land\neg\theta)$ would be a tautology, so $\psi$ would have to be a tautology. But $\psi$ also has at most one occurrence of each variable, so by induction hypothesis $\psi$ is not a tautology after all, thus $\phi$ is not a contradiction.
