4
$\begingroup$

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]

  • 0
    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!2011-04-29

3 Answers 3

6

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?

  • 0
    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.2011-04-29
4

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$

  • 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)$.2011-04-29
1

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.