If I know Double negation law, De Morgan laws and implication negation is it enough for negating any compound propositions or there are more?

I know:

Double negation law:

$ \lnot(\lnot p)\equiv p $

De Morgan laws:

$ \lnot (p \wedge q) \equiv \lnot p\vee \lnot q $

$ \lnot (p \vee q) \equiv \lnot p \wedge \lnot q $

Implication negation:

$\lnot (p \Rightarrow q) \equiv p \wedge \lnot q$

Question: Is it enough for negating any compound propositions or there are more law/rules?

1 Answer

If by "negate" you mean "put in negation normal form" - the question is trivial otherwise, since "$\neg\varphi$" is always the negation of $\varphi$ - then the answer is yes.

For example, to simplify $\neg(a\wedge (b\vee c))$ we would proceed as follows:

• $\neg(a\wedge P)\equiv\neg a\vee\neg P$.

• Taking $P$ to be $b\vee c$ above, we get $\neg P\equiv \neg b\wedge \neg c$.

• Putting these together we get $\neg(a\wedge(b\vee c))\equiv \neg a\vee (\neg b\wedge\neg c)$.

Of course, this example doesn't constitute a proof; to actually prove the result you need to argue via induction on formula complexity.