Is it possible to write all logical statements using only the biconditional operator and negation? How would one prove this using natural deduction?

Question

I'm doing a project that aims to show how a complex logical language can be reduced to a more simple but equivalent language. Specifically I am looking at whether all logical statements, i.e. statements containing any of the following connectives AND, OR, negation, implication, double implication (<-->), can be simplified to have the same evaluation (true or false) as a statement only containing negation and double implication. If this can be done, how would one go forward to prove this using structural induction?

Thanks in advance!

Answer 1

Let $S$ be a finite set of variables with $|S| > 1$. $S$ will be the set of atomic propositions.

Theorem: let $\phi$ be a proposition formed from atomic propositions in $S$ and the $\neg$ and $\iff$ operators. Then $|\{\tau : S \to 2 \mid \tau \models \phi\}|$ is even.

Proof: we proceed by structural induction on $\phi$.

The base case is $\phi \in S$. In this case, a truth assignment must send $\phi$ to $\top$ but can send the other $|S| - 1$ variables to either $\top$ or $\bot$, so there are $2^{|S| - 1}$ truth assignments $\tau$ such that $\tau \models \phi$. Since $|S| > 1$, this is an even number.

The first inductive step is negation. Suppose $|\{\tau \mid \tau \models \psi\}|$ is even. Then $\{\tau \mid \tau \models \neg \psi\} = 2^S \setminus \{\tau \mid \tau \models \psi\}$. Taking cardinalities, we have $|\{\tau \mid \tau \models \neg \psi\}| = 2^{|S|} - |\{\tau \mid \tau \models \psi\}|$. The right side is even.

The second inductive step is $\iff$. We’re considering a proposition of the form $\xi \iff \kappa$. We can show pretty easily here that $|\{\tau \mid \tau \models \xi$ and $\tau \models \kappa\}|$ and $|\{\tau \mid \tau \models \neg \xi$ and $\tau \models \neg \kappa\}|$ have the same parity, which allows us to complete this step. I’ll leave the details as an exercise. $\square$

This allows us to conclude that we can’t rewrite all propositions into equivalent ones using $\iff$ and $\neg$. In particular, there are an odd number of truth assignments making $A \land B$ hold, so we cannot possibly express this proposition using only $\iff$ and $\neg$.

Answer 2

If you've not come across the phrase functional completeness (or "adequacy") before then it may be a useful search term.

What are all the truth tables with two inputs? Can you make them all from your chosen operations ($\leftrightarrow$ and $\neg$)? If so, think about how structural induction could extend that result (what would you do to start constructing the truth tables with three inputs?).