0

I am trying to prove this equation can anyone help?

rosa_melano
  • 35
  • 2
  • 2
    What proof system are you working in? What inference rules do you have? – ayylien Mar 12 '24 at 20:52
  • 2
    Assume Q and derive a contradiction. – Mauro ALLEGRANZA Mar 12 '24 at 21:35
  • Isn't there something missing? Like you can write P->Q as it's only possible outcomes which are either "Q (if P is true) OR not P (if P is false)". And if you negate that you have P OR not Q but there's no reason why it should be not Q instead of P. – haxor789 Mar 13 '24 at 09:36
  • @haxor789 Nothing is missing. Mauro is correct. Just assume Q; derive P → Q; then you have a contradiction, so you can discharge your assumption and introduce ¬Q. – Bumble Mar 13 '24 at 15:37
  • @Bumble I unfortunately don't have the time now but I have no idea how you would do that, mind to give a source for that? – haxor789 Mar 13 '24 at 15:51
  • 1
    In classical natural deduction, going from Q to P → Q (where → is the material conditional) is just a matter of assuming P, reiterating Q and discharging the assumption P. – Bumble Mar 13 '24 at 17:02
  • 1
    Depends on the exact system, but if I were to assume standard propositional calculus, then it seems that rewriting P-->Q as (not(P))or(Q) and then use De Morgan's laws for the outer negation will give you what you want. – Joseph_Kopp Mar 13 '24 at 19:39
  • @haxor789 You chose the approach most others chose here - De Morgan’s law - but you forgot to switch OR to AND. Your conclusion should have been P AND NOT Q. – Julius Hamilton Mar 14 '24 at 04:20
  • @Bumble My problem was apparently that I didn't know the ⊢ operator and assumed it's some sort of equivalence, but apparently you can just assume the left side to be true. So you reformulate P → Q as ⌐P v Q and ⌐(⌐P v Q) by de Morgans law as P ∧ ⌐Q where if you are allowed to just assume that to be true, both parts must be true for that to be the case and so obviously P and ⌐Q could be derived from that. But you need this assumption of being true because it doesn't follow that the value of ⌐Q is the same as P ∧ ⌐Q because if it were false e.g. ⌐P then ⌐Q would be indeterminable. – haxor789 Mar 14 '24 at 12:09
  • @Bumble Though with regards to your own approach, I'm still a little puzzled how you go about things here. Sure if Q is true, then I can derive Q ⊢ Q v ⌐P as Q is already true and so the value of ⌐P is adding irrelevant fluff and I can then rephrase that as Q v ⌐P ⊢ P→Q But how do I go from here? How do you add the negation or eliminate stuff and isn't that moving backwards? – haxor789 Mar 14 '24 at 12:38
  • @haxor789 I will research this but I am pretty sure in the natural deduction proof system, “P→Q“ does not translate to “Q v ⌐P”. I am going to look up the exact rules of natural deduction proof, but I think it’s quite a different way to think about logic than what some of us are used to, that is, basic symbolic manipulation, substitution, etc. I believe natural deduction is more comparable to an older idea of logic where the symbols actually try to spell out valid principles of mental reasoning. For this reason I think it could count as “intuitionistic”. – Julius Hamilton Mar 14 '24 at 15:42
  • 1
    Each of P and Q can be either T or F (true or false). The three cases of T → T, F → T, and F → F are all true implications. But since P → Q is false, the only possibility left is T → F, or in other words P is T and Q is F. Hence this implies Q is false. – Daniel Asimov Mar 14 '24 at 20:23
  • @JuliusH. From what I can see, as long as you stay neatly boolean, these systems are all functionally complete so they reach the same end point and can be morphed into each other. What they differ is the starting point where axioms systems use axioms and a limited set of inference rules, while natural systems use no axioms and a long list of inference: rules https://en.wikipedia.org/wiki/Propositional_calculus but afaik you could derive the inference rules from the axioms and build the axioms via the inference rules etc. – haxor789 Mar 15 '24 at 14:18
  • Only a further comment to be added to this messy debate: the result is intuitionistically valid, i.e. it is not restricted to so-called Classical Logic because the proof nowhere uses LEM or some of its equivalents, like DN. THis means that the proof does not presuppose the classical equivalence of (P → Q) with (¬P ∨ Q). – Mauro ALLEGRANZA Mar 18 '24 at 07:56

