0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$\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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .