Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given the following arguments:

$ \tag A (R \to \neg S) \land (T \to \neg U)$

$ \tag B (V\to \neg W) \land (X \to \neg Y)$

$ \tag C (T \to W) \land (U \to S)$

$ \tag D V \lor R $

$$ \therefore \neg T \lor \neg U $$

how to prove this using the standard rules of inference?

share|cite|improve this question

One expects this to follow more or less directly from $(A)$ because $p\to q\iff \neg p \lor q$. However, there is no tertium no datur. One has to find ones luch starting from (D) by case analysis:

By simplification from (A): $$\tag{1}R\to\neg S$$ and $$\tag2 T\to\neg U$$ By simplification from (C): $$\tag{3}T\to W$$ and $$\tag4 U\to S$$ By modus ponens from (1): $$\tag 5R\vdash \neg S$$ By modus tollens from (4) and (5): $$\tag 6 R\vdash \neg U$$ By addition from (6) $$\tag 7 R\vdash \neg T \lor \neg U$$ By decuction theorem from (6): $$\tag 8 R\to (\neg T \lor \neg U)$$ By simplification from (B): $$\tag 9 V\to\neg W$$ By modus ponens from (9): $$\tag{10} V\vdash \neg W$$ By modus tollens from (10) and (3): $$\tag{11}V\vdash \neg T$$ By addition from (11): $$\tag{12}V\vdash \neg T\lor\neg U$$ By deduction theorem from (12) $$\tag{13}V\to( \neg T\lor\neg U)$$ By case analysis from (D), (13) and (8): $$\neg T \lor \neg U_\blacksquare$$

share|cite|improve this answer
Thanks, but I am not accustomed with sequent notation, so I couldn't understand some parts of your solution. Could you please edit it or perhaps suggest me some reference? – Quixotic Oct 25 '12 at 18:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.