3 Answers3

4

Since I have made several comments both on the question itself and the answers to it, and I have been asked for further feedback, here is a longer response.

The question is asking how to prove ¬Q from ¬(P → Q). The turnstile ⊢ can be read as: syntactically proves or entails. The question does not specify any particular logic, but since classical logic is the most commonly used logic, and within classical logic → usually refers to the material conditional it is reasonable to assume that these are intended. The question also does not specify which deductive system is to be used to formulate the derivation. If I am given the choice I will assume a Fitch style natural deduction system, though of course there are many others.

With these assumptions in place we can formulate the derivation as follows:

1. ¬(P → Q)          Given premise
2. |  Q              Assumption 
3. |  |  P           Assumption
4. |  |  Q           From 2, reiteration
5. |  P → Q          From 3, 4, conditional proof, discharging the assumption P
6. |  ¬(P → Q)       From 1, reiteration
7. |  ⊥              From 5, 6, by ⊥-introduction (we have a contradiction) 
8. ¬Q                From 2, 7, by ¬-introduction (reductio ad contradictionem)

Since the question is obviously a logic exercise, that is an answer. However, as the other responses to this question have pointed out, the material conditional does not really do a good job of representing the meaning of "if-then" in English and other natural language contexts, so this merits some explanation.

The material conditional is highly useful within formal logic and it plays an indispensable role within classical logic. It can be defined in several different ways that are provably equivalent. It is the connective that is introduced by the rule of conditional proof and eliminated by modus ponens. Using rewrite rules, (P → Q) is equivalent to (¬P ∨ Q) and also ¬(P ∧ ¬Q). It can also be defined by a truth table:

P  Q  P → Q
T  T    T
T  F    F
F  T    T
F  F    T

However, this does not make it the only formal way to represent a conditional in logic. The material conditional functions as a conditional under three assumptions:

  1. It is bivalent. It has a truth value and its truth value is always one of two possibilities, usually taken to be true and false.
  2. It is dyadic. It is a function in two variables only. There is no place for background information, side premises, or context.
  3. It is a truth function. Its truth value depends only on the truth values of its operands. It does not depend on any other properties of its operands, nor on any connection between them.

These assumptions are fine for many purposes, but they fail to hold when representing many kinds of conditionals. As a result, there are several other accounts of conditionals and their logics.

There are many non-classical logics, e.g. intuitionistic logic, relevance logics, many-valued logics, linear logic, probabilistic logics, substructural logics, connexive logics, etc., that have their own conditionals that differ from the classical material conditional.

There are conditionals that can be defined over an underlying classical logic that are stronger, in the sense of more restrictive, than the material conditional. These do not obey the rule of conditional proof without restrictions. This includes the strict conditional of modal logics, Stalnaker's variably strict conditional, David Lewis' counterfactual conditional, Ernest Adams' probabilistic conditional and many others.

The logic of conditionals has been studied extensively, especially from the late 1960s onwards. The literature on the subject is enormous: it runs to several thousands of published papers and scores of books. Unfortunately, a lot of introductory textbooks on logic introduce their readers to the material conditional and leave them with the impression that this is all there is to conditionals. My experience from talking to mathematicians in particular is that they are often astonished to learn there is a huge literature on the logic of conditionals, because their introductory textbooks don't mention it. This situation is belatedly starting to change. I have come across several recent textbooks that alert their readers to the complexity of the subject and to the existence of non-truth functional conditionals, while confining most of their coverage to the material conditional because of limitations of space.

