20
$\begingroup$

De Morgan's Law is often introduced in an introductory mathematics for computer science course, and I often see it as a way to turn statements from AND to OR by negating terms.

Is there a more intuitive explanation for why this works rather than just remembering truth tables? To me this is like using black magic, what's a better way to explain this so that it makes sense to a less mathematically inclined individual?

$\endgroup$
  • $\begingroup$ More questions like this! :D $\endgroup$ – OghmaOsiris Mar 14 '12 at 8:49
  • $\begingroup$ it's a good question.. but i don't see an intuitive way whatsoever. intuitive can be speculative as well as to who find response x intuitive or not :) $\endgroup$ – marc-andre benoit Mar 15 '12 at 5:35
12
$\begingroup$

If you like to visualize it, use the venn diagrams. See this, for instance.

I find it more simple just to memorize the basic 2 laws: everytime you "break" a negation line, you replace the AND to OR (or vice versa). Adding two negation lines changes nothing (but gives you more "lines" to break). It just works.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ I often view the negation like a wrecking ball. As it goes through the operators, it flips them around :) $\endgroup$ – Suresh Mar 14 '12 at 7:27
14
$\begingroup$

Insert real-world predicates and read aloud, for instance:

It can not be both winter and summer (at any point in time).

and

(At any point in time) It is not winter or it is not summer.

Clearly, the two statements are equivalent.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For this to work, you have to already understand the truth behind De Morgan's law at an intuitive level, even if you don't understand its statement. $\endgroup$ – Joe Mar 14 '12 at 9:26
  • 1
    $\begingroup$ I don't think so; you merely need an intuition for logic in a pragmatical sense to see that two statements like my examples are equivalent. YMMV, obviously. $\endgroup$ – Raphael Mar 14 '12 at 9:28
  • $\begingroup$ One could interpret the first statement as it cannot be winter and summer at the same time, which is basically two mutually exclusive event occurring at the same time, which cannot occur. (I'm pretty sure that's not a correct interpretation) $\endgroup$ – Ken Li Mar 14 '12 at 16:58
2
$\begingroup$

The statement $\left(\bigcup_i A_i\right)^c \subseteq \bigcap_i A_i^c$ is equivalent to $$x \in \left(\bigcup_i A_i\right)^c \Longrightarrow x \in \bigcap_i A_i^c$$ and can be read as follows:

If $x$ is not in some $A_i$, then $x$ is not in any $A_i$.

I think this latter statement is obvious. You can similarily read the converse inclusion.

| cite | improve this answer | |
$\endgroup$

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.