CS 498mp3: Logic in Computer Science: Skills list for midterm exam
In general, you should know the material covered on the topics of propositional logic and first order logic, the theorems there, and consequences of them.
While you do *not* have to be able to reproduce the proofs of major theorems,
you should have understood them in reasonable detail so as to apply the
techniques in other smaller problems.
You are also encouraged to look at the homework problems and solutions.
Some questions will be similar to these (but less hard as it is
an exam setting).
Some other specific skills you should know include:
- Propositional logic
- Ability to model properties in propositional logic
- Ability to apply the theorems in solving problems
(e.g., using Konig's lemma or compactness theorem).
- Ability to prove validity of formulas using resolution,
formally.
- Technical ability to be able to convert formulas to
certain normal forms, in particular being able
to put formula in CNF/
- Ability to reduce satisfiability of propositional formulas
to satisfiability in certain normal forma, especially CNF,
and especially using polynomial blow-up (Tseitin's method).
- First-order logic
- Ability to model properties in first-order logic.
- Ability to construct models that satisfy/falsify given
FO formulas
- Ability to construct models and to work with them.
- Ability to prove inexpressiveness of FOL using simply
model constructions or using compactness theorem.
- Know the *consequences* of the fundamental theorems
(Godel's strong completeness theorem, incompleteness theorem,
Compactness theorem, Lowenheim-Skolem theorem, and
undecidability of FOL, in particular for FO theories).