Proving the Conclusion

Question

Derivations 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,.

Answer 1

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
------
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.

Answer 2

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 
   

QED.

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.

Answer 3

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)

Becomes:

(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.