Important Announcement
PubHTML5 Scheduled Server Maintenance on (GMT) Sunday, June 26th, 2:00 am - 8:00 am.
PubHTML5 site will be inoperative during the times indicated!

Home Explore Mathematical Logic and Proving Techniques Lecture Notes

Mathematical Logic and Proving Techniques Lecture Notes

Published by Fairuz Shohaimay, 2019-08-15 23:54:09

Description: Lecture Notes with Past Semester Questions
Intended for use by CS111 UiTM Kampus Raub only

Search

Read the Text Version

Example 2.8 ������ ¬������ ¬������ ¬������ ∧ ������ T Complete the truth table below: F a) ¬������ ∧ ������ T F ������ T T F F b) (¬������ ∧ ������) ∨ ������ q r ¬r ¬r Ù p (¬������ ∧ ������) ∨ ������ T T p T F T F T T F F T T T T T F F F T F F F F F c) ¬(������ ∧ ������) d) (������ → ¬������) ∨ (������ ∧ ¬������) 45

Exercise 2.1 March 2015 Q3(b) Each of the following statements is false: If Sarah gets high marks in the exam, then Liza does as well. Liza does not get high marks, if and only if Alin gets high marks. Determine the truth value of the following statements. i) Sarah gets high marks. ii) Alin gets high marks. Exercise 2.2 October 2016 Q2(b) Each of the following statements is false: If Ahmad does his homework, then Ali will get to watch the baseball game. Ali does not get to watch the baseball game, if and only if Reza does his homework. Determine the truth value of the following statements. i) Ahmad does his homework. ii) Reza does his homework. 46

Exercise 2.3 March 2017 Q2(b) If ¬������ → ������ is false, determine the truth value of (¬������ ↔ ������) → ¬(������ ∨ ������). Exercise 2.4 January 2018 Q2(a) Consider the implication. \"If I go to the store, then I will get a soda.\" i) State the implication using \"only if\". ii) State the implication using \"if\". iii) State the converse of the implication in words. iv) State the implication as a disjunction. v) State the negation of the implication as a conjunction. Exercise 2.5 January 2018 Q2(b) Fill in the blanks with the correct answers. i) If a sentence can be classified as true or false, it is called a _________________. ii) The if-statement ������ in the implication ������ → ������ is called the __________________ while then-statement ������ is called ___________________. Exercise 2.6 December 2018 Q2(b) If ¬������ → ¬������ is false, determine the truth value of ¬(������ ∨ ������) → (������ ↔ ������). Exercise 2.7 June 2019 Q2(b) Find the truth value of ������, ������, ������, ������ if [(¬������ ∨ ������) ∧ (¬������ ∨ ¬������) ∧ (������ ∨ ¬������)] → (������ → ������) is false. 47

2.2 Logical Equivalence Definition 2.7 Two statements ������ and ������ are said to be logically equivalent, and we write ������ ⟺ ������ when the statement ������ is true (respectively, false) if and only if the statement ������ is true (respectively, false). Equivalence of two propositions can easily be established by constructing both tables for both propositions and then comparing the two. Example 2.9 Let ������: Today is Sunday. ¬������: Today is not Sunday. ¬¬������: It is not true that today is not Sunday. ������ ¬������ ¬¬������ Hence, ������ is logically equivalent to ¬¬������, or ������ ⇔ ¬¬������. Example 2.10 Let ������: Tony Stark is a billionaire. ������: Tony Stark is Iron Man. ������ ∧ ������: ¬(������ ∧ ������): ¬������: ¬������: ¬������ ∨ ¬������: 48

������ ������ ������ ∧ ������ ¬(������ ∧ ������) ¬������ ¬������ ¬������ ∨ ¬������ ¬(������ ∧ ������) logically equivalent to ¬������ ∨ ¬������ ¬(������ ∧ ������) ⇔ ¬������ ∨ ¬������ Definition 2.8 Tautology is a propositional statement that is true under any possible TRUE-FALSE valuation of its propositional variables. Example 2.11 Let ������: It is raining. ������ ∨ ¬������: Example 2.12 Let ������: Socrates is a philosopher. ������: Socrates is a joker. (������ ∧ ������) → ������: 49

Example 2.13 The following logical expression is a tautology. ((������ ∧ ������) → ������) ↔ (������ → (������ → ������)) The final column of the truth table shows that all the values are true. Definition 2.9 Contradiction is a propositional statement that is false under any possible TRUE-FALSE valuation of its propositional variables. Example 2.14 Let ������: It is raining. ������ ∧ ¬������: Example 2.15 Let ������: Tommy is a singer. ������: Tommy is an actor. (������ ∨ ������) ∧ (¬������ ∧ ¬������): 50

Definition 2.10 Contingent is a propositional statement that is true under some TRUE-FALSE valuation of its propositional variables, and false in others. Example 2.16 Let ������: Fitri loves to drive fast. ������: Fitri is a professional racer. (������ ∨ ������) ∧ ¬������: A conditional statement of the form ������ → ������ is associated with three other statements: converse, inverse and contrapositive. ������ → ������ Conditional ������ → ������ Converse Inverse ¬������ → ¬������ ¬������ → ¬������ Contrapositive 51

The truth tables for the above statements are as follows: ������ ������ ¬������ ¬������ ������ → ������ ������ → ������ ¬������ → ¬������ ¬������ → ¬������ TT F F TF F T FT T F FF T T From the table, we can conclude the following statement. • An implication is logically equivalent to its contrapositive (������ → ������) ⟺ (¬������ → ¬������) • A converse of an implication is logically equivalent to an inverse of an implication (������ → ������) ⟺ (¬������ → ¬������) Example 2.17 Given the statement, “If a cat has nine lives, then it can grow old.” We have the following: Converse: If a cat can grow old, then it has nine lives. Inverse: If a cat does not have nine lives, then it cannot grow old. Contrapositive: If a cat cannot grow old, then it does not have nine lives. Example 2.18 Given the statement, “If Amin is mindful of his spending, then he can save money.”. We have the following statement. Converse: Inverse: Contrapositive: 52

Example 2.19 Write the converse, inverse and contrapositive of the statement, “If a pizza topping has pepperoni and zucchini, then the pizza is delicious.” Converse: Inverse: Contrapositive: Example 2.20 For each of the following, fill in the blanks so that the result is a true statement. a) The converse of the inverse of ������ → ������ is the contrapositive of ������ → ������. b) The converse of the inverse of ������ → ������ is the ________________ of ~������ → ~������. c) The inverse of the converse of ________ is the inverse of ~������ → ������. d) The contrapositive of the _______________ of ~������ → ~������ is the converse of ������ → ������. Exercise 2.8 March 2012 Q2(b) By using the truth table, determine whether ii) (������ ∧ ������) is logically equivalent to ������. 53

Exercise 2.9 March 2013 Q3(a) State whether (������ ∧ ������) ∨ œ~������ ∨ (������ ∧ ~������)• ∨ (������ ∨ ~������) is a tautology, contradiction or neither. Construct a truth table to determine its truth values. Exercise 2.10 March 2013 Q3(b) For each of the following, fill in the blank with the word converse, inverse, or contrapositive so that the result is a true statement. i) The converse of the inverse of ������ → ������ is the _______________________ of ������ → ������. ii) The contrapositive of the converse of ~������ → ~������ is the ________________ of ������ → ������. iii) The inverse of the converse of ������ → ~������ is the _____________________ of ~������ → ������. iv) The contrapositive of the inverse of ������ → ������ is the __________________ of ~������ → ~������. 54

Exercise 2.11 September 2013 Q3(b) Write the converse, inverse and contrapositive of the following statement: If I am rich, then I will take a long vacation for a trip around the world. Exercise 2.12 September 2013 Q4(a) Show that the following statement is a tautology: [������ ∧ (������ → ������)] → ������ 55

Exercise 2.13 September 2013 Q4(b) Consider the following logical statement: ¬[¬[(¬������ → ������) ∧ ������] ∨ ¬������] Use the truth table to show that the statement is logically equivalent to (������ ∧ ������). Exercise 2.14 March 2014 Q3(a) Construct a truth table to determine whether (������ → ¬������) ∧ (¬������ ↔ ������) is logically equivalent to ������ → (������ ∨ ������). 56

Exercise 2.15 March 2014 Q5(c) Write in sentence the appropriate conditional proposition for each of the following conditional statement. i) I will drive to work if it rains today. Write in sentence the converse of its inverse. ii) If it rains today then I will drive to work. Write in sentence the inverse of its converse. iii) If it rains today then I will not go to work. Write in sentence the inverse of its contrapositive. Exercise 2.16 September 2014 Q3(a) Determine whether (������ ∧ ������) ↔ ������ is logically equivalent to (������ ↔ ������) ∧ (������ ↔ ������) by using a truth table. 57

