Help with proving Biconditional equivalence

  • Context: Undergrad 
  • Thread starter Thread starter the baby boy
  • Start date Start date
  • Tags Tags
    Equivalence
Click For Summary

Discussion Overview

The discussion revolves around proving the biconditional equivalence \( P \leftrightarrow Q \) is equal to \( (P \wedge Q) \vee (\neg P \wedge \neg Q) \). Participants explore various methods, including truth tables and distributive laws, to establish this logical equivalence.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Homework-related

Main Points Raised

  • One participant begins with the expression \( (P \rightarrow Q) \wedge (Q \rightarrow P) \) and attempts to manipulate it to prove the equivalence.
  • Another participant suggests that while the initial steps are correct, the subsequent approach is not effective and recommends using distributivity instead.
  • Some participants propose using truth tables to demonstrate the equivalence, while others express concerns about this method being insufficient for homework purposes.
  • There is a discussion about the application of the distributive law, with one participant clarifying that a common item, rather than a common letter, can be used for factoring.
  • One participant shares their confusion regarding distribution and expresses a desire for further guidance on how to proceed with their proof.
  • A later post introduces a new problem involving implications and asks for advice on whether to expand or reduce expressions in the proof process.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best method to prove the equivalence. Multiple approaches are discussed, including truth tables and distributive laws, with differing opinions on their effectiveness.

Contextual Notes

Some participants express uncertainty about the application of distributive laws and the validity of using truth tables, indicating a lack of clarity on the requirements for their homework.

Who May Find This Useful

Students learning basic logic, particularly those seeking to understand logical equivalences and proof techniques in mathematical reasoning.

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

  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 2 ·
Replies
2
Views
7K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K