Results 1 to 9 of 9

Math Help - How to prove logical equivalence using Theorems and substitution?

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    21

    How to prove logical equivalence using Theorems and substitution?

    So, I have the statement

    (p ^ q) \/ (p ^ q) ≡ p

    I have to prove the given logical equivalence using Theorems and not constructing a truth table. If anyone has as idea how I prove this I would appreciate an explanation and solution.

    cheers
    -ipatch
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    10,969
    Thanks
    1010
    Quote Originally Posted by ipatch View Post
    So, I have the statement

    (p ^ q) \/ (p ^ q) ≡ p

    I have to prove the given logical equivalence using Theorems and not constructing a truth table. If anyone has as idea how I prove this I would appreciate an explanation and solution.

    cheers
    -ipatch
    Just read it as a sentence:

    "p and q" or "p and not q".

    It's saying you have to have p but you may or may not have q.


    So what it's the same as having? p.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    I have to prove the given logical equivalence using Theorems and not constructing a truth table
    The solution depends on what theorems you have in mind. Every course may have a different set of those.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, ipatch!

    I don't know the names of the theorems you know.
    I hope you can follow my proof.


    Prove: . (p \;\wedge\;  q) \;\vee\; (p\; \wedge \sim q) \;\;\equiv \;\; p

    . . . . . . . . . (p \;\wedge\; q) \;\vee\; (p\; \wedge\; \sim q)

    . . (p \;\vee\; p) \;\wedge\; (p \;\vee\; \sim q) \;\wedge\; (q \;\vee\; p) \;\wedge\; (q \;\vee\; \sim q) . . Distributive

    . . . . . . p\;\wedge\;(p\;\vee\;\sim q)\;\wedge\;(p\;\vee\; q) \;\wedge\; T

    . . . . . . . . . (p\;\vee\;\sim q)\;\wedge\; (p\;\vee q)

    . . . . . . . . . . . p\;\vee(\sim q\;\wedge\; q) . . . . . . . . . . . . Distributive

    . . . . . . . . . . . . . p\;\vee\;F

    . . . . . . . . . . . . . . . p


    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello ipatch
    Quote Originally Posted by ipatch View Post
    So, I have the statement

    (p ^ q) \/ (p ^ q) ≡ p

    I have to prove the given logical equivalence using Theorems and not constructing a truth table. If anyone has as idea how I prove this I would appreciate an explanation and solution.

    cheers
    -ipatch
    Using the standard Laws of Boolean Algebra (for instance, just here) we get:
    (p \land q)\lor(p\land\neg q) \equiv p\land(q\lor\neg q) (Distributive Law)
    \equiv p\land T (Complement Law)

    \equiv p (Identity Law)
    Grandad
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2010
    Posts
    2
    (p ^ q) \/ (p ^ q) ≡ p

    1. (p ^ q) \/ (p ^ q)-----------------hypotesis
    2. (p ^ q)-----------------assume
    3. p-----------------2, ^-elim 2
    4. (p ^ q)-----------------assume
    5. p-----------------4, ^-elim 2
    6. p-----------------1, 2-3 , 4-5, \/-elim
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello again, ipatch!

    My first proof was long and clumsy.
    (Don't know where my brain was at the time.)

    There are two theorems we need. .(I don't know their names.)

    . . \begin{array}{cccc}P \;\vee \sim \!P &\equiv& t & \text{Theorem 1} \\ \\[-3mm] P \wedge \:t &\equiv& P & \text{Theorem 2} \end{array}



    . . . . \begin{array}{ccc}(p \;\wedge\; q) \;\vee\; (p\; \wedge\; \sim q) & \text{Given} \\ \\ p \;\wedge\; (q \;\vee \sim \!q) & \text{Distr.} \\ \\ p \;\wedge \;t & \text{Theorem 1} \\ \\ p & \text{Theorem 2} \end{array}

    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Feb 2010
    Posts
    2
    Quote Originally Posted by cgafa View Post
    (p ^ q) \/ (p ^ q) ≡ p

    1. (p ^ q) \/ (p ^ q)-----------------hypotesis
    2. (p ^ q)-----------------assume
    3. p-----------------2, ^-elim 2
    4. (p ^ q)-----------------assume
    5. p-----------------4, ^-elim 2
    6. p-----------------1, 2-3 , 4-5, \/-elim

    Rules used:
    conjunctive elimination ( ^-elim ) if you have A and B the you have A (or B)... simple
    disjuntive elimination (\/-elim)... a little more complex... if you have A or B and from A you can deduce C; and from B you can deduce C; then from A or B we can deduce C.....
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by ipatch View Post
    So, I have the statement

    (p ^ q) \/ (p ^ q) ≡ p

    I have to prove the given logical equivalence using Theorems and not constructing a truth table. If anyone has as idea how I prove this I would appreciate an explanation and solution.

    cheers
    -ipatch
    ipatch:
    There two kind of proofs,one in Boolean Algebra and one in propositional calculus.

    The proof in Boolean Algebra was shown by other people in the forum.

    The proof in propositional calculus is as follows:

    First we prove :  (p\wedge q)\vee (p\wedge\neg q)\Longrightarrow p and then:

    p\Longrightarrow (p\wedge q)\vee (p\wedge\neg q).

    Proof:

    1) (p\wedge q)\vee (p\wedge\neg q).................................................. ............................given

    2) (p\wedge q).................................................. ..............................................assu mption to start a conditional proof

    3) p................................................. .................................................. .....from (2) and using Conjunction Elimination (=C.E)

    4) (p\wedge q)\Longrightarrow p.................................................. ....................................from (2) to (3) and using the rule of conditional proof

    5) In the same way we prove:   (p\wedge\neg q)\Longrightarrow p

    6) (p\wedge q)\vee (p\wedge\neg q)\Longrightarrow p\vee p.................................................. ...........................from (4)and(5) and using the rule called proof by cases: [((A\Longrightarrow B)\wedge (C\Longrightarrow D))\Longrightarrow ((A\vee C)\Longrightarrow (B\vee D))].

    7) p\vee p.................................................. .......................................from (1) and (6) and using M.Ponens


    8) p\vee p\Longleftrightarrow p.................................................. .......................................tautology


    9) p\vee p\Longrightarrow p.................................................. ........................................from (8) and using biconditional elimination

    10) p................................................. .................................................. ....from (7) and (9) and using M.Ponens

    Now to prove the converse.

    Proof:

    1)p............................................... .................................................. given


    2) \neg(p\wedge q).................................................. ........................................assumption to start a conditional proof


    3) \neg p\vee\neg q.................................................. ..........................................from (2) and using De Morgan


    4) p\Longrightarrow\neg q.................................................. .....................from (3) and using material implication


    5) \neg q.................................................. .....................................from (1) and (4) and using M.Ponens


    6) p\wedge\neg q.................................................. ...........................from (1) and (5) and using Conjunction Introduction


    7) \neg(p\wedge q)\Longrightarrow(p\wedge\neg q).................................................. .......................from (2) to(6) and using the rule of conditional proof


    8) (p\wedge q)\vee (p\wedge\neg q).................................................. ........................from (7) and using material implication  (A\Longrightarrow B)\Longleftrightarrow (\neg A\vee B)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logical equivalence
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 12th 2011, 05:22 PM
  2. Logical Equivalence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 22nd 2010, 01:43 AM
  3. Prove/disprove using logical using logical arguments
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 24th 2010, 06:29 AM
  4. Logical Equivalence Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 2nd 2010, 01:06 PM
  5. Logical Equivalence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 23rd 2008, 08:17 PM

Search Tags


/mathhelpforum @mathhelpforum