Express conjuction, disjunction, etc -> only with negation AND implication

Question

As the title says, I need some help about how to express all of the logical operations, only with negation and implication.

So, how do I "convert" conjuction, disjunction, equivalence into negation and implication?

Answer 1

Hint:

Convert statement with $\{\land,\lor,\leftrightarrow\}$ to statement with only $\{\neg,\to\}$, first we should start from Conjuction and Disjunction, after this we can find out how to write Equivalence easily, since $p\leftrightarrow q\equiv (p\land q)\lor (\neg p\land \neg q)$. For Conjuction we notice that $\neg(p\to q)$ is $\neg(\neg p\lor q)$, see what will happen if we apply De Morgan's law on this ? For Disjunction, we know that $$p\lor q\equiv (p\lor q)\land(q\lor\neg q)\equiv(p\land \neg q)\lor q\equiv\neg(\neg p\lor q)\lor q$$See what will happen if we apply conditional equivalence twice.

Answer:

\begin{align}p\land q\equiv&\neg(p\to\neg q)\tag*{Conjuction}\\p\lor q\equiv&(p\to q)\to q\tag*{Disjunction}\\p\leftrightarrow q\equiv&(\neg(p\to\neg q)\to\neg(\neg p\to q))\to\neg(\neg p\to q)\tag*{Equivalence}\\\end{align}

Answer 2

We have \begin{align} p \implies q &\equiv \neg p \lor q \\ &\equiv \neg(p \land \neg q). \\ \end{align} We also have $$p \iff q \equiv (p \implies q) \land (q \implies p).$$ You can prove all three equivalences with a truth table. The second one follows from DeMorgan's laws. From manipulating these you can derive everything you need.