Topic outline

  • Logic (7,5 hp)

    Overall motivation and description

    Logic is the study of reasoning.

    In the middle of the 19th century Boole and others started to study logic with mathematical methods, e.g. Boolean algebra, which gave rise to formal logic. The treatment of logic as a mathematical subject is indispensible in both mathematics and computer science, and opens the possibility for analysing and automating many intellectual tasks, including even mathematical reasoning itself.

    This course is intended as a first course in logic. It treats the two most important logics, propositional logic and predicate logic, in depth, and shows how they are used in modelling reasoning, especially mathematical reasoning. In particular, the formal languages of predicate logic, semantics and natural deduction are studied. The systems’ soundness and completeness with respect to the semantics are proved, and are then applied to various problems.

    Goals of the course

    Students should become fluent in using propositional and predicate logic to express mathematical statements, and understand how formulas are interpreted in different models.  Students should also learn how to construct formal proofs in the natural deduction style, and how to use models to conclude that statements are not provable from axioms. Students should also acquire an understanding of the practical and philosophical implications of mathematical logic.

    Course literature

    The course will be mostly based on
    Jesper Carlström, Logic, Stockholms universitet. English edition 2013 (definitive course text); Swedish edition 2009

    Hard copies are for sale at the department's student office (Room 204) for around 180Kr.  It is also available in pdf form from the links above/below.

    Further reading (useful supplements, not required):

    Dirk van Dalen, Logic and Structure. Fourth edition. Springer 2008.
    Christian Bennet, Första ordningens logik. Studentlitteratur 2004 (in Swedish).


    Peter LeFanu Lumsdaine, (lectures)
    Håkon Robbestad Gylterud, (problem sessions)
    Examination: Final written exam 90%. 4 sets sets of hand in exercises 10% (=4x2,5%). You have to pass the exam in order to pass the course. 
  • Day 1, 01/09


    History and purpose of logic.

    Course overview.

    Inductively defined sets (Ch.3)

    The natural numbers; simple recursion and induction; strong recursion and induction.

    Other exampes: Booleans.

    Propositional Logic (Ch. 4)

    Syntax: variables, connectives, formulas

    Semantics: valuations, interpretations, tautologies

    Note: chapters 1 and 2 of Carlström are not required for the course.