2
$\begingroup$

I was exploring the inferences drawn from the truth values of $p$, $q$, and $(p \Rightarrow q)$. The truth table of material implication is:

$$\begin{array}{|c|c|c|} \hline p&q&p\Rightarrow q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ F&F&T\\\hline \end{array}$$

If $(p \Rightarrow q)$ is true and $p$ is true, we can see from the table that $q$ is true. This rule of inference is called modus ponens.

If $(p \Rightarrow q)$ is true and $q$ is false, we can see from the table that $p$ is false. This rule of inference is called modus tollens.

If $(p \Rightarrow q)$ is true and $p$ is false, we can see from the table that $q$ is undecidable. Saying that $q$ is false would amount to the fallacy called "denying the antecedent".

If $(p \Rightarrow q)$ is true and $q$ is true, we can see from the table that $p$ is undecidable. Saying that $p$ is true would amount to the fallacy called "affirming the consequent".

My question:

How does propositional logic deal with the case when $(p \Rightarrow q)$ is false? From the table above, we could immediately infer that $p$ is true and $q$ is false. Is there a name for this "rule"? Does it have any applicability? What within propositional logic would formally prevent one from applying this "rule"?

$\endgroup$
5
  • 3
    $\begingroup$ This is simply the equivalence with $p \land \lnot q$. $\endgroup$ Nov 29, 2023 at 16:48
  • $\begingroup$ I've seen $p \implies q \iff q \lor \lnot p$ offered almost as a definition of $p \implies q$. Given that and De Morgan's laws, $\lnot(p \implies q) \iff p \land \lnot q$. The former might not be a definition though, technically, but I'm not sure what else to call it. $\endgroup$ Nov 29, 2023 at 16:48
  • 2
    $\begingroup$ Confusion around material implication usually comes from not recognizing an implicit universal quantifier in example natural-language "if ... then ..." statements. Usually the correct formal translation of these statements is of the form $\forall x (P(x)\Rightarrow Q(x))$, not the form $P\Rightarrow Q$. The quantified statement behaves like a strict conditional, which matches people's intuition for conditional statements. $\endgroup$
    – Karl
    Nov 29, 2023 at 17:22
  • $\begingroup$ In your case, knowing that $\forall x (P(x)\Rightarrow Q(x))$ is false doesn't tell you anything about any particular object $x$ (matching your intuition), but knowing $P(c)\Rightarrow Q(c)$ is false for a particular $c$ tells you that $P(c)$ is true and $Q(c)$ is false. $\endgroup$
    – Karl
    Nov 29, 2023 at 17:30
  • $\begingroup$ Thank you, @Karl. You used the universal quantifier in your second comment. Did you mean to use it or to use the existential instead? $\endgroup$
    – toliveira
    Nov 30, 2023 at 12:46

3 Answers 3

2
$\begingroup$

It is indeed true the falsehood of $p \to q$ implies $p$ is true and $q$ is false. In other words, it is indeed true $\neg (p \to q)$ imples $p \wedge \neg q$. You have presented a semantic proof of a valid argument form that doesn't have a name (that I'm aware of). This should not be suprising because there are many, many valid argument forms that can be constructed in a given system.

From a syntactic point of view, every natural deduction system has a "starting" set of inference rules that contains the primitive inference rules of the system, which you can think of as inference rules we simply take for granted to be true. You can use the primitive inference rules to derive other inference rules, but derived inference rules do not allow you to prove anything new that you could not prove apart from the primitive rules. This is because anything proven with a derived rule can be proven by applying some sequence of primitive rules.

For example, suppose a system defined Modus Ponens (MP), Conjunction Introduction ($\wedge$I), and Reductio ad Absurdum (RAA) as primitive rules. Then, one could derive Modus Tollens $p \to q, \neg q \vdash \neg p$ as follows

$ \begin{array}{llll} \{1\} & 1. & p \to q & \text{premise} \\ \{2\} & 2. & \neg q & \text{premise} \\ \{3\} & 3. & p & \text{Assumption for RAA} \\ \{1,3\} & 4. & q & \text{1,3 MP} \\ \{1,2,3\} & 5. & q \wedge \neg q & \text{2,4 $\wedge$I} \\ \{1,2\} & 6. & \neg p & \text{3,5 RAA} & \square \\ \end{array} $

Thus, in such a system Modus Tollens is a derived rule, proven by the primitive rules MP, $\wedge$I, and RAA.

So, if we wish, we could take the valid form of inference you mentioned

$\neg (p \to q) \vdash p \wedge \neg q$

and give it a name like "toliveira's rule," but in most natural deduction systems (that I'm aware of) this would be one of many derived inference rules that do not have a name. Some derived inference rules are given names because they are used often, provide useful shortcuts in proofs, or capture our intuition well; others are more obscure. So, in summary I think you're simply observing a valid argument form that doesn't have a flashy name like "Modus Tollens" or "Constructive Dilemma."

$\endgroup$
2
$\begingroup$

Many textbooks will note the following logical equivalence:

$P \to Q \Leftrightarrow \neg P \lor Q$

Different books may have different names for this principle (and some may not give it any name at all), but I have most seen it referred to as the Implication equivalence.

Moreover, some texts will add a second equivalence to this, which is:

$\neg (P \to Q) \Leftrightarrow P \land \neg Q$

That is, just like something like Demorgan's come in two varieties:

DeMorgan

$\neg (P \lor Q) \Leftrightarrow \neg P \land \neg Q$

$\neg (P \land Q) \Leftrightarrow \neg P \lor \neg Q$

the Implication equivalence is sometimes also presented as having two varieties:

Implication

$P \to Q \Leftrightarrow \neg P \lor Q$

$\neg (P \to Q) \Leftrightarrow P \land \neg Q$

So the second one of these gives you exactly what you want in your question ... though it is considered an equivalence, rather than ('merely') an inference.

As inferences, we could of course consider:

$\neg (P \to Q)$

$\therefore P$

and

$\neg (P \to Q)$

$\therefore \neg Q$

but I have honestly never seen any names for either one of those inferences ... and my guess is that that is because they are so unintuitive. Indeed, they are sometimes considered examples of the Paradox of Material Implication

$\endgroup$
1
$\begingroup$

How does propositional logic deal with the case when $(p \implies q)$ is false?

You can think of it as a counter-example. $(p \implies q)$ is falsified when $p$ is true and $q$ is false.

Also, I like your contra-positive (modus tolens) idea, but in the last 2 lines (when $p$ is false), we can think of both lines as exhibiting the Principle of Vacuous Truth: Whenever the antecedent $p$ is false, the implication $(p\implies q)$ will be true regardless of the truth value of the consequent $q$.

Using a form of natural deduction, we can prove the Principle of Vacuous Truth (~P => (P => Q)) as follows:

Suppose P is false

1   ~P
    Premise

    2   P
        Premise

        3   ~Q
            Premise

        4   ~P & P
            Join, 1, 2

    5   ~~Q
        Conclusion, 3

    6   Q
        Rem DNeg, 5

7   P => Q
    Conclusion, 2

8   ~P => [P => Q]
    Conclusion, 1

(Text version. HTML version available on request.)


EDIT IN RESPONSE TO COMMENT

Screenshot:

enter image description here

$\endgroup$
2
  • $\begingroup$ I particularly liked the interpretation as a counter-example. Thank you, @Dan! In the proof, are all the indentations correct? $\endgroup$
    – toliveira
    Nov 30, 2023 at 15:30
  • $\begingroup$ @toliveira Due to a quirk of the MSE textbox feature that I use here, the indentation is messed up. Lines 1-7 should be indented once more. I would prefer to use a screenshot from my proof-checker which does not have this problem, but the moderators object to such screenshots. $\endgroup$ Nov 30, 2023 at 15:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .