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 or 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 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;
• determine if a set is countable or uncountable;
• 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;
• find the sum, difference, product, join, and meet of two matrices; 
• 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 objects of a finite set;
• 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, symmetric, and or transitive;
• combine relations and form the composite of two or more relations’
• find the inverse and complement of a relation;
• determine the projection and join of two n-ary relations;
• represent a relation as a matrix and a digraph;
• find the reflexive, symmetric and transitive closures of a relation;
• identify the various types of graphs;
• draw graph models;
• 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;
• distinguish between a graph and a tree;
• describe the components and properties of various types of trees;
• 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;