Exercise 2.17 September 2014 Q3(c) For each of the following statement, fill in the blank with the word converse, inverse or contrapositive so that the result is a true statement. i) The converse of the ___________________ of ������ → ������ is the inverse of ������ → ������. ii) The contrapositive of the ________________ of ������ → ������ is the inverse of ������ → ������. Exercise 2.18 March 2015 Q5 Write the following statements in words: a) The negation of the statement: Shima walks to school but Diana cycles to school. b) The converse of the statement: If Darmia goes to class then Arianna will go to the library. c) The inverse of the statement: Ali will attend the conference if he is not sick. Exercise 2.19 September 2015 Q2(c) Write out the inverse, converse and contrapositive of the following statement by using both symbolic logic and the statement forms. If A is a circle then the answer is wrong and the correction is needed. 58

Exercise 2.20 March 2016 Q2(a) Write out the inverse, converse and contrapositive of the following statement using symbolic logic and words. If Rasyid is sick, then he will be sad and he will not attend the class. Exercise 2.21 October 2016 Q2(a) Write out the inverse, converse and contrapositive of the following statement using symbolic logic and words. If today is rainy, then the forecasters are wrong and it is not going to be a beautiful day. 59

Exercise 2.22 March 2017 Q2(a) For each of the following statement, fill in the blank with the word converse, inverse or contrapositive so that the result is a true statement. i) The inverse of ______________________ of ¬������ → ������ is the converse of ������ → ¬������. ii) The converse of ______________________of ������ → ������ is the converse of ¬������ → ¬������ . iii) The inverse of the converse of ������ → ������ is the ______________________ of ������ → ������. iv) The converse of the contrapositive of ������ → ������ is the __________________of ������ → ������ . Exercise 2.23 March 2017 Q3(a) Using the truth table to show that the following is tautology . ¬[(������ ∨ ������) → ������] ∨ [(������ → ������) ∧ (������ → ������)] 60

Exercise 2.24 January 2018 Q3(a) Determine whether the following proposition is a tautology, a contradiction or a contingency using a truth table. ¬(������ → ������) ↔ ������ Exercise 2.25 December 2018 Q2(a) Given the following statements: Aina is saying \"if nasi kerabu is expensive then it must taste good\". Auni is saying \"if nasi kerabu taste good then it must be expensive\". Are they logically saying the same thing? Give reason(s) to support your answer. 61

Exercise 2.26 January 2018 Q3(a) Construct a truth table to show that (������ ∧ ������) ∨ œ¬������ ∨ (������ ∧ ¬������)• ∨ (������ ∨ ¬������) is tautology. Exercise 2.27 December 2018 Q5(b) Consider the following implication statement: \"Amira can perform excellently in examination if she studies consistently\". Write in symbols and word the converse and contrapositive of the statement above. 62

Exercise 2.28 June 2019 Q2(a) Fill in the blanks with converse, inverse or contrapositive for each statement below. i) The _______________ of the inverse of ������ → ������ is the inverse of ������ → ������. ii) The contrapositive of the converse of ������ → ������ is the inverse of ____________. iii) The inverse of the contrapositive of ������ → ������ is the _______________ of ������ → ������. 63

