0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – user21820 Mar 23 '16 at 5:07
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.