# Expressing the negation of $[\neg(p\land\neg q)]\land\neg r$ without $\neg,\land,\lor$

Negate $[\neg(p\land\neg q)]\land\neg r$ and replace the resulting formula by an equivalent which does not involve $\neg, \land$ or $\lor$.

Can someone tell me how to get through this question? Help!

I start with $$\neg[[\neg(p\land\neg q)]\land\neg r] = (p\land\neg q)\lor(r).$$ Is that right so far?

• If your result can use neither of $\neg$, $\land$, or $\lor$, then what can you use? Oct 22 '13 at 18:35
• Check my question again. And you should use the quantifiers (universal and existential) signs as well as the implication sigh instead of those mentioned. Oct 22 '13 at 18:38

## 2 Answers

By DeMorgan's

$$\lnot\Big(\lnot(p \land \lnot q) \land \lnot r\Big) \equiv (p \land \lnot q) \lor r$$

Now use the equivalency of $\lnot a \lor b \equiv a \rightarrow b\tag{1}$ and so $a \lor b \equiv \lnot a \rightarrow b\tag{2}$

\begin{align} (p \land \lnot q) \lor r & \equiv \lnot (p \land \lnot q) \rightarrow r \tag{2}\\ \\ & \equiv (\lnot p \lor q )\rightarrow r \tag{DeMorgan}\\ \\ & \equiv (p\rightarrow q)\rightarrow r\tag{1}\end{align}

• Thank you ver much but can you explain the reason behind (1)? Oct 22 '13 at 19:01
• It holds by definition: how we define implication. Note that each side of the equivalence in $(1)$ is false if and only if $a$ is true and $b$ is false, and is true otherwise. While you're at it, compare the truth-tables for each side of the equivalence. Oct 22 '13 at 19:04
• Can I infer that ¬a ∨ ¬b ≡ a → ¬b ? Oct 22 '13 at 19:13
• Yes indeed you can. You can also infer $a \lor \lnot b \equiv \lnot b \lor a \equiv b\rightarrow a \equiv \lnot a \rightarrow \lnot b$. Oct 22 '13 at 19:15
• @amWhy: it is nice to have that ack from the OP! +1 Oct 23 '13 at 1:04

Quantifiers are useless when what you're starting out with is a propositional formula, so your only hope is to express the result as something that consists of implications only.

And the only sensible way to make something into an implication is to match the pattern $A\to B \equiv \neg A\lor B$.

Simplifying to $(p\land\neg q)\lor r$ is good as far as it goes, but in order to become an implications, one of the operands to the $\lor$ will have to be the negation of something. Which one can you negate without reaching a dead end?