2.3 Laws of Logic Using the concepts of logical equivalence, tautology, and contradiction, the following is the list of laws for the algebra of propositions. Suppose that ������, ������, and ������ are arbitrary statements; ������¼ is any tautology, and ������¼ is any contradiction. a) Double Negation ¬¬������ ⟺ ������ b) De Morgan’s Law c) Commutative Law ¬(������ ∧ ������) ⟺ ¬������ ∨ ¬������ d) Associative Law ¬(������ ∨ ������) ⟺ ¬������ ∧ ¬������ e) Distributive Law f) Idempotent Law ������ ∧ ������ ⟺ ������ ∧ ������ g) Identity Law ������ ∨ ������ ⟺ ������ ∨ ������ h) Dominance Law (������ ∧ ������) ∧ ������ ⟺ ������ ∧ (������ ∧ ������) i) Inverse Law (������ ∨ ������) ∨ ������ ⟺ ������ ∨ (������ ∨ ������) j) Absorption Law (������ ∧ ������) ∨ ������ ⟺ (������ ∨ ������) ∧ (������ ∨ ������) k) Implication (������ ∨ ������) ∧ ������ ⟺ (������ ∧ ������) ∨ (������ ∧ ������) ������ ∧ ������ ⟺ ������ ������ ∨ ������ ⟺ ������ ������ ∧ ������¼ ⟺ ������ ������ ∨ ������¼ ⟺ ������ ������ ∧ ������¼ ⟺ ������¼ ������ ∨ ������¼ ⟺ ������¼ ������ ∧ ¬������ ⟺ ������¼ ������ ∨ ¬������ ⟺ ������¼ (������ ∧ ������) ∨ ������ ⟺ ������ (������ ∨ ������) ∧ ������ ⟺ ������ ������ → ������ ⟺ ¬������ ∨ ������ l) Biconditional ������ ↔ ������ ⟺ (������ → ������) ∧ (������ → ������) 64

Example 2.21 Simplify (������ ∨ ������) ∧ ¬(¬������ ∧ ������) using the laws of logic. (������ ∨ ������) ∧ ¬(¬������ ∧ ������) Reasons ⟺ (������ ∨ ������) ∧ (¬¬������ ∨ ¬������) ⟺ (������ ∨ ������) ∧ (������ ∨ ¬������) ⟺ ������ ∨ (������ ∧ ¬������) ⟺ ������ ∨ ������¼ ⟺ ������ Example 2.22 By using the laws of logic, simplify the following logical expression. (������ → ������) ∧ (������ → ¬������) (������ → ������) ∧ (������ → ¬������) Reasons Example 2.23 Prove the following logical equivalence. ¬œ¬œ(������ ∨ ������) ∧ ������• ∨ ¬������• ⟺ ������ ∧ ������ ¬œ¬œ(������ ∨ ������) ∧ ������• ∨ ¬������• Reasons 65

This next example shows the idea of logical equivalence being used together with the laws of logic. Example 2.24 Negate and simplify the compound statement (������ ∨ ������) → ������. Reasons Example 2.25 Let ������, ������ denote the primitive statements ������: Joe goes to school. ������: Jah pays for Joe’s lollipop. and consider the implication ������ → ������: If Joe goes to school, then Jah will pay for Joe’s lollipop. The negation of ������ → ������ is simply ¬(������ ∨ ������), but we want to avoid writing the statement as “It is not the case that if Joe goes to school, then Jah will pay for Joe’s lollipop.” ¬(������ → ������) Reasons From this, we may write the negation of ������ → ������ as “Joe goes to school, but Jah does not pay for Joe’s lollipop.” Note: The negation of an if-then statement does not begin with the word if. It is not another implication. 66

Exercise 2.29 March 2012 Q5 Give the reasons for each step in the following simplification of compound statements using the laws of logic. ¿[(������ → ������) ∨ (������ → ������)] → (������ ∨ ������)Á ⟺ [������ ∨ (������ ∨ ������)] Steps [(������ → ������) ∨ (������ → ������)] → (������ ∨ ������) Reasons ⟺ [(¬������ ∨ ������) ∨ (¬������ ∨ ������)] → (������ ∨ ������) 1) ⟺ ¿[(¬������ ∨ ������) ∨ ¬������] ∨ ������Á → (������ ∨ ������) (i) 2) ⟺ ¿[(������ ∨ ¬������) ∨ ¬������] ∨ ������Á → (������ ∨ ������) (ii) 3) ⟺ ¿[������ ∨ (¬������ ∨ ¬������)] ∨ ������Á → (������ ∨ ������) (iii) 4) ⟺ ¿[������ ∨ ¬������] ∨ ������Á → (������ ∨ ������) (iv) 5) ⟺ ¿[¬������ ∨ ������] ∨ ������Á → (������ ∨ ������) (v) 6) ⟺ ¿¬������ ∨ [������ ∨ ������]Á → (������ ∨ ������) (vi) 7) ⟺ ¬¿¬������ ∨ [������ ∨ ������]Á ∨ (������ ∨ ������) (vii) 8) ⟺ ¿¬¬������ ∧ ¬[������ ∨ ������]Á ∨ (������ ∨ ������) (viii) 9) ⟺ ¿������ ∧ ¬[������ ∨ ������]Á ∨ (������ ∨ ������) (ix) 10) ⟺ ¿������ ∨ [������ ∨ ������]Á ∧ [¬[������ ∨ ������] ∨ (������ ∨ ������)] (x) 11) ⟺ ¿������ ∨ [������ ∨ ������]Á ∧ ������¼ (xi) 12) ⟺ ¿������ ∨ [������ ∨ ������]Á (xii) 13) (xiii) 67

