2
$\begingroup$

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?

$\endgroup$
13
  • $\begingroup$ Is the V "or," or another logical statement? $\endgroup$
    – Lord Soth
    Apr 5, 2013 at 1:36
  • $\begingroup$ @LordSoth Yes, it's OR $\endgroup$
    – An employee
    Apr 5, 2013 at 1:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – hmakholm left over Monica
    Apr 5, 2013 at 1:39
  • $\begingroup$ @HenningMakholm I have to complete the proof using a Fitch diagram using Predicate Logic rules. $\endgroup$
    – An employee
    Apr 5, 2013 at 1:40
  • 1
    $\begingroup$ @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. $\endgroup$
    – An employee
    Apr 5, 2013 at 1:55

4 Answers 4

Reset to default
4
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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! $\endgroup$
    – An employee
    Apr 5, 2013 at 2:09
  • $\begingroup$ 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? $\endgroup$
    – manthanomen
    Apr 5, 2013 at 2:11
  • $\begingroup$ "→" is not part of this proof though. $\endgroup$
    – An employee
    Apr 5, 2013 at 2:15
  • $\begingroup$ It is if you use the fact that $(p \leftrightarrow q) \Leftrightarrow (p \rightarrow q) \wedge (q \rightarrow p)$. $\endgroup$
    – manthanomen
    Apr 5, 2013 at 2:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – manthanomen
    Apr 5, 2013 at 2:28
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I have to complete within a Fitch Diagram... so I can't use a truth table or other method to prove. $\endgroup$
    – An employee
    Apr 5, 2013 at 2:08
1
$\begingroup$

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.

enter image description here

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

$\endgroup$

You must log in to answer this question.

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