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.

Hey guys, I'm asked to show the following arguments are valid:

1) $p\rightarrow q$
2) $(q\lor r)\land (\lnot (q\land r))$

Therefore:
3) $\lnot q\rightarrow (\lnot p\land r)$

I know you need to use the rules of inference like modus ponens/converse fallacy but I'm confused because it doesn't look like any of the forms I've learned about?

Thanks

[Edit: corrected parentheses in line 3]

share|improve this question
1  
If $p$ implies $q$ and exactly one of $q$ and $r$ is true, then the failure of $q$ implies that $p$ is false and $r$ is true. It's obvious, isn't it? –  Christian Blatter Apr 29 '11 at 8:21
    
Hmm yes so the second statement says either q or r but not both. Now that you mention it like that I'm thinking about the second statement differently and it's much clearer, thanks! –  Arvin Apr 29 '11 at 8:47
add comment

3 Answers

Ross has provided most of the "machinery" you need to be able to prove the "Therefore..." part of your problem.

Premises:

1) $p\rightarrow q$

2) $(q\lor r)\land (\lnot (q\land r))$

3) $(q\lor r)$ (2)
4) $\lnot (q\land r)$ (2)
5) $\lnot q\lor \lnot r$ DeMorgan (4)
6) $\lnot q $ (Assumption)
7) $\ r (3, 6)$
8) $\lnot p$ (1, 6) modus tollens
9) $\lnot p \land r$ (7, 8)
10) $\lnot q \rightarrow (\lnot p \land r)$ (6 - 9)

Note that lines 6 - 9 is a subproof, of sorts. Assuming ~q in line 6, together with earlier premises and derivations, we derive ($\lnot$p $\land$ r). That allows you to conclude that IF ($\lnot$q) is true, then it follows that ($\lnot$p $\land$ r). That is, you have proven line 10.

Now your work is to provide the justification (which rules of inferences, or logical equivalences justify each step.) I mentioned a couple justifications, but I think you might be better able now to recognize the rules used in each step. For example, what is the rule that allows you to take the premise (A $\land$ B) to conclude A, (likewise you can conclude B). What is the rule that tells you that if you have A $\lor$ B, and another statement $\lnot$A, that you can conclude B?

share|improve this answer
    
It's Modus Tollens, right? Also, I think I understand it a lot better now, however there is just one part in your working I'm still a bit confused about which is part 7. How do you get r? by (3): $(q \lor r)$ and assuming $\lnot q$ does it mean $q$ is false and so (3) becomes $(F \lor r)$ or something? –  Arvin Apr 29 '11 at 7:07
    
Modus Tollens is what justifies step number 8: $p\rightarrow q$ plus $\lnot q$. My last question was asking you for the rule for which justifies step 7: yes, assuming $\lnot q$, and given q $\lor$ r, means that since (by assumption) q is false, then for step 3 to be true, it must follow that r. Sometimes it's called "or Elemination", but I learned it as "Disjunctive Syllogism"...The name for the rule is less important than understanding what it means. –  amWhy Apr 29 '11 at 12:40
add comment

Hint: If you unpack the two parts of 2), use DeMorgan's law on the second, then assume $ \lnot q$, you should be able to derive $(\lnot p)\land r$

share|improve this answer
    
Hmm right, so the DeMorgan of the second part of (2) would be $\lnot q \land \lnot r$ and if you assume $\lnot q$ you can assume $\lnot p$ right? but I dont get how you can use the second part to derive $(\lnot p)\land r$ –  Arvin Apr 29 '11 at 1:52
    
No, DeMorgan of the second part is $\lnot q \lor \lnot r$-you have to change or/and. Yes, assuming $\lnot q$ you can derive (not assume) $\lnot p$. And the $\lnot q$ in conjunction with the first clause of 2) should get you $r$. By the way, I meant you assume $\lnot q$. You caught it, and I have corrected the original response. –  Ross Millikan Apr 29 '11 at 1:58
    
So by (1), $\lnot q \rightarrow \lnot p$ and by (2) $\lnot q \rightarrow r$? So we can combine it to say $\lnot q \rightarrow \lnot p \land r$? –  Arvin Apr 29 '11 at 2:21
1  
Yes, the way I was taught to write these proofs, you assume $\lnot q$, then having proven $\lnot p$ and $r$ you should have a rule to make $\lnot p \land r$, then you can derive $\lnot q \rightarrow (\lnot p \land r)$. –  Ross Millikan Apr 29 '11 at 2:56
add comment

A slightly different approach: you need to show you cannot make an assignment of truth values to the component/atomic sentences that simultaneously make your premises true and your conclusions false. Then consider all assignments of component sentences that falsify your conclusion ( if there is no such assignment, your statement is a tautology), then check that any of these assignments to the premise sentences cannot return you a truth value T:

So we need to falsify:

3) ¬q→(¬p∧r)

first,

So we need the assignments: i)q:=F and (¬p∧r):=F , so one of the two is false, and r is true, so we have:

i.1) q:=F p:=F/T r:=F

or: i.2) q:=F p:=T r:=F/T

Are the only assignments that falsify the conclusion. We now need to check that this assignment on the antecedent does not give a truth value T

So we check: 1) p→q 2) (q∨r)∧(¬(q∧r))

i.1) returns false, since q,r are both false, then (q∨r) is false, and the conjunction of the three is false.

For i.2): We also get a false, because if p is true and q is false, then p->q is false. Again, the conjunction is false, and we conclude the argument is valid, i.e., that there is no assignment of truth values to the component sentences that makes the premises true and the conclusions false.

share|improve this answer
add comment

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.