Exercise 2.30 March 2013 Q2(b) Simplify the following by using the laws of logic. (������ ∧ ������) ↔ ������ Exercise 2.31 March 2014 Q3(b) Complete the steps as well as give the corresponding reasons in the simplification of the compound statement below using the laws of logic. (������ → ������) ∧ [������ ∨ (¬������ ∧ ������)] ……(i)…… = (¬������ ∨ ������) ∧ [������ ∨ (¬������ ∧ ������)] Absorption Law = (¬ ∨ ������) ∧ ……(ii)…… Distributive Law =……(iii)…… Inverse Law =……(iv)……∨ (������ ∧ ������) ……(v)…… = ������ ∧ ������ 68

Exercise 2.32 September 2014 Q3(b) Use the laws of logic to determine whether [������ ∧ (������ → ������)] ⟹ ������. Exercise 2.33 March 2015 Q3(a) Simplify the following statement using the laws of logic. ¬¿¬œ(¬������ → ������) ∧ ������• ∨ ¬������Á 69

Exercise 2.34 September 2015 Q3(a) Simplify the following statement using the laws of logic. [(~������ ∧ ~������) ∨ (������ ∨ ~������)] ⟺ [(~������ ∨ ~������) ∨ ������] Exercise 2.35 March 2016 Q5(b) Simplify the following using the laws of logic and state the reasons. (¬������ ∧ ������) ∨ (¬������ ∧ ������) → (������ ∨ ������) 70

Exercise 2.36 October 2016 Q5(b) Simplify the following using the laws of logic and state the reasons . ¬[¬������ ∨ (������ ∨ ������)] ∨ (������ ∨ ������) Exercise 2.37 March 2017 Q5(b) Simplify the following by using laws of logic and state the reasons. (������ ∧ ¬������) ∨ [(������ → ������) ∧ (������ → ������)] 71

Exercise 2.38 January 2018 Q3(b) State the steps and reasons using the laws of logic with your final answer in implication form. (������ ∨ ������) ∧ ¿������ ∨ œ¬������ ∨ (������ ∧ ¬������)•Á Exercise 2.39 December 2018 Q3(b) Fill in the blanks with the correct answers based on the laws of logic. (������ ∨ ������)T ∨ (������ ∨ ������T)T ______(i)______ ⟺ (������T ∧ ������T) ∨ (������T ∧ ������TT) Double Complement ⟺ (������T ∧ ������T) ∨ (������T ∧ ������) Distributive law ⟺______(ii)______ Inverse law ______(iii)______ ⟺ ������T ∧ ������ ⟺ ������T 72

Exercise 2.40 June 2019 Q4(a) Prove the proposition (������ ↔ ¬������) ⟺ (¬������ ∧ ������) ∨ (¬������ ∧ ������) using the laws of logic. 73

2.4 Logical Implication Consider the implication hypothesis (������¬ ∧ ������y ∧ … ∧ ������j) → ������ conclusion ������ = positive integers The statements ������¬, ������y, …, ������j are called premises. Definition 2.11 A valid argument is an argument whose conclusion is true whenever all the premises are true. One way to show that an argument is valid is to show that (������¬ ∧ ������y ∧ … ∧ ������j) → ������ is a tautology Example 2.26 Let ������, ������, and ������ denote the primitive statements given as ������: Dennis studies trigonometry. ������: Dennis memorizes the trigonometric identities. ������: Dennis passes the trigonometry test. Let ������¬, ������y, and ������k denote the premises ������¬: If Dennis studies trigonometry, then he will pass the trigonometry test. ������y: If Dennis does not memorize the trigonometric identities, then he’ll study trigonometry. ������k: Dennis fails the trigonometry test. ������: Therefore, Dennis memorizes the trigonometric identities. Rewrite ������¬, ������y, and ������k in symbolic form. ������¬: ������y: ������k: ������: 74

