Logic and Proof Techniques I
Syllabus, Bachelor's level, 1MA027
- Code
- 1MA027
- Education cycle
- First cycle
- Main field(s) of study and in-depth level
- Mathematics G1F
- Grading system
- Fail (U), Pass (3), Pass with credit (4), Pass with distinction (5)
- Finalised by
- The Faculty Board of Science and Technology, 18 October 2021
- Responsible department
- Department of Mathematics
Entry requirements
5 credits in mathematics. 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;
- 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 argument is valid and, in that case, implement a formal proof of the deduction or otherwise give a counterexample to the argument;
- 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 and formulas. Tautology, evaluation, counter example 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, lessons and assignments.
Assessment
Written examination (5 credits).
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.
Reading list
- Reading list valid from Autumn 2023
- Reading list valid from Autumn 2022
- Reading list valid from Spring 2022
- Reading list valid from Autumn 2019
- Reading list valid from Autumn 2017
- Reading list valid from Autumn 2012, version 2
- Reading list valid from Autumn 2012, version 1
- Reading list valid from Autumn 2010, version 2
- Reading list valid from Autumn 2010, version 1
- Reading list valid from Autumn 2007, version 2
- Reading list valid from Autumn 2007, version 1