LOGIC.pptx. To uphold certainty in validity of mathematical statements or to assert the truths of statement

mathematics in the modern world

1. Foundation of Logic Proofs

2. LESSON OBJECTIVES: To identify the different types of logical statements and their truth values; Construct truth tables Differentiate tautology from contradiction; Determine the validity of an argument; Appreciate the importance of logic in real-life situations.

3. Why do we use logic in Mathematics? To uphold certainty in validity of mathematical statements or to assert the truths of statement

4. LOGIC STATEMENTS Every language contains different types of sentences, such as statements, questions, and commands. For Example: “ 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.

5. Proposition (Statement)- is a declarative sentence that is either true (T) or false (F) but not both.

6. Example: Identifying Statements Determine whether each sentence is a proposition/statement. Florida is a state in the United States. How are you? is a prime number.  

7. Simple Statement and Compound Statement A simple statement is a statement that conveys a single idea. A compound statement is a statement that conveys two or more ideas. -connecting simple statement with words and phrases such as and, or, if,…then , and if and only if creates a compound statement.

8. Simple Statement and Compound Statement The variable p, q, r and s used to represent simple statement and the symbols to represent the connectives . Example: p: I will attend the meeting. q: I will go to school. Ans: “I will attend the meeting or I will go to school.”  

9. Logic Connectives and Symbols Statement Connective Symbolic Form Type of Statement/Proposition not p not Negation p and q and Conjunction p or q or Disjunction If p, then q If … then Conditional/Implication p if and only if q if and only if Biconditional/ Bi-implication Statement Connective Symbolic Form Type of Statement/Proposition not p not Negation p and q and Conjunction p or q or Disjunction If p, then q If … then Conditional/Implication p if and only if q if and only if Biconditional/ Bi-implication

10. Example : Consider the following simple Statements p: Today is Friday. q: It is raining. r: I am going to a movie. s: I am not going to the basketball game. Writing compound statement into symbolic form. Today is Friday and it is raining. It is not raining and I am going to a movie. Ans: (a. ) (b. ) Writing symbolic form into compound statement. b. Ans: a. I am going to the basketball game or I am going to a movie. b. If it is raining, then I am not going to the basketball game.  

11. a) Negation Let p be a proposition. The negation of p, denoted by p (also denoted by ), is the statement “It is not the case that p.” The proposition p is read “not p.” The truth value of the negation of p, p) , is the opposite of the truth value of p.  

12. The following is its truth table

13. Example: Find the negation of the proposition “Michael’s PC runs Linux” and express this in simple English. Solution: The negation is “It is not the case that Michael’s PC runs Linux.” This negation can be more simply expressed as “Michael’s PC does not run Linux.”

14. b) Conjunction Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.

15. c) Disjunction Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise.

16. Logical Connectiveness the following is the truth table

17. Example Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.” Solution: The conjunction , p ∧ q , is the proposition “Rebecca’s PC has more than 16 GB free hard disk space, and its processor runs faster than 1 GHz.”

18. Example Find the dis junction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.” Solution: The disjunction of p and q, p ∨ q , is the proposition “Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz.”

19. I mplication/ Conditional Statement Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence) other ways to read  

20. There are some other ways to express  

21. Statements Related to the Conditional Statement The converse of is . The inverse of is The contrapositive of is .   Example: “If I get the job, then I will rent the apartment.” 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.

22. Truth Tables for Conditional and Related Statements

23. B iconditional Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.

24. There are some other ways to express  

25. Quantifiers are used in writing proofs of mathematical statements. Quantifiers Universal Quantifier- is typically denoted by read as ‘for all’. In the statement it used the words none, no, all and every . The universal quantifier none and no deny the existence of something, whereas the universal all and every are used to assert that every element of a given set satisfies some condition. Existential Quantifier- are used as prefixes to assert the existence of something. It is denoted by read as ‘there exists’. Some words used for existential are some and at least one.  

26. The truth value of a simple statement is either true(T) or false(F). 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. Truth Value and Truth Tables

27. Truth Value and Truth Tables

28. Construct a truth table for .   p q r p T T T T T F T F T T F F F T T F T F F F T F F F p q r T T T T T F T F T T F F F T T F T F F F T F F F

29. Tautologies, Contradictions, and Contingencies Statements that produce propositions with the same truth value as a given compound proposition are used in the construction of mathematical arguments. A tautology is a statement that is always true by its own contexts A contradiction is a statement that is false in and of itself. A contingency is propositions whose truth depends on what the facts are; they can either be true or false. 

30. Examples 1: Either Sir Dajao will give us high grades or he will not give us high grades. That statement is a tautology, and it has a particular form, which can be represented symbolically like this: Kirby loves cooking and Kirby doesn’t love cooking. That statement is a contradiction, and it has a particular form, which can be represented symbolically like this:  

31. Example 2: Determine whether the following statement are tautology , contradiction , or contingency by using truth tables. p q   T T T T T F T T F T T T F F F T p q T T T T T F T T F T T T F F F T a)   is a tautology  

