Introduction to Discrete Math and Fundamentals of Logic PDF

MODULE 1 Introduction to Discrete Mathematics and The Fundamentals of Logic Prepared by: Mr. Israel P. Peñero Introduction Defining what discrete mathematics is, you could probably say that it is very hard to define because mathematics itself is very hard to define since there are a...

MODULE 1 Introduction to Discrete Mathematics and The Fundamentals of Logic Prepared by: Mr. Israel P. Peñero Introduction Defining what discrete mathematics is, you could probably say that it is very hard to define because mathematics itself is very hard to define since there are a lot of concepts that are involved when we talk about mathematics. But some authors have their own definitions and these are as follows: 1. Discrete mathematics is a branch of mathematics dealing with objects that can assume only distinct, separated values. 2. Discrete Mathematics is a branch of mathematics involving discrete elements that uses algebra and arithmetic. It is increasingly being applied in the practical fields of mathematics and computer science. It is a very good tool for improving reasoning and problem-solving capabilities. (https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_tutorial.pdf) 3. Discrete Mathematics deals with the study of Mathematical structures. It deals with objects that can have distinct separate values. It is also called Decision Mathematics or finite Mathematics. It is the study of mathematical structures that are fundamentally discrete in nature and it does not require the notion of continuity. (https://byjus.com/maths/discrete-mathematics/) 4. Discrete math deals with mathematical topics in the sense that it analyzes data whose values are separated such as integers: integer number line has gaps. (https://cse.buffalo.edu/~xinhe/cse191/Classnotes/note01-1x2.pdf) The term "discrete mathematics" is therefore used in contrast with "continuous mathematics," which is the branch of mathematics dealing with objects that can vary smoothly (and which includes, for example, calculus).  So, we could say, that discrete mathematics in simple words are as follows: 1. Discrete Mathematics deals with the study of Mathematical structures. 2. It deals with objects that can have distinct separate values. 3. It is also called Decision Mathematics or finite Mathematics. FUNDAMENTALS of LOGIC What is logic? Logic is an organized way of reasoning and sense-making. It studies the forms of arguments and the methods used to Aristotle distinguish correct Father of Logic from incorrect (384 BCE - 322 BCE) arguments as well as 4 making flawless FUNDAMENTALS of LOGIC Definition A proposition is a declarative statement that is true or false but not both. We could assign any capital English alphabet for a proposition but the commonly used letters for a proposition are p, q and r. 5  Examples of Propositions 1. It is raining. 2. When you work hard, you are rewarded with success. 3. There are seven days in one week. 6  The following statement are not propositions 1. Get out! 2. Logic is sweet. 3. x + 3 = 5 4. How old are you? Why do you think the above statements could not be considered as proposition? 7 MIND EXERCISES! Which of the following is a proposition? 1. 4 + 6 = 10 2. The sum of the angles of a triangle is 180 degrees. 3. The product of an odd and even number is even. 4. The capital of Batangas is Lipa City. 5. Is mathematics logic? 6. Hey there! 7. Do not panic.  Logical Connectives A word or symbol that joins two sentences to produce a new one. In mathematical logic, there are different connectors we could use and these are as follows: 1. “Not” symbolize as  or . 2. “Or” symbolize as . 3. “And” symbolize as . 4. “Implies” symbolize as or . This is in the form of “If-then” statement. 5. “If and only if” symbolize as  or .  Definition 1.NEGATION Given any statement p, another statement called the negation of p can be formed by writing “It is false that …” before p, or if possible, by inserting in p the word “not”. Symbolically, the negation of p is denoted by p or p. Illustration: Let proposition p: Roderick attends Mathematics class. The negation of the above statement would be: 10  p : Roderick will not attend Mathematics class. Symbol We could use this Translation also. It is not the case that P; It is false that P; p It is not true that P 11  Definition 2. CONJUNCTION Any two statements can be combined by the word “and” to form a composite statement which is called the conjunction of the original statements. Symbolically, conjunction of the two statements p and q can be written as p  q. Illustration: Let two propositions are as follows: p: Ernesto goes to school q: Israel goes to market. p  q : Ernesto goes to school and Israel goes to Market. Note here that the new statement could be symbolize as P: pq 12 Symbol We could use this Translation also. P moreover Q; P although Q; P still Q; P furthermore Q; pq P also Q; P nevertheless Q; P however Q; P yet Q; P but Q 13  Definition 3. DISJUNCTION Any two statements can be combined by the word “or” to form a new statement which is called the disjunction of the original two statements. Symbolically, disjunction of the two statements p and q can be written as p  q. Illustration: Let two propositions are as follows: p: Ernesto goes to school q: Israel goes to market. P : p  q : Ernesto goes to school or Israel goes to Market. 14 Symbol We could use this Translation also. P unless Q; pq 15  Definition 4. CONDITIONAL Many statements are of the form “If p then q”. This statement is called conditional statement and it is denoted by the symbol p  q or simply p q. Note that the conditional P Q is true unless P is true and Q is false. In other words, it is state that a true statement cannot imply a false statement. We call p the hypothesis Illustration:orLet premise and q the conclusion. two propositions are as follows: P: Two is positive. Q: Two is even. P Q: If two is positive, then two is an even16 number. Symbol We could use this Translation p implies q; also. p is a sufficient condition for q; p only if q; q is a necessary condition pq for p; q if p; q follows from p; q provided p; q whenever p; q is a logical consequence of p 17  Definition 5. BICONDITIONAL Another common statement is of the form “p if and only if q” or simply “p iff q”. This statement is called biconditional statement and it is denoted by the symbol p  q or p  q. Illustration: Let two propositions are as follows: p: Two is positive. q: Two is even. P: p  q: Two is positive if and only if two is even. 18 Symbol Translation P is equivalent to Q; pq P is a necessary and sufficient condition for Q; 19 SUMMARY: Logical Symbolic Type Read as Operator Form Negation Not ~ p or ¬ p not p Conjunction And pq p and q Disjunction Or p q p or q Conditional If…then p q If p, then q Biconditional if and only if p q p if and only if q Note: The operation  or  is called a unary operation because only one statement is involved while the other four operations are called binary operations because two statements are operated on. Example Translate the following logic symbols into statement. Let p: Life is beautiful. q: Life is challenging. 1. p  q 4. p   q 2. p  q 5. p   q 3.  p q 21 COMPOUND STATEMENTS AND GROUPING SYMBOLS If a compound statement is written in symbolic form, then parenthesis are used to indicate which simple statements are grouped together. The given table below illustrates the use of parenthesis to indicate groupings for some statements in symbolic form. Symbolic Form The parentheses indicate that: P  (Q   R) Q and  R are grouped together (P  Q)  R P and Q are grouped together (P R)  (R  S) P and R are grouped together R and S are grouped together If a compound statement is written as an English sentence, then a comma is used to indicate which simple statement are grouped together. Statements on the same side of a comma are grouped together. English The comma indicates that: Sentence P, and Q or Q and R are grouped together because they not R are both on the same side of the comma P and Q, or R P and Q are grouped together because they are both on the same side of the comma If P and not P and Q are grouped together because they Q, then R or are both to the left of the comma. S R and S are grouped together because they are both to the right of the comma. If a statement in symbolic form is written in English sentence, then the simple statements that appear together in parentheses in the symbolic form will all be on the same side of the comma that appears in the English sentence. Illustration: Let P, Q and R represent the following: P: You get a promotion Q: You complete the training. R: You will receive a bonus Translate the following symbolic logic into an English sentence. a) (P R)  Q b) (P Q) R c) (P R)  (R  Q) Translate the following English sentence into symbolic form. a) You get a promotion and you will receive a bonus, or you complete the training. b) If you get a promotion and complete the training, then you will receive a bonus. c) You get a promotion and receive a bonus, or you will receive a bonus and complete the training. Illustration: Let P, Q and R represent the following: P: You get a promotion Q: You complete the training. R: You will receive a bonus Translate the following symbolic logic into an English sentence. a) (P R)  Q b) (P Q) R c) (P R)  (R  Q) Translate the following English sentence into symbolic form. a) You get a promotion and you will receive a bonus, or you complete the training. b) If you get a promotion and complete the training, then you will receive a bonus. a)Note: You will Butget notaall promotion and a bonus, English sentence needsif to and onlyaif you have complete comma the training. to group sentences into a compound statement. Let us have some illustration for this. Symbolizing Propositions Example: Using the letters P, Q, R, and S to represent the following simple propositions P: Daniel attends the opera concert. Q: Kim attends the opera concert. R: Lyka performs in the opera concert. S: Gwen performs in the opera concert. respectively, translate the following into symbols. 2 6 1. Either Daniel and Kim attends the opera concert or Lyka performs in the opera concert. 2. Daniel attends the opera concert and either Kim attends the opera concert or Gwen does not perform in the opera concert. 2 7 3. Daniel and Kim will not both attend the opera concert and Lyka and Gwen will both not perform in the opera concert. 4. Either Daniel or Kim will attend the opera concert, but neither Lyka nor Gwen will perform in the opera concert. 5. Lyka will not perform in the opera concert if and only if Gwen will perform in the opera concert; but Daniel will not attend the opera concert. 2 8 Now, its your turn. Translate the following sentence into logic symbol. “Buy one notebook, take one free pencil.” P: I buy a notebook. Q: I get a free pencil. a. If I buy a notebook then I get a free pencil. b. If I buy a notebook then I don’t get a free pencil. c. If I don’t buy a notebook then I get a free pencil. d. If I don’t buy a notebook then I don’t get a 29 free pencil. Translate the following sentence into logic symbol. P: I get my salary today. Q: I treat you to dinner. a. I get my salary today and then, I treat you to dinner. b. I get my salary today and then, I don’t treat you to dinner. c. I don’t get my salary today and then, I treat you to dinner just the same. d. I don’t get my salary today and then I don’t treat you to dinner. 30 Express the following propositions in symbols, where P, Q, R and S are defined as follows. P: I understand logic. Q: I am doing well in my class in Logic. R: Logic is easy. S: I will pass all my exams in Logic. 1. Logic is easy or it is difficult. 2. I understand Logic if and only if it is easy. 3. Although I am doing well in my class in Logic, I won’t pass all my exams. 4. Logic is easy and I understand it. 31  More on Conditional Statements (Converse, Inverse and Contrapositive) Let us say the given statement is “If P then Q” symbolize as P Q and P: antecedent or hypothesis Q: consequent or conclusion Converse: If Q then P. Q P Inverse: If not P then not Q. P  Q Contrapositive: If not Q then not P. Q  P 32  If a number is a multiple of 6 then it is a multiple of 2.  CONVERSE: If a number is a multiple of 2 then it is a multiple of 6.  INVERSE: If a number is not a multiple of 6 then it is not a multiple of 2.  CONTRAPOSITIVE If a number is not a multiple of 2 then it is not a multiple of 6.  If a function is differentiable at x=a then it is continuous at x=a  CONVERSE -If a function is continuous at x=a then it is differentiable at x=a.  INVERSE -If a function is not differentiable at x=a then it is not continuous at x=a.  CONTRAPOSITIVE: -If a function is not continuous at x=a then it is not differentiable at x=a.  Now, it’s your turn! Give the converse, inverse, and contrapositive of the following implications. 1. If you are more than 60 years old, then you are entitled to a senior citizen card. 2. If P is prime then it is odd. 35  Quantifiers The words “some”, “all” and “no” that are found in sentences are called quantifiers. They tell “how many” of a certain set of objects are being considered. Other statements may not specifically contain quantifiers although quantification is implied. Let us consider the following statements: 1. Some integers are prime. This sentence is true for say the integer 3; that is , for at least one integer. The sentence can be proven false by showing that no integer is prime. 2. x2 + 3x = 4 This sentence is true since the equation will satisfy if x = -4 and x = 1. It can be proven false by showing that no number x satisfies the equation. 3. All multiples of 6 are even. This statement is true for all or any multiple of 6. Statement can be proven false by showing a single multiple of 6 which is not even. (Is there a number multiple of 6 which is not an even number?) 4. No prime is even. It is obvious that the statement is false. Why? Think of a prime number that can be considered as even number. Quantifier Symbol  Let U be the universe of discourse. Definition The phrase " For all x " is called a universal quantifier and is denoted by x. x : " for every x " " for all x " " for any x " 39 Example: Let P(x) denote x > x - 1. Assume x are real numbers. Is P(x) a proposition? No. Reason: Many possible substitutions. Is x P(x) a proposition? Yes. What is the truth value for x P(x)? Definition The statement " For some x " is called an existential quantifier and is denoted by x. x : " there exists an x " " there is at least one x " " for some x " 41 Example: Let T(x) denote x > 5 and x is from Real numbers. Is T(x) a proposition? No. Is x T(x) a proposition? Yes. What is the truth value for x T(x) ? Since 10 > 5 is true. Therefore, x T(x) is true. Example Let U   1, 0,1 1. P x  : x3  x 3 P  1 :  1  1 true 3 P 0  : 0  0 true 3 P 1 : 1 1 true xP  x  is true 43  SUMMARY OF QUANTIFIED STATEMENTS When x P(x) and x P(x) are true and Statement false? When true? When false? x P(x) P(x) is true There is an for all x x where P(x) is false. x P(x) There is P(x) is false some x for for all x. which P(x) is true. Example Let U   1, 0,1 2. Q x  : x 2 1 2 Q  1 :  1 1 true 2 Q 0  : 0  1 false 2 Q 1 : 1 1 true xQ  x  is false but xQ  x  is true 45  Example Let U   1, 0,1 3. S x  : 2 x 0 S  1 : 2  1  2 0 false S 0  : 2 0  0 true S 1 : 2 1 2 0 false xS  x  is true 46 Exercise Let U 1, 2, 4, 6, 8 and let E  x , P  x  , S  x  and M  x  denote the propositional functions E  x  : x is even P  x  : x is positive S  x  : x  1 4 M  x  : 2 x 2 Determine if each proposition is true or false. 1. E 1 6. xE  x  10. xE  x  2. S 2   M 1 7. xS  x  3. E 1   P 1 8. xM  x  4. P 1  M 4  47 9. x E  x  5. xP  x 