Help with proving Biconditional equivalence

  • #1
show that P [itex]\leftrightarrow[/itex] Q is equal to (P[itex]\wedge[/itex]Q) [itex]\vee[/itex] ([itex]\neg[/itex]P [itex]\wedge[/itex][itex]\neg[/itex]Q)

(P→Q) [itex]\wedge[/itex] (Q→P)
([itex]\neg[/itex]P[itex]\vee[/itex]Q) [itex]\wedge[/itex] ([itex]\neg[/itex]Q[itex]\vee[/itex]P)

[[itex]\neg[/itex](P[itex]\wedge[/itex][itex]\neg[/itex]Q)[itex]\wedge[/itex][itex]\neg[/itex](Q[itex]\wedge[/itex][itex]\neg[/itex]P)]

[itex]\neg[/itex][(P[itex]\wedge[/itex][itex]\neg[/itex]Q)[itex]\vee[/itex](Q[itex]\wedge[/itex][itex]\neg[/itex]P)]

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

Answers and Replies

  • #2
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
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
How can I use the distributive law here? I mean, I don't see a common letter with a connective to factor out.
 
  • #4
Bacle2
Science Advisor
1,089
10
Why not just do a truth table?
 
  • #5
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
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.


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."
 
  • #6
Deveno
Science Advisor
906
6
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
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 [itex]\rightarrow[/itex]Q) [itex]\wedge[/itex] (Q [itex]\rightarrow[/itex] R) = (P [itex]\rightarrow[/itex] R) [itex]\wedge[/itex] [(P [itex]\leftrightarrow[/itex] Q) [itex]\vee[/itex] (Q [itex]\leftrightarrow[/itex] R)]

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

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

Related Threads on Help with proving Biconditional equivalence

Replies
0
Views
3K
  • Last Post
Replies
2
Views
1K
Replies
7
Views
2K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
0
Views
2K
Top