# How to Prove $((F \iff H) \iff ((\neg F \land \neg H) \lor (F \land H)))$

I am at a complete loss here...

$(F \iff H)$ PREMISE
...
$((\neg F \land \neg H) \lor (F \land H))$ GOAL

I keep getting stuck in a loop of contradiction and not able to complete the proof.

I can use the following rules to complete the proof: Conjunction Introduction, Conjunction Elimination, Disjunction Introduction, Disjunction Elimination, Conditional Introduction (although not applicable here), Conditional Elimination (also not applicable), Negation Introduction, Falsum Introduction, Negation Elimination, Biconditional Introduction, and Biconditional Elimination.

For example: I can apply Disjunction Introduction Left ("$\lor IL$") to the current GOAL and result with either (F∧H) or (¬F∧¬H) which then becomes the new goal, such as this:

$(F \iff H)$ PREMISE
...

$(F \land H))$ GOAL

$((\neg F \land \neg H) \lor (F \land H))$

Thoughts?

• Is the V "or," or another logical statement? – Lord Soth Apr 5 '13 at 1:36
• @LordSoth Yes, it's OR – An employee Apr 5 '13 at 1:37
• Which logical system and axioms do you want to prove it from? If you're free to choose any method, then just work out the truth table. – Henning Makholm Apr 5 '13 at 1:39
• @HenningMakholm I have to complete the proof using a Fitch diagram using Predicate Logic rules. – An employee Apr 5 '13 at 1:40
• @HenningMakholm oh yes - ok - here are the rules I am "permitted" to use: Conjunction Introduction, Conjunction Elimination, Disjunction Introduction, Disjunction Elimination, Conditional Introduction (although not applicable here), Conditional Elimination (also not applicable), Negation Introduction, Falsum Introduction, Negation Elimination, Biconditional Introduction, and Biconditional Elimination. – An employee Apr 5 '13 at 1:55

I'm not sure if this proof uses the right system, but perhaps it will help you. It uses the rules of replacement typically called equivalence, implication, and distribution (twice), plus the fact that $p \lor (q \wedge \neg q) \rightarrow p$: \begin{align*} (F \leftrightarrow H) &\Leftrightarrow (F \rightarrow H) \wedge (H \rightarrow F) \\ &\Leftrightarrow (\neg F \lor H) \wedge (\neg H \lor F)\\ &\Leftrightarrow ((\neg F \lor H) \wedge \neg H ) \lor ((\neg F \lor H) \wedge F) \\ &\Leftrightarrow ((\neg F \wedge \neg H) \lor (H \wedge \neg H)) \lor ((\neg F \wedge F) \lor (H \lor F)) \\ &\Leftrightarrow (\neg F \wedge \neg H) \lor (H \wedge F) \\ &\Leftrightarrow (\neg F \wedge \neg H) \lor (F \wedge H) \end{align*}

• Thanks for the post... but I don't have the option to use what I believe you're calling implication ("if this then that"?). But this is definitely on the right path! – An employee Apr 5 '13 at 2:09
• What I call implication is $(p \rightarrow q) \Leftrightarrow (p \lor \neg q$). I use it to get line 2. Perhaps you have a similar rule? – manthanomen Apr 5 '13 at 2:11
• "→" is not part of this proof though. – An employee Apr 5 '13 at 2:15
• It is if you use the fact that $(p \leftrightarrow q) \Leftrightarrow (p \rightarrow q) \wedge (q \rightarrow p)$. – manthanomen Apr 5 '13 at 2:21
• I'm not familiar with the terms your text is using for rules, but you probably have some way to break down $F \leftrightarrow H$ into an equivalent expression. This would be your first step. – manthanomen Apr 5 '13 at 2:28

You can complete a table of values for both expressions. Completion of the table will certainly use the given rules.

• I have to complete within a Fitch Diagram... so I can't use a truth table or other method to prove. – An employee Apr 5 '13 at 2:08

(F↔H)

¬ ((¬F∧¬H) ∨ (H∧F))
¬ (¬F∧¬H)
F
H
(F ∧ H)
((¬F∧¬H) ∨ (H∧F))
┴
¬F
H
F
(F ∧ H)
((¬F∧¬H) ∨ (H∧F))
┴
¬H
(¬F∧¬H)
┴

(¬F∧¬H)
((¬F∧¬H) ∨ (H∧F))
┴

((¬F∧¬H) ∨ (H∧F))

Note that one might intuitively expect this result to be an equivalence:

$$(F\leftrightarrow H) \equiv (\neg F \land \neg H) \lor (F \land H)$$

If $$F$$ and $$H$$ are equivalent then when $$F$$ is false, $$H$$ will also be false. That is represented by $$\neg F \land \neg H$$. Similarly when $$F$$ is true, $$H$$ will be true which is represented by $$F \land H$$. One of these two cases will occur so one can connect them with a disjunction ($$\lor$$).

However, to make sure, here is a natural deduction proof using a Fitch-style proof checker. This uses the law of the excluded middle as was used in the OP's proof and considers both directions in showing the equivalence.

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/