Help with proving Biconditional equivalence

  • Thread starter Thread starter the baby boy
  • Start date Start date
  • Tags Tags
    Equivalence
AI Thread Summary
The discussion focuses on proving the biconditional equivalence P ↔ Q as equal to (P ∧ Q) ∨ (¬P ∧ ¬Q). Participants explore various logical transformations, including using truth tables and the distributive law, to demonstrate the equivalence. There is a debate on the best approach, with some suggesting the use of truth tables is insufficient for academic purposes. The conversation also shifts to a new problem involving implications and biconditional statements, with the user seeking guidance on whether to expand or reduce expressions. The overall emphasis is on understanding logical equivalences and the appropriate methods for proving them.
the baby boy
Messages
7
Reaction score
0
show that P \leftrightarrow Q is equal to (P\wedgeQ) \vee (\negP \wedge\negQ)

(P→Q) \wedge (Q→P)
(\negP\veeQ) \wedge (\negQ\veeP)

[\neg(P\wedge\negQ)\wedge\neg(Q\wedge\negP)]

\neg[(P\wedge\negQ)\vee(Q\wedge\negP)]

I don't know which law to use from this point on to prove the equivalence.
 
Physics news on Phys.org
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.
 
How can I use the distributive law here? I mean, I don't see a common letter with a connective to factor out.
 
Why not just do a truth table?
 
the baby boy said:
How can I use the distributive law here? I mean, I don't see a common letter with a connective to factor out.
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.
Bacle2 said:
Why not just do a truth table?
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."
 
distributing (¬P∨Q) over (¬Q∨P) we get:

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

can you see how to continue?
 
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 \rightarrowQ) \wedge (Q \rightarrow R) = (P \rightarrow R) \wedge [(P \leftrightarrow Q) \vee (Q \leftrightarrow R)]

I was able to get this far:
(\negP \wedge \negQ) \vee [(\negP \vee Q) \wedge R] = (\negP \vee R) \wedge [((\negP \wedge \negQ) \vee (P \wedge Q)) \vee ((\negR \wedge \negQ) \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?
 

Similar threads

Back
Top