Closed system using only implication connectives

Question

Using truth tables for the six formulas p, q, p → q, q → p, p → p, and (p →q) → q, show that every formula using only p and q as propositional letters and containing only the implication connective must be logically equivalent to one of the six formulas.

I found this problem in Introduction to Logic by Paul Herrick. Currently, I'm thinking that I need to show that every single formula using only the implication connective can only have at most one false in the final column of the truth table. This would allow me to show that what I have in these six formulas is a closed system. But I'm not sure how to do this rigorously.

Any help would be great! Thanks in advance!

Answer 1

You should use a proof by induction.

The set $S$ of all "formulaes using only p and q as propositional letters and containing only the implication connective" is the smallest set of formulaes such that :

(1) $p, \, q \in S$

(2) if $\phi, \psi \in S$, then $\phi \to \psi \in S$

Let's call $T$ the set containing your six formulaes : $T := \{ p,\, q,\, p \to q,\, q \to p,\, p\to p,\, (p \to q) \to q \}$

proof of the statement : Obviously, $p$ and $q$ are equivalent to a formula in $T$.

Suppose that both formulaes $\phi$ and $\psi$ are equivalent to a formula in $T$, say $\phi \equiv t \in T$ and $\psi \equiv u \in T$. Notice that $\phi \to \psi \equiv t \to u$, hence it is enough to prove that $t \to u$ is equivalent to a formula in $T$. There are "only" $6\times 6 = 36$ possibilities for $(t,u)$, the rest is up tu you! ;)

Answer 2

Ignoring their direction at the front, I think the easiest and clearest way would be to make a $5\times5$ "multiplication table" with the entries $p, q, p\to q, q\to p, \top$ and show that $A\to B$ was closed under those five truth tables on two variables. (The final two members of your list were both $\top$, one in a single variable and the other in two variables.)

If you felt constrained by the truth table suggestion, I like your idea about having at most one false assignment. But add in that that false assignment cannot have both assignments of $p$ and $q$ the same. (Those would give you NAND and NOR, neither of which are in your set.)

Then I think an induction proof would work out for you. Basically consider a statement of the form $A\to B$ where you assume that $A$ and $B$ are both logically equivalent to one of those forms and prove that $A\to B$ is true when $p$ and $q$ have the same assignment and that the implication has at most one false assignment.

Answer 3

Let P $\implies $ Q be a proposition and

Let P be always true distinct two cases:

Case Q = True When we have $P \implies Q$ this will be always a true implication (tautology). Since P and Q are true, the implication is always true, thus using this result as the left side of an implicatie will always yield True $\implies Q$ and since Q is true. Using our result to imply a next Q that is true.

Case Q = False

When we have $P \implies Q\equiv$ True $\implies$ false. Therefore we have a false implication. We use it to imply another Q. We get: False $\implies$ Q. Note that te left side of the implication is false, thus we can conclude that whatever implication we make it wil always evalute true. Continuing to use the result, will yield in the next result the negation of the last result opposite of.

So we already seen a case where the claim that any P and Q can be used does not hold Using P = True and Q is false. Using such combination of P and Q is not equivalent to P = True and Q is True, because Case Q = false is not a tautology, while Q = true is a tautology.

Edit:

We can also say we take P = true and Q = $\neg(P)$ This would yield the same result in truth table values, but also proves that Q can't be the negation truth value of P when P = true.