CSE115/ENGR160 Discrete Mathematics 01/18/11CSE 115/ENGR 160Office hoursCourse goalsTopicsTextbookPrerequisiteGradingClass policyPropositional logicPropositionLogical operatorsNegationExampleConjunctionSlide 16DisjunctionSlide 18Exclusive orConditional statementConditional statement pqSlide 22Common mistake for pqExampleConverse, contrapositive and inverseBiconditional statementSlide 27Truth table of compound propositionsPrecedence of logic operatorsBit operationsTranslating English to logical expressionsSlide 32System SpecificationSlide 34Slide 35Slide 36Slide 37CSE115/ENGR160 Discrete Mathematics01/18/11Ming-Hsuan YangUC Merced1CSE 115/ENGR 160•Instructor: Ming-Hsuan Yang ([email protected]) •Teaching assistant: Mentor Mahmud ([email protected]) •Lectures:–COB 279, Tuesday/Thursday 4:30 pm to 5:45 pm•Labs:–SE 138, Thursday 12:00 pm to 2:50 pm•Web site: http://faculty.ucmerced.edu/mhyang/course/cse1152Office hours•Office hours: –Wednesday 3:00 pm – 4:00 pm–SE 258•TA hours–Thursday 12:00 pm – 2:00 pm–SE 1383Course goals•Mathematical reasoning–Logic, inference, proof•Combinatorial analysis–Count and enumerate objects•Discrete structures–Sets, sequences, functions, graphs, trees, relations•Algorithmic reasoning–Specifications and verifications•Applications and modeling–Internet, business, artificial intelligence, etc.4Topics•Logic•Proof•Sets•Functions•Counting•Discrete probability•Relations•Graph•Boolean algebra5Textbook•Discrete Mathematics and Its Applications by Kenneth H. Rosen, 6th edition, McGraw Hill•Errata: http://highered.mcgraw-hill.com/sites/dl/free/0072880082/299357/Rosen_errata.pdf•Math zone: http://www.mathzone.com/6Prerequisite•Upper division standing•Basic knowledge of calculus (MATH 21 and MATH 22)•Basic knowledge in computer science7Grading•20% Homework •20% Four quizzes•30% Two midterms •30% Final8Class policy•Do not use computers or smart phone in class•All the lecture notes will be posted on the class web•Weekly homework assigned on Thursday and due in the following Thursday in class•Must be your own work•Returned in class9Propositional logic•Understand and construct correct mathematical arguments•Give precise meaning to mathematical statements•Rules are used to distinguish between valid (true) and invalid arguments•Used in numerous applications: circuit design, programs, verification of correctness of programs, artificial intelligence, etc.10Proposition•A declarative sentence that is either true or false, but not both–Washington, D.C., is the capital of USA–California is adjacent to New York–1+1=2–2+2=5–What time is it?–Read this carefully11Logical operators•Negation operator•Conjunction (and, ^)•Disjunction (or v )•Conditional statement •Biconditional statement •Exclusive Or 12Negation13Example•“Today is Friday”–It is not the case that today is Friday–Today is not Friday•At least 10 inches of rain fell today in Miami–It is not the case that at least 10 inches of rain fell today in Miami–Less than 10 inches of rain fell today in Miami14Conjunction15Conjunction: p ^ q is true when both p and q are true. False otherwiseExample•p: “Today is Friday”, q: “It is raining today”•p˄q “Today is Friday and it is raining today”–true: on rainy Fridays–false otherwise:•Any day that is not a Friday •Fridays when it does not rain 16Disjunction17Disjunction: p v q is false when both p and q are false. True otherwiseExample•p ˅ q: “Today is Friday or it is raining today”–True: •Today is Friday•It is raining today•It is a rainy Friday–False•Today is not Friday and it does not rain18Exclusive or19Exclusive Or is true when exactly one of p, q is true. False otherwiseConditional statement20Conditional Statement: p q is false when p is true and q is false. True otherwiseConditional statement pq •Also called an implication21if p, then q p implies qif p, q p only if qp is sufficient for q a sufficient condition for q is pq if p q whenever pq when p q is necessary for pa necessary condition for p is qq unless not pq follows from pConditional Statement: pq is false when p is true and q is false. True otherwiseExamplep: you go, q: I go. pq means “If you go, then I go”“You go only if I go” (not the same as “If I go only if you go”)Example•If Maria learns discrete mathematics, then she will find a good job–Maria will find a good job when she learns discrete mathematics (q when p)–For Maria to get a good job, it is sufficient for her to learn discrete mathematics (sufficient condition for q is p)–Maria will find a good job unless she does not learn discrete mathematics (q unless not p)22Common mistake for pq•Correct: p only if q•Mistake to think “q only if p”23Example•“If today is Friday, then 2+3=6”–The statement is true every day except Friday even though 2+3=6 is false24Converse, contrapositive and inverse•For p q–Converse: q p –Contrapositive: ┐q  ┐ p–Inverse: ┐p  ┐ q•Contrapositive and conditional statements are equivalent25Biconditional statement26• Biconditional Statement: “p if and only if q”• p  q is true when p, q have the same truth value. False otherwise• Also known as bi-implicationsExample•P: “you can take the flight”, q: “you buy a ticket”•P  q: “You can take the flight if and only if you buy a ticket”–This statement is true •If you buy a ticket and take the flight•If you do not buy a ticket and you cannot take the flight 27Truth table of compound propositions28Precedence of logic operators29Bit operations30Translating English to logical expressionsWhy? English is often ambiguous and translating sentences into compound propositions removes the ambiguity.Using logical expressions, we can analyze them and determine their truth values. And we can use rules of inferences to reason about them31Example“ You can access the internet from campus only if you are a computer science major or you are not a freshman. p : “You can access the internet from campus” q : “You are a computer science major” r : “You are freshmen” p  ( q v ~r ) 32System Specification•Translating sentences in natural language into logical expressions is an essential part of specifying both hardware and software