Math Help - Proposition equivalence

1. 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.

2. 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.

3. Emakarov I appreciate your Help But I need more help in proof. Also Some Other ways.................................

4. 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.

5. 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.

6. 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.

7. Re: Proposition equivalence

Welcome to the forum, benderjaii!

8. 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.

9. Re: Proposition equivalence

Originally Posted by recon
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.