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.

Prove the following argument is valid (and provide reasons):

  1. ~N v (~B*D)
  2. ~C --> ~D therefore ~(~C*N)

Our work (so far):

  1. ~N v (~B*D)
  2. ~C --> ~D therefore ~(~C*N)
  3. D-->C (contrapositive of 2)
  4. ~N v (~B*C) (substitution 3 into 1)
  5. ~N v ~(B v ~C) (Demorgan's on 4)
  6. (~N v ~B)*(~N v C) (distribute 4)
  7. ~(N*B)*(C v ~N) (demorgan's and commutive on 6)

...

  1. C v ~N
  2. ~(~C*N) (Demorgan's on the previous statement, which is being numbered 1 again even though I gave it number 99)

Line 7 has C v ~N in it, but I can't show that ~(N*B) is true, or that (~Nv~B) in line 6 is true.

This is where I've been for the past 6 hours. Help me out if you can. Thanks.

share|improve this question
1  
Note that in line 7, you have $\not(N\land B)\land (C\lor \sim N$), and you want $C\lor \sim N$. But this is usually an axiom of $\land$, that $x\land y$ implies $y$, or else is easy to prove. Maybe you've just been looking at it too long? –  MJD Jul 3 '12 at 4:02

2 Answers 2

up vote 3 down vote accepted

As you observed, $\sim(\sim C\land N)$ is equivalent to $C\lor\sim N$, by de Morgan's law. So if we prove $C\lor\sim N$, we can use de Morgan's law in reverse to get what we want.

(1) says $\sim N \lor (\sim B\land D)$. So we have two cases to consider: either $\sim N$ is true, or $\sim B\land D$ is true.

In the former case, we have $\sim N$, so we have $C\lor \sim N$ by the addition law, which says that $x$ implies $y\lor x$ for any $y$.

In the latter case, we have $\sim B\land D$, so we have $D$. (2) says $\sim C\to\sim D$, and by the contrapositive law this is equivalent to $D\to C$. Since we have $D$, we can conclude $C$ by detachment, and then $C\lor \sim N$ by addition.

In either case we have $C\lor \sim N$ and we can use de Morgan's law to get $\sim(\sim C \land \sim\sim N)$ and then eliminate the double negative to get $\sim(\sim C \land N)$ , which was what we wanted.

share|improve this answer

Your first 3 steps work out as fine.

The fourth step does work as valid, but not quite as simply as your reasoning indicates... though perhaps that's not all that relevant here.

In many systems, from this "(~(N*B)*(C v ~N))" you can infer (C v ~N) by conjunction elimination. In other words from (x*y) you can infer y.

"Line 7 has C v ~N in it, but I can't show that ~(N*B) is true, or that (~Nv~B) in line 6 is true."

You don't need to. You only need to show that from the two premises given that "~(~C*N)" is valid. Line six consists of a valid formula given the premises, because all other steps leading up to it, and the very last step you gave came as valid. You could show that, given the premises, (~Nv~B) by applying one of De Morgan's laws on the first premise, and then conjunction elimination on that obtained formula.

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.