# Constructing the $\wedge$ logical connectives using $¬$ and $\leftrightarrow$

I am trying to show that if $p, q$ are distinct propositional variables, then there is no propositional formula $\phi$ such that the only connectives are $\leftrightarrow$ and $¬$ that is tautologically equivalent to $\phi$. (Notice that $\phi$ could have other propositional variables)

I tried to proceed by induction. It's easy to show that given a propositional variable $s$, $s$ is not tautologically equivalent to $p\wedge q$: If $s$ is $p$, let $\sigma$ be a valuation such that $\sigma(p)=1$, $\sigma(q)=0$. Then $\sigma(p\wedge q)=0\neq 1=\sigma(s)$. If $s$ is $q$, let $\sigma$ be a valuation such that $\sigma(q)=1$, $\sigma(p)=0$. Then $\sigma(p\wedge q)=0\neq 1=\sigma(s)$. Finally, if $s$ is not $p$ nor $q$, let $\sigma$ be a valuation such that $\sigma(p)=1$, $\sigma(q)=1$ and $\sigma(s)=0$. It follows that $\sigma(p\wedge q)=1\neq 0=\sigma(s)$.

Now suppose $A$ and $B$ are propositional formulas containing only the connectives $\leftrightarrow$ and $¬$ and suppose that both $A$ and $B$ are not tautologically equivalent to $p\wedge q$. We must show that $A \leftrightarrow B$ and $¬A$ are not tautologically equivalent to $p\wedge q$ and that's where I'm stuck.

Questions: Do you know how to complete the proof above? Is proceeding by induction really the best way to solve this problem or is there a better way?

• Your question is almost not understandable. You say that you want to show that "there is no propositional formula $φ$ with some properties ... that is tautologically equivalent to $φ$". But any formula is equivalent to itself... Noah's answer depends on guessing your question to be asking something else. – user21820 Mar 23 '16 at 5:07

HINT: Count the number of satisfying valuations. By induction, you can show that if $\varphi$ is a formula in two propositional variables which is built out of $\iff$ and $\neg$ only, then $\varphi$ has an even number of satisfying valuations. (By "satisfying valuation" I mean assignment of truth values to the propositional variables which make $\varphi$ true.)
To make this induction go smoothly, note that if we think of e.g. a propositional variable $A$ as a formula in two variables, one of which doesn't occur, then it has two satisfying valuations.