- translate between English statements and propositional calculus
- construct truth tables for compound logical statements
- determine, using truth tables, whether two compound statements are equivalent, or whether a single statement is a tautology, a contradiction, or neither
- write the contrapositive, converse, and inverse of a logical statement
- convert any of the following representations to any other:
- digital logic circuit
- a logical statement
- an input/output table

- use basic rules of inference (e.g., modus ponens and modus tollens) to determine the validity of an argument

- use quantifiers and variables to translate between a formal and informal version of a statement
- write the negation, contrapositive, converse, and inverse of a quantified statement

- use the principle of mathematical induction to prove a formula

- determine the elements of subsets, union, intersection, difference, and complement of given sets
- list the elements of the cartesian product of two sets
- using Venn diagrams, demonstrate the basic laws (set identities) governing set operations
- show that an alleged set property is false by finding a counterexample

- specify the domain, co-domain, range, and inverse image of a function
- identify a function as one-to-one, onto, or as a one-to-one correspondence
- identify the basic properties of a composition of two functions, given the basic properties of each function
- specify the finite-state automaton, given either its transition diagram or its next-state table
- design a finite-state automaton that accepts a specified language
- specify the language accepted by a given finite-state automaton
- determine the set of strings in a language, given an alphabet and a description of the language

- compute terms of a sequence that is expressed as a recursive relation
- verify that a sequence given by an explicit formula satisfies a specific recurrence relationship
- write a recursive definition for a set of strings with a specified characteristic
- compute several values of a recursively defined function

- list the elements of a binary relation
- determine whether a binary relation is an equivalence relation and, if so, list the equivalence classes
- determine whether a given binary relation is a partial order relation
- use a Hasse diagram to represent a given partial order relation
- determine a topological sorting for a given partial order relation
- explain the application of a partial order relation to a job-scheduling problem

- define and illustrate basic terms associated with graphs and trees
- explain how a graph is used to represent a knowledge base
- determine the number of paths of a specified length from one vertex to another
- construct the adjacency matrix of a graph and a graph of an adjacency matrix
- explain how a tree is used to sort a list of items
- define and illustrate basic terms associated with paths and circuits in graphs and trees
- show the existence or absence of an Euler or Hamiltonian circuit in a graph