1

I need help proving validity of this:

((A ∧ B)∨(¬A ∧¬B))<==>(A<==>B)

This is how we did it in class, but I don't actually understand this very well. Could someone explain to me how to do this or give me something to read instead? I was absent in class when the professor showed this and the section in our textbook doesn't completely cover this.

4
  • 4
    This is probably a better question for your TA or professor than SE, honestly. But look at what you're trying to prove: it's a statement of the form X <-> Y. You show this by first proving X -> Y and then Y -> X. Those are the two big 'branches' on your proof tree. Each of those branches is itself a proof, so try to understand how those work and you'll be done. Commented Mar 6, 2015 at 17:49
  • Yes I understood that part, but what comes next? From A^B they're getting A and -A (where does -A come from?) and from it a contradiction, from which they're again getting A?
    – esnafga
    Commented Mar 6, 2015 at 19:15
  • To complete the proof in the left to right direction you need to do a disjunction elimination on ((A^B)v(~A^~B)) and show that no matter which of the disjuncts is true, (A<->B) follows. We do that by supposing (A^B) is true and derive (A<->B), and similarly for (~A^~B). Commented Mar 6, 2015 at 20:00
  • A simple way would be to just do the truth table for each. Commented Mar 9, 2015 at 19:49

2 Answers 2

2

The proof is a Natural Deduction proof.

Here is the first part (the "short" one) :

[(A ∧ B)∨(¬A ∧¬B)] → (A ↔ B)

Proof

1) (A ∧ B)∨(¬A ∧¬B) --- premise

2) (A ∧ B) --- assumed [a] for ∨-elimination

3) B --- from 2) by ∧-elimination

4) ¬B --- assumed [c]

5) --- from 3) and 4)

6) (¬A ∧ ¬B) --- assumed [b] for ∨-elimination

7) ¬B --- from 6) by ∧-elimination

8) A --- assumed [d]

9) --- from 7) and 8)

10) --- from 2)-5) and 6)-9) and 1) by ∨-elimination, discharging [a] and [b]

11) B --- from 4) and 10) by Double Negation (or RAA), discharging [c]

12) A → B --- from 8) and 11) by →-introduction, discharging [d]

In the same way, exchanging the roles of A and B, we can derive :

13) B → A

14) (A ↔ B) --- from 12) and 13) by ↔-introduction

15) [(A ∧ B)∨(¬A ∧¬B)] → (A ↔ B) --- from 1) and 14) by →-introduction.

1

One approach for handling this type of problem, when there are only a few variables involved, is to simply write out the truth tables of the two expression and verify that, for all T/F assignments to variables, the truth values of the two statements are the same.

3
  • Yes, but the professor will have this method on the exam so I have to learn to do it this way.
    – esnafga
    Commented Mar 6, 2015 at 19:01
  • Yes, I was thinking about putting that disclaimer in the answer. However, this answer could be useful to someone else who has a similar question.
    – Dave
    Commented Mar 6, 2015 at 19:24
  • @esnafga what method are you talking about exactly? It's not clear from your question.
    – user2953
    Commented Mar 6, 2015 at 19:44

Not the answer you're looking for? Browse other questions tagged .