# Elementary Discrete Math

###### Course Description

MAT/CSC1053 Elementary Discrete Mathematics [3]. An elementary study of discrete mathematics as it relates to computer science. Topics include functions, proof techniques, sets, algebra, summation, number systems, logic, Boolean algebra, probability, combinatorics, and graph theory.

Prerequisite: A grade of C- or better in MAT1013g, or a passing score on the Trigonometry Proficiency Examination.

###### Topic 1: Functions Relations And Sets
• Functions (surjections, injections, inverses, composition)
• Relations (reflexivity, symmetry, transitivity, equivalence relations)
• Sets (Venn diagrams, complements, Cartesian products, power sets)
• Pigeonhole principle
• Cardinality and countability
###### Learning Objectives:
1. Explain with examples the basic terminology of functions, relations, and sets.
2. Perform the operations associated with sets, functions, and relations.
3. Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.
###### Topic 2: Basic Logic
• Propositional logic
• Logical connectives
• Truth tables
• Normal forms (conjunctive and disjunctive)
• Validity
• Predicate logic
• Universal and existential quantification
• Modus ponens and modus tollens
• Limitations of predicate logic
###### Learning Objectives:
1. Apply formal methods of symbolic propositional and predicate logic.
2. Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms.
3. Use formal logic proofs and/or informal but rigorous logical reasoning to, for example, predict the behavior of software or to solve problems such as puzzles.
4. Describe the importance and limitations of predicate logic.
###### Topic 3: Proof Techniques
• Notions of implication, converse, inverse, contrapositive, negation, and contradiction
• The structure of mathematical proofs
• Direct proofs
• Proof by counterexample
• Mathematical induction
• Strong induction
• Recursive mathematical definitions
• Well orderings
###### Learning Objectives:
1. Outline the basic structure of and give examples of each proof technique described in this unit.
2. Discuss which type of proof is best for a given problem.
3. Relate the ideas of mathematical induction to recursion and recursively defined structures.
4. Identify the difference between mathematical and strong induction and give examples of the appropriate use of each
###### Topic 4: Basics Of Counting
• Counting arguments
• Sum and product rule
• Inclusion-exclusion principle
• Arithmetic and geometric progressions
• Fibonacci numbers
• The pigeonhole principle
• Permutations and combinations
• Common examples
###### Learning Objectives:
1. Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application.
###### Topic 5: Graphs And Trees
• Trees
• Undirected graphs
• Directed graphs
• Spanning trees/forests
• Traversal strategies
###### Learning Objectives:
1. Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each.
2. Demonstrate different traversal methods for trees and graphs.
3. Model problems in computer science using graphs and trees.
4. Relate graphs and trees to data structures, algorithms, and counting.
Topic revision: r3 - 2013-10-24 - RobertKasper

TWiki

* Webs

Copyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback