Chapter 3: Logic - A Brief History PDF

Chapter 3. Logic A Brief History “Logic will get you from A to B. Imagination will take you everywhere." – Albert Einstein One area of mathematics that has its roots deep in philosophy is the study o...

Chapter 3. Logic A Brief History “Logic will get you from A to B. Imagination will take you everywhere." – Albert Einstein One area of mathematics that has its roots deep in philosophy is the study of logic. Logic is defined as the study of formal reasoning based upon statements or propositions, but it is also commonly defined as a science of correct, critical reasoning. Additionally, logic is also said to be a belief that is supported by factual evidences. Aristotle identified some simple patterns in human reasoning while Leibniz dreamt of reducing reasoning to calculation. As a viable mathematical subject, however, logic is relatively recent: the 19th century pioneers were Bolzano, Boole, Cantor, Dedekind, Frege, Peano, C.S. Pierce, and E. Schroder. From our perspective we see their work as leading to boolean algebra, set theory, propositional logic, predicate logic, as clarifying the foundations of the natural and real number systems, and as introducing suggestive symbolic notation for logical operations. Also, their activity led to the view that logic together with set theory can serve as a basis for all of mathematics. Gottfried Wilhelm Leibniz (1646–1716) was one of the first mathematicians to make a serious study of symbolic logic. Leibniz tried to advance the study of logic from a merely philosophical subject to a formal mathematical subject. Leibniz never completely achieved this goal; however, several mathematicians, such as Augustus De Morgan (1806–1871) and George Boole (1815–1864), contributed to the advancement of symbolic logic as a mathematical discipline. Boole published The Mathematical Analysis of Logic in 1848. In this pamphlet, he argued persuasively that logic should be allied with mathematics, not philosophy. Following this, he published the more extensive work, An Investigation of the Laws of Thought in 1854. Concerning this document, the mathematician Bertrand Russell stated that, “Pure mathematics was discovered by Boole in a work which is called ‘The Laws of Thought’.” 23  The early part of the 20th century was also marked by the so-called foundational crisis in mathematics. A strong impulse for developing mathematical logic came from the attempts during these times to provide solid foundations for mathematics. Mathematical logic has now taken on a life of its own, and also thrives on many interactions with other areas of mathematics and computer science. In the second half of the last century, logic as pursued by mathematicians gradually branched into four main areas: model theory, computability theory (or recursion theory), set theory, and proof theory. The topics in this course are part of the common background of mathematicians active in any of these areas. What distinguishes mathematical logic within mathematics is that statements about mathematical objects and structures are taken seriously as mathematical objects in their own right. More generally, in mathematical logic we formalize (formulate in a precise mathematical way) notions used informally by mathematicians such as: property, statement (in a given language), structure, truth (what it means for a given statement to be true in a given structure), proof (from a given set of axioms), and algorithm. Logic Statement Every language contains different types of sentences, such as statements, questions, and commands. Consider the following statements. “Is the test today?” is a question. “Go get the newspaper” is a command. “This is a nice car” is an opinion. “Denver is the capital of Colorado” is a statement of fact. The symbolic logic that Boole was instrumental in creating applies only to sentences that are statements, the definition of which is given as follows. A statement is a declarative sentence that is either true or false, but not both. Example 1. Determine whether each sentence is a statement. 1. The main campus of the Mindanao State University is in Marawi City. 2. What will be my grade in the course, Mathematics in the Modern World? 3. Open the door. 4. 2 is a negative number. 5. 𝑥 + 1 = 5. 24 Answers: 1. The given sentence is a true statement because it satisfies the definition. It is a declarative sentence that states a fact since the Mindanao State University – Main Campus is in Marawi City. 2. The given sentence is not a statement since it is not a declarative sentence but an interrogative sentence. 3. Since the given sentence is a command, it is not a declarative sentence. It is an imperative sentence; thus, it is not a statement. 4. We all know that 2 is a positive number. This means the sentence “2 is a negative number” is false. However, this is a declarative sentence for it states an opinion. Hence, this is a statement, specifically a false statement. 5. The given sentence is a declarative sentence for it states and opinion. Additionally, we all know that it is true for 𝑥 = 4 and it is false for any other values of 𝑥. This means the sentence is either true or false depending on the value given to 𝑥, and can never be both true and false. Therefore, this is a statement, which is known as open sentence/statement. An open sentence is a statement that involves one or more variables and which becomes true or false when the variables are assigned to specific values. A truth set of an open sentence is the set of all values that will make the open sentence true. Example 2. Determine the truth set of the following open sentence. 1. 𝑥 + 1 = 5 2. 2𝑥 − 3 = 9 3. 𝑥 is a negative number such that 𝑥 2 = 4 4. 𝑥 is an integer such that 𝑥 2 = −16 5. 𝑥 2 − 25 = (𝑥 − 5)(𝑥 + 5), where 𝑥 is real Answers: 1. The only value of 𝑥 that makes the open sentence true is 4. Hence, its truth set is {4}. 2. Similarly, 6 is the only value of 𝑥 that can make the open sentence true. Hence, the truth set is {6}. 25  3. In this given open sentence, we found out that there are two values of 𝑥 that can make “𝑥 2 = 4” correct, that is, 2 and −2. However, it is stated in the sentence that 𝑥 must be negative. This means, 2 is rejected. Hence, the truth set of the given open sentence is {−2}. 4. Noting “𝑥 2 = −16”, 4𝑖 and −4𝑖 are the only values of 𝑥 that can make the equation true. However, the obtained values are not integers. Hence, the truth set for this open sentence is {} or ∅. 5. Any number that is to be substituted to 𝑥 can make the open sentence true. Hence, the truth set is set of real numbers. Simple and Compound Statements A simple statement is a statement that conveys a single idea. If a statement conveys two or more ideas, then it is a compound statement. Connecting simple statements with words and phrases such as “and”, “or”, “if... then”, and “if and only if” creates a compound statement. For instance, “I will attend the meeting or I will go to school” is a compound statement. It is composed of the two simple statements, “I will attend the meeting” and “I will go to school”. The word “or” is a connective for the two simple statements. The truth value of a simple statement is either true (T) or false (F). On the other hand, the truth value of a compound statement depends on the truth values of its simple statements and its connectives. A truth table is a table that shows the truth value of a compound statement for all possible truth values of its simple statements George Boole used symbols such as 𝑝, 𝑞, 𝑟, and 𝑠 to represent simple statements and the symbols ˄, ˅, ~, →, and ↔ to represent connectives. See the following table for a summary: 26  Logic Connectives and Symbols Statement Connective Symbolic form Type of statement not 𝒑 not ~𝑝 Negation 𝒑 and 𝒒 and 𝑝∧𝑞 Conjunction 𝒑 or 𝒒 or 𝑝∨𝑞 Disjunction If 𝒑, then 𝒒 If…then 𝑝→𝑞 Conditional 𝒑 if and only if 𝒒 if and only if 𝑝↔𝑞 Biconditional The negation of an statement 𝑝, denoted by ~𝑝 (to be read as “not 𝑝”), is a statement that says the opposite of 𝑝. This asserts that 𝑝 is false. Thus, if 𝑝 is true, then ~𝑝 is false, and if 𝑝 is false, then ~𝑝 is true. Truth table for ~𝒑 𝒑 ~𝒑 T F F T Example 3. Write the negation of the following statements. 1. 𝑝: Today is Friday. 2. 𝑞: Sheila has two extra pens. 3. 𝑟: The ABS-CBN franchise renewal was not approved by the Philippine Congress. 4. 𝑠: 3𝑥 + 1 = 5 5. 𝑡: Five is greater than 6. Answers. 1. ~𝑝: Today is not Friday. 2. ~𝑞: Sheila does not have two extra pens. 3. ~𝑟: The ABS-CBN franchise renewal was approved by the Philippine Congress. 4. ~𝑠: 3𝑥 + 1 ≠ 5 5. ~𝑡: Five is less than or equal to 6. 27  The conjunction of two statements 𝑝 and 𝑞, denoted by 𝑝 ∧ 𝑞 (and read as “𝑝 and 𝑞”), is true if and only if both 𝑝 and 𝑞 are true. The disjunction of 𝑝 and 𝑞, denoted by 𝑝 ∨ 𝑞 (and read as “𝑝 or 𝑞”), is true if and only if at least one of 𝑝 or 𝑞 is true. Truth Table for 𝒑 ∧ 𝒒 𝒑 𝒒 𝒑∧𝒒 T T T T F F F T F F F F Truth table for 𝒑 ∨ 𝒒 𝑝 𝑞 𝑝∨𝑞 T T T T F T F T T F F F Note. The word “but” is also a conjunction. It is sometimes used to precede a negative phrase. For instance, the statement “I've fallen and I can't get up" means the same as "I've fallen but I can't get up." In either case, if 𝑝 is "I've fallen" and 𝑞 is "I can get up" the conjunction above is symbolized as p ∧ ~q. 28 Example 4. Consider the following simple statements. 𝑝: Today is Friday. 𝑞: It is raining. 𝑟: I am going to a movie. 𝑠: I am not going to the basketball game. Write the following compound statements in symbolic form: 1. Today is Friday and it is raining. 2. It is not raining and I am going to a movie. 3. I am going to the basketball game or I am going to a movie. 4. Today is not Friday and it is not raining. Answers. 1. 𝑝 ∧ 𝑞 3. ∼ 𝑠 ∨ 𝑟 2. ∼ 𝑞 ∧ 𝑟 4. ~𝑝 ∧ ~𝑞 In the next example, we translate symbolic statements into English sentences. Example 5. Consider the following statements: 𝑝: The game will be played in MSU. 𝑞: The game will be shown on ABS-CBN. 𝑟: The game will not be shown on GMA. 𝑠: The Sultans are favored to win. Write each of the following symbolic statements in words: 1. 𝑞˄𝑝 3. ~𝑞 ∧ ~𝑟 2. ~𝑟˄𝑠 4. ~𝑝 ∨ 𝑠 Answers. 1. The game will be shown on ABS-CBN and the game will be played in MSU. 2. The game will be shown on GMA and the Sultans are favored to win. 3. The game will not be shown on ABS-CBN, but the game will be shown on GMA. (This is also correct, “The game will not be shown on ABS-CBN and the game will be shown on GMA.”) 4. The game will not be played in MSU or the Sultans are favored to win. 29 Example 6. Determine whether each statement is true or false. 1. 7 ≥ 5 2. 5 is a whole number and 5 is an even number. 3. 2 is a prime number and 2 is an even number. 4. 0.5 is an integer or a whole number. Solution. 1. 7 ≥ 5 means 7 > 5 or 7 = 5. Now, 𝑝: 7 > 5 is true while 𝑞: 7 = 5 is false. Thus, noting the connective “or”, the statement 7 ≥ 5 is a true statement. 2. The statement “𝑝: 5 is a whole number” is true, and the statement “𝑞: 5 is an even number” is false. Hence, keeping in mind the connective “and”, the truth value of the given statement is false. 3. This is a true statement because each simple statement is true, that is, “𝑝: 2 is a prime number” and “𝑞: 2 is an even number” are both true. 4. The given statement means 0.5 is an integer or 0.5 is a whole number. Hence, this is a false statement because “𝑝: 0.5 is an integer” and “𝑞: 0.5 is a whole number” are both false. Remark. When statements 𝑝, 𝑞, 𝑟, … involves a variable 𝑥, we may also use the notations 𝑝𝑥 , 𝑞𝑥 , 𝑟𝑥 , …, respectively. Negation of Conjunctions and Disjunctions STATEMENT TRUTH SET NEGATION TRUTH SET 𝑝𝑥 ∧ 𝑞𝑥 𝑃∩𝑄 ∼ (𝑝𝑥 ∧ 𝑞𝑥 ) ≡∼ 𝑝𝑥 ∨∼ 𝑞𝑥 𝑃𝐶 ∪ 𝑄𝐶 𝑝𝑥 ∨ 𝑞𝑥 𝑃∪𝑄 ∼ (𝑝𝑥 ∨ 𝑞𝑥 ) ≡∼ 𝑝𝑥 ∧∼ 𝑞𝑥 𝑃𝐶 ∩ 𝑄𝐶 Example 7. Given 𝑈 = {−4, −3, −2, −1,0,1,2,3,4}. Find the negation of the following and determine the truth sets of each negation: 1. 𝑝𝑥 ∧ 𝑞𝑥 : 𝑥 2 = 4 and (𝑥 + 5)(𝑥 − 2) = 0 2. 𝑝𝑥 ∨ 𝑞𝑥 : 𝑥 + 4 = 4 or 𝑥 2 < 5. 3. 𝑝𝑥 ∨ 𝑞𝑥 : 𝑥 − 1 < 2 or 3𝑥 − 2 = 0. 30 Solution. 1. The negation of the given statement is ∼ 𝑝𝑥 ∨∼ 𝑞𝑥 : 𝑥 2 ≠ 4 or (𝑥 + 5)(𝑥 − 2) ≠ 0. Now, to determine its truth set, we need to obtain the truth sets 𝑃 and 𝑄. To start with, we solve for the values of 𝑥 that will satisfy the given open sentences. For 𝑝𝑥 : 𝑥 2 = 4, we know that the only values of 𝑥 that will make it true are 2 and −2. Thus, 𝑃 = {2, −2}, and 𝑃𝐶 = {−4, −3, −1, 0, 1, 3, 4}. On the other hand, for 𝑞𝑥 : (𝑥 + 5)(𝑥 − 2) = 0, the only values of 𝑥 that satisfy the given open sentence are −5 and 2. This means that 𝑄 = {2} and 𝑄𝐶 = {−4, −3, −2, −1, 0, 1, 3, 4}. Hence, the truth set of the negation is 𝑃𝐶 ∪ 𝑄𝐶 = {−4, −3, −2, −1, 0, 1, 3, 4}. 2. The negation of the given statement is ∼ 𝑝𝑥 ∧∼ 𝑞𝑥 : 𝑥 + 4 ≠ 4 and 𝑥 2 > 5. To determine its truth set, we need to obtain the truth sets 𝑃 and 𝑄. To start with, we solve for the values of 𝑥 that will satisfy the given open sentences. For 𝑝𝑥 : 𝑥 + 4 = 4, we know that the only value of 𝑥 that will make it true is 0. This means that 𝑃 = {0} and 𝑃𝐶 = {−4, −3, −2, −1,1,2,3,4}. On the other hand, for 𝑞𝑥 : 𝑥 2 < 5, the only values of 𝑥 that satisfy the given open sentence are −2, −1, 0, 1, and 2. This means 𝑄 = {−2, −1,0, 1,2} and that 𝑄𝐶 = {−4, −3, 3, 4}. Hence, the truth set of the negation is 𝑃𝐶 ∩ 𝑄𝐶 = {−4, −3,3,4}. 3. The negation of the given statement is ∼ 𝑝𝑥 ∧∼ 𝑞𝑥 : 𝑥 − 1 > 2 or 3𝑥 − 2 ≠ 0. Applying same method we did in the first two examples, we obtain 𝑃 = {−4, −3, −2, −1,0,1,2} since the only values of 𝑥 that will make the statement 𝑝𝑥 : 𝑥 − 1 < 2 are within the interval (−∞,2], and 𝑄 = ∅ since the only value that can make the 2 statement 𝑞𝑥 : 3𝑥 − 2 = 0 true is , which is not an element of 𝑈. This follows 3 𝐶 𝐶 that 𝑃 = {3,4} and 𝑄 = 𝑈. Hence, the truth set of the negation is 𝑃𝐶 ∩ 𝑄𝐶 = {3,4}. 31 Universal and Existential Statements Suppose you are talking with your friend Jenny, and she is describing two clubs that she has joined. While describing the people in the first club, she says the following: “There exists a member of Club 1 such that the member has red hair”. In describing the second club, she says the following: “For all members in Club 2, the member has red hair.” Based on these two statements, what can you tell about the members' hair color in Club 1 and Club 2? Well, let's take a look at her statements, and pick them apart. In Mathematics, the statements “There exists a member of Club 1 such that the member has red hair” and “For all members in Club 2, the member has red hair” are two different logic statements which can be categorized as an existential statement and a universal statement, respectively. A universal statement is defined as a statement that states a property that is true to all. Examples of this are the following: 1. All positive numbers are greater than zero. 2. For every even integer 𝑥, 𝑥 is divisible by 2. 3. Ang bawat isa ay may pag-asa. 4. Ang lahat ng halaman ay nakakain. On the other hand, an existential Statement is a statement which states that there is at least one thing for which the property is true. For instance, we have the following: 1. There is a prime number that is even. 2. There exists a number which is divisible by any number except itself. 3. Mayroon isang tao sa mundo na magmamahal saiyo. 4. Mayroon isang mag aaral sa MMW na hindi makakapasa. Quantifiers and Negation The phrases “there exists” and “for all” play a huge role in logic and logic statements. In fact, they are so important that they have a special name: quantifiers. Quantifiers are words, expressions, or phrases that indicate the number of elements that a statement pertains to. In mathematical logic, there are two quantifiers: “there exists” and “for all”. In a statement, the word “some” and the phrases “there exists” and “at least one” are called existential quantifiers. Existential quantifiers are used as prefixes to 32 assert the existence of something. In symbol, we use the notation “∃𝑥” to be read as “for some 𝑥”, “there exists 𝑥 such that…”, or “there is some 𝑥 such that…” to represent existential quantifiers. Note: The symbol ∃ should be used in extension to several variables, and as part of the verbalization of a symbolic existential statement, the appropriate pronunciation should include the phrase “… such that…”. On the other hand, in a statement, the words “none”, “no”, “all”, and “every” are called universal quantifiers. The universal quantifiers “none” and “no” deny the existence of something, whereas the universal quantifiers “all” and “every” are used to assert that every element of a given set satisfies some condition. The symbolic representation of universal quantifiers is “∀𝑥” read as “for every 𝑥”, “for all 𝑥”, “for each 𝑥”, or “given any 𝑥”. Note: The symbol ∀ is also be used with an extension to several variables. Example 8. Determine the truth value in each of the following: 1. ∀𝑥 ∈ {1,2,3}: 𝑥 2 is less than 10. 2. ∃𝑥 ∈ {10,15,20}: 3𝑥 + 1 is odd. 3. ∀𝑥 ∈ {1,2,3}: 𝑥 + 𝑦 is prime. 4. ∃𝑥 ∈ {2,4,6}: 2𝑥 − 5 = 5. Answers. 1. Notice that the quantifier used in this statement is ∀𝑥, a universal quantifier. This means that all given values of 𝑥 must be true for all for 𝑝𝑥 : 𝑥 2 𝑖𝑠 𝑙𝑒𝑠𝑠 𝑡ℎ𝑎𝑛 10. To find the truth value of this universal statement, we will assign each given values of 𝑥 to 𝑝𝑥 and determine their corresponding truth value. That is, by assigning the values 1, 2, and 3 to 𝑥 in the statement “𝑥 2 𝑖𝑠 𝑙𝑒𝑠𝑠 𝑡ℎ𝑎𝑛 10”, we found out that these all led to true statements. Hence, the truth value of the statement “∀𝑥 ∈ {1,2,3}: 𝑥 2 is less than 10” is true. 2. In this example, we notice that the quantifier used in this statement is ∃𝑥, an existential quantifier. This means that there must be at least one value of 𝑥 (but not all) on the given values that will make 𝑝𝑥 : 3𝑥 + 1 𝑖𝑠 𝑜𝑑𝑑 true. Similarly, to find the truth value of this existential statement, we will assign each given values of 𝑥 to 𝑝𝑥 and determine their corresponding truth value. That is, by assigning the values 10, 15, and 20 to 𝑥 in the statement “3𝑥 + 1 𝑖𝑠 𝑜𝑑𝑑”, we found out that the statement is true only for 𝑥 = 10 and 20. 33  Hence, the truth value of the statement “∃𝑥 ∈ {10,15,20}: 3𝑥 + 1 is odd” is true. 3. For this example, since we used two variables in the extension of ∀, we need to use the concept of ordered pairs (𝑥, 𝑦). This means we have the following ordered pairs: (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2) and (3, 3). Substituting the values in the ordered pair to 𝑥 and 𝑦 in 𝑝𝑥 : 𝑥 + 𝑦 𝑖𝑠 𝑝𝑟𝑖𝑚𝑒 turns out that there are some for which the statement is true. Thus, the truth value of “∀𝑥 ∈ {1,2,3}: 𝑥 + 𝑦 is prime” is false. 4. This is done through doing similar method to what we did for example (b). Thus, its truth value is false since none of the given values of 𝑥 made 𝑝𝑥 : 2𝑥 − 5 = 5 true. Like any other logic statements, we can also negate universal and existential statements. Recall that the negation of a false statement is a true statement and that the negation of a true statement is a false statement. It is important to remember this fact when forming the negation of a quantified statement. For instance, what is the negation of the false statement, “All dogs are mean”? You may think that the negation is “No dogs are mean,” but this is also a false statement. Thus the statement “No dogs are mean” is not the negation of “All dogs are mean.” The negation of “All dogs are mean,” which is a false statement, is in fact “Some dogs are not mean,” which is a true statement. The statement “Some dogs are not mean” can also be stated as “At least one dog is not mean” or “There exists a dog that is not mean”. Negation of ∀𝒙: 𝒑 and ∃𝒙: 𝒑 STATEMENT NEGATION ∀𝑥: 𝑝 ~(∀𝑥: 𝑝) ≡ ∃𝑥: ~𝑝 ∃𝑥: 𝑝 ~(∃𝑥: 𝑝) ≡ ∀𝑥: ~𝑝 To help us easily negate any quantified statement, the following tables are useful: STATEMENT NEGATION All 𝑋 are 𝑌. Some 𝑋 are not 𝑌. No 𝑋 are 𝑌. Some 𝑋 are 𝑌. Some 𝑋 are not 𝑌. All 𝑋 are 𝑌. Some 𝑋 are 𝑌. No 𝑋 are 𝑌. 34 Example 9. Write the negation of each of the following statements. 1. Some airports are open. 2. All movies are worth the price of admission. 3. No odd numbers are divisible by 2. 4. Some students are not permitted to submit their research assignment. Answers: 1. No airports are open. 2. Some movies are not worth the price of admission. 3. Some odd numbers are divisible by 2. 4. All students are permitted to submit their research assignment. Example 10. State the negation of the following sentences and determine the truth values of each negation: 1. ∀𝑥 ∈ {0,1,2,3} : 𝑥 3 – 1 is an odd integer. 2. ∃𝑥,𝑦 ∈ {−1,0,1} : 𝑥 = 𝑦 + 1. 3. ∃𝑥 ∈ {−1, 0, 1}: 𝑥 2 = 𝑥 Answers: 1. The negation of the given statement is “∃𝑥 ∈ {0,1,2,3}: 𝑥 3 − 1 is an even integer”. To determine the truth value of this negation, we simply evaluate 𝑥 3 − 1 at each given value of 𝑥. Since 𝑥 3 − 1 is even when 𝑥 = 3, the negation is a true statement. 2. The negation of the given statement is “∀𝑥 ∈ {−1,0,1}: 𝑥 ≠ 𝑦 + 1”. To determine the truth value of the negation, we substitute the given values of 𝑥 and 𝑦 in the expression 𝑥 ≠ 𝑦 + 1. The negation is a universal statement, all values for 𝑥 and 𝑦 in the set {−1,0,1} must satisfy the condition that 𝑥 ≠ 𝑦 + 1. Observe that when 𝑥 = 1 and 𝑦 = 0, it is false that 𝑥 ≠ 𝑦 + 1. Thus, the negation is false. 3. The negation of the given statement is “∀𝑥 ∈ {−1, 0, 1}: 𝑥 2 ≠ 𝑥”. To determine the truth value of this negation, we simply evaluate 𝑥 2 ≠ 𝑥 at each given value of 𝑥. Since the negation of the given existential statement is true only for 𝑥 = −1, thus, its truth value is false. 35 Conditional Statements “If you don’t get in that plane, you’ll regret it. Maybe not today, maybe not tomorrow, but soon, and for the rest of your life.” The above quotation is from the movie Casablanca. Rick, played by Humphrey Bogart, is trying to convince Ilsa, played by Ingrid Bergman, to get on the plane with Laszlo. The sentence, “If you don’t get in that plane, you’ll regret it,” is a conditional statement. Conditional statements can be written in “if 𝑝, then 𝑞” form or in “if 𝑝, 𝑞” form. The following are conditional statements. 1. If we order pizza, then we can have it delivered. 2. If you go to the movie, you will not be able to meet us for dinner. 3. If 𝑛 is a prime number greater than 2, then 𝑛 is an odd number. In any conditional statement represented by “If 𝑝, then 𝑞” or by “If 𝑝, 𝑞,” the 𝑝 statement is called the antecedent while the 𝑞 statement is called the consequent. Example 11. Identify the antecedent and consequent in the following statements: 1. If our school was this nice, I would go there more than once a week. —The Basketball Diaries 2. Kung mahal mo ako, nangangahulugang kailangan mo ako 3. If you strike me down, I shall become more powerful than you can possibly imagine. —Obi-Wan Kenobi, Star Wars, Episode IV, A New Hope 4. If 378 is divisible by 18, then 378 is divisible by 6. 5. If 𝑥 2 = 9, then 𝑥 > 0. Answers: 1. Antecedent: our school was this nice Consequent: I would go there more than once a week 2. Antecedent: mahal mo ako Consequent: kailangan mo ako 3. Antecedent: you strike me down Consequent: I shall become more powerful than you can possibly imagine 4. Antecedent: 378 is divisible by 18 Consequent: 378 is divisible by 6 5. Antecedent: 𝑥 2 = 9 Consequent: 𝑥 > 0 Every conditional statement can be stated in many equivalent forms. It is not even necessary to state the antecedent before the consequent. For instance, the 36 conditional “If I live in Boston, then I must live in Massachusetts” can also be stated as “I must live in Massachusetts, if I live in Boston”. The table below lists some of the various forms that may be used to write a conditional statement. Equivalent forms of Conditional statements CONDITIONAL STATEMENTS If 𝑝 then 𝑞. Every 𝑝 is a 𝑞. If 𝑝, 𝑞. 𝑞, if 𝑝. 𝑝 only if 𝑞. 𝑞 provided that 𝑝. 𝑝 implies 𝑞. 𝑞 is a necessary condition for 𝑝. Not 𝑝 or 𝑞. 𝑝 is a sufficient condition for 𝑞. Example 12. Write each of the following in “If 𝑝, then 𝑞” form: 1. The number is an even number provided that it is divisible by 2. 2. Today is Friday, only if yesterday was Thursday. 3. Jenny is not Lisa’s sister or Jisoo is Lisa’s friend. 4. Being born in Korea is a necessary condition for being a citizen of Korea. Answers: 1. The statement, “The number is an even number provided that it is divisible by 2,” is in “𝑞 provided that 𝑝” form. This means that we have the following: Antecedent: “It is divisible by 2” Consequent: “The number is an even number” Thus its “If 𝑝, then 𝑞” form is “If it is divisible by 2, then the number is an even number”. 2. The statement, “Today is Friday, only if yesterday was Thursday,” is in “𝑝 only if 𝑞” form. This means that we have the following: Antecedent: “Today is Friday” Consequent: “Yesterday was Thursday” Thus its “If 𝑝, then 𝑞” form is “If today is Friday, then yesterday was Thursday”. 3. The statement, “Jenny is not Lisa’s sister or Jisoo is Lisa’s friend,” is in “Not 𝑝 or 𝑞” form. This means that we have the following: Antecedent: “Jenny is Lisa’s sister” 37  Consequent: “Jisoo is Lisa’s friend” Thus its “If 𝑝, then 𝑞” form is “If Jenny is Lisa’s sister, then Jisoo is Lisa’s friend”. 4. The statement, “Being born in Korea is a necessary condition for being a citizen of Korea,” is in “𝑞 is a necessary condition for 𝑝” form. This means that we have the following: Antecedent: “Being a citizen of Korea” Consequent: “Being born in Korea” Thus its “If 𝑝, then 𝑞” form is “If you are a citizen of Korea, then you are born in Korea”. (NOTE: Logic statements require proper sentence construction to be understood clearly.)  Arrow Notation The conditional statement, “If 𝑝, then 𝑞,” can be written using the arrow notation 𝑝 → 𝑞. The arrow notation 𝑝 → 𝑞 is read as “if 𝑝, then 𝑞” or as “𝑝 implies 𝑞.” The truth value of any conditional statement 𝑝 → 𝑞 is determined by the truth value of its antecedent and consequent. The conditional 𝑝 → 𝑞 is false only if 𝑝 is true and 𝑞 is false. It is true in all other cases. Truth table for 𝒑 → 𝒒 𝒑 𝒒 𝒑→𝒒 T T T T F F F T T F F T Note: The conditional ∀𝑥: 𝑝𝑥 → 𝑞𝑥 (or simply 𝑝𝑥 → 𝑞𝑥 ) is true if and only if P ⊆ Q where P and Q are truth sets of 𝑝𝑥 and 𝑝𝑥 respectively. Example 13. Determine the truth value of each of the following. 1. If 2 is an integer, then 2 is a rational number. 2. If 3 is a negative number, then 5 > 7. 3. If 5 > 3, then 2 + 7 = 4 4. If 4 ≥ 3, then 2 + 5 = 6. 5. If 23 and 27 are odd numbers, then these are not divisible by 2. 38 Answers: 1. Since both antecedent and consequent are true, the conditional statement is also true. 2. The truth value of the antecedent and the consequent are both false. Thus, the given conditional statement is a true statement. 3. This is a false statement since the antecedent and the consequent are true and false, respectively. 4. Note that the antecedent can also be written as 4 > 3 or 4 = 3 which is a disjunction. To determine its truth value, we need to consider the connective used. In this case, we have a disjunction, hence, the antecedent is true. Since the consequent is false, the truth value of the given conditional statement is false. 5. Similarly, the antecedent of this conditional statement can also be written as “23 is an odd number and 27 is an odd number”. Thus, taking note of the connective used, the truth value of both the antecedent and the consequent is true. Hence, the given conditional statement is a true statement.  The Negation of the conditional statement We all know that conditional statements have equivalent forms, and one of this forms is “not 𝑝 or 𝑞” which is written symbolically as ~𝑝 ∨ 𝑞. This means that “𝑝 → 𝑞” and “~𝑝 ∨ 𝑞” are equivalent, in symbols, we write 𝑝 → 𝑞 ≡ ~𝑝 ∨ 𝑞. It follows that the negation of the conditional statement 𝑝 → 𝑞, denoted by ~(𝑝 → 𝑞), can equivalently be written as ~(~𝑝 ∨ 𝑞). By one of De Morgan’s laws, it can be expressed as the conjunction 𝑝 ∧ ~𝑞. The negation 𝒑 → 𝒒 ∼ (𝒑 → 𝒒) = 𝒑 ∧∼ 𝒒 39 Example 14. Write the negation of each conditional statement. 1. If they pay me the money, I will sign the contract. 2. If the lines are parallel, then they do not intersect. 3. If I finish the report, I will go to the concert. 4. If the square of 𝑛 is 25, then 𝑛 is 5 or −5. Answers: 1. They paid me the money and I did not sign the contract. 2. The lines are parallel and they intersect. 3. I finished the report and I did not go to the concert. 4. The square of 𝑛 is 25 and 𝑛 is not 5 and −5. Derived Conditionals and Biconditional Statements The statement “𝑝 if and only if 𝑞” is called a biconditional. It is written in symbols as “𝑝 ↔ 𝑞” and is equivalent to the conjunction (𝑝 → 𝑞) ˄ (𝑞 → 𝑝). The Biconditional 𝑝 ↔ 𝑞 𝑝 ↔ 𝑞 ≡ [(𝑝 → 𝑞) ∧ (𝑞 → 𝑝)] Biconditional statements are true only when 𝑝 and 𝑞 have the same truth value. Truth table for 𝒑 ↔ 𝒒 𝒑 𝒒 𝒑↔𝒒 T T T T F F F T F F F T Example 15. State whether each biconditional is true or false. 1. 𝑥 + 4 = 7 if and only if 𝑥 = 3. 2. 𝑥 2 = 36 if and only if 𝑥 = 6. 3. 𝑥 > 7 if and only if 𝑥 > 6. 4. 𝑥 + 5 > 7 if and only if 𝑥 > 2. 40 Answers: 1. Both equations are true when 𝑥 = 3 and both are false when 𝑥 ≠ 3. Since the equations have the same truth value for any value of 𝑥, the biconditional is a true statement. 2. Both equations are true for 𝑥 = 6. However, when 𝑥 = −6, the first equation is true but the second equation is false. Thus, the two equations have the same truth value only for some values of 𝑥. Hence, the biconditional is a false statement. 3. Both equations are true for any values of 𝑥 greater than 7. Likewise, they are both false for any values less than 7. However, when 𝑥 = 7, the first equation turns false while the second equation is true. Hence, the biconditional is a false statement. 4. The two equations have the same truth value for any values of 𝑥. That is, both equations are true when 𝑥 is greater than 2, false when 𝑥 is less than 2, and false when 𝑥 = 2. Thus, this is a true statement. Every conditional statement 𝑝 → 𝑞 has three related statements, namely, the converse, the inverse, and the contrapositive. These are called derived conditionals. The converse of a conditional statement, denoted by 𝒒 → 𝒑, is formed by interchanging the antecedent 𝑝 with the consequent 𝑞. The inverse of a conditional statement, denoted by ~𝒑 → ~𝒒, is formed by negating the antecedent 𝑝 and negating the consequent 𝑞. The contrapositive of a conditional statement, denoted by ~𝒒 → ~𝒑, is formed by negating both the antecedent 𝑝 and consequent 𝑞, then interchanging these negated statements. Statements Related to the Conditional Statement 𝒑 → 𝒒 The converse of 𝑝 → 𝑞 is 𝑞 → 𝑝. The inverse of 𝑝 → 𝑞 is ∼ 𝑝 →∼ 𝑞. The contrapositive of 𝑝 → 𝑞 is ∼ 𝑞 →∼ 𝑝. Example 16. Write the converse, inverse, and contrapositive of the following: 1. If you are good in Mathematics, then you are good in logic. 2. If I get the job, then I will rent the apartment. 3. If 𝑥 is an odd integer, then 𝑥 2 + 2 is even. 4. If we have a quiz today, then we will not have a quiz tomorrow. 41 Answers: 1. Converse: If you are good in logic, then you are good in Mathematics. Inverse: If you are not good in Mathematics, then you are not good in logic. Contrapositive: If you are not good in logic, then you are not good in Mathematics. 2. Converse: If I rent the apartment, then I get the job. Inverse: If I do not get the job, then I will not rent the apartment. Contrapositive: If I do not rent the apartment, then I did not get the job. 3. Converse: If 𝑥 2 + 2 is even, then 𝑥 is an odd integer. Inverse: If 𝑥 is an even integer, then 𝑥 2 + 2 is odd. Contrapositive: If 𝑥 2 + 2 is odd, then 𝑥 is an even integer. 4. Converse: If we will not have a quiz tomorrow, then we have a quiz today. Inverse: If we do not have a quiz today, then we will have a quiz tomorrow. Contrapositive: If we will have a quiz tomorrow, then we do not have a quiz today. The truth value of the converse, inverse, and contrapositive follows the truth value of the conditional statements. The table given below consists of the truth values of the converse, inverse, and contrapositive of a conditional statement. Truth table for the converse, inverse, and contrapositive of 𝒑 → 𝒒 𝒑 𝒒 𝒒→𝒑 ~𝒑 → ~𝒒 ~𝒒 → ~𝒑 T T T T T T F T T F F T F F T F F T T T Note: The conditional statement 𝑝 → 𝑞 and its contrapositive ~𝑞 → ~𝑝 are equivalent. Similarly, the converse of the conditional statement 𝑞 → 𝑝 is equivalent to the inverse of the conditional statement ~𝑝 → ~𝑞. 42 Example 17. Determine the truth value of the converse, inverse and contrapositive of the following conditional statements. 1. If January has 31 days, then June has also 31 days. 2. If 5 > 7, then 5 > 4. 3. If Rodrigo Duterte is the current Philippine president, then Mar Roxas lost the 2016 Presidential election. 4. For all 𝑥 ∈ {−5, −4, −3, −2, −1,0,1,2,3,4,5}: If 𝑥 2 = 25, then 𝑥 = 5. Answers: 1. The converse, inverse and contrapositive of the given conditional statement are all false. 2. The converse and inverse of the given conditional statement are false, while its contrapositive is true. 3. The converse, inverse and contrapositive of the given conditional statement are all true. 4. In this example, the given conditional statement involves open sentences, that is, we labelled as 𝑝𝑥 : 𝑥 2 = 25 and 𝑞𝑥 ∶ 𝑥 = 5. Note that the truth sets of these open sentences are P = {−5,5} and Q = {5}, respectively. Thus, it clearly shows that the given conditional statement is false since 𝑃 ⊈ 𝑄. This also follows that the contrapositive is also false. Moreover, since 𝑄 ⊆ 𝑃, the converse is true which also follows that the inverse is also true since the two are equivalent. REFERENCES R. N. Aufmann, J. S. Lockdown, R. D. Nation, & D. K. Clegg, Mathematical Excursions, 3rd Edition, Brooks/Cole Cengage Learning, 2013. J. Price, J. N. Rath, & W. Leschensky, Pre-algebra, a Transition to Algebra, Lake Forest: Macmillan / McGraw - Hill Publishing Company, 1992. https://www.britannica.com/biography/George-Boole https://www.math.fsu.edu/~wooland/hm2ed/Part2Module1/Part2Module1 https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Disc rete_Math/2%3A_Logic/2.7%3A_Quanti%EF%AC%81ers https://study.com/academy/lesson/quantifiers-in-mathematical-logic-types- notation- examples.html#:~:text=Quantifiers%20are%20words%2C%20expressions%2C%20 or,' 43