Exercices de logique
Pour les exercices pratiques, utiliser les ressources disponibles
sur le site TPTP,
une introduction ici.
Exercices 1, 2, 3 et 4
Cf. la fiche de
Dominique Pastre.
Exercice 5
Cf. cet énoncé à propos des nombres premiers.
Exercice 6
Soient Σ={a,b}, L l'ensemble des mots construits sur Σ qui
se terminent par au moins un a et M une machine de Turing qui décide L.
- Déterminer la formule F(M,w) de la démonstration de
l'indécidabilité de la logique du premier ordre.
- Utiliser un démonstrateur de théorèmes, par exemple Vampire,
pour montrer que les mots a, ba et abba sont dans L.
- Utiliser un model finder, par exemple Mace4,
pour montrer que le mot vide et le mot bab ne sont pas dans L.