Mathematics for Data Science Part 1-Logic

Discrete Math

1. Mathematics for Data Science BDS MAT 109 Dr A Choudhury UCDS MAT101 1

2. How to think? 3 + 6 = 9 x + y = 9 The sum of two integers is an integer. q(x) = ax 2 + b x + c is a quadratic expression. Good mathematical language conveys a precise, clear unambiguous language. Goal : To be able to communicate mathematically by understanding the basic principles of logic. Dr A Choudhury UCDS MAT101 2

3. Logic “I argue very well. Ask any of my remaining friends. I can win an argument on any topic, against any opponent. People know this, and steer clear of me at parties. Often, as a sign of their great respect, they don't even invite me.” Dave Barry (American writer and humorist) Logic - ‘ logos ’ in Greek which loosely translated means ‘ reason’ . Ancient Greek philosophers used logic to mean ‘ reasoned speech’ , an ‘argument’. Formal logic is studied by mathematicians and philosophers. Modern day logic has its origins in the works of George Boole. ( http://www-groups.dcs.stand.ac.uk/ history/Biographies/Boole.html ). Dr A Choudhury UCDS MAT101 3

4. Formal logic Fuzziness -Need of formalism in mathematics; translating statements into symbols. Formalism: The description of something in formal mathematical or logical terms; the treatment of mathematics as a manipulation of meaningless symbols. Mathematical communication-notation, symbolic language, manipulations Prof .John T Tate, (1925-2019) Dr A Choudhury UCDS MAT101 4

5. Logic Statements/proposition Analysis of statements Logical Connectives Truth values and tables Tautology Contingency and contradiction Logical equivalence Converse and contrapositive Propositional logic-Derivation Dr A Choudhury UCDS MAT101 5

6. Proposition A statement (or a proposition ) is a declarative statement that is either true or false but not both. The two possible choices ‘true’ or ‘false’ are called the truth value of a statement. We use small letters s,u, p etc. to denote simple statements. Check which of the following sentences are propositions: How are you? 3+8=12 Hurray! The moon is made up of cheese. Dr A Choudhury UCDS MAT101 6

7. Proposition e) x is prime. f) This sentence is true. g) Some people are tall. He is not sad. i)2 is a prime and an even number. j) You can opt either Biology or Computer Science. Is there any difference between the statements h) and i) ? A statement is atomic( or simple ) if it cannot be broken into smaller statements otherwise it is molecular ( or compound). Compound statements have connectives ‘or’, ‘and’ ,’if then’. Dr A Choudhury UCDS MAT101 7

8. Analysis of statements Identifying whether a statement is simple or compound. Identify the simple statements from which the compound statement is constructed. True/false simple statements. Simple statements having quantifiers and no quantifiers. Analysis of the simple statements, followed by inferences drawn about the compound statements. Dr A Choudhury UCDS MAT101 8

9. Analysis of simple statements Decide whether the following statements are true/false. Today is Monday. All men have beard. Some men have beard. No men have beard. Words such as `all', `some' or `none' are examples of quantifiers. Quantifiers in a statement basically indicate that the statement is dealing with `quantities' or `numbers'. Statements with quantifiers are called quantified statements . Dr A Choudhury UCDS MAT101 9

10. Simple statements with quantifiers: All, some and No The quantifier ‘ all ’ means ‘ each and every .’ All men have beard. All squares are rectangles. All roses are red. All humans are mortal. The quantifier ‘ some ’ means ‘ at least one ’. Some cows are carnivorous. Some men have beard. Some girls wear trousers. The quantifier ‘ no ’ or ‘ none ’ stands for ‘ not even one ’. No rose is red. No dog can fly. None of the boys have long hair. Dr A Choudhury UCDS MAT101 10

11. Negation/double negation of simple statements without quantifiers If p denotes a simple statement then its negation ( not p) , is denoted by or If p is true then is false and vice versa. 1) p : It is raining. 2) q : Man is immortal. It is not raining. Man is not immortal. 3) r Girls have long hair. 4) s : The set {x ϵ N : x<-1} is empty. Girls do not have long hair. ⁓ s : The set {x ϵ N : x<-1} is not empty. Exercise: p: Hari is taller than Susan. What is ⁓p? q: The number of mammals is lesser than the number of insects. What is ⁓q? When we are negating a statement p, we are not bothered about its truth value with respect to our real-life experience   Dr A Choudhury UCDS MAT101 11

