Prove ′⋀(⋁)→ - How?

Question

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.

Answer 1

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$

Answer 2

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$

Answer 3

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$

Answer 4

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}$$