104

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 ponens)}$$


31

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


14

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


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

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


9

Note that $$(\lnot A \lor B) \rightarrow (\lnot A \lor B) \equiv \lnot(\lnot A \lor B) \lor (\lnot A \lor B) \equiv \top$$ In other words, the first premise is a tautology. It says nothing more than "either $\lnot(\lnot A \lor B)$ or else $(\lnot A \lor B)$ holds. And in assuming the law of the excluded middle, one of the two disjuncts must be true, and ...


9

You're exactly right - $A \not \vdash \perp$ means that $A$ is consistent. That is, we cannot derive a contradiction using $A$ as hypotheses. But there is a difference between "we can't prove it false" and "it's true"! Here's an easy example. Let's work with the theory of groups. Then $$ xy = yx \not \vdash \perp$$ Why is this? Because if ...


8

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


8

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


7

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


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

It is essentially a matter of point of view. The idea of logical axioms can be tracked back to Frege's Begriffsschrift (1879). For Frege, logic is a science, in particular, the branch of knowledge that deals with truth. Therefore, it is essential to have a body of laws governing the subject matter, namely, the notion of truth. Those are the things we know ...


7

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


7

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


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

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


7

It is the principle of explosion, also known as ex falso quodlibert: from contradiction, anything follows. In natural deduction, it says that if $\mathcal{D}$ is a derivation with conclusion $\bot$ then, for every formula $\varphi$, $$\dfrac{\genfrac{}{}{0pt}{}{\ \ \vdots \mathcal{D}}{\bot}}{\varphi}\scriptstyle\text{efq}$$ is a derivation with conclusion ...


7

See Paraconsistent Logic for a family of logics that reject Ex Falso (aka: Principle of Explosion). See also: Walter Carnielli & Marcelo Esteban Coniglio, Paraconsistent Logic: Consistency, Contradiction and Negation (Springer, 2016), as well as: Holger Andreas & Peter Verdée (editors), Logical Studies of Paraconsistent Reasoning in Science and ...


7

Yes, it is just a quick consequence of the elimination rule. $\to $ Elimination (in its most common phrasing) says that if $\Gamma\vdash A\to B$ and $\Gamma\vdash A$ then $\Gamma\vdash B.$ So, if $\Gamma\vdash A\to B,$ then $\Gamma, A\vdash A\to B.$ And of course $\Gamma,A\vdash A,$ so applying the elimination rule gives $\Gamma,A\vdash B.$


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

$$\begin{align} (1) & \alpha \rightarrow \beta && [\text{HYP}] \\ (2) & \beta \rightarrow \gamma && [\text{HYP}] \\ (3) & \alpha && [\text{HYP}] \\ (4) & \beta && [\text{MP}(1,3)] \\ (5) & \gamma && [\text{MP}(2,4)] \\ (6) & \alpha \rightarrow \gamma && [\rightarrow\text{-intro}(3,...


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