1
$\begingroup$

At the moment I'm going through a book which treats logic in a very rigorous axiomatic way. But I just got stuck in this theorem that I can't seem to be able to solve (I'm still trying hard). The thing is, that I already went through all the theorems before, and all the theorems after this particular theorem, but I still can't solve it.

This is the theorem I have to prove:

Theorem

The symbol 'y' is equal to 'and', because the book is in Spanish. At the moment, I'm going this way, and I think I'm 'very near' to prove it.

I start by the axiom 2, which it is the material conditional:

$ (R\implies S) \iff (\lnot R \lor S) $ (1)

And also using the axiom but backwards:

$ (S\implies R) \iff (\lnot S \lor R) $ (2)

I think the key is in two theorems I already proved.

First theorem:

If $A \implies B$ and $ C \implies D $ are both true, then $ (A \land C) \implies (B \land D) $ is also true

Similarly, second theorem:

If $A \implies B$ and $ C \implies D $ are both true, then $ (A \lor C) \implies (B \lor D) $ is also true

So by using this, I go this way. By using (1) and (2) and theorem 1 I get:

$ (S \implies R) \land (R \implies S) \iff [(\lnot R \lor S) \land (\lnot S \lor R)] $ is true

This is equivalent to

$ (R \iff S) \iff [(\lnot R \lor S) \land (\lnot S \lor R)] $

But I haven't been able to match the other side through already proved theorems or axioms. Some help will be greatly appreciated.


I'm editing to add the theorems of distribution:

Let A, B and C be statements. Then:

$ (A \lor B) \land C \implies [ (A \land C) \lor (B \land C)] $ is true

$ (A \land B) \lor C \iff [ (A \lor C) \land (B \lor C)] $ is true

$\endgroup$
  • 1
    $\begingroup$ Do you know the way distribution works over logical OR and logical AND? This is one way to handle it: $$(\neg R\vee S)\wedge(\neg S\vee R)=((\neg R\vee S)\wedge\neg S)\vee((\neg R\vee S)\wedge R)$$ And then repeat. It leaves you with something irritating, but that can be removed freely when the time comes as it has no impact on the value of the statement, a fact which may not be immediately obvious. $\endgroup$ – Terra Hyde Jul 16 '15 at 6:16
  • $\begingroup$ I forgot about it, thanks for the clue. I'll add the theorems regarding distribution to the post, I already proved those. I would say they are the the same you used, only that they are stated in a different way. I get near to the final of the proof, but not totally. $$ [(\lnot R \land \lnot S) \lor (\lnot R \land R)] \lor [(S \land \lnot S) \lor (S \land R)] $$ I know by theorem that $(R \land \lnot R)$ and similarly $(S \land \lnot S)$ are false, but that's all. I think we are already there, I just have to find a way to get rid of those two things which are unnecessary. $\endgroup$ – Inebriated Jul 16 '15 at 6:40
  • 1
    $\begingroup$ The $\vee$ operator is true if either one of its arguments is true. If one of them is always false, you can remove the $\vee$ and the false argument, leaving only the one that is potentially true. Check a truth table for the idea: $$\begin{array}{ccc}p&q&p\vee q\\T&F&T\\F&F&F\end{array}$$ $\endgroup$ – Terra Hyde Jul 16 '15 at 7:04
  • $\begingroup$ Thanks! When I took logic in my first courses, we used that syllogism; but at the moment I'm taking a course in Foundations of Mathematics, and the more important element seems to be rigour. I know that argument is true, and I have been thinking in it for the past two hours, but I don't know if I can use it, because it doesn't seem 'rigorous enough'. I'm still having a trouble understanding what is 'rigorous enough', and what is not. Some theorems that I proved, seemed obvious and were difficult to prove; other seemed complex, and need some basic reasoning. $\endgroup$ – Inebriated Jul 16 '15 at 10:12
  • $\begingroup$ Well, after all I finished doing it this way. Only that I stated the argument you said as a theorem, then I went to proved it rigorously, and then I used it in this theorem. Thanks to everyone. $\endgroup$ – Inebriated Jul 16 '15 at 11:35
1
$\begingroup$

I'm using natural deduction:

Theorem: $(R\leftrightarrow S) \leftrightarrow (R\land S)\lor(\neg R \land \neg S)$

Proof ($\Rightarrow$):

1) $(R\leftrightarrow S)$, assumption

2) $(R\rightarrow S)$, 1, $\leftrightarrow$-elim

3) $\neg ((R\land S)\lor(\neg R \land \neg S))$, assumption

4) $R\land S$ , assumption

5) $(R\land S)\lor(\neg R \land \neg S)$, 4, $\lor$-intro

6) $\bot$, 3,5, $\land$-intro

7) $\neg (R\land S)$, 4-6, $\neg$-intro

8) $\neg R \land \neg S$, assumption

9) $(R\land S)\lor(\neg R \land \neg S)$, 8, $\lor$-intro

10) $\bot$, 3,9, $\land$-intro

11) $\neg (\neg R \land \neg S)$, 8-10, $\neg$-intro

12) $(\neg (R\land S)) \land (\neg (\neg R \land \neg S))$, 7, 11, $\land$-intro

13) $(R\land S) \lor (\neg R \land \neg S)$, 12, De Morgan's Law

14) $\bot$, 3, 13, $\land$-intro

15) $\neg (\neg ((R\land S)\lor(\neg R \land \neg S)))$, 3-14, $\neg$-intro

16) $(R\land S) \lor (\neg R \land \neg S)$, 15, $\neg \neg$-elim

17) $(R\leftrightarrow S) \rightarrow ((R\land S) \lor (\neg R \land \neg S))$, 1-16, $\rightarrow $-intro

Can you continue from here?

$\endgroup$
  • $\begingroup$ The course I'm taking at the moment is axiomatic, so natural deduction is out of the tools. But I already proved the theorem. I had to state a theorem, prove it and then use it to prove this one. But I appreciate your help. $\endgroup$ – Inebriated Jul 16 '15 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.