I am taking a class on natural deduction for the first time and we are currently on deductive proofs, I am having trouble with this one:

Premise: A
Premise: [(A&B) or (C&D)]
Conclusion: not (C&D) implies (A&B)

I don't know how to start, maybe I need to prove a lemma first, but i am not sure what.

  • Are you sure you copied that right? You can easily prove [~(C&D) -> (A&B)] from the second premise alone. – This lad Jul 4 '14 at 3:17
  • Yes i am sure that is what is written. Unless the i am confusing the implies symbol. In my book it looks like a U flipped so the rounded edge is closest to the (A&B). How do i start on this proof without resorting to truth tables? What laws can i use? – user8363 Jul 4 '14 at 3:24

We're given two premises:

  1. A;

  2. (A ∧ B) ∨ (C ∧ D).

The goal is to assume (1-2) and derive: ¬(C ∧ D) → (A ∧ B). I should start by saying that premise (1) is useless and in what follows we'll simply use premise (2). Here is one strategy you can take. It's pretty system-neutral, so try to implement it in your particular proof system and feel free to ask for further guidance if you're not completely sure how to proceed. Hope you find it helpful and good luck.

Proof. Assume ¬(C ∧ D). Our goal is to get (A ∧ B). Premise (2) tells us that either (A ∧ B) is true or (C ∧ D) is, so we proceed to prove by cases. Assuming the first case: (A ∧ B) immediately gives us (A ∧ B). Assuming (C ∧ D) contradicts our initial assumption ¬(C ∧ D), so we get a contradiction (symbolically: ⊥). Then we eliminate the contradiction, obtaining (A ∧ B). This elimination step is warranted by the fact that in classical logic, from a contradiction anything follows. Since both disjuncts of premise (2) lead to (A ∧ B), we conclude, by disjunction-elimination (aka proof by cases) that (A ∧ B) is true. Since having assumed ¬(C ∧ D) we were able to derive (A ∧ B), we conclude by ∧-introduction (aka direct proof) that ¬(C ∧ D) → (A ∧ B).

  • Are you just allowed to assume part of the conclusion is true like that? – user8363 Jul 4 '14 at 5:09
  • @user8363 In the current context (A and B) is true. In other words, if you assume premise (2) and not(C and D), then (A and B) is true. This does not mean, of course, that you can conclude that (A and B) is true, out of this context. Does that make sense? – Hunan Rostomyan Jul 4 '14 at 6:03
  • not completely, do you mind explaining a little more? Thanks for the help by the way! – user8363 Jul 4 '14 at 6:15
  • @user8363 forget that I said "(A and B) is true". I could just say, "(A and B)". All we need to say is this: (A and B) follows from not(C and D) and premise (2) by the reasoning outlined above. – Hunan Rostomyan Jul 4 '14 at 9:19

The best way to do these exercises is simply to read and understand each premise, as well as the conclusion. If you understand the statements, you will intuitively find how to prove the conclusion. Let's take a look at the following:

  1. A

From the two premises, we know that A is the case (line 1), and we know that either both A and B are the case, or that both C and D are the case (line 2). When you have an EITHER-OR statement, you know that one or the other sides of the OR is the case (and possibly both). This means that if one of the two sides is not the case, the other side must be the case. This allows us to derive some interesting logical entailments. So, now that we understand the meaning of the two premises, let us look at the conclusion we are asked to derive.

Derive: IF NOT-(C AND D), THEN (A AND B)

This says that if C AND D is not the case, then A AND B is the case.

Well, yes, of course! This follows immediately from premise 2. Indeed, when you have an EITHER-OR statement (i.e. a disjunction), by definition one of the two sides must be true. Therefore, if one is false ('C AND D' in this exercise), then the other must be true ('A AND B' here).

So the answer to this exercise is simply to derive the conclusion from line 2, a step you must justify by appeal to the disjunctive syllogism (or disjunction elimination) rule (depending on the textbook you are using in class), applied to line 2.

By the way, premise 1 is useless to derive the desired conclusion. It's just there to mess with your head!


Already knowing the rules of inference helps. No more than three steps are needed. The second premise applies the rule of Material Implication. This states an either or is truly a conditional and vice versa. So premise 2 (a & b) V ( c & d) becomes a conditional with a denied antecedant. In this case we swap positions of the disjunction and THEN use the material implication rule like this ~ (c & d) -> (a & b).

The material implication rule converts conditionals to disjunctions and vice versa. So ANY either . . . OR is truly a conditional and any conditional is an either . . . or. The form is this: p V q is equivalent to ~p -> q. Truth tables confirm ALL inference rules. So knowing the rules is a great help and shortcut to proofs. If you have a conditional then the same rule: p -> q is equivalent to ~p V q. The capital V stands for either . . . OR.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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