Can you represent other logical operations using only $\neg$ and $\Leftrightarrow$ (not and equivalence)?

Question

I can check on WolframAlpha for how to represent some logical operations using others, but I don't see anything for $\Leftrightarrow$. Is it because it is impossible?

http://www.wolframalpha.com/input/?i=a+xor+b

Answer 1

HINT: By induction on the complexity of a formula $\varphi$ in two propositional variables $p, q$ built from $\neg$ and $\iff$, we can show that there are an even number (0, 2, or 4) of truth assignments making $\varphi$ true.

Actually, you use induction to completely classify the possible $\varphi$ which can be built in this way; this is a case of needing to assume a stronger claim in an induction argument. But this is the right idea.

This rules out the possibility of representing e.g. "$p\implies q$" (which is satisfied by three out of four truth assignments) in this way.

Answer 2

Here is an informal approach:

(By 'is equivalent to', I mean 'has the same truth table'.)

Suppose you have some formula $\phi(x_1,...,x_n)$ created with the connectives mentioned.

Then either $\phi(\lnot x_1,...., \lnot x_n)$ is equivalent to $\phi(x_1,...,x_n)$ or $\phi(\lnot x_1,...., \lnot x_n)$ is equivalent to $\lnot \phi(x_1,...,x_n)$.

This is not hard to verify by induction.

However $\lnot x_1 \implies \lnot x_2$ is not equivalent to $\lnot (\lnot x_1 \implies \lnot x_2)$ nor is it equivalent to $x_1 \implies x_2$.

This can be seen by taking the truth assignment $x_1 = 0, x_2 =1$.