### 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**

*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):**

*Logic and Structure*. Fourth edition. Springer 2008.

*Första ordningens logik*. Studentlitteratur 2004 (in Swedish).

*"A mathematical introduction to logic"*

*Logic and Computation lecture notes.*

**Teachers**

**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.**Due Thursday 2014-09-18, in class or by email before class.

TYPO: the formula in 2(c) should be “(((P1 –> P2) –> P1) –> P1)”.

Due Thursday 23-10-14, in class or by email beforehand.

(In progress.) Supplementary notes, as we are *not* following Carlström in our treatment of predicate logic. (The overall outline is the same, but some specific definitions are significantly different.)

Detatiled notes on our treatment of semantics and natural deduction (adapted from Carlström).