enter image description hereDerivations Prove that the following arguments are valid.ANSWSER IS POSTED

  1. (Q → ¬P), (¬Q → ¬P) ⊢ ¬P

notes: ⊢ stands for the conclusion. so basically, I am trying to prove how -P is a true/proper conclusion for (Q → ¬P), (¬Q → ¬P). To do this, I know inference rules need to be used, like MP, MTP, ADJ, ADD, DN, etc,.

  • Maybe the issue is with the "etc" in the list of rules... See Disjunction elimination Jul 1 at 12:54
  • Are you in a math class or a philosophy class. Each one may teach slightly different. Logic is not just logic where it is all the same thing. There are distinct kinds that are not the same. Textbooks also may differ on the inference rules you are allowed to use. Furthermore math uses different terminology on some of the same rules that philosophy uses: I.e., contraposition in math = transposition in philosophy. What did you try? You need to try something and fail and ask where you went wrong. The proof for this can consist of using four inference rules to get to ~P
    – Logikal
    Jul 1 at 12:57
  • @MauroALLEGRANZA and Logikal You say that there are limitations on the number of rules that are allowed, but does that actually effect the realm of possibilities that you're operating in, so is it a different math or is that more of a practice thing, making it either easier by not overwhelming with options or harder because you have to derive higher level options yourself?
    – haxor789
    Jul 1 at 13:25
  • 1
    got the answer. posting it on the question Jul 2 at 4:12
  • 1
    In logic there're many different systems using different rules/axioms such as yours, natural deduction (Fitch nested column style + Gentzen tree style), and Hilbert axiomatic system with MP as the only inference rule. But whatever system you use, the basic trick is same. In this case it is proof by negation as the old saying goes: To speak of the false is to reveal the true... Jul 2 at 4:40

3 Answers 3


There's more than one way to skin this cat. If you are using Fitch rules, then you have a direct proof using the following rule of disjunction elimination:

A v B
A ⊢ C
B ⊢ C

So, just prove Q v ¬Q, then assume Q and prove ¬P by modus ponens, then assume ¬Q and prove ¬P by modus ponens, and then use the Fitch rule of disjunction elimination.

Or, if you prefer, you can use an indirect proof by assuming P, then prove ¬Q by modus tollens, then prove Q by modus tollens, and hence since your assumption of P proves a contradiction, you have ¬P by reductio.


One must know what inference rules are in play. This is super important to the proof. I will name Copi rules one can use to solve with zero assumptions.

  1.   (Q -> ~P) [Premise 1]
  2.   (~Q  -> ~P)  [Premise 2]        / therefore   ~P [Conclusion]
  3.   ***.                 Line 2 Transposition 
  4.   ***.                 Lines 1, 4 Hypothetical syllogism 
  5.   ***.                 Line 5.  Material Implication
  6.    ****.               Line 6.  Tautology 


Proof done. The conclusion does not belong on another line.* The conclusion appears offset on the same line as the final premise. This is the proper format which is easy to read. All of the work below the premises should be the problem solver's work and that work is identified by this format. If anything goes wrong below line 2 then the problem solver is at fault (in this case ME). The format separates what was actually given by someone else and the work of the person solving the problem displays. That is an important distinction to make for accountability.

I did not show the work of course because this is about UNDERSTANDING a what we are doing not just getting the problem correct for homework, quiz, etc.

In all your getting get understanding.

Do not just memorize and fake your way through a course. If you were allowed to use the rules I mentioned the work should be easy.

If you are using natural deduction rules others have shown paths you can take.

I showed the Copi rules and how they differ and can get the same conclusion with zero axioms or assumptions.


