Proving Demorgan's Rule for Beginners

[InterLogic]

Homework Statement

~(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.

Homework 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).

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!

 

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

 

[Mark44]

Preferably any of the following: MP, MT, CP, DN, &E, &I, DS <>I, <>E, vI.

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.

 

[xaos]

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

 

[InterLogic]

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.

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

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

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

 

[Mark44]

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.

 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.

 

[InterLogic]

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.

 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.

Thanks!

 

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

 

[Mark44]

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

 

[xaos]

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

 

[Mark44]

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.

 

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

 

[Mark44]

Venn diagrams are about sets.

There's an old saying, "When the only tool you have is a hammer, everything looks like a nail."

 

[xaos]

grumble. fine, you keep your predicate calculus. but if n=10, and 2^n is the number of times i need to write a T and an F, I'm going to try to reformulate the question into terms of sets and writing A={x | P(x) }, X-A={x | ~P(x)} is a pretty good start.

okay, i'll try to find at my logic book again, but it put me to sleep last time i tried. oo look! a topology book! (easily distracted)