Destructive dilemma

Destructive dilemma^[1][2] is the name of a valid rule of inference of propositional logic. It is the inference that, if P implies Q and R implies S and either Q is false or S is false, then either P or R must be false. In sum, if two conditionals are true, but one of their consequents is false, then one of their antecedents has to be false. Destructive dilemma is the disjunctive version of modus tollens. The disjunctive version of modus ponens is the constructive dilemma. The destructive dilemma rule can be stated:

${\displaystyle {\frac {P\to Q,R\to S,\neg Q\lor \neg S}{\therefore \neg P\lor \neg R}}}$

Destructive dilemma

Type	Rule of inference
Field	Propositional calculus
Statement	If ${\displaystyle P}$ implies ${\displaystyle Q}$ and ${\displaystyle R}$ implies ${\displaystyle S}$ and either ${\displaystyle Q}$ is false or ${\displaystyle S}$ is false, then either ${\displaystyle P}$ or ${\displaystyle R}$ must be false.
Symbolic statement	${\displaystyle {\frac {P\to Q,R\to S,\neg Q\lor \neg S}{\therefore \neg P\lor \neg R}}}$

where the rule is that wherever instances of "${\displaystyle P\to Q}$", "${\displaystyle R\to S}$", and "${\displaystyle \neg Q\lor \neg S}$" appear on lines of a proof, "${\displaystyle \neg P\lor \neg R}$" can be placed on a subsequent line.

Formal notation

The destructive dilemma rule may be written in sequent notation:

${\displaystyle (P\to Q),(R\to S),(\neg Q\lor \neg S)\vdash (\neg P\lor \neg R)}$

where ${\displaystyle \vdash }$ is a metalogical symbol meaning that ${\displaystyle \neg P\lor \neg R}$ is a syntactic consequence of ${\displaystyle P\to Q}$, ${\displaystyle R\to S}$, and ${\displaystyle \neg Q\lor \neg S}$ in some logical system;

and expressed as a truth-functional tautology or theorem of propositional logic:

${\displaystyle (((P\to Q)\land (R\to S))\land (\neg Q\lor \neg S))\to (\neg P\lor \neg R)}$

where ${\displaystyle P}$, ${\displaystyle Q}$, ${\displaystyle R}$ and ${\displaystyle S}$ are propositions expressed in some formal system.

Natural language example

If it rains, we will stay inside.

If it is sunny, we will go for a walk.

Either we will not stay inside, or we will not go for a walk, or both.

Therefore, either it will not rain, or it will not be sunny, or both.

Proof

Step	Proposition	Derivation
1	${\displaystyle P\to Q}$	Given
2	${\displaystyle R\to S}$	Given
3	${\displaystyle \neg Q\lor \neg S}$	Given
4	${\displaystyle \neg Q\to \neg P}$	Transposition (1)
5	${\displaystyle \neg S\to \neg R}$	Transposition (2)
6	${\displaystyle (\neg Q\to \neg P)\land (\neg S\to \neg R)}$	Conjunction introduction (4,5)
7	${\displaystyle \neg P\lor \neg R}$	Constructive dilemma (6,3)

Example proof

The validity of this argument structure can be shown by using both conditional proof (CP) and reductio ad absurdum (RAA) in the following way:

1.	${\displaystyle ((P\to Q)\land (R\to S))\land (\neg Q\lor \neg S)}$	(CP assumption)
2.	${\displaystyle (P\to Q)\land (R\to S)}$	(1: simplification)
3.	${\displaystyle P\to Q}$	(2: simplification)
4.	${\displaystyle R\to S}$	(2: simplification)
5.	${\displaystyle \neg Q\lor \neg S}$	(1: simplification)
6.	${\displaystyle \neg (\neg P\lor \neg R)}$	(RAA assumption)
7.	${\displaystyle \neg \neg P\land \neg \neg R}$	(6: De Morgan's Law)
8.	${\displaystyle \neg \neg P}$	(7: simplification)
9.	${\displaystyle \neg \neg R}$	(7: simplification)
10.	${\displaystyle P}$	(8: double negation)
11.	${\displaystyle R}$	(9: double negation)
12.	${\displaystyle Q}$	(3,10: modus ponens)
13.	${\displaystyle S}$	(4,11: modus ponens)
14.	${\displaystyle \neg \neg Q}$	(12: double negation)
15.	${\displaystyle \neg S}$	(5, 14: disjunctive syllogism)
16.	${\displaystyle S\land \neg S}$	(13,15: conjunction)
17.	${\displaystyle \neg P\lor \neg R}$	(6-16: RAA)
18.	${\displaystyle (((P\to Q)\land (R\to S))\land (\neg Q\lor \neg S)))\to \neg P\lor \neg R}$	(1-17: CP)