I was given the following exercise:
For a formula $ϕ$ built up using the connectives ¬,∧,∨, let $ϕ^∗$ be constructed by swapping all ∧ by ∨ and viceversa (e.g. $ϕ=p_1 \lor \neg p_1$, $ϕ^*=p_1 \land \neg p_1$). Proove that if $ϕ$ is a tautology, $ϕ^*$ is a contradiction and viceversa.
I tried prooving it by induction over the number of logical connectives, but I'm stuck in the inductive step, where $ϕ= ϕ_1 \lor ϕ_2 $ is a tautology. So far I did the following:
Take $ϕ^*=ϕ^*_1 \land ϕ^*_2 $. Let's assume it isn't a contradiction. Obviously, both $ϕ^*_i$ aren't contradictions. It can´t be the case that $ϕ^*$ is a tautology because then both $ϕ^*_1,ϕ^*_2$ would also be tautologies and, by induction, $ϕ$ would be a contradiction, violating our hypotheses. Then it must be a contingence. If one $ϕ^*_i$ is a tautology, then the other one $ϕ^*_j$ must be a contingence. Thus, $ϕ_i$ is a contradiction and $ϕ_j$ is a contingence, but then $ϕ$ is a contingence, violating our hipotheses.
So, we are in the case where $ϕ=ϕ_1 \lor ϕ_2$ is a tautology $ϕ^*=ϕ^*_1 \land ϕ^*_2$ is a contingence, and both $ϕ^*_k$ are contingences, so by induction both $ϕ_k$ are contingences too. I'm stuck here trying to prove that this can't be the case.
Best Answer
You need to prove something more general. You are trying to prove something too narrow, so you cannot effectively use your inductive hypothesis. You need to broaden what you are trying to prove so that the inductive hypothesis becomes useful.
The more general theorem is as follows:
Consider some expression $T$ made from atomic propositions, $\land$, $\lor$, $\top$, $\bot$, and $\neg$. We construct two formulas. The first formula is $T’$, which is constructed by replacing every atomic proposition $P$ with $\neg P$. It is easy to show that $T’$ is a tautology iff $T$ is, and the same for contradiction. The second is $T^*$, which is constructed by replacing all $\land$ with $\lor$ and vice versa, and by replacing $\top$ with $\bot$ and vice versa.
I claim that $\neg T’$ is logically equivalent to $T^*$.
To prove this, it suffices to proceed by structural induction on $T$. Using the recursive definitions of $T’$ and $T^*$, this should prove straightforward.
From here, we note that $T$ is a tautology iff $T’$ is a tautology iff $\neg T’$ is a contradiction iff $T^*$ is a contradiction. The same is true when we swap “contradiction” and “tautology”.