Results 1 to 8 of 8

Math Help - need to check logical equivalence

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Smile need to check logical equivalence

    Hi

    I am reading "Introduction to Set theory" by J.Donald Monk and while going through
    some theorem there, I needed the following equivalence.

    (p\Leftrightarrow q)\wedge (r \Leftrightarrow q)\equiv (p\Leftrightarrow r)


    I want to know if this is true ? I think so. Any hints about proving this without using
    truth tables. I would just convert this into combination of \wedge and
    \vee .I tried to do that but couldn't get rid of r .

    Any pointers ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2

    Re: need to check logical equivalence

    You can use a truth table, or you can just argue that both sides have the same truth value. Here's a sketch:

    The left is true

    iff

    (p iff q) and (r iff q) are both true

    iff

    p, q have the same truth value AND r,q have the same truth value

    iff

    p,q and r have the same truth value

    iff

    p, r have the same truth value

    iff

    the right hand side is true.


    Remarks: (1) iff stands for "if and only if"

    (2) I did this very quickly, so make sure that all these steps are reversible. If there is an error it should be easy to correct - the basic idea is sound (I'm running out of the house now or I would check it more carefully).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: need to check logical equivalence

    Thanks for the reply, DrSteve , but how do I use different logical equations to go from left to the right ? If they are logically equivalent , shouldn't q
    drop somewhere ? I will briefly write what I did .... I have already proven that

    (P\Leftrightarrow Q) \equiv (P\wedge Q)\vee(\neg P \wedge \neg Q)

    so we can also write

    (R\Leftrightarrow Q) \equiv (R\wedge Q)\vee(\neg R \wedge \neg Q)

    so using this I tried to simplify

    (P\Leftrightarrow Q)\wedge(R\Leftrightarrow Q)

    doing some logical algebra I arrived at

    [P\wedge Q\wedge R]\vee[\neg P\wedge \neg Q\wedge \neg R]

    so how do I make this

    (P\Leftrightarrow R) ?

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member ModusPonens's Avatar
    Joined
    Aug 2010
    Posts
    125
    Thanks
    14

    Re: need to check logical equivalence

    EDIT: forget it.
    Last edited by ModusPonens; September 4th 2011 at 05:44 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    644

    Re: need to check logical equivalence

    Hello, issacnewton!

    I believe I have a valid proof . . .


    Prove or disprove: . (p\Leftrightarrow q)\wedge (r \Leftrightarrow q)\;\equiv\; (p\Leftrightarrow r)

    Start with the left side:

    . . \begin{array}{cc cc cc}1. & (p \Leftrightarrow q) \:\wedge\: (r \Leftrightarrow q) && 1. & \text{Given} \\ \\[-3mm] 2. & [(p \to q) \wedge (q \to p)] \wedge [(r\to q) \wedge (q \to r)] && 2. &\text{Def. bicond'l} \\ \\[-3mm] 3. & [(p\to q) \wedge (q \to r)] \wedge [(r\to q) \wedge (q \to p)] && 3. & \text{Comm. Assoc.} \\ \\[-3mm] 4. & (p \to r) \wedge (r \to p) && 4. & \text{Syllogism} \\ \\[-3mm] 5. & p \Leftrightarrow r && 5. & \text{Def. bicond'l} \end{array}

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2

    Re: need to check logical equivalence

    @Soroban: I think that you only showed the left side implies the right. Most of your steps are reversible, but I don't think you can show (4) implies (3) using a single law.

    @isaac: It looks like you're trying to convert everything to disjunctive normal form. Is this a requirement that your teacher has imposed? If so you should state it in the problem. If not, it doesn't seem like the best way to go about it.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: need to check logical equivalence

    Quote Originally Posted by issacnewton View Post
    (p\Leftrightarrow q)\wedge (r \Leftrightarrow q)\equiv (p\Leftrightarrow r)
    Soroban gave a left-to-right derivation. The other direction is false when p and r and true and q is false.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: need to check logical equivalence

    Soroban,

    I was thinking about your derivation and how you got from step 3 to 4. In
    Daniel Velleman's "How to prove it" , on page 54 , there is an exercise to prove that

    (P\Rightarrow Q)\wedge(Q\Rightarrow R)\equiv (P\Rightarrow R )\wedge[(P\Leftrightarrow Q)\vee(R\Leftrightarrow Q)]

    I have not been able to prove it , but I could see that this can be used to go from step 3 to 4. Since we have been given ,

    (P\Leftrightarrow Q)\wedge(Q\Leftrightarrow R)

    it follows from here that

    (P\Leftrightarrow Q)\vee(R\Leftrightarrow Q)

    and using the equivalence I quoted , we can say

    (P\Rightarrow Q)\wedge(Q\Rightarrow R)\equiv (P\Rightarrow R )

    is it the right conclusion ?

    But as Drsteve and emakarov have pointed out, we can prove only one direction. So may be there is something wrong in the reasoning just provided by me.
    Can anybody point out the flaw in my reasoning ?
    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. [SOLVED] Logical Vs Material equivalence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 7th 2011, 06:56 AM
  3. Logical Equivalence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 22nd 2010, 01:43 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

/mathhelpforum @mathhelpforum