How to proove De Morgan's Law for Logic?

  1. How to proove De Morgan's Law for Logic??

    Without using Truth table

    thanks folks

    DeMorgan's Law:
    Last edited: Apr 18, 2005
  2. jcsd
  3. honestrosewater

    honestrosewater 2,329
    Gold Member

    Several laws bear his name- which one do you want? Just write it out.
  4. CRGreathouse

    CRGreathouse 3,682
    Science Advisor
    Homework Helper

    I imagine he wants



    (I used - for not; how do you get the proper symbol?)
  5. De Morgan's Law:
  6. Well, here's a way to prove the first implication of the first law, ~(p&q) --> ~p v ~q

    Here the indented lines following an assumption indicate the scope of the assumption:

    Code (Text):

    1. Assume ~(p&q) v (~r&r)
       2. (p&q) --> (~r&r) (1, material implication)
       3. p --> (q --> (~r&r)) (2, exportation)
       4. p --> (~q v (~r&r)) (3, material implication)
       5. ~p v (~q v (~r&r)) (4, material implication)
       6. (~p v ~q) v (~r&r) (5, association)
    7. (~(p&q) v (~r&r)) --> ((~p v ~q) v (~r&r)) (1-6, conditional proof)

    8. Assume ~r&r
    (assumption of line 8 has no scope beyond itself)
    9. ~(~r&r) (8, reductio ad absurdum)

    10. Assume ~(p&q)
       11. ~(p&q) v (~r&r) (10, addition)
       12. (~p v ~q) v (~r&r) (7, modus ponens)
       13. ~p v ~q (9, 12, disjunctive syllogism)
    14. ~(p&q) --> (~p v ~q) (10-13, conditional proof)
    The second half of the first DeMorgan's law, (~p v ~q) --> ~(p&q),
    can be proved similarly.
  7. The key to that proof was the use of exportation to get line 7. Both halves of the second DeMorgan's law can also be proved by the same general idea, though it's slightly trickier.
  8. \neg in LaTeX (for negate).


    [tex] \neg \exists x . P(x) \Leftrightarrow \forall x. \neg P(x) [/tex]
  9. The way I learned this is that is follows from the semantic defintion of truth.

    Say you you have an interpretation M and a sentence F
    by definition

    M|= ~F iff not M|=F
    M|= (F&G) iff M|= F and M|=G
    M|= (FvG) iff M|= F or M|=G

    Thus a consequence of the definition of truth for negation and of two junctions is the fact that (F&G) is true iff ~(~Fv~G) is true, and (FvG) is true iff ~(~F&~G) is true.

    You have ~(PvQ) iff ~P&~Q, which would be equivalent to ~(FvG) iff ~~(~F&~G), which is the same as saying ~(FvG) iff (~F&~G).
  10. How do you reason that?
    Last edited: Apr 20, 2005
  11. Is there no easier way to prove DeMorgan's theorem without having to use EXPORTATION and DISJUNCTIVE SYLLOGISM rules? Is there a way to prove this Law by just using modus ponens, modus tollens, disjunctive argument, conjunctive argument, simplification, and so on?
  12. honestrosewater

    honestrosewater 2,329
    Gold Member

    What is "and so on"? What rules do you have? Just write them out, provide a link, or tell us the name of the system, if you know it; it shouldn't take but a few minutes. :smile:
  13. Construct a PK proof.
  14. AKG

    AKG 2,585
    Science Advisor
    Homework Helper

    Code (Text):
    1  | ~(P & Q)            assumption
    2  || ~(~P v ~Q)         assumption
    3  ||| P                 assumption
    4  |||| Q                assumption
    5  |||| P & Q            3, 4 conjunction introduction
    6  |||| ~(P & Q)         1, repitition
    7  ||| ~Q                4-6 negation introduction
    8  ||| ~P v ~Q           7, disjunction introduction
    9  ||| ~(~P v ~Q)        2, repitition
    10 || ~P                 3-9, negation introduction
    11 || ~P v ~Q            10, disjunction introduction
    12 || ~(~P v ~Q)         2, repitition
    13 | ~P v ~Q             2-12 negation elimination
    Code (Text):
    1  | ~P v ~Q               assumption
    2  || ~P                   assumption
    3  ||| P & Q               assumption
    4  ||| P                   3, conjunction elimination
    5  ||| ~P                  2, repitition
    6  || ~(P & Q)             3-5, negation introduction
    7  || ~Q                   assumption
    8  ||| P & Q               assumption
    9  ||| Q                   8, conjunction elimination
    10 ||| ~Q                  7, repitition
    11 || ~(P & Q)             8-10 negation introduction
    12 | ~(P & Q)              1, 2-5, 7-11 disjunction elimination
    Last edited: Oct 29, 2005
  15. Re: How to proove De Morgan's Law for Logic??

    how to simplify (-p^q)v-(pvq) using the logical equivalence?
  16. Re: How to proove De Morgan's Law for Logic??

    How do you prove the following? I understand that it is part of demorgans law.. but how do i get rid of the double negative?

    -(-A v -B) therefore (A & B)
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?