1
$\begingroup$

I'm going a course in computer science math, and I came across an exercise that is the following:

Use the rules of equivalence and/or inference to prove:

$\lnot P \land (P \lor Q)\rightarrow Q$

Now, I hate to ask for help, but I have no idea how to derive anything from this, even though I have a cheat sheet for all the equivalence and inference rules in the course.

I tried to solve it with:

  1. $\lnot P \land (P \lor Q)\rightarrow Q$ (initial statement)
  2. $(\lnot P, P \lor Q)\rightarrow Q$ (simplification)
  3. $Q \rightarrow Q$ (disjunctive syllogism)

But this seems wrong. Does anyone else have a clue on which rules to apply for this? Thank you.

$\endgroup$
1
$\begingroup$

First of all, it is probably a good idea to add parentheses to avoid any kind of ambiguity. So, I would write $\lnot P \land (P \lor Q)\rightarrow Q$ as $(\lnot P \land (P \lor Q))\rightarrow Q$

Second:

I tried to solve it with:

  1. $\lnot P \land (P \lor Q)\rightarrow Q$ (initial statement)
  2. $(\lnot P, P \lor Q)\rightarrow Q$ (simplification)
  3. $Q \rightarrow Q$ (disjunctive syllogism)

But this seems wrong.

You are correct that your proof does not work. You can never apply inference rules to components of a statement; you can apply inference rules only to whole statements.

For example, Simplification states that from $P \land Q$ you can infer $P$. However, if I apply this to $(P \land Q) \rightarrow R$, and try to infer $P \rightarrow R$, something goes horribly wrong. Consider: $P$: you are an adult male, $Q$: you are unmarried, $R$: you are a bachelor. With this the statement $(P \land Q) \rightarrow R$ is true, but clearly $P \rightarrow R$ is false!

On the other hand, equivalence rules can be applied to component statements.

Third, come up with a 'proof plan'. Now, if you ever need to prove a conditional, $99$ times out of a $100$ you should do a Conditional Proof: Assume the 'if' part, and try to get to the 'then' part. So, the proof 'skeleton' or 'proof plan' will be:

$1. \lnot P \land (P \lor Q) \text{ Assumption}$

...

$n. Q$

$n+1. (\lnot P \land (P \lor Q))\rightarrow Q \text{ Conditional Proof } 1-n$

Finally, let's do this!

$1. \lnot P \land (P \lor Q) \text{ Assumption}$

$2. \lnot P \quad \text{ Simplification } 1$

$3. P \lor Q \quad \text{ Simplification } 1$

$4. Q \quad \text{ Disjunctive Syllogism } 2,3 $

$5. (\lnot P \land (P \lor Q))\rightarrow Q \text{ Conditional Proof } 1-4$

$\endgroup$
  • $\begingroup$ Thank you, something new I've learned today! $\endgroup$ – tobulos1 Sep 5 '17 at 5:29
  • $\begingroup$ @tobulos1 You're welcome! $\endgroup$ – Bram28 Sep 5 '17 at 12:37
1
$\begingroup$

De Morgan's property helps: $\lnot P \land (P \lor Q) \equiv (\lnot P \land P)\lor(\lnot P \land Q)\equiv \lnot P \land Q\to Q$

$\endgroup$
  • $\begingroup$ I'm sorry, I must be slow tonight. Could you explain how $\lnot P \land P$? How did that happen? $\endgroup$ – tobulos1 Sep 4 '17 at 18:44
  • $\begingroup$ Its there due to De Morgan's law. And its truth value is $0$ or $F$ ( false ). My logic knowledge is rusty too, so I gave whatever I had here... $\endgroup$ – DeepSea Sep 4 '17 at 18:45
  • $\begingroup$ @tobulos1 It is due to distribution: $A\wedge(B\vee C) ~\iff ~(A\wedge B)\vee (A\wedge C)$.$$\neg P\wedge(P\vee Q) ~{~\iff~ (\neg P\wedge P)\vee (\neg P\wedge Q) \\~\iff~\neg P\wedge Q \\~\implies Q}$$ $\endgroup$ – Graham Kemp Sep 5 '17 at 0:48
1
$\begingroup$

Starting assumption: $$\lnot P \land (P \lor Q)$$ Using distributive law is equivallent to: $$(\lnot P \land P) \lor (\lnot P \land Q)$$ Since $\lnot P \land P$ is false, is equivallent to: $$(\lnot P \land Q)$$ By weakening the conjunction, it implies: $$Q$$ Therefore by discharging the assumption: $\lnot P \land (P \lor Q) \rightarrow Q$

$\endgroup$
0
$\begingroup$

Indeed.   To prove: $(\neg P\wedge(P\vee Q))\to Q$, it suffices to show $\{\neg P, P\vee Q\} \vdash Q$ , which is the very form of a disjunctive syllogism, a valid rule of inference*, so we are done.

  • But that is not quite what you claimed. You had the idea, not the form.

(* in classical and intuitionistic systems.)

To drill down a bit more:

$$\begin{array}{l:ll}\hdashline \quad 1 & \neg P\wedge (P\vee Q) & &\text{Assume }\neg P\wedge (P\vee Q) \\ \quad 2 & \neg P &1, \wedge\mathsf E&\textrm{Simplification}\\ \quad 3 & P\vee Q & 1, \wedge\mathsf E&\textrm{Simplification} \\ \quad 4 & Q & 2,3,\vee\mathsf E&\textrm{Disjunctive Syllogism} \\ \hline \blacksquare & (\neg P\wedge (P\vee Q))\to Q & 1,4,\to\mathsf I & \text{Discharge }\neg P\wedge (P\vee Q) \end{array}$$

$\endgroup$

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.