For some explanation of how the material conditional differs from ordinary conditionals in natural usage and some references, see my answer to this question.

Bumble
  • 24,872
  • 3
  • 32
  • 73
  • A question that interests me is, “is this provably the only possible proof in the natural deduction system?” I think a proof system where proofs reduce to a standard/identical form is called “normal”, or something? – Julius Hamilton Mar 14 '24 at 16:00
  • 1
    There are any number of proofs, even for a given deductive system. The differences may be trivial, or they may introduce arbitrary complications. Maybe in some cases there could be a canonical simplest proof. But being simplest is mainly of pragmatic value. – Bumble Mar 14 '24 at 16:48
1

A very intuitive way of thinking about this is, material implication is satisfied under these conditions:

P Q (P->Q)
1 1   1
0 1   1
0 0   1
1 0   0

The converse of P->Q should have the exact opposite truth values of P->Q, which is what the definition of the negation symbol is:

P Q (P->Q)  !(P->Q)
1 1   1        0
0 1   1        0
0 0   1        0
1 0   0        1

Notice how the only condition for which “not (P implies Q)” is true is when P is true and Q is false. So if “P does not imply Q” is a true statement, then the only possibility is that P is true and Q is false.

I am still learning this myself, but I have come to believe it is a profound mistake to think of the material implication arrow -> as the intuitive idea of “if-then”. I believe this is commonly taught to undergraduates in subjects like linguistics and computer science, and it makes people confused, because it ultimately is not that good of a conceptual analogy.

What I appreciate about Speakpigeon’s answer is that it addresses exactly this idea and reformulates the implication arrow as “not P or Q”. I personally find their answer correct, in spite of the detractors.

Based on statements from Mauro and Bumble, I think there is quite another way to approach this “proof”. In the proof system of “natural deduction”, as far as I know, all you can really do with a material implication arrow is interpret it as “an assumption” or a “conditional proof”. I do not know for sure, but I wonder if this means that in natural deduction, the only way to prove a conditional is via proof by contradiction?

By assuming Q, we hope to derive P -> Q. Bumble explains how this is conventionally done with the rules of natural deduction:

Make a second assumption - P.

In this (assumed) context, Q is true. “Discharging the assumption” is a rule where whatever is proven after some assumption, becomes a material implication statement that is valid: “assumption -> conclusion”.

So we have derived “P -> Q”.

I admit I need to think more about this to see if there are other ways to do this in natural deduction.

Julius Hamilton
  • 1,559
  • 4
  • 29
  • The material conditional is a simple kind of conditional and it has an important place in classical logic. It is the conditional that is introduced by the rule of classical conditional proof and eliminated by classical modus ponens. It serves as a conditional under the assumption that it is bivalent, dyadic, and a truth function. But there are other conditionals that do not obey these assumptions, both within classical logic and non-classical logics... – Bumble Mar 14 '24 at 03:24
  • So it is correct to say that the material conditional is not the only conditional and not a particularly good way to represent "if-then" in English. But the question is a logic exercise. In the absence of explicit statement to the contrary, it is reasonable to assume that the question is about classical logic and the material conditional. – Bumble Mar 14 '24 at 03:25
  • I don’t disagree. Could you elaborate on what the rule of classical conditional proof is, and what the definition of bivalent and dyadic are? I was thinking earlier today about how ‘->’ is the only non-symmetric logical operator amongst common logical operators, and wanting to know if there is a deep reason why it is seen as so essential if it has this slightly contingent or quirky definition. – Julius Hamilton Mar 14 '24 at 03:50
  • 1
    @JuliusH.: Conditional proof is the following rule of inference: "Assume that P is true. Prove that Q is true. Therefore, discharging our assumption, P implies Q." This is also the main reason that mathematicians tend to phrase it as "If P then Q" - you literally prove it by assuming P and proving Q from P. – Kevin Mar 14 '24 at 04:49
-4

How do I prove the following? ¬(P → Q) ⊢ ¬Q

