# Help with proving Biconditional equivalence

1. Nov 11, 2011

### the baby boy

show that P $\leftrightarrow$ Q is equal to (P$\wedge$Q) $\vee$ ($\neg$P $\wedge$$\neg$Q)

(P→Q) $\wedge$ (Q→P)
($\neg$P$\vee$Q) $\wedge$ ($\neg$Q$\vee$P)

[$\neg$(P$\wedge$$\neg$Q)$\wedge$$\neg$(Q$\wedge$$\neg$P)]

$\neg$[(P$\wedge$$\neg$Q)$\vee$(Q$\wedge$$\neg$P)]

I don't know which law to use from this point on to prove the equivalence.

2. Nov 11, 2011

### D H

Staff Emeritus
You started right with going from (P→Q) ∧ (Q→P) to (¬P∨Q) ∧ (¬Q∨P), but from there on you are taking the wrong path. Not invalid; just wrong. That path won't get you to the desired result. Try using distributivity.

Or just use the dumb approach of showing that P ↔ Q and (P∧Q) ∨ (¬P ∧¬Q) have the identical truth tables.

3. Nov 11, 2011

### the baby boy

How can I use the distributive law here? I mean, I don't see a common letter with a connective to factor out.

4. Nov 12, 2011

### Bacle2

Why not just do a truth table?

5. Nov 12, 2011

### D H

Staff Emeritus
Who said you need a common letter to factor out? All you need is a common item.

Given a conjunctive normal form (A∨B)∧(C∨D), you can use either (A∨B) or (C∨D) as the common item in applying distributivity. Using (A∨B) as the common item yields ((A∨B)∧C)∨((A∨B)∧D) . (You'll get (A∧(C∨D))∨(B∧(C∨D)) if you use (C∨D) as the common item.) Now apply the distributive law again to put this into disjunctive normal form.

Perhaps because the instructor said something along the lines of "You can easily prove these conjectures by showing they have the same truth tables. Do that and you will receive zero points on this homework."

6. Nov 12, 2011

### Deveno

distributing (¬P∨Q) over (¬Q∨P) we get:

(¬P∨Q)∧(¬Q∨P) = [(¬P∨Q)∧¬Q]∨[(¬P∨Q)∧P]

can you see how to continue?

7. Dec 4, 2011

### the baby boy

Hello,

Thank you all for helping me with this. I am only self-learning basic logic from a book, and the author never worked out distribution of all of the content in the parentheses to another, so I only thought you could distribute one letter at a time.

I have a new problem:

Prove (P $\rightarrow$Q) $\wedge$ (Q $\rightarrow$ R) = (P $\rightarrow$ R) $\wedge$ [(P $\leftrightarrow$ Q) $\vee$ (Q $\leftrightarrow$ R)]

I was able to get this far:
($\neg$P $\wedge$ $\neg$Q) $\vee$ [($\neg$P $\vee$ Q) $\wedge$ R] = ($\neg$P $\vee$ R) $\wedge$ [(($\neg$P $\wedge$ $\neg$Q) $\vee$ (P $\wedge$ Q)) $\vee$ (($\neg$R $\wedge$ $\neg$Q) $\vee$ (R $\wedge$ Q))]

How should I proceed? Should I continue to expand the left side of the equation or somehow try to reduce the right?