Logic and Proof Techniques I

5 credits

Syllabus, Bachelor's level, 1MA027

A revised version of the syllabus is available.

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, 15 March 2007
Responsible department: Department of Mathematics

Entry requirements

Algebra I

Learning outcomes

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

give an account of important concepts and definitions in the area of the course;

exemplify and interpret important concepts in specific cases;

formulate important results and theorems covered by the course;

describe the main features of the proofs of important theorems;

express problems from relevant areas of applications in a mathematical form suitable for further analysis;

use the theory, methods and techniques of the course to solve mathematical problems;

present mathematical arguments to others.

Higher grades, 4 or 5, require a higher level of proficiency. The student should be able to solve problems of greater complexity, i.e. problems requiring a combination of ideas and methods for their solution, and be able to give a more detailed account of the proofs of important theorems and by examples and counter-examples be able to motivate the scope of various results. Requirements concerning the student's ability to present mathematical arguments and reasoning are greater.

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 problem solving sessions.

Assessment

Written examination at the end of the course. Moreover, compulsory assignments may be given during the course.