CETS8AB LOGIC AND REASONING

CETS8AB

Logic and reasoning

ECTS Credits : 2

Semester : S8

Person(s) in charge :

jean-Yves MARION, associate professor,  jean-yves.marion@univ-lorraine.fr

Keywords :

Logic, Reasoning

Prerequisites : The only one is to know that one plus one is two...

Objective : Logic and reasoning

Program and content :

Teaching goals:

What is a demonstration? Can any problem be resolved? Are mathematics coherent? What
are the limitations of calculation? This module will try to give answers to all these questions.
First of all, we will formalise the notion of demonstration and its relation to the notion of
truth, thus leading to Gödel’s Completeness Theorem (1930). Next we will tackle the
central notion of undecidability and decidability, going on to examine the Incompleteness
theorems (Church-Gödel-Turing). This will naturally lead us to automatic demonstration
algorithmic construction. And ultimately we will look at the relation between demonstrations
and algorithms with the knowledge that certain constructive logic demonstrations are, in
essence, algorithms.
The development and application of logic affects philosophy, linguistics, IT (complexity,
automatic demonstration, security, database), and complex systems.

Content:

First order logic:
o Semantic and syntactical duality
o Formal system and deduction
o Completeness theorem (Gödel 1930) and compactedness theorem

Basics of the proof theory:

o Lambda calculation
o Proofs and programs: Curry-Howard’s Isomorphism
o Type systems and sure programming
• Calculability and Complexity
o Undecidable problems, incompleteness theorems
o Decidable fragments, NP problems and automatic deduction

Each session will be composed of a lecture followed by a discussion and a tutorial. Some articles will be provided to provide further understanding of the course content.

Non-french speakers are welcome.

Abilities :

Levels

Description and operational verbs

Know 

Understand

Apply 

Analyse

Summarise

Assess

Evaluations :

• Written test

• Continuous Control

• Oral report

• Project

• Written report