Entry requirements

Algebra I

Learning outcomes

In order to pass the course (grade 3) the student should be able to

explain how the formulas in predicate logic can be interpreted as true or false;

translate statements and reasoning from natural language to propositional and predicate logical language;

explain the concepts tautology, valid syllogism, logical truth and logical consequence;;

convert propositional logic formulas to disjunctive and conjunctive normal form;

determine, in elementary cases, if a propositional or predicate logical deduction is valid and, in that case, implement a formal proof of the deduction;

formulate the soundness theorem and the completeness theorem.

Content

Language of propositional logic and of predicate logic. Functionally complete set of connectives. Formalisation of natural language. Induction over terms and formulas. Tautology, evaluation. Truth table. Disjunctive and conjunctive normal form. 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. Boolean algebra. Briefly about the difference between classical and intuitionistic logic.

Instruction

Lectures and lessons.

Assessment

Written or oral examination at the end of the course. Moreover, compulsory assignments may be given during the course in accordance with instructions at course start.