Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
What have you tried so far? (hint: try a truth table) –  a little don 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
1  
@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

4 Answers 4

up vote 1 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.