# Proof by contradiction: negation of conjunction

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"?

• If you want to derive a contradiction (if any) from $P \wedge (\neg Q \lor \neg R)$, you have to consider the two cases forming the disjunction. – Mauro ALLEGRANZA Jan 26 '20 at 9:54
• @MauroALLEGRANZA, yes that I know - I meant it 'loosely' i.e. in the context of the proof technique. Thank you for pointing it out - removed the sentence for clarity. – Xandru Mifsud Jan 26 '20 at 9:55
• @MauroALLEGRANZA, so if I understood correctly, you first show contradiction of $P \wedge \neg Q$ independent of $P \wedge \neg R$, and then similarly for $P \wedge \neg R$ independent of $P \wedge \neg Q$. – Xandru Mifsud Jan 26 '20 at 9:57
• See Proof by cases: if you show that (P∧¬Q) implies a contra and that (P∧¬R) implies a contra, it is fine. – Mauro ALLEGRANZA Jan 26 '20 at 9:58
• Thanks @MauroALLEGRANZA, your last comment clarifies the matter for me. Please, how can I mark it as solved by you? – Xandru Mifsud Jan 26 '20 at 10:00

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.
• @BenW --- NO. Se the Wiki entry regarding Didjunction Elim linked above: if we have $P \to R$ and $\to R$, we can conclude that $R$ follows from $P \lor Q$. – Mauro ALLEGRANZA Jan 28 '20 at 20:18