Proof By Contradiction logical argument

Question

$(p \to q) \land (q \to (r \land s)) \land (\neg r \lor (\neg t \lor u)) \land (p \land t) \to u$

I am supposed to prove the valid argument above using Proof by Contradiction and so far I cant seem to find any samples on how to d it :( Please help :"(

Answer 1

To prove something by contradiction, assume

• All the assumptions
• The negation of the conclusion

For example, in your problem, the assumptions are:

1. $p \to q$
2. $(q \to (r \land s))$
3. $(\neg r \lor (\neg t \lor u))$
4. $p$
5. $t$

The conclusion is:

1. $u$

Hence we begin the problem by assuming toward a contradiction that the following are true

1. $p \to q$
2. $(q \to (r \land s))$
3. $(\neg r \lor (\neg t \lor u))$
4. $p$
5. $t$
6. $\neg u$

Now just start arguing logically until you hit a contradiction.

For example, you could write

7. $q$ [Since $p$ is true by (4), we deduce $q$ by (1).]

Just keep building an argument like this until you finish. You may have to break into cases to deal with (3). As in:

"By (3), there are two cases. In case A, we have that $\neg r$. In case B, we have $\neg t \vee u$. Let us now consider case A..."

Your goal is to deduce a contradiction in all cases. Hence every case you consider has to end in the word "contradiction".

Answer 2

A proof by contradiction means

• assume that the statement does not hold,
• from this assumption derive a contradiction ($\bot$),
• conclude that the assumption must have been wrong and the statement does indeed hold.

An implication $\phi \to \psi$ is true iff

under all the assignments where the antecedent $\phi$ is true, the succedent $\psi$ is true as well

which is equivalent to stating

there is no assignment such that the antecedent $\phi$ is true but the succedent $\psi$ is false

So if you want to prove the truth of an implication by contradiction,

• start with assuming the negation of the implication, that this, you assume that

  there is an assignment such that the antecendent is true and the succedent is false

• from this assumption you then derive a contradiction,

• conclude that the assumption must have been wrong, and hence that there can indeed be no assignment which makes the antecedent true but the succedent false, hence the implication must hold.

Applied to your example, that means

• assume that the antecedent $(p \to q) \land (q \to (r \land s)) \land (\neg r \lor (\neg t \lor u)) \land (p \land t)$ is true and
• that the succedent $u$ is false, i.e. assume $\neg u$,
• derive a contradiction $\bot$,
• conclude that the assumption $\neg u$ must have been wrong, and that the succedent $u$ is indeed true if the antecendent $(p \to q) \land (q \to (r \land s)) \land (\neg r \lor (\neg t \lor u)) \land (p \land t)$ is true, hence the implication $(p \to q) \land (q \to (r \land s)) \land (\neg r \lor (\neg t \lor u)) \land (p \land t) \to u$ must hold.