Build the truth table for the implication. ������ ������ ������ ¬������ ������ → ������ ¬������ → ������ ¬������ œ(������ → ������) ∧ (¬������ → ������) ∧ ¬������• → ������ ������ ������¬ ������y ������k ������¬ ∧ ������y ∧ ������k (������¬ ∧ ������y ∧ ������k) → ������ Since the final column is all true, the implication is a tautology. Hence, œ(������ → ������) ∧ (¬������ → ������) ∧ ¬������• → ������ is a valid argument. Example 2.27 For any primitive statements ������, ������, and ������, the implication is a tautology. ¤������ ∧ œ(������ ∧ ������) → ������•¥ → (������ → ������) ������ ������ ������ ¤������ ∧ œ(������ ∧ ������) → ������•¥ → (������ → ������) ������¬ ������y ������ ������¬ ∧ ������y (������¬ ∧ ������y) → ������ Consequently, for the premises ������y: ������¬: and the conclusion ������: we know that ¤������ ∧ œ(������ ∧ ������) → ������•¥ → (������ → ������) is a valid argument. The truth of the conclusion ������ is deduced or inferred from the truth of premises ������¬ and ������y. 75

Definition 2.12 If ������ and ������ are arbitrary statements such that ������ → ������ is a tautology, then we say that ������ logically implies ������ (written as ������ ⟹ ������). Example 2.28 From the previous examples (Example 5.24 & 5.25), we can say that • Since œ(������ → ������) ∧ (¬������ → ������) ∧ ¬������• → ������ ⟺ ������¼, then œ(������ → ������) ∧ (¬������ → ������) ∧ ¬������• logically implies ������ œ(������ → ������) ∧ (¬������ → ������) ∧ ¬������• ⟹ ������ • Since ¤������ ∧ œ(������ ∧ ������) → ������•¥ → (������ → ������) ⟺ ������¼, then because each of the implications is a tautology. Exercise 2.41 March 2015 Q3(b) Construct a truth table to determine whether: [(������ → ������) ∧ (������ → ¬������) ∧ ������] logically implies ¬������ State your reason. 76

Exercise 2.42 September 2015 Q2(d) Construct a truth table to show (������ ∨ ~������) → (~������ ∧ ������) implies (~������ ∧ ������) is a tautology. Exercise 2.43 March 2016 Q3(a) Using a truth table, determine whether (~������ ↔ ������) ∧ (������ ↔ ~������) logically implies (~������ → ������). 77

Exercise 2.44 October 2016 Q3(a) Using a truth table, determine whether (~������ ↔ ������) ∧ (������ ↔ ������) logically implies (������ → ������). Exercise 2.45 June 2019 Q4(b) Construct a truth table to determine whether (������ ∧ ¬������) logically implies (¬������ ∨ ¬������). 78

2.5 Rules of Inference The validity of an argument can be determined using a truth table. But this method can become tedious, especially when an argument involves too many primitive statements. Thus, a technique called \"Rules of Inference\" should be used as presented below. Rule of Example Name of Rule Inference ������ → ������ If I watch Netflix, then today is Sunday. Rule of Detachment a) ������ I watch Netflix. (Modus Ponens) ∴ ������ Therefore, today is Sunday. ������ → ������ If 100 is divisible by 50, then 50 is even. b) ������ → ������ If 50 is even, then 50 is divisible by 2. Law of Syllogism ∴ ������ → ������ Therefore, 100 is divisible by 2. ������ → ������ If I watch Netflix, then today is Sunday. c) ¬������ Today is not Sunday. Modus Tollens ∴ ¬������ Therefore, I don’t watch Netflix. ������ ∨ ������ Steve is at the library or the coffee shop. Disjunctive Syllogism d) ¬������ Steve is not at the library. ∴ ������ Therefore, Steve is at the coffee shop. ������ Conjunction e) ������ Simplification ∴ ������ ∧ ������ Addition ������ ∧ ������ f) ∴ ������ ������ g) ∴ ������ ∨ ������ All the argument above can be shown to be valid by using truth tables. We can also use equivalent identity to determine the validity of arguments, which includes Contrapositive: ������ → ������ ⟺ ¬������ → ¬������ Implication: ������ → ������ ⟺ ¬������ ∨ ������ 79

