# Thread: need to check logical equivalence

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

$\displaystyle (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 $\displaystyle \wedge$ and
$\displaystyle \vee$ .I tried to do that but couldn't get rid of $\displaystyle r$ .

Any pointers ?

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

3. ## 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

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

so we can also write

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

so using this I tried to simplify

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

doing some logical algebra I arrived at

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

so how do I make this

$\displaystyle (P\Leftrightarrow R)$ ?

4. ## Re: need to check logical equivalence

EDIT: forget it.

5. ## Re: need to check logical equivalence

Hello, issacnewton!

I believe I have a valid proof . . .

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

Start with the left side:

. . $\displaystyle \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}$

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

7. ## Re: need to check logical equivalence

Originally Posted by issacnewton
$\displaystyle (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.

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

$\displaystyle (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 ,

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

it follows from here that

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

and using the equivalence I quoted , we can say

$\displaystyle (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 ?