Discrete Mathematics I

At the end of the course, the successful student should be able to:

• write English statements in symbolic form using prepositional variables or functions, logical connectives and any necessary quantifiers;
• determine the truth value of a statement under an interpretation;
• determine the negation, converse, inverse, and contrapositive of a statement;
• verify logical equivalencies;
• demonstrate an understanding of tautologies, contradictions and duals;
• prove the properties of logic;
• determine the cardinality of sets, subsets, power sets and Cartesian products;
• combine sets using the set operators;
• prove set identities using a series of known set identities or by showing that each expression is a subset of the other;
• use membership tables or Venn diagrams to prove set identities;
• classify functions as injective, surjective or bijective;
• demonstrate an understanding of domains, codomains, ranges, mappings and images;
• create new functions by composition;
• find the inverse of an injective function;
• demonstrate an understanding of the floor and ceiling functions;
• compute finite sums;
• give a big-O estimate for a function;
• write a simple algorithm in pseudocode;
• determine the time complexity of simple algorithms;
• demonstrate an understanding of divisibility, the greatest common divisor and modular arithmetic;
• use the Euclidean algorithm to find the gcd of two numbers;
• convert between binary, octal and hexadecimal; 
• demonstrate an understanding of the rules of inference;
• analyze an argument as to its validity using the concepts of mathematical logic;
• use a direct proof, indirect proof, or contradiction to prove a mathematical theorem;
• prove mathematical theorems using formal inductive techniques;
• give a recursive definition of a function or a set;
• use the sum and product rules and tree diagrams to solve basic counting problems;
• apply the inclusion-exclusion principle to solve counting problems for two tasks;
• solve counting problems using the Pigeon-Hole Principle;
• count unordered selections of distinct objects;
• count ordered arrangements of a set of disctinct objects;
• count ordered and unordered selections of r objects chosen with or without repetition from a set of n elements;
• count the number of arrangements of a set of objects some of which are indistinguishable; 
• find the expansion of a binomial;
• determine the probability of a combination of events for an equi-probable sample space;
• determine whether or not a relation is reflexive, irreflexive, symmetric, antisymmetric and 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;
• demonstrate an understanding of the vocabulary of graph theory;
• determine whether a graph is bi-partite or not;
• represent a graph as an adjacency matrix and an incidence matrix;
• determine whether a pair of graphs are isomorphic;
• find circuits and paths in a graph;