Results 1 to 6 of 6

Math Help - proof of De Morgan laws

  1. #1
    Banned
    Joined
    Jul 2009
    Posts
    107

    proof of De Morgan laws

    Challenge problem:

    prove the laws of De Morgan:

    ~(p^q) <=> ~p v~q

    ~(p v q) <=> ~p ^~q ,by using the inference rules of the propositional calculus

    Moderator approved. CB
    Last edited by CaptainBlack; June 18th 2010 at 11:21 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Prove that ~(p^q) <=> ~p v~q.

    I like using the natural deduction rules, with the introduction and elimination rules for each symbol. I also like Fitch-style proofs. I will use periods to denote subproofs.


    =>
    1 . ~(p ^ q) Assumption.
    2 . . ~(~p v ~q) Assumption.
    3 . . . ~p Assumption
    4 . . . ~ p v ~q v intro: 3
    5 . . . contradiction contradiction intro: 4, 2
    6 . . ~~p ~ Intro: 3-5
    7 . . p ~ Elimination: 6
    8 . . . ~q Assumption
    9 . . . ~p v ~q v Intro: 8
    10 . . . contradiction contradiction intro 9, 2
    11 . . ~~q ~ Intro: 8-10
    12 . . q ~ Elimination: 11
    13 . . p ^ q ^ Intro: 7, 12
    14 . . contradiction contradiction intro: 1, 13
    15 . ~~(~p v ~q) ~ Intro: 2-14
    16 . ~p v ~q ~ elimination: 15.

    <=
    1 . ~p v ~q Assumption
    2 . . ~p Assumption
    3 . . . p ^ q Assumption
    4 . . . p ^ Elimination: 3
    5 . . . contradiction contradiction intro: 4, 2
    6 . . ~(p ^ q) ~ Intro: 3-5
    . . break
    7 . . ~q Assumption
    8 . . . p ^ q Assumption
    9 . . . q ^ Elimination: 8
    10 . . . contradiction contradiction Intro: 9, 7
    11 . . ~(p ^ q) ~ Intro: 8-10
    . . break
    12 . ~(p ^ q) v Elimination: 1, 2-6, 7-11.

    That, I think, does it for the first DeMorgan law.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by alexandros View Post
    Challenge problem:

    prove the laws of De Morgan:

    ~(p^q) <=> ~p v~q

    ~(p v q) <=> ~p ^~q ,by using the inference rules of the propositional calculus
    I'm not sure about my approach, I'm using this reference:

    Spoiler:

    Propositional calculus - Wikipedia, the free encyclopedia (subheading: Example 1. Simple axiom system)

    The rule of inference is modus ponens (i.e. from p and (p \to q), infer q). Then a \lor b is defined as \neg a \to b, and a \land b is defined as \neg(a \to \neg b).


    First one

    Spoiler:

    1. \neg(p \land q)

    2. \neg(\neg(p \to \neg q)) (definition)

    3. p \to \neg q (elimination of double negative)

    4. \neg\neg p \to \neg q (double negative introduction)

    5. \neg(\neg p) \to (\neg q) (adding parentheses to clarify)

    6. \neg p \lor \neg q (definition)

    Is this acceptable methodology?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    You could use the fact that the algebra of sets is Boolean isomorphic with sentence logic and then the idea (at least to me) is more obvious.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Jul 2009
    Posts
    107
    Quote Originally Posted by Ackbeet View Post
    Prove that ~(p^q) <=> ~p v~q.

    I like using the natural deduction rules, with the introduction and elimination rules for each symbol. I also like Fitch-style proofs. I will use periods to denote subproofs.


    =>
    1 . ~(p ^ q) Assumption.
    2 . . ~(~p v ~q) Assumption.
    3 . . . ~p Assumption
    4 . . . ~ p v ~q v intro: 3
    5 . . . contradiction contradiction intro: 4, 2
    6 . . ~~p ~ Intro: 3-5
    7 . . p ~ Elimination: 6
    8 . . . ~q Assumption
    9 . . . ~p v ~q v Intro: 8
    10 . . . contradiction contradiction intro 9, 2
    11 . . ~~q ~ Intro: 8-10
    12 . . q ~ Elimination: 11
    13 . . p ^ q ^ Intro: 7, 12
    14 . . contradiction contradiction intro: 1, 13
    15 . ~~(~p v ~q) ~ Intro: 2-14
    16 . ~p v ~q ~ elimination: 15.

    <=
    1 . ~p v ~q Assumption
    2 . . ~p Assumption
    3 . . . p ^ q Assumption
    4 . . . p ^ Elimination: 3
    5 . . . contradiction contradiction intro: 4, 2
    6 . . ~(p ^ q) ~ Intro: 3-5
    . . break
    7 . . ~q Assumption
    8 . . . p ^ q Assumption
    9 . . . q ^ Elimination: 8
    10 . . . contradiction contradiction Intro: 9, 7
    11 . . ~(p ^ q) ~ Intro: 8-10
    . . break
    12 . ~(p ^ q) v Elimination: 1, 2-6, 7-11.

    That, I think, does it for the first DeMorgan law.
    On proof (=>) ,step (9) is wrong ,it should be : ~q v ~p instead of ~p v~q.

    And then use commutativity to end up with : ~p v~q.

    The rest is correct ,except the mentioning of the deduction theorem as a final step in both proofs.

    The style of the proof is based on 7 basic laws :

    1) Conjunction Introduction and Elimination

    2) Disjunction Introduction and Elimination

    3) The law of double negation

    4) Contradiction and finally

    5) The rule of conditional proof ( deduction theorem).

    Good work
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Jul 2009
    Posts
    107
    Quote Originally Posted by undefined View Post
    I'm not sure about my approach, I'm using this reference:

    Spoiler:

    Propositional calculus - Wikipedia, the free encyclopedia (subheading: Example 1. Simple axiom system)

    The rule of inference is modus ponens (i.e. from p and (p \to q), infer q). Then a \lor b is defined as \neg a \to b, and a \land b is defined as \neg(a \to \neg b).

    Actually you can prove : a\vee b\Longleftrightarrow\neg a\Longrightarrow b and a\wedge b\Longleftrightarrow\neg(a\Longrightarrow\neg b)

    So definition is redundant.


    First one

    Spoiler:

    1. \neg(p \land q)

    2. \neg(\neg(p \to \neg q)) (definition)

    3. p \to \neg q (elimination of double negative)

    4. \neg\neg p \to \neg q (double negative introduction)

    5. \neg(\neg p) \to (\neg q) (adding parentheses to clarify)

    6. \neg p \lor \neg q (definition)

    Is this acceptable methodology?
    Apart from few mistakes and the style of writing your proof is correct.

    A complete and correct proof on the lines of your proof would be the following:

    1) \neg(p\wedge\neg q).................................................. ....................Assumption

    2) p\Longrightarrow\neg q.................................................. ..........From (1) and using the theorem (in propositional calculus) \neg(a\wedge b)\Longrightarrow a\Longrightarrow\neg b

    3) \neg p\vee\neg q.................................................. ....................From (2) and using the theorem a\Longrightarrow\ b\Longrightarrow\neg a\vee b

    4) \neg(p\wedge q)\Longrightarrow\neg p\vee\neg q............................................From (1) to (3) by using the rule of conditional proof

    Usually in proofs in propositional calculus we use basic ,well known, rules of inference like the ones that Ackbeet used in his proof.

    To use other theorems like you did in your proof you have to show the validity of those theorems by either writing proofs for those theorems or establish that they are tautologies thru true tables
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. De Morgan's Laws proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 17th 2011, 02:56 AM
  2. 2 Questions about probability+De Morgan laws
    Posted in the Statistics Forum
    Replies: 11
    Last Post: April 12th 2011, 07:20 PM
  3. De Morgan's second law Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 23rd 2010, 08:07 PM
  4. De Morgan's laws
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 18th 2008, 01:16 AM
  5. de morgan's laws
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 24th 2008, 05:17 PM

Search Tags


/mathhelpforum @mathhelpforum