# Is $\neg(\neg p \lor \neg q) \iff (p \land q)$ a tautology?

This was an example from my textbook and answer is not provided.

Basically I'm asking because if it is, then $\neg(\neg p \lor \neg q)$ is equivalent to $p \land q$, meaning that $\neg \neg p$ is $p$, $\neg \neg q$ is $q$, and $\neg \lor$ is $\land$.

• Yes (de Morgan's law). Jul 31 '16 at 8:47

$\neg(P \lor Q)\iff(\neg P)\land(\neg Q)\tag1$ $\neg(P \land Q)\iff(\neg P)\lor(\neg Q)\tag2$

This question is the first case, with $P=\neg p$ and $Q=\neg Q$.

You can use truth table to prove your question.

$$\begin{array}{c|c|c|c} p&q&\neg(\neg p \lor \neg q)&p\land q\\\hline T&T&T&T\\\hline T&F&F&F\\\hline F&T&F&F\\\hline F&F&F&F \end{array}$$

Therefore $\neg(\neg p \lor \neg q)\iff(p\land q)$.

$\blacksquare$

• This makes much more sense, also I hadn't come across the laws so that might be why they tried to use De Morgan's Law as an example, thanks very much! Jul 31 '16 at 8:50

The tautology is correct, but:

$$\neg(\neg p \lor \neg q) \not\implies \neg\neg p (\neg\lor) \neg\neg q$$

because the distribution law only applies to the operands, and NOT to the operator.

• That is very helpful to know, thank you! Jul 31 '16 at 8:56
• Arguably you're wrong at least from a certain point of view. If you view propositions as elements in a boolean lattice, and $\land,\lor$ as meet and join, then $\neg$ is an isomorphism that maps $\land$ to $\lor$ and vice versa! @SamirChahine: At your current level, you may want to simply look at the duality principle at en.wikipedia.org/wiki/Duality_principle_%28Boolean_algebra%29, where the switch is an instance of something more general called an isomorphism. Jul 31 '16 at 12:07
• @SamirChahine: Basically, an isomorphism is a relabeling that commutes with the operations, meaning that ( relabel then operate ) gives the same result as ( operate then relabel ). You can treat "$\neg$" as a relabeling operation that relabels $p$ to $\neg p$ and vice versa, and relabels $\land$ to $\lor$ and vice versa. Jul 31 '16 at 12:16