Results 1 to 9 of 9
Like Tree1Thanks
  • 1 Post By benderjaii

Math Help - Proposition equivalence

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    6

    Proposition equivalence

    Show that the propositions p1 , p2 , p3 , p4 , and p5 can be shown to be equivalent
    by proving that the conditional statements p1 -> p4, p3 -> p1, p4 -> p2, p2 -> p5, and
    p5 -> p3, are true.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Assume that the implications are true. One has to show that p_i, i=1,\dots,5 are either all true or all false.

    Assume that p_1 is true; then show that all p_4, p_2, p_5, p_3 are true. Now assume that p_1 is false; show that p_3, p_5, p_2, p_4 are false.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    6
    Emakarov I appreciate your Help But I need more help in proof. Also Some Other ways.................................
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    So, for example, suppose that the implications are true and p1 is false. We need to show that p3, p5, p2, p4 are false. One of the true implications is p3 -> p1. Looking at the truth table for implication, what does it say about the truth value of p3?

    Once you establish that p3 is false, consider the true implication p5 -> p3. What does it say about p5?

    To solve this problem, you need to understand when exactly p -> q is true depending on whether p and q are true (the truth table for implication). I also assume that p and q are equivalent, by definition, means that both p and q are true or both are false. If you have a different definition of "equivalent", for example, that p -> q /\ q -> p is derivable in some system, then you need to say so.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    1 -> 4
    3 -> 1
    4 -> 2
    2 -> 5
    5 -> 3

    Show

    1 <-> 2
    2 <-> 3
    3 <-> 4
    4 <-> 5
    5 <-> 1

    (from which it will follow that they're all equivalent, just by going full circle from any one to another).

    1 -> 4 and 4 -> 2, so 1 -> 2.
    2 -> 5 and 5 -> 3 and 3 -> 1, so 2 -> 1
    so 1 <-> 2

    Etc.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2014
    From
    United States
    Posts
    1
    Thanks
    1

    Re: Proposition equivalence

    A really interesting way to solve this problem is with graph theory. A step by step proof is below:

    1. Each proposition (p1, p2, ... p5) should be drawn as a node on a graph.
    2. A directed arrow should be drawn to represent the relationship ("a implies b") where a and b are nodes on the graph. For example a directed arrow should be drawn between nodes p1 and p4.

    Next analyze the graph. You'll see that there are five nodes, each having an in-degree of 1 and an out-degree of 1. According to Euler's proof, a Euler Circuit exists for a directed graph if it's connected and the in-degree and each node has the same in-degree and as its out-degree.

    Since this graph satisfies the conditions, it is a Euler Circuit so every node contains a path back to itself passing through every other node exactly once. According to our relation then ("a implies b") every node of our graph implies every other node including itself. Thus the statements are equivalent.
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Proposition equivalence

    Welcome to the forum, benderjaii!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779

    Re: Proposition equivalence

    Hello, recon!

    \text{Show that the propositions }p_1 , p_2 , p_3 , p_4 , p_5\text{ can be shown to be equivalent by proving that the}
    \text{conditional statements: } p_1\!\to\!p_4,\, p_3\!\to\! p_1,\, p_4\!\to\!p_2,\, p_2\!\to\!p_5,\, p_5\!\to\!p_3\text{ are true.}

    We have: . \begin{Bmatrix}p_1\to p_4 & [1] \\ p_4 \to p_2 & [2] \\ p_2\to p_5 & [3] \\ p_5\to p_3 & [4] \\ p_3\to p_1 & [5] \end{Bmatrix}


    We are given:. [1]\;\;p_1\to p_4

    From [2], [3], [4], [5], we have:

    . . \big[(p_4\to p_2) \wedge(p_2\to p_5) \wedge (p_5\to p_3) \wedge (p_3\to p_1)\big] \;\Longrightarrow (p_4\to p_1) . Syllogism


    Hence, we have: . (p_1\to p_4) \wedge (p_4\to p_1)

    Therefore: . p_1 \:\Longleftrightarrow\;p_4


    Prove the remaining equivalences in a similar manner.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,453
    Thanks
    1868

    Re: Proposition equivalence

    Quote Originally Posted by recon View Post
    Show that the propositions p1 , p2 , p3 , p4 , and p5 can be shown to be equivalent
    by proving that the conditional statements p1 -> p4, p3 -> p1, p4 -> p2, p2 -> p5, and
    p5 -> p3, are true.
    Somewhat tedious but this is here is one way to do this. We are given "p1->p4" so if p1 is true, so is p4. Also we are give "p4-> p2", "p2->p5", "p5->p3" and "p3-> p1". That is, if p4 is true then p2 is true so p5 is true so p3 is true and then p1 is true. Therefore p1 is true. Since p1->p4 and p4->p1, p1 and p =p4 are equivalent.

    Similarly, p1->p4 and p4-> p2 so if p1 is true then p4 is true and so p2 is true. That is, if p1 is true so is p2. But p2->p5, p5->p3, and p3->p1. So if p2 is true so is p1. Since p1-> p2 and p2-> p1, they are equivalent.

    If you do this for p1 is equivalent to each of p2, p3, p4, and p5, then you use "if pn is equivalent to p1 and p1 is equivalent to pm, then pn is equivalent to pm" to prove the other equivalences.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  2. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:36 PM
  3. Proposition Help!?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 04:16 PM
  4. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 10:03 AM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum