Aperçu des sections
Section 1
Ce cours est composé de plusieurs chapitres :
Dans le chapitre 1, on va aborder le problème de la décidabilité, c'est à dire on va poser un problème puis on décidera s'il est décidable, indécidable ou semi-décidable (on va prendre comme exemple le problème du PCP ).
Dans le chapitre 2 : on passera directement à la calculabilité et dans cette partie on va prendre comme exemple: la machine de Turing puis les fonctions primitives récursives. ce chapitre se terminera par une série d'exercices (Série de TD 1 sur le support).
Dans le chapitre 3 : On fera une introduction sur les systèmes formels en décrivant leurs composants et propriétés puis on fera quelques exercices surtout sur la création des systèmes formels basés règles (Série de TD 2 sur le support).
Le chapitre 4 : Dans ce chapitre, on entamera la partie la plus importante du cours qui est la logique propositionnelle. dans cette partie on va définir le langage de cette logique et la notion de démonstration, puis on va mettre l'accent sur les deux méthodes de démonstration (La théorie des modèles et la théorie de la preuve). Ce chapitre se termine par une série d'exercices (Série de TD 3 sur le support de cours).
Chapitre 5 : dans ce chapitre, on continu avec la logique mais on passe à la logique du premier ordre dans la quelle on trouve de nouvelles notions telles que la notion de prédicat, les quantificateurs et les fonctions, .. etc. On va définir son système de preuve en abordant les deux approches "la théorie des modèles" puis "la théorie de la preuve".
Si on arrive à terminer tous ces chapitres, on fera une introduction sur le modèle de preuve d'Herbrand en passant par les formes prenexes et clausales.
Section 2
Dans ce fichier, vous trouvez un exemple sur les problèmes indécidables qui est le PCP (Problème de correspondance de POST).