# Proposition Negation Help: $\forall_x[p(x) \to \neg q(x)]$

Negate and simplify the the quantified statement: $$\forall_x[p(x) \to \neg q(x)]$$

$\neg\forall_x[p(x) \to \neg q(x)] \tag 1$

$\exists_x\neg [p(x) \to \neg q(x)] \tag 2$

$\exists _x[\neg p(x)\leftrightarrow \neg(¬q(x))] \tag 3$

$\exists _x[\neg p(x) \leftrightarrow q(x)] \tag 4$

My answer is not correct. I believe I have made a mistake (I am unsure how to deal with the implies symbol), and, hence, clarification would be much obliged.

• Why the down vote? – Git Gud Feb 18 '18 at 21:35
• Can you make a truth table for $\neg (A\to B)$? – Git Gud Feb 18 '18 at 21:38
• @Git Gud, I believe this is the truth table. How do I apply that? \begin{align} &0 \ \\ &0 & \\ &1 \\ &0 & \end{align} – smkar Feb 18 '18 at 21:45
• That's not a table, that's a column, but let us assume you're thinking correctly. Can you now build the truth table for $\neg A\leftrightarrow \neg B$? – Git Gud Feb 18 '18 at 21:49
• $$\begin{array}{cc|cc} A & B & ¬A & ¬B &¬A↔¬B \\ \hline 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 1\\ \end{array}$$ – smkar Feb 18 '18 at 21:58

Your transition from (2) to (3) is incorrect. Using $\lnot p\leftrightarrow q \equiv (\lnot p \to q) \land (q \to \lnot p)$:

(2) $\quad \not\equiv \quad$ (3/4)

**Instead, we can to use the definition of implication: $a \to b \equiv \lnot a \lor b$:

$\quad \equiv \quad$

$$\neg\forall_x[p(x) \to \neg q(x)] \tag 1$$

$$\exists_x\neg [p(x) \to \neg q(x)] \tag 2$$

$$\exists_x\neg[\lnot p(x) \lor \lnot q(x)]\tag {(3) Definition: implication}$$

$$\exists_x [\lnot \lnot p(x) \land \lnot\lnot q(x)]\tag{(4) DeMorgan's Rule}$$

$$\exists_x [p(x)\land q(x)]\tag {(5) Double Negation}$$

$\quad \equiv\quad$ $\quad \equiv\quad$