MATH 2420 – Content Standards

Title: Discrete Mathematics

As a result of completing the course Discrete Mathematics, MATH 2420, students will be able to:

  1. Identify logical form, form compound statements using the connectives and, or and not, determine truth tables of more general compound statements, determine whether two statement forms are logically equivalent or nonequivalent, apply De Morgan’s laws to form negations of and and or, determine whether a statement is a tautology or a contradiction, and use logical equivalences to simplify statement forms.
  2. Determine truth tables for compound statements containing conditional and biconditional connectives, represent if-then as or, and then use this representation to negate an if-then statement, determine the negation, contrapositive, converse and inverse of a conditional statement, rewrite a conditional statement as an “only if” statement, and as sufficient and necessary conditions.
  3. Determine whether and argument is valid or invalid, use valid argument forms such as modus ponens, modus tollens, etc. to do complex deductions, and illustatrate a proof by contradiction using the knights and knaves example.
  4. Give the input/output table for the following gates: OR, AND and NOT, find a Boolean expression (input/output table, respectively) of a circuit, find a circuit corresponding to a Boolean circuit (input/output table, respectively) by finding the disjunctive-normal or sum-of-products form, determine whether two logical circuits are equivalent, and simplify a combinatorial circuit.
  5. Represent a binary (hexadecimal, octal) number as a decimal number, represent a decimal (hexadecimal, octal) number in binary notation, represent a binary number in hexadecimal (octal) notation, and add and subtract binary numbers.
  6. Determine the domain and the truth set of a predicate variable, identify universal and existential statements, be able to write these statements in formal and informal language, and identify universal conditional statements, negate universal and existential statements, as well as statements containing both universal and existential statements.
  7. Define an even (odd) integer, prove an existential statement using an example, use a direct proof to prove universal statements such as “The sum of an even integer and an odd integer is odd”, “If the difference of any two integers is odd, then so is their sum”, etc., disprove a universal statement by an example, follow the directions for writing proofs of universal statements, and identify common mistakes in proving statements.
  8. Use direct proofs or counterexamples to prove or disprove statements involving the rational numbers.
  9. Use direct proofs or counterexamples to prove or disprove statements involving the divisibility of integers, and use the quotient-remainder theorem to illustrate a proof by division into cases.
  10. Use methods of proofs by contradiction and contraposition to prove various statements.
  11. Find the explicit formula for a sequence, and be able to do calculations involving factorial, summation and product notations.
  12. Be able to prove statements using mathematical induction.
  13. Determine whether one set is a subset of another, whether two sets are equal, whether an element is in a set or not, be able to determine the union, intersection, difference and complement of sets, illustrate sets using Venn diagrams, determine the Cartesian product of two or more sets, prove set identities, use set identities to derive new set properties from old set properties, use Venn diagrams to prove set identities, determine whether sets form a partition of a given set, and determine the power set of a set.
  14. Determine whether a relationship is a function or not, determine the domain, co-domain, range of a function, and the inverse image of x, prove or disprove whether a function is one-to-one or not, determine whether a function is onto or not, determine the inverse of a one-to-one correspondence, determine the composition of two functions, and show that if two functions are one-to-one (onto) so too is their composition.
  15. Determine the arrow diagram of a relation, whether a relation is a function or not, determine the inverse of a relation, whether a relation is reflexive, symmetric or transitive, determine the transitive closure of a relation, show that the binary relation induced by a partition is an equivalence relation, and show that the set of equivalence classes of an equivalence relation on A forms a partition of A.
  16. Identify loops, parallel edges, etc. in a graph, draw the complete graph on n vertices, and the complete bipartite graph on (m,n) vertices, determine whether a graph is bipartite or not, list all the subgraphs of a given graph, determine the degree of a vertex in a graph, prove that the sum of the degrees of the vertices is equal to twice the number of edges, show that in any graph there is an even number of vertices of odd degree, apply these results, and determine the complement of a simple graph.
  17. Determine whether a walk is a path, simple path, closed walk, circuit or a simple circuit, determine whether a graph is connected or not, prove that a graph has an Euler circuit if and only if the graph is connected and every vertex of the graph has even degree, determine whether a given graph has an Euler circuit and, if so, indicate one, prove that a graph has an Euler path if and only if the graph is connected and has exactly two vertices of odd degree, determine whether a given graph has an Euler path and, if so, indicate one, and determine whether a graph has a Hamiltonian circuit and, if so, indicate one.
  18. Determine whether a graph is a tree or not, show that any tree with more than one vertex has two leaves, show that any tree with n vertices has n-1 edges, show that if G is an connected graph with n vertices and n-1 edges, then G is a tree, determine in a rooted tree, the root, level of a given vertex, height of the tree, children, parent, siblings, ancestors and descendants of a vertex, determine whether a given tree is a binary or full binary tree, and prove results regarding binary trees.
  19. Apply Kruskal’s algorithm or Prim’s algorithm to determine a minimal spanning tree for a given graph.