Discrete Structures CMSC 250 Lecture 1AdministrativeMotivationExamplesOverall themeCourse topicsChapter 1, Propositional LogicStatement/propositionOther symbols and definitions for constructing compound statementsTruth table for Truth table for Truth table for Translation of English to symbolic logic statementsTranslation #1Translation #2Translation #3#3 continued- 2 x 6The exclusive orPrecedence between the operatorsOther "more advanced" truth tablesDiscrete Structures CMSC 250 Lecture 2Special truth tablesSpecial results in the truth tableLogical equivalences Theorem 1.1.1 - page 14Further logical equivalencesDeMorgan's lawsProve by truth table and by rulesDiscrete Structures CMSC 250 Lecture 3Conditional statementsConverting to ContrapositiveConverse and inverseOnly ifBiconditionalOther English words for implicationArgumentDiscrete Structures CMSC 250 Lecture 4Rules of Inference (Table 1.3.1- Page 39)Proofs using rules of inferenceConditional worldsConditional world assumption leads to contradictionProve using the conditional world methodsDiscrete Structures CMSC 250 Lecture 5Use both conditional world methods1CMSC 250Discrete StructuresCMSC 250Lecture 12CMSC 250AdministrativeSyllabusLecture section: MWF 10-11Lab/discussion section Every week (mostly):–Worksheet–Quiz –HomeworkClass webpageThree midterms, as noted on the syllabus (on the class webpage)Academic integrity3CMSC 250MotivationWhy learn this material?Some things can be directly appliedSome things are good to knowSome things just teach a way of thinking and expressing yourself4CMSC 250ExamplesDirectly applied- circuits to do additionConditionals in if statementsThings which are good to know- for example that the square root of 2 can’t be storedWay of thinking- the number of primes is infinite5CMSC 250Overall themeProofs of theoremsExamples of theorems6CMSC 250Course topicsPropositional logic (and circuits)Predicate calculus - quantificationElementary number theoryMathematical inductionSetsCounting - combinations and probabilityFunctionsRelationsGraph theory7CMSC 250Chapter 1, Propositional Logic8CMSC 250Statement/propositionDeclarative (true or false)Symbolized by a letterExamples:–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.9CMSC 250Other symbols and definitionsfor constructing compound statementsConjunction"and" is symbolized by Disjunction"or" is symbolized by Negation"not" is symbolized by ~ (or sometimes )10CMSC 250Truth table for p qp q1 11 0 0 1 0 0100011CMSC 250Truth table for p qp q1 11 0 0 1 0 0 111012CMSC 250Truth table for pp 100113CMSC 250Translation of English to symbolic logic statementsThe sky is blue.–one simple (atomic) statement- assign a letter or name to it, i.e., bThe 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 ^ gThe sky is blue or the sky is purple.–one statement–disjunction of two atomic statements–each single statement gets a name, i.e., b, p–and join with i.e., b p14CMSC 250Translation #1The 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 p15CMSC 250Translation #2The 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 ^ ~ d16CMSC 250Translation #32 x 6English: x is greater than or equal to 2 and less than or equal to 6Two statements:–"x is greater than or equal to 2"- name this p–"x is less than or equal to 6"- name this qBecomes p ^ q17CMSC 250#3 continued- 2 x 6p 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 sq is actually a compound statement–x is less than 6 or x is equal to 6 m n–"x is less than 6" is symbolized by m–"x is equal to 6" is symbolized by np ^ q becomes (r s) ^ (m n)18CMSC 250The exclusive orThe exclusive or of p and q is p or q, but not bothIt’s indicated using It’s the same as (p q) (p q)p qp q1 11 0 0 1 0 0 011019CMSC 250Precedence between the operators~ (not) has highest precedence^ (and) / (or) have equal precedenceuse parentheses to override the operators' default precedence, or when a statement has operators with the same precedence, or just for claritya ^ b c20CMSC 250Other "more advanced" truth tables(p ^ r) (q ^ r)(p ^ ~r) (p ^ r)(p ^ q) (~q ~p)(p ^ ~r) (q ~r)21CMSC 250Discrete StructuresCMSC 250Lecture 222CMSC 250Special truth tablesp ~pp ^ ~p (p ^ ~q) vs. (~q ^ p)(p ^ q) vs. ~ (~q ~p)23CMSC 250Special results in the truth tableTautological 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 24CMSC 250Logical equivalences Theorem 1.1.1 - page 14Double negative:~(~p) pCommutative: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)25CMSC 250Further logical equivalencesIdempotent: p ^ p p and p p pAbsorption: p (p ^ q) p and
View Full Document
Unlocking...