Negation with De Morgan’s law

Question

I'm having a hard time getting my head around transformation proofs. There is one particular example demonstration in the material I'm studying which I can't make sense of

From this

¬ (¬ (¬ p) ∨ ¬ (¬ q))

We get

¬ (¬ (¬ p ∧ ¬ q))

I can see that we've gone from a disjunction to a conjunction, but I don't get why the negation that was outside of q was removed.

De Morgan’s first law (p ∧ q) ≡ ¬ p ∨ ¬ q

Answer 1

$$\neg(\neg(\neg p) \vee \neg(\neg q))=\neg(p\vee q)=\neg p\wedge \neg q=\neg(\neg(\neg p \wedge\neg q)))$$

Answer 2

First note that the first $\neg$ is useless to prove the "equality". You can write your problem as follows: $$\neg \neg p \lor \neg \neg q$$ which you can reduce to $p\lor q$. Second you apply the de Morgan's law (the correct one was given by Mr. Newman) and the result appears.

Answer 3

Let's define some abbreviations:

$$\begin{align} A &= \neg p \\ B &= \neg q \\ C &= (\neg A) \lor (\neg B) \\ D &= \neg(A\land B) \end{align}$$

Then you're asking about rewriting $\neg C$ to $\neg D$ (unfold all the abbreviations if you're unsure that this is actually what you're doing).

But $C$ and $D$ are clearly equivalent by De Morgan's laws, and since $\neg C$ and $\neg D$ is just $C$ and $D$ both placed in the same context, they will be equivalent too.

Answer 4

The steps to get from the first formula to the second one are as follows:

1. $\neg( p \vee q)\quad\quad\quad$ (because $\neg(\neg x) \equiv x$, double negation)
2. $\neg p \land \neg q\quad\quad\quad$ (because $\neg(x \vee y) \equiv \neg x \land \neg y$, De Morgan)
3. $\neg(\neg(\neg p \land \neg q))\quad$ (because $\neg(\neg x) \equiv x$, double negation)