|
HU Credits:
4
Degree/Cycle:
1st degree (Bachelor)
Responsible Department:
computer sciences
Semester:
1st Semester
Teaching Languages:
Hebrew
Campus:
E. Safra
Course/Module Coordinator:
Prof. Noam Nisan
Yannai A. Gonczarowski
Coordinator Office Hours:
Teaching Staff:
Prof Noam Nisan
Mr.
Course/Module description:
We will study basic concepts in Mathematical Logic (first order logic), formulas, structures, truth values and rules of inference. We will prove the Validity Theorem, Gödel's Completeness Theorem and the Compactness Theorem.
To facilitate the learning experience for programming-oriented students, learning some the proofs in the course will be facilitated via programming exercises. For example, learning the proof of the Tautology Theorem will be facilitated by programming a function whose input is a propositional formula and whose output is either a proof for the validity of the formula (if the formula is a tautology) or a model where the formula is not valid (if the formula is not a tautology).
Course/Module aims:
See learning outcomes.
Learning outcomes - On successful completion of this module, students should be able to:
Understand basic notions in mathematical logic.
Understand the notion of a formula.
Understand induction of formulas.
Understand Gödel's completeness theorem
Attendance requirements(%):
non
Teaching arrangement and method of instruction:
Lecture + self-practice via the Python programming language.
Course/Module Content:
Propositional calculus. Logical connectives. Truth tables. The languages of predicate calculus. Quantifiers. Terms and formulas. Free and bound variables. Structures. Interpretations. Satisfaction of formulas in structures. The theory of a set of structures. Models of a set of formulas. Logical axioms and rules of inference. The Soundness Theorem. Post's Tautology Theorem. Derived rules. The substitution theorem.
The deduction theorem. The constants theorem. Equivalence theorem. Prenex form. Gödel's completeness theorem and the compactness theorem
Required Reading:
non
Additional Reading Material:
Course/Module evaluation:
End of year written/oral examination 50 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 50 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %
Additional information:
Prerequisites: knowledge in the Python programming language.
|