I guess on stackoverflow you'd get closed for asking homework questions but as I couldn't find rules against that (yet, correct me if I'm wrong), let's do this logical sudoku real quick:

Assuming that this operator ⊢ stand for equality of tautology or something like that https://en.wikipedia.org/wiki/Logical_connective

Now validity of a statement means that if the premises were true the conclusion must also be true. So it's essentially: Premise1∧Premise2 → Conclusion.

((Q → ¬P) ∧ (¬Q → ¬P)) → ¬P

Now you can apply a Simplification of disjunctive antecedents (* see proof of why that can be applied further down in this answer)

((Q ∨ ¬Q) → ¬P) → ¬P

Now (Q ∨ ¬Q) is obviously true, so there's no harm done adding another true statement with an and due to the fact that True And Statement would still obviously have the same truth value as the statement itself.

(Q ∨ ¬Q) ∧ ((Q ∨ ¬Q) → ¬P) → ¬P

Now if we look closely at this we could see that his is modus ponens and therefore a tautology. Which can be made more clear by replacing (Q ∨ ¬Q) with idk a symbol R of the same truth value:

R ∧ (R → ¬P) → ¬P

Where as said R ∧ (R → ¬P) is ¬P due to MP, which concludes this proof.

And for the other one (that is now no longer part of the question, but was when this answer was written...): (Q → ¬R), (¬P → R) ⊢ (¬P → ¬Q)

One can use the Contraposition A → B = ¬B → ¬A. So:

(Q → ¬R) ∧ (¬P → R) → (¬P → ¬Q)


(R → ¬Q) ∧ (¬P → R) → (¬P → ¬Q)

And from there it follows from the transitive property of the Material conditional that ¬P → ¬Q at which it again follows from itself which also concludes that it's valid.

So you should obviously look up what was done and why you are allowed to do that ;)

Update: A practice problem to study is still a home work ;)

Proof that you can rephrase SDA in terms of the copi rules (assuming those are your constraints) Anyway well you need to rephrase these logical operations in terms of your equivalence and interference rules:

So for example you'd need to show that (A ∨ B) → C is the same as A → C ∧ B → C : So here you would apply imp to get:

¬(A ∨ B) ∨ C

From there you would apply De Morgan to the parenthesis:

(¬A ∧ ¬B) ∨ C

Assuming that the distributive law which isn't listed in the previous list but in this one: https://en.wikipedia.org/wiki/Propositional_calculus

Is part of the derivation laws. You can write that as:

(¬A ∨ C) ∧ (¬B ∨ C)

Which if you can interpret as two imp statements connected with an AND:

(A → C) ∧ (B → C)

So the Simplification of disjunctive antecedents can indeed be applied even with the derivation laws of the propositional logic. Though you'd go the other way around, but as these are equivalence relations that shouldn't be a problem. I leave it to your practice to fit that into the right form or was that your problem?

For the Contraposition there's a nice simple proof on Wikipedia: https://en.wikipedia.org/wiki/Contraposition#Simple_proof_by_definition_of_a_conditional

which should suffice the derivation rules.

And the transitive relation in proposition logic is apparently called Hypothetical syllogism which also has a prove written in the formal language.

  • It isn't homework, it is a practice problem for studying. Also, this isn't the format that I am looking for, but I appreciate your response! Jul 1 at 11:00
  • Updated my post. Not in formal logic but that shouldn't be too hard from there.
    – haxor789
    Jul 1 at 12:41
  • The goal was to get ~p. You do not show that. You show SDA follows. By the way which textbook would you think shows SDA as an inference rule? I would venture to say zero. I am glad you broke down SDA using some common inference rules used in actual textbooks but SDA was not what was to be proved. It looks like you took the conclusion to be part of each premise and then you tried to prove it. Where did you learn that? What textbooks teach the method you used? Or did you just Google this?
    – Logikal
    Jul 1 at 12:49
  • @Logikal Apparently SDA is called "Disjunction Elimination" and my proof actually gets you to ¬P after applying SDA/DE and Modus Ponen or mp. And yes I'm more familiar with the boolean algebra than the proposition logic, but they're not doing something inherently different by calling it different names... And what matters is the logic not the nomenclature. And if there's no consistency in textbooks then that's doubly important.
    – haxor789
    Jul 1 at 13:21
  • @haxor789 No disjunctive elimination is very different from SDA conceptually. They are not identical but perhaps they get you to the same place. The method is super important. Most systems use a Fitch style proof method. You can Google that to see what it looks like. The competition is the Gentzen style proof system which you can also Google. The reasoning you do is not reliable because you get the conclusion— the thing is can you do it all the time with 100 percent accuracy? So getting the answer correct is not the main goal. Is the method reliable IS.
    – Logikal
    Jul 1 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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