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

Question

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?

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. — hmakholm left over Monica, Apr 05 '13 at 01:39
@HenningMakholm I have to complete the proof using a Fitch diagram using Predicate Logic rules. — An employee, Apr 05 '13 at 01:40
Thanks @EuYu for the edit :) I wasn't completely sure which symbols to use here - it seems different sites use different symbols for the or, biconditional, and and :-P — An employee, Apr 05 '13 at 01:42
@Christopher: "Predicate logic" is a shared name for a family of proof systems of very different character and internal structure. It can stand for any proof system that proves the same entailment as your favorite formalization of it. So just saying "predicate logic" doesn't help the reader understand which kind of proof it is you need. — hmakholm left over Monica, Apr 05 '13 at 01:42
@HenningMakholm - I need the same type of help as similar to this problem: http://math.stackexchange.com/questions/351208/how-to-prove-that-a-lor-b-land-lnot-a-lor-b-b — An employee, Apr 05 '13 at 01:44
@Christopher: The question you link to also doesn't explain which formal system its asker wants to prove his goal in. If the answer happened to be useful to the asker, it must have been by pure luck. And the accepted answer there certainly has nothing at all to do with Fitch diagrams. — hmakholm left over Monica, Apr 05 '13 at 01:47
@HenningMakholm Can you give me a few examples of what you mean by "formal system"? Maybe I'm just brain dead tonight... :-\ — An employee, Apr 05 '13 at 01:49
@Christopher: Sulrely you must have some rules for what kind of things are legal to do in a formal proof. For example one of the rules might be that if you have proved $A\to B$ and have proved $A$, then you're allowed to conclude $B$. You need to either reproduce those rules in your question, or link to a definite description of them. — hmakholm left over Monica, Apr 05 '13 at 01:51
@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 05 '13 at 01:55
@HenningMakholm I've updated the question to illustrate the application of one of the rules... does this help? — An employee, Apr 05 '13 at 02:02
@Christopher: No, you need to show what the rules are, not just list the names your textbook happens to call them by. — hmakholm left over Monica, Apr 05 '13 at 02:03

manthanomen · Answer 1 · 2013-04-05T02:25:15.550

4

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*}

edited Apr 05 '13 at 02:25

answered Apr 05 '13 at 02:05

manthanomen

3,186

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 05 '13 at 02: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 05 '13 at 02:11
"→" is not part of this proof though. – An employee Apr 05 '13 at 02:15
It is if you use the fact that $(p \leftrightarrow q) \Leftrightarrow (p \rightarrow q) \wedge (q \rightarrow p)$. – manthanomen Apr 05 '13 at 02:21
Unfortunately I don't have that option for this problem... is there another way? – An employee Apr 05 '13 at 02:26
1

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 05 '13 at 02:28

score 3 · Accepted Answer · answered Apr 09 '13 at 18:40

(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))

score 2 · Answer 3 · answered Apr 05 '13 at 02:07

2

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

answered Apr 05 '13 at 02:07

Taladris

11,339
5
32
58

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

score 1 · Answer 4 · answered Aug 18 '19 at 04:23

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/

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

4 Answers4