12. Double negation of simple statements without quantifiers The negation of is p, that is, not not p is the same as p. The statement ` not not p ' is called a double negation . p : Mary has a lamb. q : Today is Sunday. r : Alice speaks the truth. ⁓ ⁓ p : It is not true that Mary does not have a lamb. ⁓ ⁓ q: It is not the case that today is Sunday. ⁓ ⁓ r: It is not true that Alice does not speak the truth.   Dr A Choudhury UCDS MAT101 12

13. Negation/double negation of simple statements with quantifiers Negation of statements having the quantifier ‘All’, “Some” and “No/None” 1) p: All birds fly. ⁓p: Some birds do not fly. q : Some boys are not tall. ⁓ q: All boys are tall. r : Some girls wear skirts. ⁓r: No girl wears skirts. 4) s : No new born baby can walk. ⁓s: Some new born babies can walk. Dr A Choudhury UCDS MAT101 13

14. Logical Connectives The compound statements are built by using five logical connectives connecting simple statements denoted by ‘p’ ,’q ’ (propositional variables).   Dr A Choudhury UCDS MAT101 14

15. Truth value and truth tables The truth value of a statement is determined by the truth value(s) of its parts, depending on its connectives. is true when both p and q are true. is true when p or q or both are true. is true when p is false or q is true or both. is true when both p and q are true or both p and q are false. is true when p is false.   Dr A Choudhury UCDS MAT101 15

16. Truth values of conjunction and disjunction 1. p :Every dog is an Alsatian but every tiger is a cat. p: Every dog is an Alsatian. q: Every tiger is a cat. What is its truth value? 2. All humans swim and all birds can fly.(‘and’ stands for both) 3. p q: I have a cat or I have a dog. What is the truth value?(“or” is inclusive- either or and both). Meaning-I have only a cat or I have only a dog or that I have both a cat and a dog.   Dr A Choudhury UCDS MAT101 16

17. Truth tables for the logical connectives You are given the truth table of p and q , and you have to calculate the truth table of (⁓p) q Truth tables of negation, disjunction and conjunction. Construct the truth table of (p ˅ q)˄r.   Dr A Choudhury UCDS MAT101 17

18. For example, let p be the statement `I study hard' and let q be the statement `I will do well in my math examination'. Then the implication denoted by p→q will be the statement `if I study hard then I will do well in my math examination'. p→q is false when p is true but q is false, this is the only scenario when p→q is false. p is the ‘antecedent’ and q is the ‘ consequent’. Dr A Choudhury UCDS MAT101 18 Truth tables for conditional /implications

19. General rule The number of input variables decide the number of input rows in a table. If there are n input variables, the truth-table will have 2 n input rows. The number of columns will be the sum of the number of connectives and the number of input variables. In the statement (p ˅ q)˄r, we have 2 connectives, namely, We also have 3 input variables, p, q and r . The truth-table for (p ˅ q)˄r will have 2 + 3 = 5 columns and 8 rows.   Dr A Choudhury UCDS MAT101 19

20. Tautology A statement s which is always true on the basis of its logical form alone is called a tautology . A tautology does not say anything about the real world . s: T.   Dr A Choudhury UCDS MAT101 20

21. Contradiction and Contingency A statement s which is always false on the basis of its logical form alone is called a contradiction. A statement s which is neither true nor false is called a contingency. Dr A Choudhury UCDS MAT101 21

22. Logical equivalence Two statements are logically equivalent provided both the statements have the same truth value under any assignment of truth values. Let r , s be compound statements built up from the same input variables. Then we can construct truth-tables for both r , s, with the exact same input rows. Then r ≡ s (logically equivalent) if and only if the output column for r and s are identical. Example: If a quadrilateral has a pair of parallel sides then it has a pair of supplementary angles. Equivalently, If a quadrilateral does not have a pair of supplementary angles then it does not have a pair of parallel sides. Rephrasing a mathematical statement can provide insights and helps in proving or refuting it.   Dr A Choudhury UCDS MAT101 22

23. De Morgan’s Laws: Construct the truth tables for the pairs of statements given below. Decide whether they are logically equivalent or not. Give reasons. , ⁓ p The logical equivalences in the truth tables are the basis of De Morgan’s laws:   Dr A Choudhury UCDS MAT101 23

24. Converse and contrapositive The statement q → p is called the converse and the statement q → p is the contrapositive of the statement p → q . Example: s: “If x is greater than 3 then x 2 is greater than 9 x ϵ Z.” Converse: If x 2 is greater than 9 then x is greater than 3 x ϵ Z. Contrapositive: If x 2 is not greater than 9 then x is not greater than 3, x ϵ Z. For any statement s the truth table of contrapositive of s is logically equivalent to s but the converse of s might not be so.   Dr A Choudhury UCDS MAT101 24

25. Example p: I study. q: I do well in my exams. ‘If I study well then I do well in my exams’. Direct statement ‘If I do well in my exams then I have studied’. Converse statement ‘If I do not study then I will not do well in my exams’. Inverse statement ‘If I did not do well in my exams then I have not studied.’ Contrapositive statements Dr A Choudhury UCDS MAT101 25

26. Negating implications “If you do not carry an umbrella, you will get soaked” is “ You carry an umbrella or you will get soaked”. p ˅ q≡ ⁓p →q “ It is not the case that if you carry an umbrella then you will not get soaked” is “You carry an umbrella and you will be soaked” . ⁓(p →⁓q ) ≡ p ˄q Dr A Choudhury UCDS MAT101 26

27. Propositional logic Limitations of the truth table approach: Each time a statement is added we have to double the number of rows, which becomes unwieldy. Propositional logic looks into how the propositions interact with each other. The formulas in the symbolic logic are manipulated to make logical derivations formally.( propositional calculus ) The formal derivations help us to analyze complex logical statements where truth tables are impractical. These derivations are used in mathematical discourses. The system of derivation rules and proof sequences is a simple example of mathematical proof. Dr A Choudhury UCDS MAT101 27

28. References: 1) Hunter, D.J. (2015). Essentials Of Discrete Mathematics. 3rd Edition. Jones & Bartlett Learning. 2) Lehman, E., Leighton, F.T., & Meyer, A.R. (2017). Mathematics for Computer Science. https://courses.csail.mit.edu/6.042/spring17/mcs.pdf 3) Janacek, G.J., & Close, M.L. (2011). Mathematics for Computer Scientists. http://web.ftvs.cuni.cz/hendl/metodologie/gentle-introduction-to-mathematics-for-computer.pdf 4) Oscar Levin (2016). Discrete Mathematics: An Open Introduction. Create Space Independent Publishing Platform. 5) Desai K R. (2013). Mathematical Recurrence Relations: Visual Mathematics. Create Space Independent Publishing Platform. 6) Bagai S.,Habib A.,& Venkataraman G.,(2017) : A Bridge to Mathematics https://in.sagepub.com/en-in/sas/a-bridge-to-mathematics/book258675   Dr A Choudhury UCDS MAT101 28