Logique symbolique
Michael Genesereth
Département d’informatique
Stanford University
Bien qu’il soit possible d’enseigner la logique en utilisant uniquement la langue anglaise, cela est problématique. Les phrases du langage naturel peuvent être complexes ; elles peuvent être ambiguës ; et ne pas comprendre le sens d’une phrase peut conduire à des erreurs de raisonnement.
Même des phrases très simples peuvent poser problème. Nous voyons ici deux phrases grammaticalement légales. Elles sont identiques en tout sauf le dernier mot, mais leur structure est entièrement différente. Dans la première, le verbe principal est blossoms, alors que dans la seconde blossoms est un nom et le verbe principal est sank.
Les cerisiers fleurissent au printemps.
Les cerisiers fleurissent au printemps sank.
Pour un autre exemple de complexité grammaticale, considérons l’extrait suivant tiré du contrat de location de l’Université du Michigan. Dans ce cas, la phrase est suffisamment longue et la structure grammaticale suffisamment complexe pour que les gens doivent souvent la lire plusieurs fois pour comprendre précisément ce qu’elle dit.
L’Université peut résilier ce bail lorsque le locataire, ayant fait une demande et signé ce bail avant l’inscription, n’est pas admissible à l’inscription ou ne s’inscrit pas à l’Université ou quitte l’Université à tout moment avant l’expiration de ce bail, ou pour violation de toute disposition de ce bail, ou pour violation de tout règlement de l’Université relatif aux Halls résidents, ou pour des raisons de santé, en fournissant à l’étudiant un avis écrit de cette résiliation 30 jours avant la date effective de la résiliation, à moins que la vie, l’intégrité physique ou les biens ne soient mis en danger, que le locataire se livre à la vente ou à l’achat de substances contrôlées en violation de la loi fédérale, étatique ou locale, ou que le locataire ne soit plus inscrit en tant qu’étudiant, ou que le locataire se livre à l’utilisation ou à la possession d’armes à feu, d’explosifs, de liquides inflammables, de feux d’artifice ou d’autres armes dangereuses dans le bâtiment, ou qu’il déclenche une fausse alarme, auquel cas un préavis de 24 heures maximum serait suffisant.
A titre d’exemple d’ambiguïté, supposons que j’écrive la phrase Il y a une fille dans la pièce avec un télescope. Voir la figure 6 pour deux significations possibles de cette phrase. Est-ce que je dis qu’il y a une fille dans une pièce contenant un télescope ? Ou est-ce que je dis qu’il y a une fille dans la pièce et qu’elle tient un télescope ?
Figure 6 – Il y a une fille dans la pièce avec un télescope.
Ces complexités et ambiguïtés peuvent parfois être humoristiques si elles conduisent à des interprétations que l’auteur n’avait pas prévues. Voir les exemples ci-dessous pour quelques titres de journaux tristement célèbres aux interprétations multiples. L’utilisation d’un langage formel élimine de telles ambiguïtés involontaires (et, pour le meilleur ou le pire, évite également tout humour involontaire).
|
La foule se précipitant pour voir le pape en piétine 6 à mort Journal Star, Peoria, 1980
|
||||
|
||||
|
||||
|
Le poulet frit cuit au micro-ondes gagne un voyage The Oregonian, Portland, 1981
|
Pour illustrer les erreurs qui surviennent lors du raisonnement avec des phrases en langage naturel, considérons les exemples suivants. Dans le premier, nous utilisons la transitivité de la relation better pour dériver une conclusion sur la qualité relative du champagne et du soda à partir de la qualité relative du champagne et de la bière et de la qualité relative ou de la bière et du soda. Jusqu’ici tout va bien.
Le champagne est meilleur que la bière.
La bière est meilleure que le soda.
Donc, le champagne est meilleur que le soda.
Maintenant, considérons ce qui se passe lorsque nous appliquons la même règle de transitivité dans le cas illustré ci-dessous. La forme de l’argument est la même que précédemment, mais la conclusion est un peu moins crédible. Le problème dans ce cas est que l’utilisation de rien ici est syntaxiquement similaire à l’utilisation de bière dans l’exemple précédent, mais en anglais il signifie quelque chose d’entièrement différent.
Bad sex is better than nothing.
Rien n’est mieux que le bon sexe.
Donc, le mauvais sexe est mieux que le bon sexe.
La logique symbolique élimine ces difficultés par l’utilisation d’un langage formel pour coder l’information. Étant donné la syntaxe et la sémantique de ce langage formel, nous pouvons donner une définition précise de la notion de conclusion logique. De plus, nous pouvons établir des règles de raisonnement précises qui produisent toutes et seulement des conclusions logiques.
À cet égard, il y a une forte analogie entre les méthodes de la Logique Formelle et celles de l’algèbre du lycée. Pour illustrer cette analogie, considérons le problème d’algèbre suivant.
Xavier est trois fois plus âgé que Yolanda. La somme de l’âge de Xavier et de l’âge de Yolanda est égale à douze. Quel âge ont Xavier et Yolanda?
Typiquement, la première étape de la résolution d’un tel problème consiste à exprimer l’information sous forme d’équations. Si nous laissons x représenter l’âge de Xavier et y l’âge de Yolanda, nous pouvons saisir les informations essentielles du problème comme indiqué ci-dessous.
x – 3y = 0
x + y = 12
En utilisant les méthodes de l’algèbre, nous pouvons ensuite manipuler ces expressions pour résoudre le problème. D’abord, nous soustrayons la deuxième équation de la première.
x – 3y = 0
x + y = 12
-4y = -12
Puis, nous divisons chaque côté de l’équation résultante par -4 pour obtenir une valeur pour y. Puis en substituant à nouveau dans l’une des équations précédentes, nous obtenons une valeur pour x.
x = 9
y = 3
Maintenant, considérez le problème de logique suivant.
Si Mary aime Pat, alors Mary aime Quincy. Si c’est lundi et qu’il pleut, alors Mary aime Pat ou Quincy. Si c’est lundi et qu’il pleut, Mary aime-t-elle Quincy ?
Comme pour le problème d’algèbre, la première étape est la formalisation. Soit p la possibilité que Mary aime Pat ; soit q la possibilité que Mary aime Quincy ; soit m la possibilité qu’on soit lundi ; et soit r la possibilité qu’il pleuve.
Avec ces abréviations, on peut représenter l’information essentielle de ce problème avec les phrases logiques suivantes. La première dit que p implique q, c’est-à-dire que si Marie aime Pat, alors Marie aime Quincy. La seconde dit que m et r impliquent p ou q, c’est-à-dire que si on est lundi et qu’il pleut, alors Marie aime Pat ou Marie aime Quincy.
| p | ⇒ | q |
| m ∧ r | ⇒ | p ∨ q |
Comme pour l’algèbre, la logique formelle définit certaines opérations que nous pouvons utiliser pour manipuler des expressions. L’opération présentée ci-dessous est une variante de ce que l’on appelle la résolution propositionnelle. Les expressions au-dessus de la ligne sont les prémisses de la règle, et l’expression en dessous est la conclusion.
| p1 ∧ … ∧ pk | ⇒ | q1 ∨ … ∨ ql |
| r1 ∧ … ∧ rm | ⇒ | s1 ∨ ….. ∨ sn |
| p1 ∧ … ∧ pk ∧ r1 ∧ … ∧ rm | ⇒ | q1 ∨ ….. ∨ ql ∨ s1 ∨ … ∨ sn |
Il existe deux élaborations de cette opération. (1) Si une proposition à gauche d’une phrase est la même qu’une proposition à droite de l’autre phrase, on peut laisser tomber les deux symboles, à condition de ne laisser tomber qu’une seule paire de ce type. (2) Si une constante est répétée sur le même côté d’une même phrase, on peut supprimer toutes les occurrences sauf une.
Nous pouvons utiliser cette opération pour résoudre le problème de la vie amoureuse de Marie. En regardant les deux prémisses ci-dessus, nous remarquons que p apparaît à gauche d’une phrase et à droite de l’autre. Par conséquent, nous pouvons annuler le p et ainsi dériver la conclusion que, si est lundi et qu’il pleut, alors Marie aime Quincy ou Marie aime Quincy.
| p | ⇒ | q |
| m ∧ r | ⇒ | p ∨ q |
| m ∧ r | ⇒ | q ∨ q |
Laissant tomber le symbole répété du côté droit, nous arrivons à la conclusion que, si c’est lundi et qu’il pleut, alors Mary aime Quincy.
| m ∧ r | ⇒ | q ∨ q |
| m ∧ r | ⇒ | q |
Cet exemple est intéressant car il présente notre langage formel pour coder les informations logiques. Comme avec l’algèbre, nous utilisons des symboles pour représenter les aspects pertinents du monde en question, et nous utilisons des opérateurs pour connecter ces symboles afin d’exprimer des informations sur les choses que ces symboles représentent.
L’exemple introduit également l’une des opérations les plus importantes en logique formelle, à savoir la résolution (dans ce cas, une forme restreinte de résolution). La résolution a la propriété d’être complète pour une classe importante de problèmes logiques, c’est-à-dire qu’elle est la seule opération nécessaire pour résoudre tout problème de cette classe.