1
$\begingroup$

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

Any advice is greatly appreciated.

$\endgroup$
1
  • $\begingroup$ Yes (de Morgan's law). $\endgroup$
    – georg
    Jul 31 '16 at 8:47
4
$\begingroup$

De Morgan's laws:

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Jul 31 '16 at 8:50
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ That is very helpful to know, thank you! $\endgroup$ Jul 31 '16 at 8:56
  • $\begingroup$ 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. $\endgroup$
    – user21820
    Jul 31 '16 at 12:07
  • $\begingroup$ @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. $\endgroup$
    – user21820
    Jul 31 '16 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.