# Propositional Logic (calculus)…stuck

Derive $c$ using:

1. $b \implies \lnot a$ (b implies negated a)
2. $a \land b$ (a and b)

This is what I have done so far:

1. $a \land b$ premise
2. $b\implies -a$ premise
3. $b$ $\land$-elim, 1
4. $\lnot a$ $\implies$-elim, 2,3

now I have $a$ and $\lnot a$ but I still don't know how to solve for $c$. Anyone have any ideas?

-

What you need here is the principle of explosion, also known as ex falso quodlibet in Latin: If you have derived a contradiction, you're allowed to leap anywhere at all from that in one step.

Precisely how you formally justify that leap varies considerably with the proof system your're working in. The other answers so far all give reasonable suggetions; an additional one that that aligns reasonably well with how ordinary mathematical proofs go is:

... and therefore $a\land \neg a$.

Now I will prove $c$ indirectly. We assume $\neg c$, and then seek to derive a contradiction. But $a\land \neg a$ is a contradiction. (Never mind that we didn't use $\neg c$ to get it, it's enough that we have it). Therefore, by contradiction, $c$. Q.E.D.

-

If $\neg a$, then certainly $\neg a \vee c$... can you see how to eliminate $\neg a$ from that?

(The essence of this argument is the logical principle of ex falso quodlibet, meaning roughly that if you have a contradiction in your logical system, you can prove any statement at all).

-

Well, now you have $a \land -a$, which is a wrong statement, and you may derive anything from it, in particular $c$. Remember that $p \Rightarrow q$ is always true, if $p$ is false, regardless of $q$.

-

Note that $b \Rightarrow (\neg a)$ is the same as $(\neg b) \vee \neg (a)$. Moreover, this is the same as $\neg (a \wedge b)$.

Let $P$ abbreviate $a \wedge b$. In particular 2. is $P$. From the first paragraph, we have shown that 1. gives $\neg P$.

Hence you have $P \wedge \neg P$.

By using truth table, you can check that $(P \wedge \neg P) \Rightarrow c$ is a Tautology (always true) for all $c$.

So far, we have $P \wedge \neg P$ and $(P \wedge P) \Rightarrow c$. By Modus Ponen, you have $c$.

A formal system is sometimes called inconsistent if it can prove a contradiction (i.e. $P \wedge \neg P$). An alternative definition of inconsistent is that the formal system can prove everything. The argument here shows that the two definition are equivalent.

-
 thx for the help, got it! – Mark Manickaraj Sep 13 '12 at 21:42

If you have Modus Ponens (MP) and the following axioms (for all formulas $\alpha$, $\beta$ and $\gamma$):

A1.  $(\alpha \rightarrow (\beta \rightarrow \alpha)$

A2.  $(\alpha \rightarrow (\beta \rightarrow \gamma) \rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma)$

A3.  $((\neg \beta \rightarrow \neg \alpha) \rightarrow (\alpha \rightarrow \beta))$

Then a formal derivation of $c$ from $\Gamma = \{a, \neg a\}$ could be

1. $\neg a \rightarrow (\neg c \rightarrow \neg a)$  [from A1]
2. $\neg a$ [from $\Gamma$]
3. $(\neg c \rightarrow \neg a)$  [MP from 1 and 2]
4. $(\neg c \rightarrow \neg a) \rightarrow (a \rightarrow c)$  [from A3]
5. $(a \rightarrow c)$  [MP from 3 and 4]
6. $a$  [from $\Gamma$]
7. $c$  [MP from 5 and 6]
-