# Stuck trying to simply a logical expression

Simplify:

$$\neg[p \to \neg(p \land q)]$$

My Attempt:

1: $$\neg(p \lor \neg(p \land q) \quad \textit{Implication Law}$$

2: $$\neg((p \lor \neg p) \lor q)] \quad \textit{First de Morgan's Law}$$

3: $$\neg(\neg p \lor \neg q) \quad \textit{Second Idempotent Law}$$

I am stuck, and cannot decide on the next step. My mind thinks of the Double Negation law or alternatively one of the de Morgan's laws.

Simplify:

$$\neg[p \to \neg(p \land q)]$$

My Attempt:

1: $$\neg(p \lor \neg(p \land q) \quad \textit{Implication Law}$$

No. That should be $$\neg(\color{red}\neg p \lor \neg(p \land q)$$

2: $$\neg((p \lor \neg p) \lor q)] \quad \textit{First de Morgan's Law}$$

No. Applying DeMorgan on $$\neg(p \lor \neg(p \land q)$$ should get you $$\neg(p \lor (\neg p \lor \color{red} \neg q))$$. You also need to apply an Association to move the parentheses like you did. And you have an extra closing $$]$$

3: $$\neg(\neg p \lor \neg q) \quad \textit{Second Idempotent Law}$$

No. You can't apply Idempotence on your $$\neg((p \lor \neg p) \lor q)$$. You need two identical disjuncts (like $$p \lor p$$ or $$\neg p \lor \neg p$$, but you have $$p \lor \neg p$$). But had you done the first steps correct, you would have been able to do an Idempotence after all:

$$\neg (p \to \neg(p \land q))$$

1: $$\neg(\neg p \lor \neg(p \land q) \quad \textit{Implication Law}$$

2: $$\neg(\neg p \lor (\neg p \lor \neg q)) \quad \textit{de Morgan's Law}$$

3: $$\neg((\neg p \lor \neg p) \lor \neg q) \quad \textit{Association}$$

4: $$\neg(\neg p \lor \neg q) \quad \textit{Idempotence}$$

5: $$\neg \neg p \land \neg \neg q \quad \textit{de Morgan's}$$

6: $$p \land q \quad \textit{Double Negation}$$

$$\phi\rightarrow \psi$$ is logically equivalent to $$\neg \phi \lor \psi$$ (sometimes called the implication law).

1. $$\therefore \neg(p\rightarrow \neg(p\land q)) = \neg(\neg p \lor \neg(p\land q))$$

$$\neg(\neg \phi \lor \neg \psi)$$ is logically equivalent to $$\phi\land\psi$$

1. $$\therefore \neg(\neg p \lor \neg (p\land q)) = p \land (p\land q)$$ (this is one of De Morgan's Laws).

$$\land$$ is associative, IE: $$\phi\land(\psi\land\chi)$$ is equivalent to $$(\phi\land\psi)\land\chi$$,

So we can write $$p\land(p\land q)$$ as $$(p\land p)\land q$$.

This $$p\land p$$ is equivalent to just $$p$$. Therefore the answer is $$p\land q$$. You might have figured out this last step by looking at $$p\land(p\land q)$$ but this is the more detailed reason why.

This can be verified using a truth table.