{"id":37,"date":"2016-12-16T18:14:05","date_gmt":"2016-12-16T18:14:05","guid":{"rendered":"https:\/\/pressbooks.ccconline.org\/introtologic\/chapter\/4-proofs\/"},"modified":"2025-10-13T17:23:06","modified_gmt":"2025-10-13T17:23:06","slug":"4-proofs","status":"publish","type":"chapter","link":"https:\/\/pressbooks.ccconline.org\/introtologic\/chapter\/4-proofs\/","title":{"raw":"Proofs","rendered":"Proofs"},"content":{"raw":"

4.1 \u00a0A problem with semantic demonstrations of validity<\/h2>\r\n
\r\n

Pre-Reading Questions<\/p>\r\n\r\n<\/header>\r\n

\r\n
    \r\n \t
  1. What\u2019s the purpose of writing a formal proof in logic?<\/li>\r\n \t
  2. How does a derivation differ from simply identifying a conclusion?<\/li>\r\n \t
  3. Why is it important to keep track of assumptions in a proof?<\/li>\r\n \t
  4. What strategies might help when you're stuck and can\u2019t immediately see how to derive a conclusion?<\/li>\r\n<\/ol>\r\n<\/div>\r\n<\/div>\r\n
    \r\n

    Key Terms<\/p>\r\n\r\n<\/header>\r\n

    \r\n
      \r\n \t
    • Proof<\/strong> - a sequence of statements that demonstrates the truth of a proposition (a statement that can be either true or false) by deriving it from a set of accepted truths (axioms or premises) using valid rules of inference.<\/li>\r\n \t
    • Derivation<\/strong> - a step-by-step process of demonstrating the validity of an argument by showing how a conclusion can be logically derived from a set of premises using established rules of inference.<\/li>\r\n \t
    • Premise<\/strong> - a statement that is assumed to be true and is used as evidence or support for a conclusion.<\/li>\r\n \t
    • Conclusion<\/strong> - a statement that follows directly and reasonably from the evidence or premises presented.<\/li>\r\n \t
    • Justification Rule<\/strong> - a principle that allows us to infer a justified conclusion from justified premises.<\/li>\r\n \t
    • Subproof<\/strong> - a proof within a larger proof, often used to derive a conditional statement or to demonstrate a proof by contradiction.<\/li>\r\n \t
    • Goal-Directed Strategy<\/strong> - a plan or course of action designed to achieve a specific, predefined objective or desired outcome.<\/li>\r\n<\/ul>\r\n<\/div>\r\n<\/div>\r\nGiven that we can test an argument for validity, it might seem that we have a fully developed system to study arguments. \u00a0However, there is a significant practical difficulty with our semantic method of checking arguments using truth tables (you may have already noted what this practical difficulty is, when you did problems 1e and 2e of chapter 3). \u00a0Consider the following argument:\r\n

      Jasmine will go to the party.<\/p>\r\n

      If Jasmine will go to the party, then Helena will.<\/p>\r\n

      If Helena will go to the party, then Fatima will.<\/p>\r\n

      If Fatima will go to the party, then Olivia will.<\/p>\r\n

      If Olivia will go to the party, then Elizabeth will.<\/p>\r\n

      If Elizabeth will go to the party, then Mia will.<\/p>\r\n

      If Mia will go to the party, then Giada will.<\/p>\r\n

      If Giada will go to the party, then Hillary will.<\/p>\r\n

      If Hillary will go to the party, then Chen will.<\/p>\r\n

      If Chen will go to the party, then Julie will.<\/p>\r\n

      _____<\/p>\r\n

      Julie will go to the party.<\/p>\r\nMost of us will agree that this argument is valid. \u00a0It has a rather simple form, in which one sentence is related to the previous sentence, so that we can see the conclusion follows from the premises<\/strong>. \u00a0Without bothering to make a translation key, we can see the argument has the following form.\r\n

      P<\/span><\/strong><\/p>\r\n

      (P<\/strong><\/span>\u2192Q<\/strong>)<\/span><\/p>\r\n

      (Q<\/strong>\u2192R<\/strong>)<\/span><\/p>\r\n

      (R<\/strong>\u2192S<\/strong>)<\/span><\/p>\r\n

      (S<\/strong>\u2192T<\/strong>)<\/span><\/p>\r\n

      (T<\/strong>\u2192U<\/strong>)<\/span><\/p>\r\n

      (U<\/strong>\u2192V<\/strong>)<\/span><\/p>\r\n

      (V<\/strong>\u2192W<\/strong>)<\/span><\/p>\r\n

      (W<\/strong>\u2192X<\/strong>)<\/span><\/p>\r\n

      (X<\/strong>\u2192Y<\/strong>)<\/span><\/p>\r\n

      _____<\/span><\/p>\r\n

      Y<\/span><\/strong><\/p>\r\nHowever, if we are going to check this argument, then the truth table will require 1024 rows! \u00a0This follows directly from our observation that for arguments or sentences composed of n atomic sentences, the truth table will require 2n<\/span><\/span>\u00a0rows. \u00a0This argument contains 10 atomic sentences. \u00a0A truth table checking its validity must have 210<\/span>\u00a0<\/span>rows, and 210<\/span><\/span>=1024. \u00a0Furthermore, it would be trivial to extend the argument for another, say, ten steps, but then the truth table that we make would require more than a million rows!\r\n\r\nFor this reason, and for several others (which become evident later, when we consider more advanced logic), it is very valuable to develop a syntactic proof method. \u00a0That is, a way to check proofs not using a truth table, but rather using rules of syntax.\r\n\r\nHere is the idea that we will pursue. \u00a0A valid argument is an argument such that, necessarily, if the premises are true, then the conclusion<\/strong> is true. \u00a0We will start just with our premises. \u00a0We will set aside the conclusion, only to remember it as a goal. \u00a0Then, we will aim to find a reliable way to introduce another sentence into the argument, with the special property that, if the premises are true, then this single additional sentence to the argument must also be true. \u00a0If we could find a method to do that, and if after repeated applications of this method we were able to write down our conclusion, then we would know that, necessarily, if our premises are true then the conclusion is true.\r\n\r\nThe idea is more clear when we demonstrate it. \u00a0The method for introducing new sentences will be called \u201cinference rules\u201d. \u00a0We introduce our first inference rules for the conditional. \u00a0Remember the truth table for the conditional:\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
      \u03a6 \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/th>\r\n\u03a8<\/span><\/th>\r\n(\u03a6\u2192\u03a8)<\/span><\/th>\r\n<\/tr>\r\n
      T \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/strong><\/td>\r\nT<\/span><\/strong><\/td>\r\nT<\/span><\/strong><\/td>\r\n<\/tr>\r\n
      T \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/strong><\/td>\r\nF<\/span><\/strong><\/td>\r\nF<\/span><\/strong><\/td>\r\n<\/tr>\r\n
      F \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/strong><\/td>\r\nT<\/span><\/strong><\/td>\r\nT<\/span><\/strong><\/td>\r\n<\/tr>\r\n
      F \u00a0 \u00a0 \u00a0\u00a0<\/span><\/strong><\/td>\r\nF<\/span><\/strong><\/td>\r\nT<\/span><\/strong><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nLook at this for a moment. \u00a0If we have a conditional like (P<\/strong>\u2192Q<\/strong>)<\/span>\u00a0(looking at the truth table above, remember that this would meant that we let \u03a6<\/span>\u00a0<\/strong>be P<\/span>\u00a0<\/strong>and \u03a8<\/span>\u00a0<\/strong>be Q<\/span><\/strong>), do we know whether any other sentence is true? \u00a0From (P<\/strong><\/span>\u2192Q<\/strong>)<\/span>\u00a0alone we do not. \u00a0Even if (P<\/strong>\u2192Q<\/strong>)<\/span>\u00a0is true, P<\/span>\u00a0<\/strong>could be false or Q<\/span>\u00a0<\/strong>could be false. \u00a0But what if we have some additional information? \u00a0Suppose we have as premises both (P<\/strong><\/span>\u2192Q<\/strong>)<\/span>\u00a0and P<\/span><\/strong>. \u00a0Then, we would know that if those premises were true, Q<\/span>\u00a0<\/strong>must be true. \u00a0We have already checked this with a truth table.\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
      <\/td>\r\n<\/td>\r\npremise<\/strong><\/td>\r\n\u00a0premise<\/strong><\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/strong><\/td>\r\nQ<\/strong><\/td>\r\n(P\u2192Q)<\/strong><\/td>\r\nP<\/strong><\/td>\r\nQ<\/strong><\/td>\r\n<\/tr>\r\n
      T<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\n<\/tr>\r\n
      T<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\n<\/tr>\r\n
      F<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\n<\/tr>\r\n
      F<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nThe first row of the truth table is the only row where all of the premises are true; and for it, we find that Q<\/span>\u00a0<\/strong>is true. \u00a0This, of course, generalizes to any conditional. \u00a0That is, we have that:\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
      <\/td>\r\n<\/td>\r\npremise<\/strong><\/td>\r\npremise<\/strong><\/td>\r\n<\/td>\r\n<\/tr>\r\n
      \u03a6<\/strong><\/td>\r\n\u03a8<\/strong><\/td>\r\n(\u03a6\u2192\u03a8)<\/strong><\/td>\r\n\u03a6<\/strong><\/td>\r\n\u03a8<\/strong><\/td>\r\n<\/tr>\r\n
      T<\/em><\/td>\r\nT<\/em><\/td>\r\nT<\/em><\/td>\r\nT<\/em><\/td>\r\nT<\/em><\/td>\r\n<\/tr>\r\n
      T<\/em><\/td>\r\nF<\/em><\/td>\r\nF<\/em><\/td>\r\nT<\/em><\/td>\r\nF<\/em><\/td>\r\n<\/tr>\r\n
      F<\/em><\/td>\r\nT<\/em><\/td>\r\nT<\/em><\/td>\r\nF<\/em><\/td>\r\nT<\/em><\/td>\r\n<\/tr>\r\n
      F<\/em><\/td>\r\nF<\/em><\/td>\r\nT<\/em><\/td>\r\nF<\/em><\/td>\r\nF<\/em><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nWe now capture this insight not using a truth table, but by introducing a rule. \u00a0The rule we will write out like this:\r\n

      (<\/span>\u03a6<\/strong>\u2192<\/span>\u03a8<\/strong>)<\/span><\/p>\r\n

      \u03a6<\/strong><\/p>\r\n

      _____<\/span><\/p>\r\n

      \u03a8<\/strong><\/p>\r\nThis is a syntactic rule. \u00a0It is saying that whenever we have written down a formula in our language that has the shape of the first row (that is, whenever we have a conditional), and whenever we also have written down a formula that has the shape in the second row (that is, whenever we also have written down the antecedent of the conditional), then go ahead, whenever you like, and write down a formula like that in the third row (the consequent of the conditional). \u00a0The rule talks about the shape of the formulas, not their meaning. \u00a0But of course we justified<\/strong> the rule by looking at the meanings.\r\n\r\nWe describe this by saying that the third line is \u201cderived\u201d from the earlier two lines using the inference rule.\r\n\r\nThis inference rule is old. \u00a0We are, therefore, stuck with its well-established, but not very enlightening, name: \u00a0\u201cmodus ponens\u201d. \u00a0Thus, we say, for the above example, that the third line is derived from the earlier two lines using modus ponens.\r\n

      \r\n

      Check for Understanding<\/p>\r\n\r\n<\/header>\r\n

      \r\n
        \r\n \t
      1. The text presents an argument about ten people attending a party. Create your own similar argument with a different subject matter that would have the same logical structure.<\/li>\r\n \t
      2. If we were to extend the party argument to include 20 people instead of 10, how many rows would the truth table require? What does this tell us about the scalability of truth tables for checking validity?<\/li>\r\n<\/ol>\r\n<\/div>\r\n<\/div>\r\n

        4.2 \u00a0Direct proof<\/h2>\r\nWe need one more concept: \u00a0that of a proof<\/strong>. \u00a0Specifically, we\u2019ll start with the most fundamental kind of proof, which is called a \"direct proof.\" \u00a0The idea of a direct proof is: \u00a0we write down as numbered lines the premises of our argument. \u00a0Then, after this, we can write down any line that is justified by an application of an inference rule to earlier lines in the proof. \u00a0When we write down our conclusion, we are done.\r\n\r\nLet us make a proof of the simple argument above, which has premises (P<\/strong>\u2192Q<\/strong>)<\/span>\u00a0and P<\/span><\/strong>, and conclusion Q<\/span><\/strong>. \u00a0We start by writing down the premises and numbering them. \u00a0 There is a useful bit of notation that we can introduce at this point. \u00a0It is known as a \u201cFitch bar\u201d, named after a logician Frederic Fitch, who developed this technique. \u00a0We will write a vertical bar to the left, with a horizontal line indicating that the premises are above the line.\r\n\r\n\"\"\r\n\r\nIt is also helpful to identify where these steps came from. \u00a0We can do that with a little explanation written out to the right.\r\n\r\n\"\"\r\n\r\nNow, we are allowed to write down any line that follows from an earlier line using an inference rule.\r\n\r\n\"\"\r\n\r\nAnd, finally, we want a reader to understand what rule we used, so we add that into our explanation, identifying the rule and the lines used.\r\n\r\n\"\"\r\n\r\nThat is a complete direct proof.\r\n\r\nNotice a few things. \u00a0The numbering of each line, and the explanations to the right, are bookkeeping; they are not part of our argument, but rather are used to explain our argument. \u00a0However, always do them because, it is hard to understand a proof without them. \u00a0Also, note that our idea is that the inference rule can be applied to any earlier line, including lines themselves derived using inference rules. \u00a0It is not just premises to which we can apply an inference rule. \u00a0Finally, note that we have established that this argument must be valid. \u00a0From the premises, and an inference rule that preserves validity, we have arrived at the conclusion. \u00a0Necessarily, the conclusion is true, if the premises are true.\r\n\r\nThe long argument that we started the chapter with can now be given a direct proof.\r\n\r\n\"\"\r\n\r\nFrom repeated applications of modus ponens, we arrived at the conclusion. \u00a0If lines 1 through 10 are true, line 19 must be true. \u00a0The argument is valid. \u00a0And, we completed it with 19 steps, as opposed to writing out 1024 rows of a truth table.\r\n\r\nWe can see now one of the very important features of understanding the difference between syntax and semantics. \u00a0Our goal is to make the syntax of our language perfectly mirror its semantics. \u00a0By manipulating symbols, we manage to say something about the world. \u00a0This is a strange fact, one that underlies one of the deeper possibilities of language, and also, ultimately, of computers.\r\n
        \r\n

        Check for Understanding<\/p>\r\n\r\n<\/header>\r\n

        \r\n
          \r\n \t
        1. Critical Thinking Task:\u00a0<\/strong>Describe the purpose of the \"Fitch bar\" when evaluating proofs.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<\/div>\r\n

          4.3 \u00a0Other inference rules<\/h2>\r\n
          \r\n

          Key Terms<\/p>\r\n\r\n<\/header>\r\n

          \r\n
            \r\n \t
          • Double-Negation Rule\u00a0<\/strong>- the rule that any premise or conclusion can be added or subtracted if they are negated twice.<\/li>\r\n \t
          • Repeat<\/strong> - if proof of an argument becomes long, and a particular line is necessary again later in the proof, then this rule allows an identical line to be repeated logically.<\/li>\r\n<\/ul>\r\n<\/div>\r\n<\/div>\r\nWe can now introduce other inference rules. \u00a0Looking at the truth table for the conditional again, what else do we observe? \u00a0Many have noted that if the consequent of a conditional is false, and the conditional is true, then the antecedent of the conditional must be false. \u00a0Written out as a semantic check on arguments, this will be:\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
            <\/td>\r\n<\/td>\r\npremise<\/strong><\/td>\r\npremise<\/strong><\/td>\r\n<\/td>\r\n<\/tr>\r\n
            \u03a6<\/strong><\/td>\r\n\u03a8<\/strong><\/td>\r\n(\u03a6\u2192\u03a8)<\/strong><\/td>\r\n\u00ac\u03a8<\/strong><\/td>\r\n\u00ac\u03a6<\/strong><\/td>\r\n<\/tr>\r\n
            T<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\n<\/tr>\r\n
            T<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\n<\/tr>\r\n
            F<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\n<\/tr>\r\n
            F<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n(Remember how we have filled out the truth table. \u00a0We referred to those truth tables used to define \u201c\u2192\u201d and \u201c\u00ac\u201d<\/span>, and then for each row of this table above, we filled out the values in each column based on that definition.)\r\n\r\nWhat we observe from this truth table is that when both (\u03a6<\/strong>\u2192\u03a8<\/strong>)<\/span>\u00a0and \u00ac\u03a8<\/strong><\/span>\u00a0<\/strong>are true, then \u00ac\u03a6<\/strong><\/span>\u00a0<\/strong>is true. \u00a0Namely, this can be seen in the last row of the truth table.\r\n\r\nThis rule, like the last, is old, and has a well-established name: \u00a0\u201cmodus tollens\u201d. \u00a0We represent it schematically with\r\n

            (\u03a6<\/strong>\u2192\u03a8<\/strong>)<\/span><\/p>\r\n

            \u00ac\u03a8<\/strong><\/span><\/p>\r\n

            _____<\/span><\/p>\r\n

            \u00ac\u03a6<\/strong><\/span><\/p>\r\nWhat about negation? \u00a0If we know a sentence is false, then this fact alone does not tell us about any other sentence. \u00a0But what if we consider a negated negation sentence? \u00a0Such a sentence has the following truth table.\r\n\r\n\r\n\r\n\r\n\r\n
            \u03a6<\/th>\r\n\u00ac\u00ac\u03a6<\/th>\r\n<\/tr>\r\n
            T<\/strong><\/em><\/td>\r\nT<\/strong><\/em><\/td>\r\n<\/tr>\r\n
            F<\/strong><\/em><\/td>\r\nF<\/strong><\/em><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nWe can introduce a rule that takes advantage of this observation. \u00a0In fact, it is traditional to introduce two rules, and lump them together under a common name. \u00a0The rules\u2019 name is \u201cdouble negation<\/strong>\u201d. \u00a0Basically, the rule says we can add or take away two negations any time. \u00a0Here are the two schemas for the two rules:\r\n
            \r\n

            \u03a6<\/strong><\/p>\r\n

            _____<\/span><\/p>\r\n

            \u00ac\u00ac<\/span>\u03a6<\/strong><\/p>\r\n\r\n<\/div>\r\nand\r\n

            \u00ac\u00ac<\/span>\u03a6<\/strong><\/p>\r\n

            _____<\/span><\/p>\r\n

            \u03a6<\/strong><\/p>\r\nFinally, it is sometimes helpful to be able to repeat a line. \u00a0Technically, this is an unnecessary rule, but if a proof gets long, we often find it easier to understand the proof if we write a line over again later when we find we need it again. \u00a0So we introduce the rule \u201crepeat<\/strong>\u201d.\r\n

            \u03a6<\/strong><\/p>\r\n

            _____<\/span><\/p>\r\n

            \u03a6<\/strong><\/p>\r\n\r\n

            \r\n

            Check for Understanding<\/p>\r\n\r\n<\/header>\r\n

            \r\n
              \r\n \t
            1. Critical Thinking Task:<\/strong> Compare the two formal proofs \"modus ponens\" and \"modus tollens.\" How can they be applied to your arguments?<\/li>\r\n<\/ol>\r\n<\/div>\r\n<\/div>\r\n

              4.4 \u00a0An example<\/h2>\r\nHere is an example that will make use of all three rules. \u00a0Consider the following argument:\r\n

              (Q<\/strong>\u2192P<\/strong>)<\/span><\/p>\r\n

              (\u00acQ<\/strong>\u2192R<\/strong>) <\/span><\/p>\r\n

              \u00acR<\/strong><\/span><\/p>\r\n

              _____<\/span><\/p>\r\n

              P<\/span><\/strong><\/p>\r\nWe want to check this argument to see if it is valid.\r\n\r\nTo do a direct proof, we number the premises so that we can refer to them when using inference rules.\r\n\r\n\"\"\r\n\r\nAnd, now, we apply our inference rules. \u00a0Sometimes, it can be hard to see how to complete a proof. \u00a0In the worst case, where you are uncertain of how to proceed, you can apply all the rules that you see are applicable and then, assess if you have gotten closer to the conclusion; and repeat this process. \u00a0Here in any case is a direct proof of the sought conclusion.\r\n\r\n\"\"\r\n\r\nDeveloping skill at completing proofs merely requires practice. \u00a0You should strive to do as many problems as you can.\r\n

              4.5 \u00a0Problems<\/h2>\r\n
                \r\n \t
              1. Critical Thinking Task:\u00a0<\/strong>Create a brief lesson on how to use the rules modus ponens, modus tollens, and double negation in the proof of an argument.<\/li>\r\n \t
              2. Complete a direct derivation<\/strong> (also called a \u201cdirect proof\u201d) for each of the following arguments, showing that it is valid. You will need the rules modus ponens, modus tollens, and double negation.\r\n
                  \r\n \t
                1. Premises: (P<\/strong>\u2192Q<\/strong>)<\/span>, \u00ac\u00acP<\/strong><\/span>. Show: \u00ac\u00acQ<\/strong><\/span>.<\/li>\r\n \t
                2. Premises: Q<\/span><\/strong>, (\u00acP<\/strong>\u2192\u00acQ<\/strong>)<\/span>. Show: P<\/span><\/strong>.<\/li>\r\n \t
                3. Premises: \u00acQ<\/strong><\/span>, (\u00acQ<\/strong>\u2192S<\/strong>)<\/span>. Show: S<\/span><\/strong>.<\/li>\r\n \t
                4. Premises: \u00acS<\/strong><\/span>, (\u00acQ<\/strong>\u2192S<\/strong>)<\/span>. Show: Q<\/span><\/strong>.<\/li>\r\n \t
                5. Premises: (S<\/strong>\u2192\u00acQ<\/strong>)<\/span>, (P<\/strong>\u2192S<\/strong>)<\/span>, \u00ac\u00acP<\/strong><\/span>. Show: \u00acQ<\/strong><\/span>.<\/li>\r\n \t
                6. Premises: (T<\/strong>\u2192P<\/strong>)<\/span>, (Q<\/strong>\u2192S<\/strong>)<\/span>, (S<\/strong>\u2192T<\/strong>)<\/span>, \u00acP<\/strong><\/span>. Show: \u00acQ<\/strong><\/span>.<\/li>\r\n \t
                7. Premises: R<\/strong>, P<\/strong>, (P <\/strong><\/span>\u2192<\/span>\u00a0(R <\/strong><\/span>\u2192<\/span>\u00a0Q<\/strong>))<\/span>. Show: Q<\/span><\/strong>.<\/li>\r\n \t
                8. Premises: ((R<\/strong>\u2192S<\/strong>)\u2192Q<\/strong>)<\/span>, \u00acQ<\/strong><\/span>, (\u00ac(R<\/strong>\u2192S<\/strong>)\u2192V<\/strong>)<\/span>. Show: V<\/span><\/strong>.<\/li>\r\n \t
                9. Premises: \u00a0(P<\/strong>\u2192(Q<\/strong>\u2192R<\/strong>))<\/span>,\u00a0\u00ac(Q<\/strong>\u2192R<\/strong>)<\/span>. \u00a0Show: \u00a0\u00acP<\/strong><\/span>.<\/li>\r\n \t
                10. Premises: \u00a0(\u00ac(Q<\/strong>\u2192R<\/strong>)\u2192P<\/strong>)<\/span>, \u00acP<\/strong><\/span>, Q<\/span><\/strong>. Show: \u00a0R<\/span><\/strong>.<\/li>\r\n \t
                11. Premises: \u00a0P<\/span><\/strong>, (P<\/strong>\u2192R<\/strong>)<\/span>, (P<\/strong>\u2192(R<\/strong>\u2192Q<\/strong>))<\/span>. \u00a0Show: \u00a0Q<\/span><\/strong>.<\/li>\r\n \t
                12. Premises: \u00a0\u00acR<\/strong><\/span>, (S<\/strong>\u2192R<\/strong>)<\/span>, P<\/span><\/strong>, (P<\/strong>\u2192(T<\/strong>\u2192S<\/strong>))<\/span>. \u00a0Show: \u00a0\u00acT<\/strong><\/span>.<\/li>\r\n \t
                13. Premises: \u00a0P<\/span><\/strong>, (P<\/strong>\u2192Q<\/strong>)<\/span>, (P<\/strong>\u2192R<\/strong>)<\/span>, (Q<\/strong>\u2192(R<\/strong>\u2192S<\/strong>))<\/span>. \u00a0Show: \u00a0S<\/span><\/strong>.<\/li>\r\n \t
                14. Premises: \u00a0(P<\/strong>\u2192(Q<\/strong>\u2192R<\/strong>))<\/span>, P<\/span><\/strong>, ((Q<\/strong>\u2192R<\/strong>)\u2192\u00acS<\/strong>))<\/span>, ((T<\/strong>\u2192V<\/strong>)\u2192S<\/strong>)<\/span>. \u00a0Show: \u00a0\u00ac(T<\/strong>\u2192V<\/strong>)<\/span>.<\/li>\r\n<\/ol>\r\n<\/li>\r\n \t
                15. In normal colloquial English, write your own valid argument with at least two premises. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like logic). \u00a0Translate it into propositional logic and use a direct proof to show it is valid.<\/li>\r\n \t
                16. In normal colloquial English, write your own valid argument with at least three premises. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like logic). \u00a0Translate it into propositional logic and use a direct proof to show it is valid.<\/li>\r\n \t
                17. Make your own key to translate into propositional logic the portions of the following argument that are in bold. \u00a0Using a direct proof, prove that the resulting argument is valid.<\/li>\r\n<\/ol>\r\nInspector Tarski told his assistant, Mr. Carroll, \u201cIf Wittgenstein had mud on his boots, then he was in the field<\/span><\/strong>. \u00a0Furthermore, if Wittgenstein was in the field, then he is the prime suspect for the murder of Dodgson<\/strong>. \u00a0Wittgenstein did have mud on his boots<\/strong>.<\/span>\u00a0 We conclude, Wittgenstein is the prime suspect for the murder of Dodgson<\/strong>.<\/span>\u201d","rendered":"

                  4.1 \u00a0A problem with semantic demonstrations of validity<\/h2>\n
                  \n
                  \n

                  Pre-Reading Questions<\/p>\n<\/header>\n

                  \n
                    \n
                  1. What\u2019s the purpose of writing a formal proof in logic?<\/li>\n
                  2. How does a derivation differ from simply identifying a conclusion?<\/li>\n
                  3. Why is it important to keep track of assumptions in a proof?<\/li>\n
                  4. What strategies might help when you’re stuck and can\u2019t immediately see how to derive a conclusion?<\/li>\n<\/ol>\n<\/div>\n<\/div>\n
                    \n
                    \n

                    Key Terms<\/p>\n<\/header>\n

                    \n
                      \n
                    • Proof<\/strong> – a sequence of statements that demonstrates the truth of a proposition (a statement that can be either true or false) by deriving it from a set of accepted truths (axioms or premises) using valid rules of inference.<\/li>\n
                    • Derivation<\/strong> – a step-by-step process of demonstrating the validity of an argument by showing how a conclusion can be logically derived from a set of premises using established rules of inference.<\/li>\n
                    • Premise<\/strong> – a statement that is assumed to be true and is used as evidence or support for a conclusion.<\/li>\n
                    • Conclusion<\/strong> – a statement that follows directly and reasonably from the evidence or premises presented.<\/li>\n
                    • Justification Rule<\/strong> – a principle that allows us to infer a justified conclusion from justified premises.<\/li>\n
                    • Subproof<\/strong> – a proof within a larger proof, often used to derive a conditional statement or to demonstrate a proof by contradiction.<\/li>\n
                    • Goal-Directed Strategy<\/strong> – a plan or course of action designed to achieve a specific, predefined objective or desired outcome.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n

                      Given that we can test an argument for validity, it might seem that we have a fully developed system to study arguments. \u00a0However, there is a significant practical difficulty with our semantic method of checking arguments using truth tables (you may have already noted what this practical difficulty is, when you did problems 1e and 2e of chapter 3). \u00a0Consider the following argument:<\/p>\n

                      Jasmine will go to the party.<\/p>\n

                      If Jasmine will go to the party, then Helena will.<\/p>\n

                      If Helena will go to the party, then Fatima will.<\/p>\n

                      If Fatima will go to the party, then Olivia will.<\/p>\n

                      If Olivia will go to the party, then Elizabeth will.<\/p>\n

                      If Elizabeth will go to the party, then Mia will.<\/p>\n

                      If Mia will go to the party, then Giada will.<\/p>\n

                      If Giada will go to the party, then Hillary will.<\/p>\n

                      If Hillary will go to the party, then Chen will.<\/p>\n

                      If Chen will go to the party, then Julie will.<\/p>\n

                      _____<\/p>\n

                      Julie will go to the party.<\/p>\n

                      Most of us will agree that this argument is valid. \u00a0It has a rather simple form, in which one sentence is related to the previous sentence, so that we can see the conclusion follows from the premises<\/strong>. \u00a0Without bothering to make a translation key, we can see the argument has the following form.<\/p>\n

                      P<\/span><\/strong><\/p>\n

                      (P<\/strong><\/span>\u2192Q<\/strong>)<\/span><\/p>\n

                      (Q<\/strong>\u2192R<\/strong>)<\/span><\/p>\n

                      (R<\/strong>\u2192S<\/strong>)<\/span><\/p>\n

                      (S<\/strong>\u2192T<\/strong>)<\/span><\/p>\n

                      (T<\/strong>\u2192U<\/strong>)<\/span><\/p>\n

                      (U<\/strong>\u2192V<\/strong>)<\/span><\/p>\n

                      (V<\/strong>\u2192W<\/strong>)<\/span><\/p>\n

                      (W<\/strong>\u2192X<\/strong>)<\/span><\/p>\n

                      (X<\/strong>\u2192Y<\/strong>)<\/span><\/p>\n

                      _____<\/span><\/p>\n

                      Y<\/span><\/strong><\/p>\n

                      However, if we are going to check this argument, then the truth table will require 1024 rows! \u00a0This follows directly from our observation that for arguments or sentences composed of n atomic sentences, the truth table will require 2n<\/span><\/span>\u00a0rows. \u00a0This argument contains 10 atomic sentences. \u00a0A truth table checking its validity must have 210<\/span>\u00a0<\/span>rows, and 210<\/span><\/span>=1024. \u00a0Furthermore, it would be trivial to extend the argument for another, say, ten steps, but then the truth table that we make would require more than a million rows!<\/p>\n

                      For this reason, and for several others (which become evident later, when we consider more advanced logic), it is very valuable to develop a syntactic proof method. \u00a0That is, a way to check proofs not using a truth table, but rather using rules of syntax.<\/p>\n

                      Here is the idea that we will pursue. \u00a0A valid argument is an argument such that, necessarily, if the premises are true, then the conclusion<\/strong> is true. \u00a0We will start just with our premises. \u00a0We will set aside the conclusion, only to remember it as a goal. \u00a0Then, we will aim to find a reliable way to introduce another sentence into the argument, with the special property that, if the premises are true, then this single additional sentence to the argument must also be true. \u00a0If we could find a method to do that, and if after repeated applications of this method we were able to write down our conclusion, then we would know that, necessarily, if our premises are true then the conclusion is true.<\/p>\n

                      The idea is more clear when we demonstrate it. \u00a0The method for introducing new sentences will be called \u201cinference rules\u201d. \u00a0We introduce our first inference rules for the conditional. \u00a0Remember the truth table for the conditional:<\/p>\n\n\n\n\n\n\n\n
                      \u03a6 \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/th>\n\u03a8<\/span><\/th>\n(\u03a6\u2192\u03a8)<\/span><\/th>\n<\/tr>\n
                      T \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/strong><\/td>\nT<\/span><\/strong><\/td>\nT<\/span><\/strong><\/td>\n<\/tr>\n
                      T \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/strong><\/td>\nF<\/span><\/strong><\/td>\nF<\/span><\/strong><\/td>\n<\/tr>\n
                      F \u00a0 \u00a0 \u00a0 \u00a0<\/span><\/strong><\/td>\nT<\/span><\/strong><\/td>\nT<\/span><\/strong><\/td>\n<\/tr>\n
                      F \u00a0 \u00a0 \u00a0\u00a0<\/span><\/strong><\/td>\nF<\/span><\/strong><\/td>\nT<\/span><\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                      Look at this for a moment. \u00a0If we have a conditional like (P<\/strong>\u2192Q<\/strong>)<\/span>\u00a0(looking at the truth table above, remember that this would meant that we let \u03a6<\/span>\u00a0<\/strong>be P<\/span>\u00a0<\/strong>and \u03a8<\/span>\u00a0<\/strong>be Q<\/span><\/strong>), do we know whether any other sentence is true? \u00a0From (P<\/strong><\/span>\u2192Q<\/strong>)<\/span>\u00a0alone we do not. \u00a0Even if (P<\/strong>\u2192Q<\/strong>)<\/span>\u00a0is true, P<\/span>\u00a0<\/strong>could be false or Q<\/span>\u00a0<\/strong>could be false. \u00a0But what if we have some additional information? \u00a0Suppose we have as premises both (P<\/strong><\/span>\u2192Q<\/strong>)<\/span>\u00a0and P<\/span><\/strong>. \u00a0Then, we would know that if those premises were true, Q<\/span>\u00a0<\/strong>must be true. \u00a0We have already checked this with a truth table.<\/p>\n\n\n\n\n\n\n\n\n
                      <\/td>\n<\/td>\npremise<\/strong><\/td>\n\u00a0premise<\/strong><\/td>\n<\/td>\n<\/tr>\n
                      P<\/strong><\/td>\nQ<\/strong><\/td>\n(P\u2192Q)<\/strong><\/td>\nP<\/strong><\/td>\nQ<\/strong><\/td>\n<\/tr>\n
                      T<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\n<\/tr>\n
                      T<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\n<\/tr>\n
                      F<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\n<\/tr>\n
                      F<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                      The first row of the truth table is the only row where all of the premises are true; and for it, we find that Q<\/span>\u00a0<\/strong>is true. \u00a0This, of course, generalizes to any conditional. \u00a0That is, we have that:<\/p>\n\n\n\n\n\n\n\n\n
                      <\/td>\n<\/td>\npremise<\/strong><\/td>\npremise<\/strong><\/td>\n<\/td>\n<\/tr>\n
                      \u03a6<\/strong><\/td>\n\u03a8<\/strong><\/td>\n(\u03a6\u2192\u03a8)<\/strong><\/td>\n\u03a6<\/strong><\/td>\n\u03a8<\/strong><\/td>\n<\/tr>\n
                      T<\/em><\/td>\nT<\/em><\/td>\nT<\/em><\/td>\nT<\/em><\/td>\nT<\/em><\/td>\n<\/tr>\n
                      T<\/em><\/td>\nF<\/em><\/td>\nF<\/em><\/td>\nT<\/em><\/td>\nF<\/em><\/td>\n<\/tr>\n
                      F<\/em><\/td>\nT<\/em><\/td>\nT<\/em><\/td>\nF<\/em><\/td>\nT<\/em><\/td>\n<\/tr>\n
                      F<\/em><\/td>\nF<\/em><\/td>\nT<\/em><\/td>\nF<\/em><\/td>\nF<\/em><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                      We now capture this insight not using a truth table, but by introducing a rule. \u00a0The rule we will write out like this:<\/p>\n

                      (<\/span>\u03a6<\/strong>\u2192<\/span>\u03a8<\/strong>)<\/span><\/p>\n

                      \u03a6<\/strong><\/p>\n

                      _____<\/span><\/p>\n

                      \u03a8<\/strong><\/p>\n

                      This is a syntactic rule. \u00a0It is saying that whenever we have written down a formula in our language that has the shape of the first row (that is, whenever we have a conditional), and whenever we also have written down a formula that has the shape in the second row (that is, whenever we also have written down the antecedent of the conditional), then go ahead, whenever you like, and write down a formula like that in the third row (the consequent of the conditional). \u00a0The rule talks about the shape of the formulas, not their meaning. \u00a0But of course we justified<\/strong> the rule by looking at the meanings.<\/p>\n

                      We describe this by saying that the third line is \u201cderived\u201d from the earlier two lines using the inference rule.<\/p>\n

                      This inference rule is old. \u00a0We are, therefore, stuck with its well-established, but not very enlightening, name: \u00a0\u201cmodus ponens\u201d. \u00a0Thus, we say, for the above example, that the third line is derived from the earlier two lines using modus ponens.<\/p>\n

                      \n
                      \n

                      Check for Understanding<\/p>\n<\/header>\n

                      \n
                        \n
                      1. The text presents an argument about ten people attending a party. Create your own similar argument with a different subject matter that would have the same logical structure.<\/li>\n
                      2. If we were to extend the party argument to include 20 people instead of 10, how many rows would the truth table require? What does this tell us about the scalability of truth tables for checking validity?<\/li>\n<\/ol>\n<\/div>\n<\/div>\n

                        4.2 \u00a0Direct proof<\/h2>\n

                        We need one more concept: \u00a0that of a proof<\/strong>. \u00a0Specifically, we\u2019ll start with the most fundamental kind of proof, which is called a “direct proof.” \u00a0The idea of a direct proof is: \u00a0we write down as numbered lines the premises of our argument. \u00a0Then, after this, we can write down any line that is justified by an application of an inference rule to earlier lines in the proof. \u00a0When we write down our conclusion, we are done.<\/p>\n

                        Let us make a proof of the simple argument above, which has premises (P<\/strong>\u2192Q<\/strong>)<\/span>\u00a0and P<\/span><\/strong>, and conclusion Q<\/span><\/strong>. \u00a0We start by writing down the premises and numbering them. \u00a0 There is a useful bit of notation that we can introduce at this point. \u00a0It is known as a \u201cFitch bar\u201d, named after a logician Frederic Fitch, who developed this technique. \u00a0We will write a vertical bar to the left, with a horizontal line indicating that the premises are above the line.<\/p>\n

                        \"\"<\/p>\n

                        It is also helpful to identify where these steps came from. \u00a0We can do that with a little explanation written out to the right.<\/p>\n

                        \"\"<\/p>\n

                        Now, we are allowed to write down any line that follows from an earlier line using an inference rule.<\/p>\n

                        \"\"<\/p>\n

                        And, finally, we want a reader to understand what rule we used, so we add that into our explanation, identifying the rule and the lines used.<\/p>\n

                        \"\"<\/p>\n

                        That is a complete direct proof.<\/p>\n

                        Notice a few things. \u00a0The numbering of each line, and the explanations to the right, are bookkeeping; they are not part of our argument, but rather are used to explain our argument. \u00a0However, always do them because, it is hard to understand a proof without them. \u00a0Also, note that our idea is that the inference rule can be applied to any earlier line, including lines themselves derived using inference rules. \u00a0It is not just premises to which we can apply an inference rule. \u00a0Finally, note that we have established that this argument must be valid. \u00a0From the premises, and an inference rule that preserves validity, we have arrived at the conclusion. \u00a0Necessarily, the conclusion is true, if the premises are true.<\/p>\n

                        The long argument that we started the chapter with can now be given a direct proof.<\/p>\n

                        \"\"<\/p>\n

                        From repeated applications of modus ponens, we arrived at the conclusion. \u00a0If lines 1 through 10 are true, line 19 must be true. \u00a0The argument is valid. \u00a0And, we completed it with 19 steps, as opposed to writing out 1024 rows of a truth table.<\/p>\n

                        We can see now one of the very important features of understanding the difference between syntax and semantics. \u00a0Our goal is to make the syntax of our language perfectly mirror its semantics. \u00a0By manipulating symbols, we manage to say something about the world. \u00a0This is a strange fact, one that underlies one of the deeper possibilities of language, and also, ultimately, of computers.<\/p>\n

                        \n
                        \n

                        Check for Understanding<\/p>\n<\/header>\n

                        \n
                          \n
                        1. Critical Thinking Task:\u00a0<\/strong>Describe the purpose of the “Fitch bar” when evaluating proofs.<\/li>\n<\/ol>\n<\/div>\n<\/div>\n

                          4.3 \u00a0Other inference rules<\/h2>\n
                          \n
                          \n

                          Key Terms<\/p>\n<\/header>\n

                          \n
                            \n
                          • Double-Negation Rule\u00a0<\/strong>– the rule that any premise or conclusion can be added or subtracted if they are negated twice.<\/li>\n
                          • Repeat<\/strong> – if proof of an argument becomes long, and a particular line is necessary again later in the proof, then this rule allows an identical line to be repeated logically.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n

                            We can now introduce other inference rules. \u00a0Looking at the truth table for the conditional again, what else do we observe? \u00a0Many have noted that if the consequent of a conditional is false, and the conditional is true, then the antecedent of the conditional must be false. \u00a0Written out as a semantic check on arguments, this will be:<\/p>\n\n\n\n\n\n\n\n\n
                            <\/td>\n<\/td>\npremise<\/strong><\/td>\npremise<\/strong><\/td>\n<\/td>\n<\/tr>\n
                            \u03a6<\/strong><\/td>\n\u03a8<\/strong><\/td>\n(\u03a6\u2192\u03a8)<\/strong><\/td>\n\u00ac\u03a8<\/strong><\/td>\n\u00ac\u03a6<\/strong><\/td>\n<\/tr>\n
                            T<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\n<\/tr>\n
                            T<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\n<\/tr>\n
                            F<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\n<\/tr>\n
                            F<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                            (Remember how we have filled out the truth table. \u00a0We referred to those truth tables used to define \u201c\u2192\u201d and \u201c\u00ac\u201d<\/span>, and then for each row of this table above, we filled out the values in each column based on that definition.)<\/p>\n

                            What we observe from this truth table is that when both (\u03a6<\/strong>\u2192\u03a8<\/strong>)<\/span>\u00a0and \u00ac\u03a8<\/strong><\/span>\u00a0<\/strong>are true, then \u00ac\u03a6<\/strong><\/span>\u00a0<\/strong>is true. \u00a0Namely, this can be seen in the last row of the truth table.<\/p>\n

                            This rule, like the last, is old, and has a well-established name: \u00a0\u201cmodus tollens\u201d. \u00a0We represent it schematically with<\/p>\n

                            (\u03a6<\/strong>\u2192\u03a8<\/strong>)<\/span><\/p>\n

                            \u00ac\u03a8<\/strong><\/span><\/p>\n

                            _____<\/span><\/p>\n

                            \u00ac\u03a6<\/strong><\/span><\/p>\n

                            What about negation? \u00a0If we know a sentence is false, then this fact alone does not tell us about any other sentence. \u00a0But what if we consider a negated negation sentence? \u00a0Such a sentence has the following truth table.<\/p>\n\n\n\n\n\n
                            \u03a6<\/th>\n\u00ac\u00ac\u03a6<\/th>\n<\/tr>\n
                            T<\/strong><\/em><\/td>\nT<\/strong><\/em><\/td>\n<\/tr>\n
                            F<\/strong><\/em><\/td>\nF<\/strong><\/em><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                            We can introduce a rule that takes advantage of this observation. \u00a0In fact, it is traditional to introduce two rules, and lump them together under a common name. \u00a0The rules\u2019 name is \u201cdouble negation<\/strong>\u201d. \u00a0Basically, the rule says we can add or take away two negations any time. \u00a0Here are the two schemas for the two rules:<\/p>\n

                            \n

                            \u03a6<\/strong><\/p>\n

                            _____<\/span><\/p>\n

                            \u00ac\u00ac<\/span>\u03a6<\/strong><\/p>\n<\/div>\n

                            and<\/p>\n

                            \u00ac\u00ac<\/span>\u03a6<\/strong><\/p>\n

                            _____<\/span><\/p>\n

                            \u03a6<\/strong><\/p>\n

                            Finally, it is sometimes helpful to be able to repeat a line. \u00a0Technically, this is an unnecessary rule, but if a proof gets long, we often find it easier to understand the proof if we write a line over again later when we find we need it again. \u00a0So we introduce the rule \u201crepeat<\/strong>\u201d.<\/p>\n

                            \u03a6<\/strong><\/p>\n

                            _____<\/span><\/p>\n

                            \u03a6<\/strong><\/p>\n

                            \n
                            \n

                            Check for Understanding<\/p>\n<\/header>\n

                            \n
                              \n
                            1. Critical Thinking Task:<\/strong> Compare the two formal proofs “modus ponens” and “modus tollens.” How can they be applied to your arguments?<\/li>\n<\/ol>\n<\/div>\n<\/div>\n

                              4.4 \u00a0An example<\/h2>\n

                              Here is an example that will make use of all three rules. \u00a0Consider the following argument:<\/p>\n

                              (Q<\/strong>\u2192P<\/strong>)<\/span><\/p>\n

                              (\u00acQ<\/strong>\u2192R<\/strong>) <\/span><\/p>\n

                              \u00acR<\/strong><\/span><\/p>\n

                              _____<\/span><\/p>\n

                              P<\/span><\/strong><\/p>\n

                              We want to check this argument to see if it is valid.<\/p>\n

                              To do a direct proof, we number the premises so that we can refer to them when using inference rules.<\/p>\n

                              \"\"<\/p>\n

                              And, now, we apply our inference rules. \u00a0Sometimes, it can be hard to see how to complete a proof. \u00a0In the worst case, where you are uncertain of how to proceed, you can apply all the rules that you see are applicable and then, assess if you have gotten closer to the conclusion; and repeat this process. \u00a0Here in any case is a direct proof of the sought conclusion.<\/p>\n

                              \"\"<\/p>\n

                              Developing skill at completing proofs merely requires practice. \u00a0You should strive to do as many problems as you can.<\/p>\n

                              4.5 \u00a0Problems<\/h2>\n
                                \n
                              1. Critical Thinking Task:\u00a0<\/strong>Create a brief lesson on how to use the rules modus ponens, modus tollens, and double negation in the proof of an argument.<\/li>\n
                              2. Complete a direct derivation<\/strong> (also called a \u201cdirect proof\u201d) for each of the following arguments, showing that it is valid. You will need the rules modus ponens, modus tollens, and double negation.\n
                                  \n
                                1. Premises: (P<\/strong>\u2192Q<\/strong>)<\/span>, \u00ac\u00acP<\/strong><\/span>. Show: \u00ac\u00acQ<\/strong><\/span>.<\/li>\n
                                2. Premises: Q<\/span><\/strong>, (\u00acP<\/strong>\u2192\u00acQ<\/strong>)<\/span>. Show: P<\/span><\/strong>.<\/li>\n
                                3. Premises: \u00acQ<\/strong><\/span>, (\u00acQ<\/strong>\u2192S<\/strong>)<\/span>. Show: S<\/span><\/strong>.<\/li>\n
                                4. Premises: \u00acS<\/strong><\/span>, (\u00acQ<\/strong>\u2192S<\/strong>)<\/span>. Show: Q<\/span><\/strong>.<\/li>\n
                                5. Premises: (S<\/strong>\u2192\u00acQ<\/strong>)<\/span>, (P<\/strong>\u2192S<\/strong>)<\/span>, \u00ac\u00acP<\/strong><\/span>. Show: \u00acQ<\/strong><\/span>.<\/li>\n
                                6. Premises: (T<\/strong>\u2192P<\/strong>)<\/span>, (Q<\/strong>\u2192S<\/strong>)<\/span>, (S<\/strong>\u2192T<\/strong>)<\/span>, \u00acP<\/strong><\/span>. Show: \u00acQ<\/strong><\/span>.<\/li>\n
                                7. Premises: R<\/strong>, P<\/strong>, (P <\/strong><\/span>\u2192<\/span>\u00a0(R <\/strong><\/span>\u2192<\/span>\u00a0Q<\/strong>))<\/span>. Show: Q<\/span><\/strong>.<\/li>\n
                                8. Premises: ((R<\/strong>\u2192S<\/strong>)\u2192Q<\/strong>)<\/span>, \u00acQ<\/strong><\/span>, (\u00ac(R<\/strong>\u2192S<\/strong>)\u2192V<\/strong>)<\/span>. Show: V<\/span><\/strong>.<\/li>\n
                                9. Premises: \u00a0(P<\/strong>\u2192(Q<\/strong>\u2192R<\/strong>))<\/span>,\u00a0\u00ac(Q<\/strong>\u2192R<\/strong>)<\/span>. \u00a0Show: \u00a0\u00acP<\/strong><\/span>.<\/li>\n
                                10. Premises: \u00a0(\u00ac(Q<\/strong>\u2192R<\/strong>)\u2192P<\/strong>)<\/span>, \u00acP<\/strong><\/span>, Q<\/span><\/strong>. Show: \u00a0R<\/span><\/strong>.<\/li>\n
                                11. Premises: \u00a0P<\/span><\/strong>, (P<\/strong>\u2192R<\/strong>)<\/span>, (P<\/strong>\u2192(R<\/strong>\u2192Q<\/strong>))<\/span>. \u00a0Show: \u00a0Q<\/span><\/strong>.<\/li>\n
                                12. Premises: \u00a0\u00acR<\/strong><\/span>, (S<\/strong>\u2192R<\/strong>)<\/span>, P<\/span><\/strong>, (P<\/strong>\u2192(T<\/strong>\u2192S<\/strong>))<\/span>. \u00a0Show: \u00a0\u00acT<\/strong><\/span>.<\/li>\n
                                13. Premises: \u00a0P<\/span><\/strong>, (P<\/strong>\u2192Q<\/strong>)<\/span>, (P<\/strong>\u2192R<\/strong>)<\/span>, (Q<\/strong>\u2192(R<\/strong>\u2192S<\/strong>))<\/span>. \u00a0Show: \u00a0S<\/span><\/strong>.<\/li>\n
                                14. Premises: \u00a0(P<\/strong>\u2192(Q<\/strong>\u2192R<\/strong>))<\/span>, P<\/span><\/strong>, ((Q<\/strong>\u2192R<\/strong>)\u2192\u00acS<\/strong>))<\/span>, ((T<\/strong>\u2192V<\/strong>)\u2192S<\/strong>)<\/span>. \u00a0Show: \u00a0\u00ac(T<\/strong>\u2192V<\/strong>)<\/span>.<\/li>\n<\/ol>\n<\/li>\n
                                15. In normal colloquial English, write your own valid argument with at least two premises. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like logic). \u00a0Translate it into propositional logic and use a direct proof to show it is valid.<\/li>\n
                                16. In normal colloquial English, write your own valid argument with at least three premises. Your argument should just be a paragraph (not an ordered list of sentences or anything else that looks like logic). \u00a0Translate it into propositional logic and use a direct proof to show it is valid.<\/li>\n
                                17. Make your own key to translate into propositional logic the portions of the following argument that are in bold. \u00a0Using a direct proof, prove that the resulting argument is valid.<\/li>\n<\/ol>\n

                                  Inspector Tarski told his assistant, Mr. Carroll, \u201cIf Wittgenstein had mud on his boots, then he was in the field<\/span><\/strong>. \u00a0Furthermore, if Wittgenstein was in the field, then he is the prime suspect for the murder of Dodgson<\/strong>. \u00a0Wittgenstein did have mud on his boots<\/strong>.<\/span>\u00a0 We conclude, Wittgenstein is the prime suspect for the murder of Dodgson<\/strong>.<\/span>\u201d<\/p>\n","protected":false},"author":158,"menu_order":4,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":"cc-by-nc-sa"},"chapter-type":[],"contributor":[],"license":[56],"class_list":["post-37","chapter","type-chapter","status-publish","hentry","license-cc-by-nc-sa"],"part":27,"_links":{"self":[{"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/pressbooks\/v2\/chapters\/37","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/wp\/v2\/users\/158"}],"version-history":[{"count":20,"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/pressbooks\/v2\/chapters\/37\/revisions"}],"predecessor-version":[{"id":344,"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/pressbooks\/v2\/chapters\/37\/revisions\/344"}],"part":[{"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/pressbooks\/v2\/parts\/27"}],"metadata":[{"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/pressbooks\/v2\/chapters\/37\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/wp\/v2\/media?parent=37"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/pressbooks\/v2\/chapter-type?post=37"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/wp\/v2\/contributor?post=37"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/pressbooks.ccconline.org\/introtologic\/wp-json\/wp\/v2\/license?post=37"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}