MATH 2305 - Discrete Mathematics (3-3-0). A course designed to prepare math, computer science and engineering majors with a background in abstraction, notation and critical thinking for the mathematics most directly related to computer science. Topics to be covered include formal logic, various proof techniques, mathematical induction, recursion, sets and relations. The number of topics required for coverage has been kept modest so as to allow adequate time for students to develop theorem-proving skills.

Textbook: Discrete Mathematics with Applications, 5th Edition by Epp. Cengage Learning ISBN: 9781337694193

The main objective of the course is to introduce the student to the concept of "proof" applied in different settings.

Throughout the course, students will be expected to demonstrate their understanding of Discrete Mathematics by being able to do each of the following:

1. 1. Use mathematically correct terminology and notation.  
   2. Discuss definitions and diagram strategies for potential proofs in logical sequential order without mathematical symbols (plain English).

1.4 Construct direct, indirect proofs and provide strategies for division into cases.

1.5 Use counterexamples.

1.6 Apply logical reasoning to solve a variety of problems.

2. Propositional Logic

2.1 Write English sentences for logical expressions and vice-versa. Use standard notations of

propositional logic.

2.2 Complete and use truth tables for expressions involving the following logical connectives:

negation, conjunction, disjunction, conditional, and biconditional.

2.3 Define and use the terms: proposition (statement), converse, inverse, contrapositive, tautology, and contradiction.

2.4 Apply standard logical equivalences. Be able to prove that two logical expressions are or are

not logically equivalent.

2.5 Determine if a logical argument is valid or invalid by tables or trees. Apply standard rules of inference including (but not limited to) Modus Ponens, Modus Tollens, Transitivity, and Elimination. Recognize fallacies such as the Converse Error and the Inverse Error.

3. Predicate Logic

3.1 Translate between English sentences and logic symbols for universally and existentially quantified

statements, including statements with multiple quantifiers.

3.2 Write the negation of a quantified statement involving either one or two quantifiers.

3.3 Determine if a quantified statement involving either one or two quantifiers is true or false.

4. Elementary Number Theory

4.1 Construct correct direct and indirect (contradiction and contraposition) proofs involving

concepts from elementary number theory such as even and odd integers, rational and

irrational numbers, and divisibility. 

4.2 Find a counterexample to show that a proposed statement involving concepts from

elementary number theory is false.

4.3 State and use the Quotient-Remainder Theorem (Division Algorithm) and apply the mod, div, floor and ceiling in the proof of the Division Algorithm.  

4.4 Apply the Euclidean Algorithm.

5. Mathematical Induction

5.1 State the Principle of Mathematical Induction.

5.2 Construct induction proofs involving summations, inequalities, divisibility arguments, counting arguments, recurrence relation correctness and incorrectness. 

6. Set Theory

6.1 Use set notation, including the notations for subsets, unions, intersections, differences,

complements, cross (Cartesian) products, and power sets.

6.2 Prove that a proposed statement involving sets is true, or give a counterexample to show that

it is false.  Be able to prove, if so, that a set is empty.

9. Relations

9.1 State the definitions of binary relation, reflexive, symmetric, transitive, equivalence relation,

equivalence class, class representative, and partition.

9.2 Show that a binary relation on a set is an equivalence relation, or give a counterexample to

show that it is not.

9.3 Given an equivalence relation on a set, find the equivalence classes of the relation and show

that they form a partition of the set.

9.4 Show that congruence modulo m is an equivalence relation on the integers, and that

congruence classes modulo m form a partition of the integers.

9.5 Sequences.  Recursive Relations.  Solution by Iteration.  Check Correctness by Induction. First Order Difference Equations.  Second Order Difference Equations.  

The course will cover sections from the following chapters in order to meet the outcomes above: 

Core Sections:

Logic (Chapters 2 and 3) Sections 2.1 to 2.4 and Sections 3.1 to 3.4

Number Theory (Chapter 4) Section 4.1 to 4.4 and 4.6 to 4.8

Induction and Sequences (Chapter 5) Sections 5.1 to 5.4 and 5.6, 5.7

Set Theory (Chapter 6) Sections 6.1 and 6.2

Relations (Chapter 8) Sections 8.1, 8.2 and 8.3

Optional Sections (two to five sections from below):

Functions (Sections 7.1 to 7.3)

RSA (Section 8.4)

Cardinality (Section 7.4)

Partial Order Relations (Section 8.5)

Discrete Probability (Sections 9.8 and 9.9)

Pigeonhole Principle (Section 9.4)

Graphs (Sections 10.1 to 10.4)

Counting (Sections 9.2 to 9.6)

Analysis of Algorithm Efficiency (Sections 11.1 to 11.5)

Upon successful completion of the course, a student should be able to:

1. Construct mathematical arguments using logical connectives and quantifiers.
2. Verify the correctness of an argument using propositional and predicate logic and truth tables.
3. Demonstrate the ability to solve problems using counting techniques and combinatorics in the context of discrete probability.
4. Solve problems involving recurrence relations and generating functions.
5. Use graphs and trees as tools to visualize and simplify situations.
6. Perform operations on discrete structures such as sets, functions, relations, and sequences.
7. Construct proofs using direct proof, proof by contraposition, proof by contradiction, proof by cases, and mathematical induction.
8. Apply algorithms and use definitions to solve problems and prove statements in elementary number theory.