Note: The book I'm using doesn't have any solutions/answers so I will be posting some of the questions I'm unsure about in the hope that someone will check it for me.

Question: Re-write $X\leftrightarrow Y$ using only $\neg$ and $\vee$.

My attempt: We have $$X\leftrightarrow Y$$ $$\equiv (X\rightarrow Y)\wedge (Y\rightarrow X)$$ $$\equiv ((\neg X)\vee Y)\wedge ((\neg Y)\vee X)$$ where the last equivalence follows from the fact that $(A\rightarrow B)\leftrightarrow ((\neg A)\vee B)$.

Now since $(X\wedge Y)\equiv \neg ((\neg X)\vee (\neg Y))$, the last line above becomes $$\neg ((\neg ((\neg X)\vee Y))\vee (\neg ((\neg Y)\vee X)))$$ which is our answer. $\Box$

Thank you very much for your help.


I think your answer looks correct. Alternatively, the two-way implication says that either both are true or both are false: $$\begin{align} X\leftrightarrow Y&\equiv(X\wedge Y)\vee(\neg X\wedge\neg Y)\\ &\equiv\neg(\neg X\vee\neg Y)\vee\neg(X\vee Y) \end{align}$$

| cite | improve this answer | |

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.