Editing Destructive dilemma

{{Short description|Rule of inference of propositional logic}}
{{Infobox mathematical statement
| name = Destructive dilemma
| type = [[Rule of inference]]
| field = [[Propositional calculus]]
| statement = If <math>P</math> implies <math>Q</math> and <math>R</math> implies <math>S</math> and either <math>Q</math> is false or <math>S</math> is false, then either <math>P</math> or <math>R</math> must be false.
| symbolic statement = <math>\frac{P \to Q, R \to S, \neg Q \lor \neg S}{\therefore \neg P \lor \neg R}</math>
}}
{{Transformation rules}}

'''Destructive dilemma'''<ref>Hurley, Patrick. A Concise Introduction to Logic With Ilrn Printed Access Card. Wadsworth Pub Co, 2008. Page 361</ref><ref>Moore and Parker</ref> is the name of a [[Validity (logic)|valid]] [[rule of inference]] of [[propositional calculus|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 [[material conditional|conditionals]] are true, but one of their [[consequent]]s is false, then one of their [[Antecedent (logic)|antecedent]]s has to be false. ''Destructive dilemma'' is the [[Logical disjunction|disjunctive]] version of ''[[modus tollens]]''. The disjunctive version of ''[[modus ponens]]'' is the [[constructive dilemma]]. The destructive dilemma rule can be stated:

:<math>\frac{P \to Q, R \to S, \neg Q \lor \neg S}{\therefore \neg P \lor \neg R}</math>

where the rule is that wherever instances of "<math>P \to Q</math>", "<math>R \to S</math>", and "<math>\neg Q \lor \neg S</math>" appear on lines of a proof, "<math>\neg P \lor \neg R</math>" can be placed on a subsequent line.

==Formal notation==
The ''destructive dilemma'' rule may be written in [[sequent]] notation:

: <math>(P \to Q), (R \to S), (\neg Q \lor \neg S) \vdash (\neg P \lor \neg R)</math>

where <math>\vdash</math> is a [[metalogic]]al symbol meaning that <math>\neg P \lor  \neg R</math> is a [[logical consequence|syntactic consequence]] of <math>P \to Q</math>, <math>R \to S</math>, and <math>\neg Q \lor \neg S</math> in some [[formal system|logical system]];

and expressed as a truth-functional [[tautology (logic)|tautology]] or [[theorem]] of propositional logic:

:<math>(((P \to Q) \land (R \to S)) \land (\neg Q \lor \neg S)) \to (\neg P \lor \neg R)</math>

where <math>P</math>, <math>Q</math>, <math>R</math> and <math>S</math> 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==
{| class="wikitable"
! ''Step''
! ''Proposition''
! ''Derivation''
|-
|1|| <math>P \to Q</math> || Given
|-
|2|| <math>R \to S</math> || Given
|-
|3|| <math>\neg Q \lor \neg S</math> || Given
|-
|4|| <math>\neg Q \to \neg P</math> || [[Transposition (logic)|Transposition]] (1)
|-
|5|| <math>\neg S \to \neg R</math> || Transposition (2)
|-
|6|| <math>(\neg Q \to \neg P) \land (\neg S \to \neg R)</math> || [[Conjunction introduction]] (4,5)
|-
|7|| <math>\neg P \lor \neg R</math> || [[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:

{|
|-
|align=right| 1. || <math>((P\to Q)\and (R\to S))\and(\neg Q\or\neg S)</math> || (CP assumption)
|-
|align=right| 2. || <math>(P\to Q)\and(R\to S)</math> || (1: simplification)
|-
|align=right| 3. || <math>P\to Q</math> || (2: simplification)
|-
|align=right| 4. || <math>R\to S</math> || (2: simplification)
|-
|align=right| 5. || <math>\neg Q\or\neg S</math> || (1: simplification)
|-
|align=right| 6. || <math>\neg(\neg P\or\neg R)</math> || (RAA assumption)
|-
|align=right| 7. || <math>\neg\neg P\and\neg\neg R</math> || (6: [[De Morgan's Law]])
|-
|align=right| 8. || <math>\neg\neg P</math> || (7: simplification)
|-
|align=right| 9. || <math>\neg\neg R</math> || (7: simplification)
|-
|align=right| 10. || <math>P</math>|| (8: [[double negation]])
|-
|align=right| 11. || <math>R</math>|| (9: double negation)
|-
|align=right| 12. || <math>Q</math>|| (3,10: modus ponens)
|-
|align=right| 13. || <math>S</math>|| (4,11: modus ponens)
|-
|align=right| 14. || <math>\neg\neg Q</math> || (12: double negation)
|-
|align=right| 15. || <math>\neg S</math> || (5, 14: [[disjunctive syllogism]])
|-
|align=right| 16. || <math>S\and\neg S</math> || (13,15: [[Logical conjunction|conjunction]])
|-
|align=right| 17. || <math>\neg P\or\neg R</math> || (6-16: RAA)
|-
|align=right|
|-
|align=right| 18. || <math>(((P\to Q)\and(R\to S))\and(\neg Q\or\neg S)))\to\neg P\or\neg R</math> || (1-17: CP)
|}

==References==
{{reflist}}

== Bibliography ==
* Howard-Snyder, Frances; Howard-Snyder, Daniel; Wasserman, Ryan. The Power of Logic (4th ed.). McGraw-Hill, 2009, {{ISBN|978-0-07-340737-1}}, p. 414.

==External links==
*http://mathworld.wolfram.com/DestructiveDilemma.html

{{DEFAULTSORT:Destructive Dilemma}}
[[Category:Rules of inference]]
[[Category:Dilemmas]]
[[Category:Theorems in propositional logic]]