MTH 288 Discrete Mathematics (3 cr.)
Presents topics in sets, counting, graphs, logic, proofs, functions, relations, mathematical induction, Boolean Algebra, and recurrence relations.
Prerequisite: MTH 263 Calculus I with a grade of C or better or equivalent. Lecture 3 hours per week.
Logic:
Propositional Logic
Conjunction, Disjunction and Exclusive OR, Negation
Conditional and Biconditional Statements
Tautology and Contradiction
Logical Equivalence
Truth Tables
Rules of Inference
Valid Arguments
Fallacies
Universal and Existential Quantifiers
Rules of Inference for Quantified Statements
Logic Unit Objectives: Construct Compound Statements using logical operators. Construct Truth Tables for Compound Statements. Prove Logical Equivalence. Employ De Morgan Laws. Identify valid and fallacious argument forms. Employ Universal and Existential Quantifiers. Translate English statements using Quantifiers. Employ Rules of Inference for Quantified Statements in argument construction.
Proofs:
Proving Conditional and Biconditional Statements
Proving Universal Statements
Direct proof
Contrapositive Proof of P → Q (Assume Not-Q and prove Not-P)
Proof by Contradiction of P → Q (Assume P and Not Q, and prove contradiction)
Existence and Uniqueness proof
Proofs Unit Objectives: Apply the appropriate techniques to construct proofs of mathematical statements in a variety of contexts utilizing various methods of proof: direct and contrapositive proof, reduction to contradiction, existence and uniqueness, and disproof.
Set Theory:
Introduction to Sets:
Set membership, equality of sets, empty set, Universal set, Union, Intersection, Complement
Subsets
Power Sets
Cartesian Product
Venn Diagrams
Bijective (one-to-one) mappings
Finite and infinite sets
Dedekind infinite sets
Countable and uncountable sets
Cardinality
Set Theory Unit Objectives: Classify and distinguish various finite and infinite sets; apply the elements of basic set theory to construct proofs of statements involving the concepts of set membership, subsets, and cardinality.
[Proofs involving set membership, subsets, cardinality. Set Theory learning unit should include proofs that two sets (finite or infinite) are equinumerous (of the same size). Proof involves a construction of bijective function between the sets]
Functions:
Domain and Range
Injective, Surjective, and Bijective Functions
Composition of Functions
Inverse of a Function
Functions Unit Objectives: Identify injective, surjective, and bijective functions, composition of functions and inverse functions.
[Proofs involving injective, bijective, composition and inverse functions]
Relations:
Relation Properties: Reflexive and Irrefelexive, Symmetric, Antisymmetric, and Transitive
Closures of Relations
Equivalence Relations
Equivalence Classes
Partial Orderings
Relations Unit Objectives: Demonstrate sufficient knowledge and reasoning skills by proving statements involving relations (equivalence, partitions, and closure), functions (injective, bijective, inverse), divisibility and congruence, and partial order.
[Proofs involving properties, equivalence, partitions, closure, partial order]
Number Theory:
Properties of Integers
Divisors and Prime Numbers
Primes and Unique Factorization (Fundamental Theorem of Arithmetic)
Greatest Common Factor
Division Algorithm
Modular Arithmetic (Congruences)
Number Theory Unit Objectives: Find divisors, GCF and LCM, perform unique factorization. Employ Division Algorithm. Perform arithmetic with modular numbers, solve linear congruence equations.
[Proofs involving divisibility and congruence]
Induction and Recursion:
Mathematical Induction
Strong Mathematical Induction
Well-Ordering Principle
Recursively Defined Functions
Induction and Recursion Unit Objectives: Prove statements using mathematical induction and strong induction. Understand properties of Well-Ordering Principle and its equivalence to Mathematical Induction. Identify recursively generated functions and recursively defined sets.
[Proofs involving Mathematical Induction and Recursion]
Counting:
Product Rule and Sum Rule
Inclusion-exclusion principle
The Pigeonhole Principle
Permutations and Combinations
Binomial coefficients
Counting Unit Objectives: Solve basic combinatorial problems relating to counting principles, permutations and combinations, binomial coefficients, inclusion-exclusion principle, and basic discrete probability.
Graphs and Trees:
Graphs: definitions and basic properties
Paths and Circuits
Trees
Graphs and Trees Unit Objectives: Understand graph terminology, types of graph connected graphs, components of graph, Euler graph, Hamiltonian path and circuits. Apply properties of graphs to construct mathematical trees, paths, and circuits.
Boolean Algebra and Logic Gates (optional, but taught at most 4-year colleges in Discrete Math course):
Boolean Algebra
Boolean Sum, Product and Complement
Boolean Variables and Boolean Functions
Identities of Boolean Algebra
Logic Gates
Combinations of Gates
Circuits
Minimization of Circuits
Boolean Algebra Unit Objectives: Identify properties of Boolean expressions and functions, and Identities of Boolean Algebra. Construct circuits for a given output.