The final will be held 1:30 to 3:30 in the usual classroom.
The exam will be multiple choice, like our midterm and last year's midterm. Naturally, the exam will focus somewhat on testable topics; so be it. (E.g., asking you to do a complicated deduction is more suited to homework than an exam; simple deductions are fair game.)
I will give references, like the list of logical axioms in our system. You can also bring a note page: One side of a 8.5x11 sheet, or the equivalent area. Books and calculators (?!) will not be allowed.
Topics:
Zero-knowledge proofs: Be familiar with the main concepts of soundness, completeness, zero-knowledge, and non-triviality. Possible questions: As in last year's midterm, I'll present a new ZKP and ask you to explain what happens when we make minor and significant changes.
Enderton chapter 2, topics: 2.0, 2.1, 2.2, 2.4, 2.5. For the following, detailed proofs will not be on the test, though the statement and general idea of the proof may be on the exam:
- Completeness theorem
- Undecidability of number theory with + and *
- Decidability of number theory with only + (Presburger arithmetic)
Note that details of the soundness theorem, which amount to showing the logical validity of the axioms, is fair game. The compactness theorem follows easily from soundness and completeness and is allowed.
Make sure you understand the key concepts of
- true in a structure,
- logical consequence of a set of wffs,
- deducible from a set of wffs,
- decidable by an algorithm,
and the relationships among these that we discussed.
Also, know the difference between a parameter of a first order language (like + in the language of number theory) and the interpretation of + in a particular structure like the natural numbers, numbers mod 5, or the complexes.
Be able to build a structure that satisfies a given set of wffs and to determine whether a wff is true in a structure and variable assignment.
#final_exam
