Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

6 Answers 6

up vote 7 down vote accepted

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.

share|improve this answer
    
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).

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
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
share|improve this answer

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]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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