You better not.

The implication ¬(P → Q) ⊢ ¬Q is just false. ¬(P → Q) does not imply ¬Q.

However, if what you mean is really to prove ¬(¬P ∨ Q) ⊢ ¬Q, then it’s really trivial.

¬(¬P ∨ Q) is P ∧ ¬Q, and P ∧ ¬Q implies ¬Q, so ¬(¬P ∨ Q) implies ¬Q.

Still, P → Q is not ¬P ∨ Q, and ¬(P → Q) ⊢ ¬Q is false, so you cannot prove ¬(P → Q) ⊢ ¬Q.

Unless you equivocate by saying P → Q when you really mean ¬P ∨ Q.

Speakpigeon
  • 7,364
  • 1
  • 11
  • 26
  • Don’t you believe both Q→(P→Q) and (P →Q)→(~Q →~P)? If so, then which of the following do you disbelieve: Modus Ponens or Uniform Substitution? – PW_246 Mar 13 '24 at 18:01
  • This answer is completely on the right track. The answerer is thinking authentically about that these symbols even mean. Whether or not you agree with their judgment, it is the right approach. – Julius Hamilton Mar 13 '24 at 20:55
  • 2
    The stated entailment relation does fail to hold for some logics other than classical. For example, it fails in relevance logics, probabilistic logics and connexive logics, and it fails for the Stalnaker conditional. But since classical logic is the most commonly used logic, it is reasonable to assume the question is asking about classical logic and the material conditional, unless it explicitly says otherwise. – Bumble Mar 14 '24 at 02:05
  • @Bumble "it is reasonable to assume the question is asking about classical logic" Sure, but it is not reasonable to equivocate by saying P → Q when you really mean ¬P ∨ Q. – Speakpigeon Mar 14 '24 at 10:17
  • Perhaps this argument/comment-thread can be ended if we make it clearer upfront that the answerer does not consider ”P → Q” to be equivalent to “¬P ∨ Q”. I find this valid - as other answers touch upon, rigorously defining an intuitive idea of “implication” or “conditionality” into a symbolic calculus is not a simple topic. Perhaps the answerer can expand in their answer on their thoughts on this, to dissuade future critics? – Julius Hamilton Mar 14 '24 at 15:53
  • @Speakpigeon how is that? – PW_246 Mar 14 '24 at 16:47
  • 1
    @JuliusH. "if we make it clearer upfront that the answerer does not consider ”P → Q” to be equivalent to “¬P ∨ Q”." I clearly don't, but it is up to the questioner to ask for a proof for ¬(¬P ∨ Q) ⊢ ¬Q. The question as it is says ¬(P → Q) ⊢ ¬Q, so I reply for ¬(P → Q) ⊢ ¬Q and ¬(P → Q) ⊢ ¬Q is false. – Speakpigeon Mar 14 '24 at 17:28
  • @PW_246 "how is that?" You are spreading misinformation/opinions without justification, as if they were brute facts, by claiming that "they spread misinformation/opinions without justification, as if they were brute facts". – Speakpigeon Mar 14 '24 at 17:31
  • @Speakpigeon what? It’s well known that almost every time there is a post about Classical implication or the null set or something, you’re going to come by with an opinion that goes against the norm (and usually contradicts your previous stances) without providing any philosophical justification. You did it on this post by saying that the sequent in question is just false without giving a logical counter-model or at least an epistemic defeater for said sequent. – PW_246 Mar 14 '24 at 18:15
  • @PW_246 "Classical implication or the null set" What's that? Doesn't even exist! There is just the implication and then ¬(P → Q) ⊢ ¬Q is just false. Where is your justification to the contrary? The "norm"!!!! Whoa. Impressive. Me, I am talking about the real world. Come back to earth. - 2. "usually contradicts your previous stances" Nah. Only in your imagination. You are confusing contradicting your dogma and contradicting myself. Learn to see the difference. – Speakpigeon Mar 15 '24 at 10:40