Cette section donne quelques éléments de repère sur la logique. Que recouvre ce terme, comment nous aborderons cette thématique dans le cours et les usages qui peuvent en être fait en particulier en informatique.
Logique vient du grec logos (raison, langage, raisonnement).
La logique manipule des énoncés (on parle de manière équivalente de propriété, ou de formule) qui sont des phrases auxquelles on peut attribuer un sens qui est une valeur de vérité, vrai ou faux. Les phrases suivantes sont des énoncés.
Par contre la phrase “la couleur du cheval blanc d’Henri IV” n’est pas un énoncé. En effet cette phrase désigne une couleur et pas une valeur de vérité.
Le langage est essentiel pour préciser de quoi on parle. En effet, un énoncé peut être vrai ou faux suivant la manière dont on interprète les mots. La logique est une manière scientifique et systématique d’étudier la notion de vérité.
La logique ne s’intéresse pas seulement aux énoncés et à la notion de vérité. Elle concerne également la notion de raisonnement. Tout comme en informatique, il peut y avoir plusieurs manières d’arriver à un résultat.
Le raisonnement est un cheminement (une déduction) qui permet à partir d’énoncés que l’on suppose vrais (que l’on appelle des hypothèses ou encore des axiomes), de construire de nouveaux énoncés appelés conséquences ou conclusion. Un raisonnement suit un ensemble de règles logiques données.
Exemple
Tous les hommes sont mortels
or Socrate est un homme
donc Socrate est mortel.
Le raisonnement suivant est par contre beaucoup plus douteux. Il part d’hypothèses possibles pour aboutir à une conclusion qui est fausse.
Exemple
Tous les hommes sont mortels
or l’âne Francis n’est pas un homme
donc l’âne Francis est immortel.
Un raisonnement suit des règles précises. C’est un procédé suffisament élémentaire pour convaincre que si les hypothèses sont vraies alors la conclusion que l’on a déduite est aussi vraie. Quelques exemples de raisonnement sont :
Montrer qu’un énoncé est vrai ou faux n’est pas en général décidable (il n’y a pas de programme qui répond à cette question). Vérifier qu’un raisonnement suit bien les règles du jeu peut en général s’effectuer mécaniquement. Certains raisonnements sont adaptés à l’humain, d’autres aux machines…
La logique étudie des règles du jeu qui permettent de construire des raisonnements logiques. On se pose des questions comme:
L’extrait suivant est tiré de la pièce de théatre Rhinoceros, d’Eugène Ionesco. C’est un dialogue entre un Logicien et un Vieux Monsieur, qui sous couvert de raisonnement logique, énonce des absurdités.
Démontrer c’est apporter une évidence du fait que quelque chose est vrai. Il existe plusieurs sortes de preuve, plus ou moins rigoureuses :
(http://www.pion.ch/Logic/preuves.html)
Dans ce cours, on s’intéresse à des méthodes rigoureuses mais aussi à des formats de preuve qui vont être transposables sur ordinateur.
Le questionnement sur les fondements des mathématiques s’est développé du début du 20ème siècle avec la théorie des ensembles. Quelques logiciens importants dans ce domaine sont Tarski, Russel, Hilbert et Gödel. Des résultats surprenants à l’époque ont été le paradoxe de Russell ainsi que le théorème d’incomplétude de Gödel.
Le paradoxe de Russel a montré qu’un ensemble d’énoncés de la théorie des ensembles proposé initialement comme fondement des mathématiques était incohérent c’est-à-dire qu’il permettait de déduire une contradiction et à partir de là n’importe quelle propriété. Il a fallu restreindre l’ensemble des énoncés, en particulier interdire l’existence d’un ensemble de tous les ensembles pour obtenir la théorie des ensembles de Zermelo-Fraenkel que l’on utilise de nos jours.
Le théorème d’incomplétude de Gödel répond négativement à la question de l’existence d’un ensemble d’hypothèses qui pourrait fonder les mathématiques. Le théorème dit que si un ensemble d’énoncés, vus comme des hypothèses, a des «bonnes» propriétes, comme d’être récursif (étant donné une formule de la logique, on peut décider si c’est ou non une des hypothèses), d’être cohérent (on ne peut pas déduire toutes les formules à partir de ces hypothèses) et d’être suffisament expressif pour modéliser les entiers naturels, alors il existe une formule qui, dans ce système, ne peut ni être prouvée, ni être réfutée (c’est-à-dire que, à partir de ces hypothèses, on ne peut prouver ni la formule, ni la négation de cette formule).
En informatique, on peut définir de manière universelle l’ensemble des fonctions “calculables” et on connait plusieurs systèmes pour les représenter (Machine de Turing, lambda-calcul, fonctions récursives). En logique, aucun système “raisonnable” n’est suffisament puissant pour permettre de démontrer toutes les «vérités».
En logique mathématique, les formules et le raisonnement sont les objets de l’étude comme les nombres en arithmétique, les fonctions en analyse, les espaces vectoriels en algèbre linéaire.
On va raisonner sur les objets de base de la logique, à savoir les énoncés mathématiques et les raisonnements, et établir des théorèmes mathématiques sur ces objets : il y a deux niveaux différents qu’il ne faut pas confondre.
Cette situation se retrouve aussi en informatique où on écrit parfois des programmes qui manipulent d’autres programmes (les compilateurs).
Il existe des liens très étroits entre logique et informatique dont voici quelques illustrations :
La logique se programme sur ordinateur : on introduit alors des structures informatiques pour représenter des propriétés logiques et on construit des outils pour les manipuler.
On se pose alors des questions informatiques sur la logique auxquelles nous apporterons des réponses dans ce cours :
L’objectif du cours est de se familiariser avec le formalisme logique de base, à savoir la logique du premier ordre. On introduira la notion de terme, de formule, de démonstration, de validité, le lien entre syntaxe et sémantique. Ce cours met en pratique des outils mathématiques utilisés en informatique tels que la récurrence structurelle et les définitions par système d’inférence.
Le programme du cours couvre les éléments suivants :