Can you represent other logical operations using only $\neg$ and $\Leftrightarrow$ (not and equivalence)? 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
 A: 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.
A: 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$.
