Proof by contradiction: negation of conjunction

logicproof-writingpropositional-calculus

Consider we have the following statement to prove: $P \implies Q \wedge R$.
For a proof by contradiction, we assume $P \wedge (\neg Q \lor \neg R)$.

How would one go about this? Typically to prove a statement of the form $(A \lor B) \implies C$, we show $A \implies C$ and then $B \implies C$. Do we break down such a proof by contradiction into such cases?

Mainly:

  1. Does it suffice to reach separate contradictions by considering the cases $P \wedge \neg Q$ and $P \wedge \neg R$ separately?

  2. Must one also consider the case when $(P \wedge \neg Q)$ and $(P \wedge \neg R)$ are both assumed to hold "simultaneously"?

Many thanks in advance for your help.

Best Answer

If we want to derive a contradiction (if any) from $P ∧ (¬Q∨¬R)$, we have to consider the two cases forming the equivalent disjunction:

$(P ∧ ¬Q) ∨ ( P ∧ ¬R)$.

See Proof by cases: if we show that $(P∧¬Q)$ implies a contradiction and that $(P∧¬R)$ implies a contradiction, it is done.

Related Question