Below is an outline of the concepts covered during the course. The final exam is cumulative, but will focus on material from the second half of the course (bolded below). You should expect several concepts from the first part of the course to re-appear. I won’t force you to write any Fitch-style proofs, but I may still ask questions about logic, truth tables, and the process of proving/deriving propositions in our logical system. The following topics are all fair game for the final:
- Sets
- Definition
- Notation
- Set builder notation
- Set equality
- Subset / proper subset
- Power sets
- Union / intersection / difference
- Lists
- Definition
- Notation
- Comparison with sets
- Relations
- Definition
- Notation
- Cartesian product
- Relational databases / basic SQL
- Functions
- Definition
- Notation
- Comparison with relations
- Function composition
- Math functions vs. programming language functions
- Partial vs. total functions
- One-to-one / onto / bijective functions
- Invertable functions
- Propositional logic
- Propositions
- Evaluation of the truth of compound propositions (using the Suppes-style diagrammatic method)
- Truth tables (you’ll need to know definitions of the connectives for this)
- Truth table arguments (and if they are valid/invalid)
- Bit strings and XOR ciphers
- Recursion and Induction
- Definitions
- Recurrence relations
- Tracing recursive functions
- Proving properties of recursive functions
- Regular Expressions
- Definitions
- Formal notation (not Java syntax)
- Construction of REs
- Relation to formal languages
- Connections with finite automata
- Finite Automata
- Definitions / Notation
- State transition diagrams
- NFA vs DFA
- Construction of FAs
- Mealy Machines
- Turing Machines
- Definitions / Notation
- Construction of TMs
- Computability
- Halting problem
- Formal Grammars
- Chomsky hierarchy
- Connections with FAs, TMs
- Connections with formal languages
- Connections with regular expressions