# need to check logical equivalence

• Sep 4th 2011, 11:47 AM
issacnewton
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 ?(Bug)
• Sep 4th 2011, 12:13 PM
DrSteve
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).
• Sep 4th 2011, 12:33 PM
issacnewton
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)$ ?

(Emo)(Drink)
• Sep 4th 2011, 05:23 PM
ModusPonens
Re: need to check logical equivalence
EDIT: forget it.
• Sep 4th 2011, 05:31 PM
Soroban
Re: need to check logical equivalence
Hello, issacnewton!

I believe I have a valid proof . . .

Quote:

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

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

• Sep 5th 2011, 08:28 AM
DrSteve
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.
• Sep 5th 2011, 01:17 PM
emakarov
Re: need to check logical equivalence
Quote:

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.
• Sep 5th 2011, 10:49 PM
issacnewton
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 ? (Bow)