1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSMilos [email protected] Sennott SquareDiscrete Mathematics for Computer ScienceM. HauskrechtCS 441 Discrete mathematics for CSCourse administriviaInstructor: Milos Hauskrecht5329 Sennott [email protected]: Zitao Liu5406 Sennot Square, [email protected] web page:http://www.cs.pitt.edu/~milos/courses/cs441/2M. HauskrechtCS 441 Discrete mathematics for CSCourse administriviaLectures: • Tuesdays, Thursdays: 11:00 AM - 12:15 PM • 205 LAWRNRecitations: • held in 5313 SENSQ– Section 1: Thursdays 4:00 – 4:50 PM – Section 2: Fridays: 11:00 – 11:50 AM M. HauskrechtCS 441 Discrete mathematics for CSCourse administriviaTextbook:• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 7th Edition, McGraw Hill, 2012.Exercises from the book will be givenfor homework assignments 6thedition3M. HauskrechtCS 441 Discrete mathematics for CSCourse administriviaGrading policy• Exams: (50%)• Homework assignments: 40%• Lectures/recitations: 10%M. HauskrechtCS 441 Discrete mathematics for CSCourse administriviaWeekly homework assignments• Assigned in class and posted on the course web page• Due one week later at the beginning of the lecture• No extension policyCollaboration policy:• You may discuss the material covered in the course with your fellow students in order to understand it better • However, homework assignments should be worked on and written up individually4M. HauskrechtCS 441 Discrete mathematics for CSCourse administriviaCourse policies:• Any un-intellectual behavior and cheating on exams, homework assignments, quizzes will be dealt with severely• If you feel you may have violated the rules speak to us as soon as possible.• Please make sure you read, understand and abide by the Academic Integrity Code for the Faculty and College of Arts and Sciences.M. HauskrechtCS 441 Discrete mathematics for CSCourse syllabusTentative topics:• Logic and proofs• Sets• Functions• Integers and modular arithmetic• Sequences and summations• Counting• Probability• Relations• Graphs5M. HauskrechtCS 441 Discrete mathematics for CSCourse administriviaQuestionsM. HauskrechtCS 441 Discrete mathematics for CSDiscrete mathematics• 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.• 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.6M. HauskrechtCS 441 Discrete mathematics for CSCourse syllabusTentative topics:• Logic and proofs• Sets• Functions• Integers and modular arithmetic• Sequences and summations• Counting• Probability• Relations• GraphsM. HauskrechtCS 441 Discrete mathematics for CSCourse syllabusTentative topics:• Logic and proofs• Sets• Functions• Integers and modular arithmetic• Sequences and summations• Counting• Probability• Relations• Graphs7M. HauskrechtCS 441 Discrete mathematics for CSLogicLogic:• defines a formal language for representing knowledge and for making logical inferences• It helps us to understand how to construct a valid argumentLogic defines:• Syntax of statements• The meaning of statements• The rules of logical inference (manipulation)M. HauskrechtCS 441 Discrete mathematics for CSPropositional logic• The simplest logic• Definition:– 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)8M. HauskrechtCS 441 Discrete mathematics for CSPropositional 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 FM. HauskrechtCS 441 Discrete mathematics for CSComposite 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 movie9M. HauskrechtCS 441 Discrete mathematics for CSComposite statements• More complex propositional statements can be build from elementary statements using logical connectives.• Logical connectives:– Negation– Conjunction– Disjunction– Exclusive or– Implication– BiconditionalM. HauskrechtCS 441 Discrete mathematics for CSNegationDefinition: 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.10M. HauskrechtCS 441 Discrete mathematics for CSNegation• 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.M. HauskrechtCS 441 Discrete mathematics for CSNegation•A truth table displays the relationships between truth values (T or F) of different propositions.p¬pTFFTRows: all possible values of elementary propositions:11M. HauskrechtCS 441 Discrete mathematics for CSConjunction• 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