Tautologies and Simple Proofs in Prop Logic

MODR 1760 A & E 2024-25 L08 Propositional Logic: Tautologies and Simple Proofs in Prop Logic This lecture is based on pp. 243 to 247 of Govier’s text, and reading these pages is a good idea. You can skip the section on ‘Conditional Proof,’ I am not using that section for the Quiz 7 or Test 2. I. Simple Proofs in Propositional Logic The main point of today’s lecture is to teach you to use some valid arguments as ‘steps’ or short cuts to show that an argument is valid. We already know a number of valid arguments in PL as we tested examples for validity with truth-tables. Some logically valid arguments are so famous that they have names. Review these and the examples using them below. Modus Ponens (MP for short): Given PQ and P as premises, Q is a valid conclusion. Modus Tollens (MT for short): Given PQ and ~Q, ~ P follows as a valid conclusion. Here are some new ones: Transposition (Trans): Given P  Q, ~Q  ~P is a valid conclusion. Addition (Add): Given P, conclude P V Q, whatever sentence Q may be. Simplification (Simp): Given P&Q, conclude either P or Q on its own. Conjunction (Conj): Given P, Q separately, conclude P&Q. Disjunctive Syllogism (DS): Given PVQ and ~Q, conclude P. Hypothetical Syllogism (HS): Given P  Q and Q  R, conclude P  R. Constructive Dilemma (CD): Given all 3 of PVQ, P  R, Q  S, conclude R V S. Each of these logical forms is a valid argument that you can recognize as valid because of its logical connectives having this form. These are very useful to be able to recognize, and they show up in many academic, legal and business contexts. They can also be used together to show that other arguments are valid logical forms. We also know that the following pairs of sentences are equivalent to one another: De Morgan (DeM): ~(P&Q) is equivalent to ~PV~Q and ~(PVQ) is equivalent to ~P & ~Q. Double Negation (DN): P is equivalent to ~ ~ P. Implication (Imp): P  Q is equivalent to ~P V Q. This means that each of these logical forms will have the same truth possibilities, and the same meaning as its equivalent form. Equivalent forms can be substituted for one another in a proof. Try to put each of these logical forms into English, or look for examples of them and you will see that many of them are already obviously valid to common sense. Some take more reflection to realize that they are valid. There are a couple of famous invalid forms of argument that a truth-table has revealed to us are never valid, and which have sometimes been confused with the valid forms MP and MT. The first is called affirming the consequent: Do not confuse this with Modus Ponens. (Check the difference by comparing it with MP.) PQ Q Therefore, P. It is Invalid. The second is called Denying the Antecedent: Do not confuse this with Modus Tollens. (Check the difference again.) PQ ~P Therefore, ~Q. Let’s use some of the 12 rules above to construct a simple proof of another argument. Example 1: Suppose I have the passage: “If the pond is polluted, then its water is not good to drink and it does not have any fish living in it. The pond is polluted. Therefore, its water is not good to drink.” This has the logical form: P  (~W & N) P Therefore, ~W P: The pond is polluted. W: The pond’s water is good to drink. N: No fish live in the pond. I think that perhaps this is valid, and I want to check. I proof of ~W can be given from 2 simple steps: First copy over the premises and give them a number. Then consider what rules you can use to help you get to the conclusion. 1. P  (~W & N) 2. P Therefore by MP 3. (~W & N) Then by Simplification. 4. ~W The argument is valid! Example 2: If Shauna has a job parking cars, then Shauna has a driver’s license. But Shauna does not have a driver’s license. Therefore, Shauna does not have a job parking cars and working at the Delta Luxury hotel. 1. P  R. Premise 2. ~R. Premise Therefore by Modus Tollens, 3. ~P And by Addition, 4. ~P V ~Q, and applying DeMorgan’s rule, (~P V ~Q) is equivalent to ~(P & Q) 5. ~ (P&Q). Try the following proof problems now: Use the rules given above. I have posted a separate file with these rules listed in one place it is called: “Prop Rules List.” a. ~A & ~B ~B  C Therefore C. b. P  (QVR) ~Q & ~R Therefore, ~P. c. P ( P V Q)  R Therefore, R. Also do Exercise 4A on p. 248-9 of Govier’s text. I will also provide some questions in the file “Lecture 9 Questions.” II. Tautologies and Contradictions, and Contingent Sentences A tautology in English is a sentence that is always true. an example is “whatever will be, will be.” It is true whatever happens. or “Either the plane will take off, or it will not take off.” Propositional logic can explain these sentences as true in virtue of their logical words. We can show that (Definition) a tautology in propositional logic is a sentence that is true on every row of its truth table. Whatever basic sentences are, (true or false), the whole sentence will be true. Propositional logic tautologies are the logical form of English sentences. Suppose P: The plane will take off. P  ~ P is true. P~P P T F P T F V T T ~P F T Also H  H is a tautology in propositional logic. It translates the English, “If it happens, then it happens.” H T F H T F  T T H T F A contradiction is the opposite of a tautology. When we say something is a contradiction in English it means it is impossible for it to be true. If someone states a contradiction, they are either making a joke, or lying, or trying to show another sentence is false, or talking about something mystical, that cannot be explained. In propositional logic, (Definition) a contradiction is a sentence that gets false for every row of its truth-table. Example of a contradiction: “I am a human being and I am not a human being.” H & ~H H T F H T F & F F ~H F T Most sentences of English and most logical forms are neither tautologies nor contradictions. They are sentences that are true in some circumstances, and false in other circumstances. And we need real world proof to tell us what their truth value is. This is unlike tautologies or contradictions which we can know are true or false by their form only. These sentences are called contingent. In propositional logic, a contingent sentence is one that is neither a tautology or a contradiction. That means (Definition) a contingent sentence has some row that makes it false and some row that makes it true. B T T F F C T F T F B&C T F F F ~(B&C) F T T T Pelham exercises: Use a truth-table to identify each of the following as either a tautology, a contradiction, or a contingent sentence. a.) (A&B)  B b.) (A&~B) & (A  B) c. ) A & (~AVB) d. ) B V (~B & A) e.) ~A  (A B)