The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

Hot answers tagged natural-deduction

106

It's true that if $P$ is false then $P\Rightarrow Q$ is true. But the question is not asking if $P\Rightarrow Q$ is true, it's asking you if you can infer $P$ from $P\Rightarrow Q$ and $Q$. Let's be concrete. Suppose "if Mark is drunk, then Mark is happy" is a true statement, because Mark is a happy drunk. Given that Mark is presently happy, may we infer ...

54

This pattern is a logical fallacy called Affirming the Consequent, though I often call it Modus Bogus. To show it is not a valid inference, here is a simple Refutation by Logical Analogy: If I have blond hair, I have hair I have hair Therefore, I have blond hair Here is my favorite logical fallacy: $$\frac{}{\therefore P}\qquad \text{(hokus ... 30 Even if affirming the consequent is not valid, other logical rules still work. Other logical rules still work. Therefore, affirming the consequent is not valid? 19 Not stated in the other answers so far is that you misunderstood the meaning of logical validity, which means that, in every situation where the premises hold, the conclusion also holds. Now you may have observed that if Q is true then (P \to Q) is also true, by looking at the truth table of implication. But that is not what you should be looking for. ... 15 It could be done, as described in the other answers. But it would not make capture-avoiding substitution easier to define, so there's no real benefit. On the other hand, we would lose the sometimes useful property that a sentence can be substituted into any context without needing to look inside it. It would also be more difficult to define local rewrites ... 13 The issue is that that kind of rule requires awareness of the contents of smaller wffs. Think about the other rules - none of them say anything about "if such-and-such a symbol appears inside...". The rule you're proposing would look something like this: "If \varphi is a wff, v is a variable, and \varphi does not include the strings '\forall v' or '\... 12 As others have said, the question is asking whether it is necessarily the case that whenever P \Rightarrow Q and Q are true, P must be true. My personal favoured instantiations of P and Q are 'it is Saturday' and 'it is the weekend' respectively; modus morons would enable us to infer: (1) If it is Saturday, then it is the weekend. [premise] (2) ... 11 if P⇒Q and Q it does not matter whether P or ¬P That's the point. It doesn't matter whether P or \neg P: The statement becomes true for P and \neg P either. Therefore, you can not deduce that it must be P. It could be P, but it might just as well be \neg P, because both would entail the truth of the statement. By writing$$\frac{A}{\...

10

Well, here's my solution even though I've used 4 'unallowed' rules. $\neg\exists x\forall y(Dx\implies Dy)\quad$ assumption for $\neg$ introduction $\forall x\neg\forall y(Dx\implies Dy)\quad$ DeMorgan's for quantifiers $\forall x\exists y \neg(Dx\implies Dy)\quad$ DeMorgan's for quantifiers $\forall x\exists y\neg(\neg Dx\vee Dy)\quad$ Conditional ...

10

A logical axiom can be considered a rule of inference that happens to have no antecedents. Any interesting proof system must have at least one axiom and one rule of inference with premises. If it has no axioms then there is no way to begin a proof in the empty theory, and without rules of inference all that could be proven would be the axioms themselves. ...

10

The other answers have perfectly settled this question, however I thought I would share another funny example. It is not exactly the same logical structure, but very similar. This example originates from the satirical play Erasmus Montanus written in 1722 by Danish-Norwegian writer Ludvig Holberg. In Danish it goes like this En sten kan ikke flyve. ...

9

I would like not to use de morgan law, as you would need to include that as a premise. I was thinking of this proof. $\lnot (p \lor \lnot p) \quad \quad \quad (H)$ $p \quad \quad \quad \quad \quad (H)$ $p \lor \lnot p \quad \quad \; \;(\lor \text{I} 2)$ $\bot \quad \quad \quad \quad \;\;(\lnot \text{E}1,3)$ $\lnot p \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\... 7 Layout: To prove that$\neg P\lor Q$is a formal consequence of$P\to Q$, start by assuming$P\to Q$and further suppose that$\neg (\neg P\lor Q)$holds. At this point you should prove$P\lor \neg P$and perform$\lor$-$\text{Elim}$on this disjunction. It's easy to find contradictions on both cases yielding$\neg \neg (\neg P\lor Q)$. For the other ... 7 This statement can be proved in minimal logic. When you rewrite the negations as implications in the usual way, the statement is $$((\alpha \to \bot) \land ((\alpha \to \bot) \to \bot) \to \bot$$ which is really of the form $$(X \land X \to Y) \to Y$$ which is just a form of modus ponens. The provability of the statement has nothing to do with negation, ... 7 We need contradiction in the proof (but it is not a poof by contradiction) : 1)$\lnot \exists x \ Px$--- premise 2)$\quad\quad| \quad Px$--- assumed [a] 3)$\quad\quad| \quad \exists x \ Px$--- from 2) by$\exists$-intro 4)$\quad\quad| \quad\bot$--- contradiction! from 1) and 3) 5)$\lnot Px$--- from 2)-4) by$\lnot$-intro, discharging [a] 6) ... 7 You were right to doubt your proof; it's not quite right. The main mistake is that you are effectively closing two subproofs at once once you go from 2.2.3 to 3, but you can only close one subproof at a time, in the reverse order in which you opened them. Also: you need to have line 1 as an assumption of a subproof, and close that subproof once you have ... 7 In your first example$y$does not occur free in step 2 and in your second example$x$does not occur free in step 1, so the problem is not with the variable occurrences in the antecedents to the inference steps. What is wrong in both examples is that you have not done the substitutions correctly when deriving the succedents of the inference step. When you ... 7 You can say that the hypothesis$\Gamma, A \land B$is stronger than$\Gamma, A$because in$\Gamma, A \land B$you have more hypotheses than in$\Gamma, A$. But the statement$\Gamma, A \land B \vdash C$(i.e.$C$is derivable from the hypotheses$\Gamma, A \land B$) is weaker (in the sense of less general or less informative) than the statement$\Gamma, A \...

6

When are you entitled to assert a conditional $P \to Q$? Precisely when, given $P$ as an assumption, you are in a position to assert $Q$. The natural deduction rule "conditional proof" or "$\to$-introduction" encapsulates that fundamental assumption about the meaning of the conditional. It's an introduction rule because it tells you that when you can argue ...

6

In natural deduction proofs, it is good to "think ahead", and at any stage of a proof look at what you are trying to derive at that stage, and ask yourself "How can I prove that?" So, in this case, you start with the premiss $(P \to (Q \to R))$ and your target is to derive $((P \land Q) \to R)$. OK: ask what kind of proposition is that target? what ...

6

The most likely reason one would use natural deduction in a proof is because it parallels the way people think. When trying to prove some complicated implication chain like $$(A\to(B\to C))\to((A\to B)\to(A\to C)),$$ most people find it more logical and reasonable to assume the left part and deduce the right part rather than working with axioms that deal ...

6

You can think about it in this way: $(A\to B)\land(\neg A\to C)$ is a rule you're given, which tells you what happens when you know the truth value of $A$. If $A$ is true, then you must have $B$; if $A$ is false, you must have $C$. And since $A\lor\neg A$ is a tautology (always true), then either you have $A$ and $B$ or you have $\neg A$ and $C$, which we ...

6

Example Let $\Gamma$ the set of first-order Peano axioms: no variables free. 1) $\Gamma \vdash \exists x (x = 0)$ --- easily provable 2) $\Gamma, x=0 \vdash x=0$ --- obvious 3) $\Gamma \vdash x=0$ --- from 1) and 2) by $\exists$-elim : wrong ! 4) $\Gamma \vdash \forall x (x=0)$ --- from 3) by $\forall$-intro, 1) $\Gamma, x=0 \vdash x = 0$ 2) $\Gamma,... 6 To prove it in set theory, we need some definitions and some basic results : Definition of function :$(∀x)(∀y)(∀z)(\langle x,y \rangle \in f \land \langle x,z \rangle \in f \to y = z)$; equality between (Kuratowski) pairs :$\langle x,y \rangle = \langle u,v \rangle \to x = u \land y = v$; definition of domain of a relation:$\mathcal D R$is ... 6 1)$\lnot (A \lor \lnot A)$--- assumed [a] 2)$A$--- assumed [b] 3)$A \lor \lnot A$--- from 1) by$\lor$-intro 4)$\lnot A$--- from the contradiction : 2) and 3) by$\lnot$-intro, discharging [b] 5)$A \lor \lnot A$---$\lor$-intro 6)$\lnot \lnot (A \lor \lnot A)$--- from the contradiction : 1) and 5) by$\lnot$-intro, discharging [a] 7)$A \...

