Discrete Mathematics I

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

• translate an English statement into symbolic form using propositional variables or functions, logical connectives and quantifiers.
• determine the truth value of a compound proposition.
• state the converse, inverse, and contrapositive of an implication.
• verify logical equivalencies.
• determine whether a proposition is a tautology, contingency, or contradiction.
• find the dual of a proposition.
• negate a quantified expression.
• derive a valid conclusion using rules of inference.
• analyze the validity of an argument using rules of inference.
• apply direct proof, indirect proof, and proof by contradiction methods to prove a mathematical theorem.
• determine the cardinality of sets, subsets, power sets and Cartesian products.
• combine sets using set operators.
• prove set identities using the method of subsets, membership tables, and derivations from standard set identities.
• determine if a function is an injection, surjection or a bijection.
• describe the domain, codomain, and range of a function.
• find the image and preimage of a point or set of points of a function.
• find the composition of two or more functions.
• find the inverse of a bijective function.
• derive properties related to the floor and ceiling functions.
• find the value of a term in a sequence.
• represent a sequence in recursive and closed forms.
• evaluate finite sums.
• give a big-O estimate for a function.
• write a simple algorithm.
• determine the time complexity of a simple algorithm.
• use divisibility properties of integers and the division algorithm to derive and prove properties of congruences and modular arithmetic.
• find the greatest common divisor of two integers using the Euclidean algorithm.
• convert the representation of an integer from one base to another.
• prove mathematical theorems using strong and weak principles of mathematical induction.
• convert the representation of a function or set from recursive to closed form, and visa versa.
• solve counting problems using sum, product, inclusion-exclusion (up to three sets), and pigeon hole principles.
• count the number of different combinations and permutations of elements selected from a set. This includes cases of distinguishable and indistinguishable elements as well as selection with and without replacement.
• find the expansion of a binomial expression.
• determine the probability of an event for an equi-probable sample space.
• determine whether or not a relation is reflexive, irreflexive, symmetric, antisymmetric, or transitive.
• represent a relation as a matrix and a digraph.

Optional Topics:

• determine whether a string belongs to the language generated by a given grammar.
• classify a grammar.
• find the language created by a grammar.
• draw the state diagram for a finite-state machine.
• construct a finite-state machine to perform a function.
• determine the output of a finite state machine.