# Showing a propositional formula is a contradiction

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

-
What have you tried so far? (hint: try a truth table) –  futurebird May 10 '11 at 22:25
I added what I have but I don't believe it is correct since the question states that it is supposed to be a contradiction –  user10695 May 10 '11 at 22:32
@user10695: Make your titles informative; "help please" is not informative. Don't use all caps: it's the network equivalent of yelling. –  Arturo Magidin May 10 '11 at 23:27

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.

-
Thanks. I see the contradiction now. I was throwing it away forgetting the AND there –  user10695 May 10 '11 at 23:03

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

-

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.

-

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

-