# 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.

-
I don't understand the "never mind" part here. CCNcKqNqc holds in classical logic. So, you can deduce KqNq, use Nc via conditional introduction, yielding CNcKqNq, and then use CCNcKqNqc and detachment to get "c". The form CCNcKqNqc makes it clear, at least to me, that the contradiction might NOT have arisen from the negation "Nc", but rather some other way (I suggest that contradictions often happen because of a deficiency in care with respect to combinations). I do not believe that obvious to many people and it seems very important to know. –  Doug Spoonwood Sep 12 '13 at 3:22

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

Using natural deduction (cf. van Dalen, Logic and Structure):

1. b⟹¬a Premise
2. a∧b Premise
3. b ∧-Elimination (Right), 2
4. ¬a ⟹-Elimination, 1, 3
5. a ∧-Elimination (Left), 2
6. ⊥ ¬-Elimination, 4, 5
7. c ⊥-Rule
-

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]
-