There's a printable worksheet for this chapter. Click on logic15work.rtf. De Morgan's Laws
Here are some more theorems.
Theorems 5 & 6 (De Morgan's Laws)
3. ~(P ^ Q) (~P v ~Q)
4. ~(P v Q) (~P ^ ~Q)
If they're not obviously true to you, consider the following little dialog.
Hatter: "Alice is mad and the dormouse is mad." White Rabbit: "That's not true." Hatter: "What's not true?" White Rabbit: "It's not true that Alice is mad and the dormouse is mad." Hatter: "Now, is that the same as saying that Alice is not mad and the dormouse is not mad?" White Rabbit: "No, it's not the same as that." Hatter: "Is it the same as saying that Alice is mad or the dormouse is mad?" White Rabbit: "Good heavens no, it's not the same as that at all!" Hatter: "Well, is it the same as saying that it's not true that Alice is mad or the dormouse is mad?" White Rabbit: "By my ears and whiskers, it's not that either!" Hatter: "So it must be the same as saying that Alice is not mad or the dormouse is not mad." White Rabbit: "Yes, it is certainly the same as that. Good work, my millinerious friend!" Hatter: "Milliners make women's hats. I'm a hatter." White Rabbit: "Yes, but millinerious sounds better." Hatter: "Hmph! So how do you know that saying 'It's not true that Alice is mad and the dormouse is mad' is the same as saying 'Alice is not mad or the dormouse is not mad'?" White Rabbit: "Oh, it's a law that Gussie de Morgan came up with. Come, let's repeat our conversation with logical symbols." Hatter: "Do we have to?" White Rabbit: "Yes." Hatter: "Ma ^ Md (Alice is mad and the dormouse is mad.)" White Rabbit: "~(Ma ^ Md) (It's not true that Alice is mad and the dormouse is mad.)" Hatter: "Is that the same as ~Ma ^ ~Md (Alice is not mad and the dormouse is not mad?)" White Rabbit: "No." Hatter: "Is it the same as Ma v Md (Alice is mad or the dormouse is mad.)" White Rabbit: "No." Hatter: "Well, is it the same as ~(Ma v Md) (it's not true that Alice is mad or the dormouse is mad)?" White Rabbit: "No." Hatter: "So it must be the same as ~Ma v ~Md (Alice is not mad or the dormouse is not mad)." White Rabbit: "Yes, ~(Ma ^ Md) is certainly the same as ~Ma v ~Md" Hatter: "Well, that was fun. But how do you know Gussie is right about this?" White Rabbit: "Well, look at this truth table."
Which sentences have the same truth functions? Which truth functions are unique?
Notice that Ma ^ Md and Ma v Md have truth functions that are not repeated, so neither of them is logically equivalent to any of the other sentences. But look, ~(Ma ^ Md) has the same truth function as ~Ma v ~Md, and ~(Ma v Md) has the same truth function as ~Ma ^ ~Md, which means that ~(Ma ^ Md) is logically equivalent to ~Ma v ~Md, and ~(Ma v Md) is logically equivalent to ~Ma ^ ~Md. Which is what De Morgan's laws say.
Another way to get used to De Morgan's laws is to explore the logical properties of the three operators involved ("^", "V" and "~"). Take the following set of arguments and determine which ones are valid and which are invalid, using truth tables where necessary. (There's a printable worksheet. Click on logic15work.rtf)
When you have thoroughly explored the logic of all these arguments, look at the following list of pairs of arguments. Notice that in each pair, the conclusion of one argument is the premise of the other, and vice versa. Now, try to find pairs where both arguments are valid. (You can do this by referring to your previous work on the above arguments to circle valid args and cross out invalid arguments.
If you've correctly identified all the valid and invalid arguments, your pattern of circles and crosses should make deMorgan's laws abundantly clear.
Notice that De Morgan's Laws can't get you from ~(R ^ S) to ~R ^ ~S. Those two sentences are not logically equivalent to each other.
Neither are ~(R v S) and ~R v ~S or ~(R ^ S) and ~(R v S).
The only two logical equivalences we have are (~R v ~S) ~(R ^ S) and ~(R v S) (~R ^ ~S)
Notice the following facts about applications of DML to placeholders like "S" and "R"..
1. If we start with one tilde ("~"), we end up with two.
2. If we start with two tildes, we end up with one.
3. If we start with a carat ("^"), we end up with a wedge ("v").
4. If we start with a wedge, we end up with a carat.
5. If we start without parentheses, we end up with them.
6. If we start with parentheses, we end up without them.
Finally, and to practice for the inevitable quiz, go through the following arguments again, this time ignoring the issue of validity, pick out all and only the arguments that represent instances of de Morgan's laws. (Remember, don't just pick out valid arguments. Pick out only those arguments whose validity follows directly from de Moragan's laws.)
Now, the following is not assigned, so you can ignore it. But I think this stuff is wicked cool.
(~P v ~Q)