32. b)   p q   T T F T F T F F F F F T T T T F F T T T p q T T F T F T F F F F F T T T T F F T T T is contingent  

33. c)   p q   T T F F T F T F T T F F F T F F F F F F T F F F p q T T F F T F T F T T F F F T F F F F F F T F F F is a contradiction  

34. An argument consists of a set of statements called premises and another statement called the conclusion . An argument is valid if the conclusion is true whenever all the premises are assumed to be true. An argument is invalid if it is not a valid arguments. Symbolic Arguments

35. Example: Determine the validity of the following argument. Beside each statement is the corresponding symbolic form. First Premise: If Aristotle was human , then Aristotle was mortal . p q Second Premise: Aristotle was human. p Conclusion: Therefore, Aristotle was mortal. q   p q First premise Second premise p Conclusion q T T T T T T F F T F F T T F T F F T F F p q Second premise p Conclusion q T T T T T T F F T F F T T F T F F T F F

36. Arguments & Euler Diagrams P Q P Q Q Q P P All Ps are Qs No Qs are Ps Some Qs are Ps Some Qs are not Ps

37. Two statements are equivalent if they both have the same truth value for all possible truth values of their simple statements. The notation is used to indicate that the statements and are equivalent.   Equivalent Statements

38. Example 3: Show that   p q T T T F F F T T F F T T T T F T T F F F T F F T F T F T p q T T T F F F T T F F T T T T F T T F F F T F F T F T F T

39. Example 4: Show that   p q T T T T T T T T F F T F F T F T T F F F T F F T T T T T p q T T T T T T T T F F T F F T F T T F F F T F F T T T T T

40. Example 5: Show that   p q r T T T T T T T T F F T T T F T F T T T F F F T T F T T T T T F T F F F T F F T F F F F F F F F F p q r T T T T T T T T F F T T T F T F T T T F F F T T F T T T T T F T F F F T F F T F F F F F F F F F T T T T T T T T T T T T T T T F F T T F T F F T T T T T T T T T T T T T T T T F F T T F T F F T

41. Along with the two statements that are logically equivalent to every other statement, there are two more pairs of logically equivalent statements known as De Morgan's laws De Morgan’s Law De Morgan’s Law  

42. Example 6: p: I like Discrete Mathematics q: I like Number Theory Then, “I like Discrete Mathematics and I like Number Theory” can be presented . By the first De Morgan’s Law, is equivalent to . Consequently, we can express the negation of our original statements as “I don’t like Discrete Mathematics or I don’t like Number Theory” which equivalent to “ It is not the case that I like Discrete Mathematics and I like Number Theory”  

43. Let’s also prove this law using truth table.     p q   T T T F F F F T T F F T F T T T F T F T T F T T F F F T T T T T p q T T T F F F F T T F F T F T T T F T F T T F T T F F F T T T T T

44. Example 7: p: Nico is on the red team q: James is on the blue team Then, “ Nico is on the red team or James is on the blue team” can be presented . By the second De Morgan’s Law, is equivalent to . Consequently, we can express the negation of our original statements as “ Nico isn’t on the red team and James isn’t on the blue team” which equivalent to “It is not the case that Nico is on the red team or James is on the blue team”  

45. Let’s also prove this law using truth table.     p q   T T T F F F F T T F T F F T F T F T T F T F F T F F F T T T T T p q T T T F F F F T T F T F F T F T F T T F T F F T F F F T T T T T

46. In logic, many common logical equivalences exist and are often listed as laws or properties. The following tables illustrates some of these: EQUIVALENCE NAME Identity Laws Domination Laws Idempotent Laws Double Negation Laws Commutative Laws EQUIVALENCE NAME Identity Laws Domination Laws Idempotent Laws Double Negation Laws Commutative Laws

47. In logic, many common logical equivalences exist and are often listed as laws or properties. The following tables illustrates some of these: EQUIVALENCE NAME Associative Laws Distributive Laws De Morgan’s Law Absorption Laws Negation Laws EQUIVALENCE NAME Associative Laws Distributive Laws De Morgan’s Law Absorption Laws Negation Laws

48. Logical Equivalence Involving Conditional Statements  

49. Logical Equivalence Involving Bi-conditional Statements  

50. PROBLEM SET

51. Which of these sentences are propositions? What are the truth values of those that are propositions? What time is it? There are no black flies in Maine. 4 + x = 5. 2 + 3 = 5. Let p and q be the propositions “The election is decided” and “The votes have been counted,” respectively. express each of these compound proposition as an English sentence.  

52. 3. Write the following symbolic form using P, Q, and R for statements and the symbols where P: Pres. Dela Cruz is a good president Q: Government officials are corrupt R: People are happy a) If Pres. Dela Cruz is a good president, then government officials are not corrupt b) If government officials are not corrupt, then the people are happy. c) If Pres. Dela Cruz is a good president and people are happy, then the government officials are not corrupt. d) Pres. Dela Cruz is not a good president if and only if government officials are corrupt and the people are not happy.  

53. 4. Write out the truth tables for the following propositional forms. 5. Prove that using truth table.