# Proving Demorgan's Rule

1. Mar 27, 2009

### InterLogic

1. The problem statement, all variables and given/known data

~(X&Y) } ~X v ~Y

I need to be able prove this rule, also known as Demorgan's rule. Preferably by using any of the following rules: MP, MT, CP, DN, &E, &I, DS <>I, <>E, vI. Although basically any rules that don't go way over my head and aren't way too advanced for me I could use as well. As long as I am able to understand it. I might be able to get away using RA (reductio ad absurdum) but I am not sure and I don't think I am supposed to be using it in this proof, so I want to stay away from using that.

2. Relevant equations

All the relevant info about the problem is given above. It's a proof of Demorgan's rule (or at least one of them I guess).

3. The attempt at a solution

~(X&Y) } ~X v ~Y
1 1. ~(X&Y) A

I am not really sure where to start. I need to know how to do this in order to take an upcoming exam and I am totally lost right now. If someone could either provide an answer or help me out on this I would greatly appreciate it. Thanks!

Last edited: Mar 27, 2009
2. Mar 27, 2009

### Wretchosoft

You want to prove that these two sets are equal, right? Two sets are equal if they are subsets of each other, so if you can show that every element in the left-hand set is in the right-hand set, and vice-versa, you will be done.

I have no idea what that string of abbreviations is, by the way.

3. Mar 27, 2009

### Staff: Mentor

I'm guessing you meant "Preferably by any of the following: ..."
Would the first two acronyms be modus ponens and modus tollens? And contrapositive for the third?
We're pretty sharp on mathematics on this forum, but not all of us are familiar with the arcana of logic. That's not to say that we don't have firm grasps on logic.

4. Mar 27, 2009

### xaos

if x in not in A, where else could x be?
if x in not in B, where else could x not be?

5. Mar 27, 2009

### InterLogic

Yeah, preferably using any of these rules. Not to say you couldn't use other rules if it just isn't doable.

MP, MT, CP, DN, &E, &I, DS <>I, <>E, vI.

Here are the rules spelled out in English, corresponding to the symbols:

Modus Ponens, Modus Tollens, Conditional Proof, Double Negation, &Elimination, &Introduction, Disjunctive Syllogism, Biconditional Introduction, Biconditional Elimination, Or

I don't understand what you are trying to do here. What do you mean "not in A" and "not in B"? There are no variables named "A" or "B" in this problem...

Last edited: Mar 27, 2009
6. Mar 27, 2009

### Staff: Mentor

Can you do it with a truth table? The statements X and Y can individually be true or false, so you'll have four rows in your truth table.

Code (Text):

X | Y | ~(X & Y)  | ~X v ~ Y
------------------------------
T |  T |      ?    |      ?
T | F  |      ?    |      ?
F |  T |      ?    |      ?
F | F  |      ?    |      ?
------------------------------

If the 3rd and 4th columns are identical, the two expressions at the tops of these columns are equivalent.

7. Mar 27, 2009

### InterLogic

Thanks!

Last edited: Mar 27, 2009
8. Mar 28, 2009

### xaos

A and B are arbitrary. my point was that if you look at basic point-set properties, you can start to see how to answer this question using the subset/implication method already suggested. i'm no expert tutor here, and was attempting to limit my hinting, since i tend to give too much away.

9. Mar 28, 2009

### Staff: Mentor

There is a form of De Morgan's Laws for sets, but the OP was asking about the form that has to do with logic and propositions.

There are two of these laws for sets:
$$(A \cup B)^C = A^C \cap B^C$$
$$(A \cap B)^C = A^C \cup B^C$$

where the C exponent indicates complement

10. Mar 28, 2009

### xaos

set= {set of all objects such that some proposition is true}
i'm sorry, but i don't get whatever the difference is.

11. Mar 28, 2009

### Staff: Mentor

Interlogic was asking about the form of De Morgan's Law that applies to propositions: statements whose value is either true or false. It wasn't the form that applies to sets. There's a difference between a set and a proposition.

12. Mar 28, 2009

### xaos

yeah, i thought it was strange notation for set building. but my little venn diagram beats up your tough truth table 3 out of every 4 proofs...

13. Mar 29, 2009