Example 2.29 Use the rules of inference and equivalent statement to show that the following arguments are valid. a) ������ ∧ ������ ������ → ������ ∴ ������ ∨ ������ No. Reasons 1. ������ ∧ ������ Premise 1 2. ������ → ������ Premise 2 3. ������ 1, simplification 4. ������ 2, 3, Modus Ponens 5. ������ ∨ ������ 4, Addition with r b) ������ → ������ ¬������ → ������ ������ → ������ ∴ ¬������ → ������ No. Reasons 1. ¬������ → ������ 2. ������ → ������ 3. ¬������ → ������ 4. ������ → ������ 5. ¬������ → ¬������ 6. ¬������ → ������ 80

Example 2.30 Consider the following argument. If Min is nominated for the team leader post, then Sue will not vote for Min. If Min is the elected team leader, then Min is nominated for the post. Sue did not vote for Min. Therefore, Min is not the elected team leader. a) Write all the primitive statements. b) Write all the premises and the conclusion. c) Show that the above argument is valid by using rules of inference. 81

Example 2.31 Find the conclusion for the following argument. If Alex decides to sleep late at night, then he will watch a football match. If Alex decides not to sleep late at night, then he will wake up early. If Alex wakes up early, then he will attend a lecture. 82

Definition 2.13 Proof by Contradiction is a method of indirect proof to prove that the conclusion of an argument is true, and it follows that the argument is valid. Suppose we want to proof an argument is valid. • Assume the conclusion is not true. • Use the rules of inference and (or) laws of logic to find that there is a contradiction in the premises. The contradiction indicates that it is not true that the conclusion is not true. Hence, the conclusion must be true. Therefore, the argument is valid. Example 2.32 Using contradiction method, show that the following argument is valid. [(������ → ������) ∧ (¬������ ∨ ������) ∧ (������ ∨ ������)] → (������ ∨ ������) No. Steps Reasons 1. ¬(������ ∨ ������) Assume by Contradiction (Negate conclusion) 2. ¬������ ∧ ¬������ 1, De Morgan’s law 3. ¬������ 2, Simplification 4. ¬������ ∨ ������ Premise 2 5. ¬������ 3, 4, Disjunctive Syllogism 6. ������ → ������ Premise 1 7. ¬������ 2, Simplification 8. ¬������ 6, 7, Modus Tollens 9. ������ ∨ ������ Premise 3 10. ������ 8, 9, Disjunctive Syllogism 11. ¬������ ∧ ������ ⇔ ������ 5, 10, Conjunction (Contradiction) 12. ∴ ������ ∨ ������ 1, 11, Rule of Contradiction (Conclusion is true) 83

Example 2.33 Use the method of contradiction and rules of inference to prove that the following argument is valid. ������ → (������ ∧ ������) ¬������ ∴ ¬������ No. Steps Reasons Definition 2.14 An argument is invalid when all the premises are true, but the conclusion is false. An argument can be proven as invalid by giving a counterexample. That is, determine the truth value for each of the primitive statements such that all the premises are true but the conclusion is false. Example 2.34 The truth values ������: ������, ������: ������, ������: ������ and ������: ������ provide the counterexample for the following invalid argument. (������ ∨ ¬������) → ¬������ (������ ∨ ¬������) → ¬������ (⟺ ������) ������ → ¬������ ������ → ¬������ ¬������ → ������ ¬������ → ������ (⟺ ������������)) ������ ∧ ������ (⟺ ������ ∧ ������ (⟺ ������) ∴ ������ ∨ ������ ∴ ������ ∨ ������ (⟺ ������) 84

Exercise 2.46 March 2012 Q3 Consider the following argument: If Kamal takes the medicine, then he will get well. Kamal will take the medicine if the medicine is not bitter. Kamal is not well. Therefore, the medicine is bitter. a) Determine all the primitive propositions in the above argument and rewrite them using the symbols ������, ������ and ������. b) Convert the argument into symbolic form. c) Prove the validity of the argument. 85

Exercise 2.47 March 2013 Q4 Consider the following argument: If Amir plays golf in the morning then he watches television in the evening. If Amir watches television in the evening and Daniel plays basketball then Ali or Lim sink a birdie on the last hole. If Ahmad won the golf tournament, then Amir plays golf in the morning and Daniel plays basketball. Lim did not sink a birdie on the last hole. Ahmad won the golf tournament. Therefore, Ali sinks a birdie on the last hole. a) Declare the primitive propositions in the argument above using symbols ������, ������, ������, ������, ������ and ������. b) Write the premises of the argument using those symbols. c) Prove the validity of the argument by using the rules of inference. 86

