0
$\begingroup$

Please help me with showing that the expression $P\land (Q\lor \neg P) \land \neg Q$ is a contradiction? Your help is greatly appreciated

What I have tried so far:

$\begin{align*} &C = \text{contradiction}\\ &\Rightarrow P\land (Q\land \neg Q) \lor (\neg Q\land \neg P)\\ &\Rightarrow P\land C\lor (\neg Q\land \neg P)\\ &\Rightarrow P\land (\neg Q\land \neg P)\\ &\Rightarrow (P\land \neg Q)\land (P\land \neg P)\\ &\Rightarrow (P\land \neg Q) \end{align*}$

  • 1
    @user10695: Make your titles **in$f$ormative**; "help please" is not in$f$ormative. Don't use all caps: it's the network equivalent of **yelling**.2011-05-10

4 Answers 4

0

$P\land (Q\lor \neg P) \land \neg Q$

1)You have a statement of the form $A \land B \land C$, with A=$P$, B=$Q\lor \neg P$, and C=$\neg Q$ , which is true exactly when each of the three statements is true.

For A, C to be true, we must have $P$ is true, and $\neg Q$ is also true, so that Q is false. No problem so far. But we have concluded: 1)P is true. 2)Q is false.

Rewrite now the statement as: ($P \land \neg Q) \land (Q\lor\neg P)$ , and we know that the statement in the first parenthesis is true, so that the one on the right parenthesis must also be true. Show now that $Q\lor\neg P)$ cannot be true, given the choices of truth values for P,Q:

But now we must show that the term $Q\lor \neg P$ cannot be true.

So, when is $Q\lor \neg P$ true? Exactly when either of $Q$ or $\neg P$ is true.

Use 1,2 above to show that , given these truth-value assignments, this statement cannot be true.

2

Notice that $Q \lor \lnot P$ is the negation of $\lnot Q \land P$.

1

The formula $P \land (Q \lor \neg P) \land \neg Q$ is contradictory, consider cases. It is equivalent to one of the following:

  • $P \land Q \land \neg Q$
  • $P \land \neg P \land \neg Q$

and both these formulas contain $X \land \neg X$ which is contradictory.

  • 0
    Thanks. I see the contradiction now. I was throwing it away forgetting the AND there2011-05-10
1

Without any further restrictions on what method you want to use, I give you another way to get to C. Your original formula is

a. P∧(Q∨¬P)∧¬Q

'Simplificating' thrice, applying 'material implication' to (Q ∨ ¬P), and then by Modus Ponens, infer ¬P, and finally (P ∧ ¬P), i.e., C.

All this should be shorter than a Truth Table. Another proof sketch:

'Simplificating' thrice again, applying conmutation to (Q ∨ ¬P), and then 'material implication', MP to the resulting formula, to get Q, and then (Q ∧ ¬Q), i.e., C.

Also shorter than a Truth Table.