# Proving a theorem of logic

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:

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

• 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. – Terra Hyde Jul 16 '15 at 6:16
• 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. – Inebriated Jul 16 '15 at 6:40
• 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}$$ – Terra Hyde Jul 16 '15 at 7:04
• 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. – Inebriated Jul 16 '15 at 10:12
• 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. – Inebriated Jul 16 '15 at 11:35

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?

• 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. – Inebriated Jul 16 '15 at 11:31