Discrete Structures CMSC 250 Lecture 1 CMSC 250 1 Administrative Syllabus Lecture section MWF 10 11 Lab discussion section Every week mostly Worksheet Quiz Homework Class webpage Three midterms as noted on the syllabus on the class webpage Academic integrity CMSC 250 2 Motivation Why learn this material Some things can be directly applied Some things are good to know Some things just teach a way of thinking and expressing yourself CMSC 250 3 Examples CMSC 250 Directly applied circuits to do addition Conditionals in if statements Things which are good to know for example that the square root of 2 can t be stored Way of thinking the number of primes is infinite 4 Overall theme CMSC 250 Proofs of theorems Examples of theorems 5 Course topics CMSC 250 Propositional logic and circuits Predicate calculus quantification Elementary number theory Mathematical induction Sets Counting combinations and probability Functions Relations Graph theory 6 Chapter 1 Propositional Logic CMSC 250 7 Statement proposition Declarative true or false Symbolized by a letter Examples CMSC 250 Today is Monday 5 2 7 3 6 18 The sky is blue Why is the sky blue Barack Obama Two students in the class have a GPA of 3 275 This sentence is false The current king of France is bald 8 Other symbols and definitions for constructing compound statements Conjunction and is symbolized by Disjunction or is symbolized by Negation not is symbolized by or sometimes CMSC 250 9 Truth table for CMSC 250 p q p q 1 1 1 1 0 0 0 1 0 0 0 0 10 Truth table for CMSC 250 p q p q 1 1 1 1 0 1 0 1 1 0 0 0 11 Truth table for CMSC 250 p p 1 0 0 1 12 Translation of English to symbolic logic statements The sky is blue one simple atomic statement assign a letter or name to it i e b The sky is blue and the grass is green one statement conjunction of two atomic statements each single statement gets a letter or name i e b g and join with i e b g The sky is blue or the sky is purple CMSC 250 one statement disjunction of two atomic statements each single statement gets a name i e b p and join with i e b p 13 Translation 1 The sky is blue or purple two statements the sky is blue name this b the sky is purple name this p it s still a disjunction the sky is blue or the sky is purple b p CMSC 250 14 Translation 2 The sky is blue but not dark two statements the sky is blue name this b the sky is dark name this d conjunction with negation the sky is blue and the sky is not dark the sky is blue and it is not the case that the sky is dark it is not the case that the sky is dark is d b d CMSC 250 15 Translation 3 2 x 6 English x is greater than or equal to 2 and less than or equal to 6 Two statements x is greater than or equal to 2 name this p x is less than or equal to 6 name this q CMSC 250 Becomes p q 16 3 continued 2 x 6 p is actually a compound statement x is greater than 2 or x is equal to 2 r s x is greater than 2 is symbolized by r x is equal to 2 is symbolized by s q is actually a compound statement x is less than 6 or x is equal to 6 x is less than 6 is symbolized by m x is equal to 6 is symbolized by n m n p q becomes r s m n CMSC 250 17 The exclusive or CMSC 250 The exclusive or of p and q is p or q but not both It s indicated using It s the same as p q p q p q p q 1 1 0 1 0 1 0 1 1 0 0 0 18 Precedence between the operators CMSC 250 not has highest precedence and or have equal precedence use parentheses to override the operators default precedence or when a statement has operators with the same precedence or just for clarity a b c 19 Other more advanced truth tables p r q r p r p r p q q p p r q r CMSC 250 20 Discrete Structures CMSC 250 Lecture 2 CMSC 250 21 Special truth tables p p p p p q vs q p p q vs q p CMSC 250 22 Special results in the truth table Tautological proposition a tautology is a statement that can never be false all of the lines of the truth table have the result true Contradictory proposition a contradiction is a statement that can never be true all of the lines of the truth table have the result false Logical equivalence of two propositions two statements are logically equivalent if they will be true in exactly the same cases and false in exactly the same cases all of the lines of one column of the truth table have all of the same truth values as the corresponding lines from another column of the truth table it s indicated using CMSC 250 23 Logical equivalences Theorem 1 1 1 page 14 Double negative p p Commutative p q q p and p q q p Associative p q r p q r and p q r p q r Distributive p q r p q p r and p q r p q p r CMSC 250 24 Further logical equivalences Idempotent p p p Absorption p p q p and p p c Universal bound p c c and p c p Negation p p t and p p q p Identity p t p and p p p and p t t Negations of t and c t c CMSC 250 and c t 25 DeMorgan s laws p q p q Example in English It is not the case that Pete or Quincy went to the store Pete did not go to the store and Quincy did not go to the store p q p q Example in English It is not the case that both Pete and Quincy went to the store Pete did not go to the store or Quincy did not go to the store CMSC 250 26 Prove by truth table and by rules p q q p p p q p q p q p p q p q p q q p CMSC 250 27 Discrete Structures CMSC 250 Lecture 3 CMSC 250 28 Conditional statements Hypothesis conclusion If this then that The hypothesis implies the conclusion has lowest precedence Examples in English If it is raining I will carry my umbrella If you don t eat your dinner you will not get dessert CMSC 250 p q p q 1 1 1 0 0 1 0 0 1 0 1 1 29 Converting to p …
View Full Document
Unlocking...