[Math] Proving a theorem of logic

foundationslogicphilosophy

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

Best Answer

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?

Related Question