Welcome!Frequently Asked QuestionsCourse goalsSo, what’s this class about?What is Mathematics, really?Discrete Structures We’ll StudyRelationships Between StructuresSome Notations We’ll LearnWhy Study Discrete Math?Uses for Discrete Math in Computer ScienceCourse Outline (as per Rosen)Topics Not CoveredA Proof ExamplePropositionsProof of Pythagorean TheoremFinally: Have Fun!Propositional Logic (§1.1)Definition of a PropositionExamples of PropositionsOperators / ConnectivesSome Popular Boolean OperatorsThe Negation OperatorThe Conjunction OperatorConjunction Truth TableThe Disjunction OperatorDisjunction Truth TableNested Propositional ExpressionsA Simple ExerciseThe Exclusive Or OperatorExclusive-Or Truth TableNatural Language is AmbiguousThe Implication OperatorImplication Truth TableExamples of ImplicationsWhy does this seem wrong?Resolving the DiscrepancyEnglish Phrases Meaning p qConverse, Inverse, ContrapositiveHow do we know for sure?The biconditional operatorBiconditional Truth TableBoolean Operations SummarySome Alternative NotationsCompSci 1021.1Welcome! Discrete Mathematics for Computer ScienceCompSci 102D106 LSRCM, W 1:15-2:30Professor: Jeffrey ForbesCompSci 1021.2Frequently Asked QuestionsWhat are the prerequisites? CPS 6 but CPS 100 preferredMath 31 & 32How does this course fit into the curricula?Useful foundation for courses like Compsci 130 and 140Solid grounding in mathematical foundationsReplaces requirement of Math 135 (probability), Math 124 (Combinatorics) and Math 187 (Logic)What is recitation? Is it required?Recitation is a more hands-on section where you will do problems and discuss solutions. Your work there will be graded.How do keep up to date?Read web page regularly http://www.cs.duke.edu/courses/spring05/cps102Read discussion forum regula rlyhttp://www.cs.duke.edu/phpBB2/index.php?c=37Read your emailCompSci 1021.3Course goalsWhat we want to teachPrecise, reliable, powerful thinkingThe ability to state and prove nontrivial facts, in particular about programsMathematical foundations and ideas useful throughout CSCorrectly read, represent and analyze various types of discrete structures using standard notations.What areasPropositions and ProofsInductionBasics of CountingArithmetic AlgorithmsProbabilityStructuresCompSci 102 © Michael Frank 1.4So, what’s this class about?What are “discrete structures” anyway?What are “discrete structures” anyway?•““DiscreteDiscrete” (” ( “discreet”!) “discreet”!) - Composed of distinct, - Composed of distinct, separable parts. (Opposite of separable parts. (Opposite of continuouscontinuous.).) discretediscrete::continuouscontinuous :: :: digitaldigital::analoganalog•““StructuresStructures” ” - Objects built up from simpler objects - Objects built up from simpler objects according to some definite pattern.according to some definite pattern.•““Discrete MathematicsDiscrete Mathematics” ” - The study of discrete, - The study of discrete, mathematical objects and structures.mathematical objects and structures.CompSci 102 © Michael Frank 1.5What is Mathematics, really?•It’s It’s notnot just about numbers! just about numbers!•Mathematics is Mathematics is muchmuch more than that: more than that:•But, these concepts can be But, these concepts can be aboutabout numbers, numbers, symbols, objects, images, sounds, symbols, objects, images, sounds, anythinganything!!Mathematics is, most generally, the study of any and all absolutely certain truths about any and all perfectly well-defined concepts.CompSci 102 © Michael Frank 1.6Discrete Structures We’ll Study•PropositionsPropositions•PredicatesPredicates•ProofsProofs•SetsSets•FunctionsFunctions•Orders of GrowthOrders of Growth•AlgorithmsAlgorithms•IntegersIntegers•SummationsSummations•SequencesSequences•StringsStrings•PermutationsPermutations •CombinationsCombinations•RelationsRelations•GraphsGraphs•TreesTrees•Logic CircuitsLogic Circuits•AutomataAutomataCompSci 102 © Michael Frank 1.7Relationships Between Structures•““→→” ” ::≝≝ “Can be defined in terms of” “Can be defined in terms of”SetsSequencesn-tuplesMatricesNaturalnumbersIntegersRelationsFunctionsGraphsReal numbersComplex numbersStringsPropositionsProofsTreesOperatorsProgramsInfiniteordinalsVectorsGroupsBitsNot all possibilitiesare shown here.CompSci 102 © Michael Frank 1.8Some Notations We’ll Learn ⎣ ⎦)(deg][)|(),,;(][)() (mod modlcmgcd,/|max min,,,)(:||)}(|{,,},,{)()(1][T01111vaRFEpnnnCrnaaambabaOaaxgfxfBAfAABASTSSxxPxaaxPxxPxqpqpqpqppRmnijbkniiSniin+∗=∈−=Δ⎟⎟⎠⎞⎜⎜⎝⎛⋅≡ΘΩ→∪⊆∅∉∴∃∀⇔→⊕∧¬∏∑LLoLIABAARNZÏααCompSci 102 © Michael Frank 1.9Why Study Discrete Math?•The basis of all of digital information processing is: The basis of all of digital information processing is: Discrete manipulations of discrete structures represented Discrete manipulations of discrete structures represented in memory.in memory.•Useful for solving the following calendarUseful for solving the following calendar–Scheduling cab drivers for the OlympicsScheduling cab drivers for the Olympics–AkamaiAkamai–Formal specification of XMLFormal specification of XML•Discrete math concepts are also widely used throughout Discrete math concepts are also widely used throughout math, science, engineering, economics, biology, math, science, engineering, economics, biology, etc.etc., …, …•A generally useful tool for rational thought!A generally useful tool for rational thought!CompSci 102 © Michael Frank 1.10Uses for Discrete Math in Computer Science•Advanced algorithms Advanced algorithms & data structures& data structures•Programming Programming language compilers & language compilers & interpreters.interpreters.•Computer networksComputer networks•Operating systemsOperating systems•Computer architectureComputer architecture•Database management Database management systemssystems•CryptographyCryptography•Error correction codesError correction codes•Graphics & animation Graphics & animation algorithms, game algorithms, game engines, engines, etc.etc.……•I.e.I.e., the whole field!, the whole field!CompSci 102 © Michael Frank 1.11Course Outline (as per Rosen)1.1.Logic (Logic (§1.1-4§1.1-4))2.2.Proof methods (Proof methods
View Full Document
Unlocking...