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.


1 Answer 1


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}$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .