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?

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

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

  • $\begingroup$ Thank you ver much but can you explain the reason behind (1)? $\endgroup$ Oct 22 '13 at 19:01
  • $\begingroup$ 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. $\endgroup$
    – amWhy
    Oct 22 '13 at 19:04
  • $\begingroup$ Can I infer that ¬a ∨ ¬b ≡ a → ¬b ? $\endgroup$ Oct 22 '13 at 19:13
  • $\begingroup$ 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$. $\endgroup$
    – amWhy
    Oct 22 '13 at 19:15
  • $\begingroup$ @amWhy: it is nice to have that ack from the OP! +1 $\endgroup$
    – Amzoti
    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?


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.