6

It is indeed a rather 'natural' thing to conclude $P \rightarrow Q$ when the assumption of $P$ leads to $Q$. However, many formal proof systems use the 'assume and discharge' for fairly natural proof techniques other than this kind of conditional proof. The proof by contradiction is a very common one in fact: Assume $P$, and if that leads to a ...

6

I would do it slightly differently, but as always people use somewhat different systems for natural deduction. Begin 1) $(P \land \lnot Q) \rightarrow Q$ (ass.) 2) $P$ (ass.) 3) $\lnot Q$ (ass.) 4) $(P \land \lnot Q)$ introduction $\lnot$ from 2,3. 5) $Q$ (modus ponens from 1. and 4.) 6) $\bot$ from $5$ and $3$. 7) $\lnot \lnot Q$ (from introduction $\... 6 The theorem says that to prove an implication it is enough to assume the hypothesis and proceed to prove the conclusion. Proofs of that kind tend to be more natural than proofs that conclude the implication directly. Just as in regular mathematical practice: many theorems have the form "Assuming$A$, then we have$B$", and we usually prove them by assuming ... 6 'True' refers to the English statement (2.2), 'correct' refers to the sequent$\Gamma \vdash \Psi\$. The authors aim to define when a sequent is correct in a technical sense, and they use the common sense of 'true' in natural language (the meta-level). In other words, the meaning of the paragraph is that if the situation described by (2.2) holds (i.e. the ...

Only top voted, non community-wiki answers of a minimum length are eligible