Exercise 2.48 September 2013 Q5 Consider the following argument: Today is not a public holiday and Atikah is planning to go to Pulau Langkawi. If Atikah meets with Sabrina then today is a public holiday. If Atikah does not meet with Sabrina then she will go shopping at IKEA. If Atikah goes shopping at IKEA then she will feel very happy. a) Use variables ������, ������, ������, ������ and ������ to represent the five (5) primitive statements given in the above argument. a) Rewrite the argument in symbolic form. b) Use the Rules of Inference to establish a conclusion. Hence, state in words the conclusion obtained. 87

Exercise 2.49 March 2014 Q4 Consider the following argument: If today is Monday, then Hamid has to meet with his supervisor or go to the library. If his supervisor is sick, he will not meet with his supervisor. Today is Monday and his supervisor is sick. a) Use variables ������, ������, ������ and ������ to represent the four (4) primitive statements given in the above argument. b) Rewrite the argument in symbolic form. c) Use the Rules of Inference to find the conclusion of the argument. Hence rewrite the conclusion in the form of a compound statement. 88

Exercise 2.50 September 2014 Q5 Given the following argument: If Sham goes to the racetrack, then Suzi will be mad. If Joe plays cards all night, then Camelia will be mad. If either Suzi or Camelia gets mad, then the attorney will be notified. The attorney has not heard from either of these two clients. Consequently, Sham did not make it to the racetrack and Joe did not play cards all night. a) Declare all the primitive propositions in the argument above using symbols ������, ������, ������, ������ and ������. Hence write the premises of the arguments using those symbols. b) Use the rules of inference to establish the validity of the arguments in (a). 89

Exercise 2.51 March 2015 Q4 Consider the following argument: If Amin is practicing singing, then he is playing a guitar. If he plays a guitar, then Salwa will play the violin. Amin will perform at a show at PWTC or Salwa will not play violin. Amin does not perform at a show at PWTC or Salwa will give him a guitar. Salwa will not give him a guitar. Therefore, Amin is not practicing singing. a) Declare all the primitive propositions in the argument above using symbols p, q, r, s and t. b) Rewrite the arguments in (a) in symbolic form. c) Prove the validity of the argument using the rules of inference. 90

Exercise 2.52 September 2015 Q3(b) Consider the following argument: If the clock is working then Ali wakes up early and he will go to work. If the clock is broken then he is healthy. Ali will not go to work or he is happy. He is not happy. Therefore, he is healthy. i) Declare the primitive propositions in the argument above using symbols ������, ������, ������, ������, and ������. ii) Write the premises of the argument using those symbols. iii) Prove the validity of the argument by using the rules of inference. 91

Exercise 2.53 September 2015 Q3(c) Prove that the argument below is valid using the rule of contradiction. ~������ → ~������ ������ → ������ ~������ ∧ ~������ ∴ ~������ 92

Exercise 2.54 March 2016 Q5(a) Consider the following argument: If Daniel plays the piano all day, then Amirah will be happy. If Zamarul sings a traditional song, then Elisha will be happy. If either Amirah or Elisha are happy, then the producer will receive the lyrics from these two musicians. The producer has not received the lyrics from the musicians. So that, Daniel did not play the piano all day and Zamarul did not sing a traditional song. i) Declare all the primitive propositions in the argument above using the variables ������, ������, ������, ������ and ������. ii) Write the premises of the arguments using variables ������, ������, ������, ������ and ������. Then, use the rules of inference to establish the validity of the arguments. 93

Exercise 2.55 October 2016 Q5(a) Consider the following argument: If Eric composes music in the afternoon, then he practices in the evening. If Eric composes music in the afternoon and practices in the evening then Henry or Amber cleans the house. If Jackson wins the music competition, then Eric composes music in the afternoon and John plays basketball. Amber did not clean the house. Jackson won the music competition. Therefore, Henry cleans the house. i) Declare all the primitive propositions in the argument above using the variables ������, ������, ������, ������, ������ and ������. ii) Write the premises of the arguments using ������, ������, ������, ������, ������ and ������. iii) Prove the validity of the argument by using the rules of inference. 94


Like this book? You can publish your book online for free in a few minutes!
Create your own flipbook