CS 291 Final Exam Terms and Concepts

Be familiar with truth tables and know how to use them to show the truth value of statements.
Know what makes a statement a well-formed formula (wff).
Understand the hierarchy of evaluation for the logical connectives and be able to unambiguously interpret wffs.
Know how to show that two wffs are logically equivalent by doing a step-by-step proof from one form to the other.
You should be familiar with the basic equivalences from Figure 6.6 on page 404.
Understand what it means for a wff to be a tautology, a contradiction or a contingency and be able to determine which of these any wff is using Quine's method.
Be familiar with Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF). Be able to turn a wff into either form using equivalences and using truth tables.

Know how to do proofs using natural deduction.
You will have access to the Proof Rules on page 422 of your book. Know how to use them to do step-by-step proofs where each step is justified by previous steps and proof rules.
This includes being able to do nested Conditional Proofs (CP) and Indirect Proofs (IP).

Understand predicates, existential quantifiers and universal quantifiers over a domain.
Know what a well-formed formula (wff) is and all the standard terminology associated with this idea.
Be familiar with scope of quantified variables and how to distinguish bound from free variables.
Know the concepts of valid, unsatisfiable and satisfiable as applied to wffs.
Know what universal and existential closures are.

Be familiar with the concept of logical equivalence.
Be able to do various manipulations to show that one logical form is equivalent to another logical form.
Know about prenex normal form and how to to through the steps to put a wff into this form.
Beyond this, be able to put wffs into disjunctive normal form and conjunctive normal form.
Be able to formalize English sentences into wffs and find natural sounding English sentences that are equivalent to wffs.

Know how to do formal conditional proofs in FOL using natural deduction.
Be familiar with universal instantiation (UI), existential generalization (EG), existential instantiation (EI), and universal generalization (UG).
Be able to take English sentences, translate them into formal wffs and go through the process of doing a formal proof.

There are various proofs in this section that I won't expect you do do much with.
You should know the Equal for Equals (EE) rule well enough to use it in proofs.
You should extend your ability to formalize English sentences in FOL to include aspects of equality, as in the homework problems.

You should understand the {P} S {Q} syntax used in program correctness proofs.
Know the Assignment Axiom and the Consequence Rules and how to use them in proofs.
Be familiar with the Composition Rule and the If-Then Rule and If-Then-Else Rule and how to use them in proofs. If I expected you to use any of these three rules in proofs, I would give them to you on the exam.
I do not expect you to be able to do correctness proofs with the While Rule or any of the array assignment stuff or program termination proofs.

I expect you to be able to take logical wffs and put them in clausal form, including Skolemization as necessary. This includes being able to carefully apply Skolem's Rule.
You should be able to do resolution proofs, both with propositional logic clauses and first-order logic clauses.
Understand substitution and unification and how they are used in resolution proofs.
Be able to use Robinson's Unification Algorithm to find most general unifiers (mgus).
To restate, be able to do full blown first-order logic resolution proofs from beginning to end.

Given a description of a language, be able to find a regular expression for it.
Know how to do simple manipulations to show that two regular expressions are equivalent.

Given a DFA or NFA, be able to write down the transition table.
Given a regular expression, be able to construct a DFA or NFA for recognizing that language.
Given an FA, be able to find an equivalent regular expression.
Be familiar with the Prolog code for representing and reasoning with FAs.
Understand Mealy Machines and Moore Machines and be able to show what their output would be given an input string.

Know how to use the Pumping Lemma for Regular Languages to show that particular languages are not regular.

Know how to do derivations given a grammar.
Be able to find a grammar for a language given a description of the language.
Understand how to show that a grammar is ambiguous by finding two parse trees for the same sentence.

Know what a pushdown automata is.
Know how to construct a pushdown automaton for a given context-free language.
Be aware that there is a version of the pumping lemma for showing that languages are not context-free.

Be able to describe the Turing Machine model of computation.
Understand the concept of a Universal Turing Machine and why it is so important.

Know what the Church-Turing thesis is and be able to give a brief explanation of it.

Know what a decision problem is and what it means for a decision problem to be decidable or undecidable or partially decidable.
Be able to explain what the Halting Problem is and approximately describe why it is undecidable.