1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proving Demorgan's Rule

  1. Mar 27, 2009 #1
    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. jcsd
  3. Mar 27, 2009 #2
    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.
  4. Mar 27, 2009 #3


    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.
  5. Mar 27, 2009 #4
    if x in not in A, where else could x be?
    if x in not in B, where else could x not be?
  6. Mar 27, 2009 #5
    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
  7. Mar 27, 2009 #6


    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.
  8. Mar 27, 2009 #7
    Last edited: Mar 27, 2009
  9. Mar 28, 2009 #8
    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.
  10. Mar 28, 2009 #9


    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:
    [tex](A \cup B)^C = A^C \cap B^C[/tex]
    [tex](A \cap B)^C = A^C \cup B^C[/tex]

    where the C exponent indicates complement
  11. Mar 28, 2009 #10
    set= {set of all objects such that some proposition is true}
    i'm sorry, but i don't get whatever the difference is.
  12. Mar 28, 2009 #11


    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.
  13. Mar 28, 2009 #12
    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...
  14. Mar 29, 2009 #13


    Staff: Mentor

    Venn diagrams are about sets.

    There's an old saying, "When the only tool you have is a hammer, everything looks like a nail."
  15. Mar 30, 2009 #14
    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)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook