Skip to main content
Engineering LibreTexts

1.5.3: Proofs in predicate logic

  • Page ID
    9913
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    So far in this section, we have been working mostly with propositional logic. But the definitions of valid argument and logical deduction apply to predicate logic as well.

    One of the most basic rules of deduction in predicate logic says that \((\forall x P(x)) \Longrightarrow\)P(a) for any entity a in the domain of discourse of the predicate P. That is, if a predicate is true of all entities, then it is true of any given particular entity. This rule can be combined with rules of deduction for propositional logic to give the following valid arguments:

    屏幕快照 2019-07-01 09.43.52.png

    These valid arguments go by the names of modus ponens and modus tollens for predicate logic. Note that from the premise ∀x(P(x) → Q(x)) we can deduce P(a) → Q(a). From this and from the premise that P(a), we can deduce Q(a) by modus ponens. So the first argument above is valid. The second argument is similar, using modus tollens.

    The most famous logical deduction of them all is an application of modus ponens for predicate logic

    屏幕快照 2019-07-01 09.44.23.png

    This has the form of modus ponens with P(x) standing for “x is human”, Q(x) standing for “x is mortal”, and a standing for the noted entity, Socrates.

    To disprove validity of arguments in predicate logic, you again need to provide a counterexample. These are most easily given in the form of a mathematical structure. Consider for instance the following argument:

    屏幕快照 2019-07-01 09.44.54.png

    This argument is not valid and we can prove that using the following structure A.

    D={a,b}
    \(P^{A}\) = {a}
    \(Q^{A}=\) {a}

    As you can see, the first premise is true. There is an x such that P(x) holds, namelyx = a. The second premis is also true, as for all x for which P(x) holds (so only x = a),Q(x) also holds (and indeed Q(a)) holds. However the conclusion is false, as Q(b) does not hold, so the Q(x) does not hold for all x.

    There is a lot more to say about logical deduction and proof in predicate logic, and we’ll spend the whole of the next chapter on the subject.

    Exercises

    1. Verify the validity of modus tollens and the Law of Syllogism.
    2. Each of the following is a valid rule of deduction. For each one, give an example of a valid argument in English that uses that rule. 屏幕快照 2019-07-01 09.46.25.png
    3. There are two notorious invalid arguments that look deceptively like modus ponens and modus tollens: 屏幕快照 2019-07-01 09.47.11.png
      1. Show that each of these arguments is invalid. Give an English example that uses each of these arguments.
    4. Decide whether each of the following arguments is valid. If it is valid, give a formal proof. If it is invalid, show that it is invalid by finding an appropriate assignment of truth values to propositional variables. 屏幕快照 2019-07-01 09.49.14.png
    5. For each of the following English arguments, express the argument in terms of propositional logic and determine whether the argument is valid or invalid.
      1. a) If it is Sunday, it rains or snows. Today, it is Sunday and it’s not raining. Therefore, it must be snowing.
      2. b) If there is herring on the pizza, Jack won’t eat it. If Jack doesn’t eat pizza, he gets angry. Jack is angry. Therefore, there was herring on the pizza.
      3. c) At 8:00, Jane studies in the library or works at home. It’s 8:00 and Jane is not studying in the library. So she must be working at home.

    1.5.3: Proofs in predicate logic is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.

    • Was this article helpful?