Entry requirements

5 credits in mathematics of computer science. Participation in Algebra I.

Learning outcomes

On completion of the course, the student should be able to:

• explain how the formulas in predicate logic can be interpreted as true or false;
• explain induction and recursion over terms, formulas, and proofs, and perform simple induction proofs in this field;
• translate statements and reasoning from natural language to propositional and predicate logical language;
• explain the concepts tautology, valid syllogism, logical truth and logical consequence;
• determine, in elementary cases, if a propositional or predicate logical argument is valid and, in that case, implement a formal proof of the deduction or otherwise give a counterexample to the argument;
• perform simple formal proofs in an interactive proof system;
• formulate the soundness theorem and the completeness theorem, explain their meaning and apply them in concrete examples.

Content

Language of propositional logic and languages of predicate logic. Functionally complete set of connectives. Formalisation of natural language. Induction over terms, formulas and proofs. Tautology, evaluation, counter example evaluation. Truth table. Structure for a given first order predicate language. Interpretation of a first order language in a structure. Model and counter model. Satisfiability. Axioms for a theory. Provability, natural deduction, consistency and independence. The concepts of soundness and completeness of a proof system. Incompleteness. Compactness theorem.

Translation of simple formal proofs or proofs in natural language in an interactive proof system. Some information about incompleteness.

Instruction

Lectures and lessons. Assignments and computer exercises that can provide bonus points for the regular exam.

Assessment

Written examination at the end of the course.

If there are special reasons for doing so, an examiner may make an exception from the method of assessment indicated and allow a student to be assessed by another method. An example of special reasons might be a certificate regarding special pedagogical support from the disability coordinator of the university.