MATH275

Download as PDF

Discrete Mathematics

MathematicsScience, Tech, Engr & Math

Overview Goals, Topics, and Objectives Assessment, Requirements, and Outcomes Register for this Course

Course Goals

To provide an introduction to the mathematical reasoning required to read, comprehend, and construct mathematical arguments.
To provide methods for working with discrete structures-the abstract mathematical structures used to represent discrete objects and the relationships between these objects.
To demonstrate classes of problems solved by the specification of algorithms.
To present applications of discrete mathematics-in particular, applications to computer science.

Core Course Topics

Logic and Proof
1. Define the negation of a proposition.
2. Define (using truth tables) the disjunction, conjunction, exclusive or, conditional, and biconditional of the propositions p and q.
3. Define the converse, inverse, and contrapositive of a conditional statement.
4. Determine whether two propositions are logically equivalent.
5. Determine whether an argument is valid.
6. Describe what is meant by, and give examples of, direct proofs and proofs by contradiction.
7. Prove a biconditional statement.
8. Apply the rules of logic to evaluate and construct mathematical arguments and proofs.
Sets and Functions
1. Determine whether one set is a subset of another.
2. Determine the cardinality of a set.
3. Determine the union, intersection, difference, and symmetric difference of two sets.
4. Explain the relationship between logical equivalences and set identities.
5. Define the domain, codomain, and range of a function.
6. Define what it means for a function to be one-to-one or onto and give examples of functions that are or are not one-to-one or onto.
7. Define and apply various types of functions encountered in discrete structures, including the ceiling and floor functions and recursive functions.
Algorithms
1. Describe algorithms, including search and sort algorithms, that will accomplish various tasks.
2. Express an algorithm in pseudocode.
3. Determine properties of an algorithm, including its computational complexity.
Induction and Recursion
1. Prove a statement by mathematical induction.
2. Prove a statement using strong induction.
3. Give recursive definitions and describe recursive algorithms.
4. Solve problems involving basic results from number theory, matrices, sequences and summations, and recursive definitions.
5. Use assertions to determine the correctness of a program.
Counting
1. Solve problems, including probability problems, that require counting principles (including the product rule, the sum rule, and principle of inclusion-exclusion).
2. State, and solve problems involving, the Pigeonhole Principle.
3. Determine, and solve problems involving, the number of permutations or combinations of n objects taken r at a time.
Relations
1. Describe properties of a relation, including an n-ary relation.
2. Represent a relation using various methods.
3. Determine whether a relation is an equivalence relation.
4. Determine whether a relation is a partial ordering.
Graphs and Trees
1. Describe properties of graphs, including paths and connectedness.
2. Determine whether a graph is bipartite.
3. Determine whether two graphs are isomorphic.
4. Determine whether a graph is a tree.
5. Apply results relating the numbers of edges and vertices of various types in trees.
Boolean Algebra
1. Compute the complement of a Boolean function.
2. Compute the sum and product of Boolean functions.
Modeling Computation
1. Describe properties of finite-state machines.

Learning Objectives

Upon successful completion of this course, students will be able to:

Logic and Proof: Define the negation of a proposition.

Logic and Proof: Define (using truth tables) the disjunction, conjunction, exclusive or, conditional, and biconditional of the propositions p and q.

Logic and Proof: Define the converse, inverse, and contrapositive of a conditional statement.

Logic and Proof: Determine whether two propositions are logically equivalent.

Logic and Proof: Determine whether an argument is valid.

Logic and Proof: Describe what is meant by, and give examples of, direct proofs and proofs by contradiction.

Logic and Proof: Prove a biconditional statement.

Logic and Proof: Apply the rules of logic to evaluate and construct mathematical arguments and proofs.

Sets and Functions: Determine whether one set is a subset of another.

Sets and Functions: Determine the cardinality of a set.

Sets and Functions: Determine the union, intersection, difference, and symmetric difference of two sets.

Sets and Functions: Explain the relationship between logical equivalences and set identities.

Sets and Functions: Define the domain, codomain, and range of a function.

Sets and Functions: Define what it means for a function to be one-to-one or onto and give examples of functions that are or are not one-to-one or onto.

Sets and Functions: Define and apply various types of functions encountered in discrete structures, including the ceiling and floor functions and recursive functions.

Algorithms: Describe algorithms, including search and sort algorithms, that will accomplish various tasks.

Algorithms: Express an algorithm in pseudocode.

Algorithms: Determine properties of an algorithm, including its computational complexity.

Induction and Recursion: Prove a statement by mathematical induction.

Induction and Recursion: Prove a statement using strong induction.

Induction and Recursion: Give recursive definitions and describe recursive algorithms.

Induction and Recursion: Solve problems involving basic results from number theory, matrices, sequences and summations, and recursive definitions.

Induction and Recursion: Use assertions to determine the correctness of a program.

Counting: Solve problems, including probability problems, that require counting principles (including the product rule, the sum rule, and principle of inclusion-exclusion).

Counting: State, and solve problems involving, the Pigeonhole Principle.

Counting: Determine, and solve problems involving, the number of permutations or combinations of n objects taken r at a time.

Relations: Describe properties of a relation, including an n-ary relation.

Relations: Represent a relation using various methods.

Relations: Determine whether a relation is an equivalence relation.

Relations: Determine whether a relation is a partial ordering.

Graphs and Trees: Describe properties of graphs, including paths and connectedness.

Graphs and Trees: Determine whether a graph is bipartite.

Graphs and Trees: Determine whether two graphs are isomorphic.

Graphs and Trees: Determine whether a graph is a tree.

Graphs and Trees: Apply results relating the numbers of edges and vertices of various types in trees.

Boolean Algebra: Compute the complement of a Boolean function.

Boolean Algebra: Compute the sum and product of Boolean functions.

Modeling Computation: Describe properties of finite-state machines.