Stud copy Discrete Math Week1&222222.pptx

discrete math

1. DISCRETE MATHEMATICS EMMA R. MAGBAYAO (Professor) COURSE CODE: MS101 CREDIT UNIT : 3 units

2. UNIVERSITY VISION STATEMENT A dynamic center for the development of competent and competitive human resource as foundation for growth and advancement of the City of Valenzuela.

3. UNIVERSITY MISSION STATEMENT To provide the citizens of Valenzuela an efficient and effective institution of higher learning that will make them skillful, productive, competent, civic-minded, and God-loving toward a peaceful, healthy, and progressive city.

4. COLLEGE V ISION STATEMENT Aims to become the premier institution of higher learning, providing the city with competent and committed engineers and IT professionals that will help the development of the city of Valenzuela and the nation.

5. COLLEGE MISSION STATEMENT To develop the students of the city of Valenzuela into top-caliber engineers and IT professionals who are proficient, committed, and environmentally aware, with good leadership skills that will comply with the needs of the city and the nation.

6. The students will be graded according to the following: Attendance 10% Class Standing 20% Quizzes 30% Major Examinations 40% Total 100% Passing Remark 75% Students will be assessed at other times during the term by the following: Examinations Quizzes Machine Problems

7. House Rules Attendance Absentees Latecomers Mobile phones Classroom behavior

8. Course Syllabus Topics: Logic and proofs Sets Functions Integers and modular arithmetic Sequences and summations Counting Probability Relations Graphs

9. Computers use discrete structures to represent and manipulate data. Computer Science is not Programming Computer Science is not Software Engineering Edsger Dijkstra: “ Computer Science is no more about computers than Astronomy is about telescopes. ” Computer Science is about problem-solving. WHY DISCRETE MATHEMATICS?

10. Discrete Mathematics – study of mathematical structures and objects that are fundamentally discrete rather than continuous . Examples of objects with discrete values are – integers , graphs , or statements in logic .

11. Discrete mathematics and computer science . Concepts from discrete mathematics are useful for describing objects and problems in computer algorithms and programming languages . These have applications in cryptography, automated theorem proving, and software development.

12. Mathematics is at the heart of problem-solving Defining a problem requires mathematical rigor Use and analysis of models, data structures, and algorithms requires a solid foundation of mathematics To justify why a particular way of solving a problem is correct or efficient (i.e., better than another way) requires analysis with a well-defined mathematical model. WHY DISCRETE MATHEMATICS?

13. Your boss is not going to ask you to solve - an MST (Minimal Spanning Tree) or - a TSP (Travelling Salesperson Problem) Rarely will you encounter a problem in an abstract setting However, he/she may ask you to build a rotation of the company ’ s delivery trucks to minimize fuel usage It is up to you to determine - a proper model for representing the problem and - a correct or efficient algorithm for solving it PROBLEM SOLVING REQUIRES MATHEMATICAL RIGOR

14. A limo company has hired you/your company to write a computer program to automate the following tasks for a large event. TASK1: IN THE FIRST SCENARIO, BUSINESSES REQUEST - limos and drivers - for a fixed period of time, specifying a start data/time and end date/time and - a flat charge rate The program must generate a schedule that accommodates the maximum number of customers37 SCENARIO I

15. TASK 2: IN THE SECOND SCENARIO - the limo service allows customers to bid on a ride so that the highest bidder gets a limo when there aren ’ t enough limos available The program should make a schedule that - is feasible (no limo is assigned to two or more customers at the same time) - While maximizing the total profit SCENARIO II

16. TASK 3: HERE EACH CUSTOMER - is allowed to specify a set of various times and - bid an amount for the entire event. - The limo service must choose to accept the entire set of times or reject it The program must again maximize the profit. SCENARIO III

17. Build a mathematical model for each scenario Develop an algorithm for solving each task Justify that your solutions work Prove that your algorithms terminate. Termination Prove that your algorithms find a solution when there is one. Completeness Prove that the solution of your algorithms is correct Soundness Prove that your algorithms find the best solution (i.e., maximize profit). Optimality (of the solution) Prove that your algorithms finish before the end of life on earth. Efficiency, time & space complexity WHAT ’ S YOUR JOB?

18. Give you the foundations that you will use to eventually solve these problems. Task1 is easily (i.e., efficiently) solved by a greedy algorithm Task2 can also be (almost) easily solved, but requires a more involved technique, dynamic programming. Task3 is not efficiently solvable by any known technique. It is believed today that to guarantee an optimal solution, one needs to look at all (exponentially many) possibilities THE GOAL OF THIS COURSE

19. Digital computers are based on discrete “atoms” (bits). Therefore, both a computer’s - structure (circuits) and - operations (execution of algorithms) can be described by discrete math. WHY CARE ABOUT DISCRETE MATH?

20. Useful tools for discrete mathematics: Logic Set Theory Functions Sequences MATHEMATICAL APPETIZERS

21. Crucial for mathematical reasoning Used for designing electronic circuitry Logic is a system based on propositions . A proposition is a statement that is either true or false (not both). We say that the truth value of a proposition is either true (T) or false (F). Corresponds to 1 and in digital circuits LOGIC

22. Logic defines a formal language for representing knowledge and for making logical inferences It helps us to understand how to construct a valid argument Logic defines: Syntax of statements The meaning of statements The rules of logical inference (manipulation)

23. Propositional logic • The simplest logic – A proposition is a statement that is either true or false. • Examples: – Pitt is located in the Oakland section of Pittsburgh. (T) – 5+2=8. • (F) – It is raining today. • (either T or F)

24. Propositional logic • Examples (cont.): – How are you? • a question is not a proposition – x+5=3 • since x is not specified, neither true nor false –   2 is a prime number. • (T) –   She is very talented. • since she is not specified, neither true nor false –   There are other life forms on other planets in the universe. • either T or F

25. “Elephants are bigger than mice.” THE STATEMENT/PROPOSITION GAME Is this a statement? yes Is this a proposition? yes What is the truth value of the proposition? true

26. “ 520 < 111” THE STATEMENT/PROPOSITION GAME Is this a statement? yes Is this a proposition? yes What is the truth value of the proposition? false

27. “y > 5” THE STATEMENT/PROPOSITION GAME Is this a statement? yes Is this a proposition? no Its truth value depends on the value of y, but this value is not specified. We call this type of statement a propositional function or open sentence .

28. “Today is January 29 and 99 < 5” THE STATEMENT/PROPOSITION GAME Is this a statement? yes Is this a proposition? yes What is the truth value of the proposition? false

29. “Please do not fall asleep.” Is this a statement? no Is this a proposition? no Only statements can be propositions. It’s a request. THE STATEMENT/PROPOSITION GAME

30. “If elephants were red, they could hide in cherry trees.” Is this a statement? yes Is this a proposition? yes What is the truth value of the proposition? probably false THE STATEMENT/PROPOSITION GAME

31. “x < y if and only if y > x” Is this a statement? yes Is this a proposition? yes What is the truth value of the proposition? true … because its truth value does not depend on specific values of x and y. THE STATEMENT/PROPOSITION GAME

32. Composite statements • More complex propositional statements can be build from elementary statements using logical connectives. Example: Proposition A: It rains outside Proposition B: We will see a movie A new (combined) proposition : If it rains outside then we will see a movie

33. As we have seen in the previous examples, one or more propositions can be combined to form a single compound proposition/composite statements . We formalize this by denoting propositions with letters such as p, q, r, s , and introducing several logical operators . COMBINING PROPOSITIONS

34. The following logical operators: Negation (NOT) Conjunction (AND) Disjunction (OR) Exclusive or (XOR) Implication (if – then) Biconditional (if and only if) LOGICAL OPERATORS (CONNECTIVES) Truth tables can be used to show how these operators can combine propositions to compound propositions.

35. Negation Definition : Let p be a proposition. The statement "It is not the case that p." is another proposition, called the negation of p . The negation of p is denoted by ¬ p and read as "not p." Example: Pitt is located in the Oakland section of Pittsburgh. It is not the case that Pitt is located in the Oakland section of Pittsburgh. Other examples: – 5+2 8. – 10 is not a prime number. – It is not the case that buses stop running at 9:00pm.  

36. Negate the following propositions: – It is raining today. It is not raining today. – 2 is a prime number. • 2 is not a prime number – There are other life forms on other planets in the universe. • It is not the case that there are other life forms on other planets in the universe.

37. Unary Operator, Symbol:  NEGATION (NOT) P  P true false false true A truth table displays the relationships between truth values (T or F) of different propositions.

38. Conjunction • Definition : Let p and q be propositions. The proposition " p and q " denoted by p  q, is true when both p and q are true and is false otherwise. The proposition p  q is called the conjunction of p and q. • Examples: –  Pitt is located in the Oakland section of Pittsburgh and 5 + 2 = 8 –  It is raining today and 2 is a prime number. –  2 is a prime number and 5 + 2 8. –  13 is a perfect square and 9 is a prime.  

39. Binary Operator, Symbol:  CONJUNCTION (AND) P Q P Q true true true true false false false true false false false false

40. Disjunction • Definition : Let p and q be propositions. The proposition " p or q " denoted by p  q, is false when both p and q are false and is true otherwise. The proposition p  q is called the disjunction of p and q. • Examples: – Pitt is located in the Oakland section of Pittsburgh or 5 + 2 = 8. – It is raining today or 2 is a prime number. – 2 is a prime number or 5 + 2 8. – 13 is a perfect square or 9 is a prime.  

41. Binary Operator, Symbol:  DISJUNCTION (OR) P Q P  Q true true true true false true false true true false false false

42. P Q P Q P Q true true true false false true false false Conjunction and disjunction Four different combinations of values for p and q

43. • Definition: Let p and q be propositions. The proposition " p exclusive or q " denoted by p  q , is true when exactly one of p and q is true and it is false otherwise. Exclusive OR (XOR)

44. Binary Operator, Symbol:  P Q P  Q true true false true false true false true true false false false EXCLUSIVE OR (XOR)

45. Definition : Let p and q be propositions. The proposition " p implies q " denoted by p  q is called implication . It is false when p is true and q is false and is true otherwise. In p  q, p is called the hypothesis and q is called the conclusion . Implication

46. Binary Operator, Symbol:  IMPLICATION (IF - THEN) P Q P  Q true true true true false false false true true false false true

47. • Definition : Let p and q be propositions. The biconditional p  q ( read p if and only if q ), is true when p and q have the same truth values and is false otherwise. Biconditional

48. Binary Operator, Symbol:  BICONDITIONAL (IF AND ONLY IF) P Q P  Q true true true true false false false true false false false true

49. Statements and operators can be combined in any way to form new statements. STATEMENTS AND OPERATORS P Q  P  Q (  P)(  Q) true true false false false true false false true true false true true false true false false true true true

50. Statements and operators can be combined in any way to form new statements. STATEMENTS AND OPERATIONS P Q P Q  ( P Q) (  P)(  Q) true true true false false true false false true true false true false true true false false false true true

51. Thank you for listening! GOD bless you all!