Course syllabus - Mathematical Logic for Computer Science

Objectives

The course presents basic concepts and methods of mathematical logic of importance for further studies in computer science. Additionally, training in logical thinking and the ability to make self-analysis and solution of logical problems are practiced.
 

Learning outcomes

At the end of a passed course, the student is expected to be able to
- describe and apply the following basic concepts: formal languages, formulas, valuations and models for formal languages.
- formalize statements made in a natural language into a formal language.
- perform semantic proof and deduction.
- determine and prove the consistency and inconsistency as well as dependence and independence of formulas.
- describe and apply the Completeness Theorem for predicate logic
- describe the axioms and set up models for the axiom systems for Peano arithmetic and for Boolean algebra.
- describe logic systems with multiple truth values, modal logic and temporal logic as well as perform calculations for truth values in these systems.
- describe the main elements of Gödel's Incompleteness Theorem.

Course content

Classical first-order predicate logic:  Formal language. Valuation. Model. Formal derivation (semantic proof and deduction). Consistency & inconsistency, dependency & independency. Soundness, completeness. Relation, function.
Axiom system: Axiom system for arithmetic of natural numbers and for Boolean algebra.
Non-classical logic system: Logic system with multiple truth values. Logic with new connectives (modal logic) and time structure (temporal logic).
Introduction to Gödel's Incompleteness Theorem.
 

Tuition

Lectures combined with exercises and individual assignment.
 

Specific requirements

Discrete Mathematics 7,5 credits or equivalent.

Examination

Exercises (INL1), 2.5 credits, marks Pass (G)
Written and/or oral examination (TEN1), 5 credits, marks 3, 4 or 5

A student who has a certificate from MDU regarding a disability has the opportunity to submit a request for supportive measures during written examinations or other forms of examination, in accordance with the Rules and Regulations for Examinations at First-cycle and Second-cycle Level at Mälardalen University (2020/1655). It is the examiner who takes decisions on any supportive measures, based on what kind of certificate is issued, and in that case which measures are to be applied.

Suspicions of attempting to deceive in examinations (cheating) are reported to the Vice-Chancellor, in accordance with the Higher Education Ordinance, and are examined by the University’s Disciplinary Board. If the Disciplinary Board considers the student to be guilty of a disciplinary offence, the Board will take a decision on disciplinary action, which will be a warning or suspension.

Grade

Pass with distinction, Pass with credit, Pass, Fail