2.Introduction à la logique formelle

La première idée pour "représenter" des connaissances est de se rapprocher d'un système "logique", c'est-à-dire capable de dire le Vrai et le Faux en fonction d'axiomes de bases et de "théorèmes" de dérivation. On retrouve bien sûr la "patte" des mathématiciens logiciens, en particuliers des logiciens grecs, dont le plus célèbre est sans aucun doute Aristote (voir l'encyclopédie Yahoo par exemple).

2.1. Systèmes formels

Pour construire une langue (par exemple le français), on a besoin de 4 choses :

un alphabet (a, b, ..., z, blanc, virgule, parenthèse ouvrante, ...)
un procédé de formation des mots, qui est la concaténation de caractères de l'alphabet : (le mot "sdfgh^el" ne peut pas être construit sur la langue française, le mot "sdfgheuyu-fhsl" ne veut sûrement rien dire mais peut-être construit sur la langue française
un dictionnaire, qui permet de savoir que "chat" est français, alors que "cat" ne l'est pas
des règles de grammaire, qui permettent de savoir que "chattes" est français, alors qu'il n'est pas dans le dictionnaire.

2.1.1. Définition

Pour construire un système formel, nous aurons besoin de 4 choses analogues :

un alphabet, ensemble de symboles pas nécessairement réduit à des caratères
un procédé de formation des expressions (p.f.e.), pas nécessairement la concaténation
un ensemble d'axiomes, c'est-à-dire d'expressions obéissant aux deux premiers points ci-dessus, et dont on décide arbitrairement qu'ils appartiennent au système
des règles de dérivation qui, à partir des axiomes, permettent de produire des théorèmes (c'est-à-dire des expressions appartenant au système), et peuvent ensuite s'appliquer aux théorèmes pour en produire d'autres

2.1.2. Exemple

Considérons le système "peu" :

alphabet = l'ensemble des trois symboles "p" , "e" , et "u"
p.f.e. = concaténation
axiome = upueuu
règles :
- R1 : si une expression de la forme AeB est un théorème (où "A" désigne n'importe quelle suite de "u", de "p", et de "e", et B de même), alors l'expression uAeBu est aussi un théorème
- R2 : si une expression de la forme AeB est un théorème, alors l'expression AueuB est aussi un théorème

Questions :

Q1 = uupuueuuuu est-il un théorème?
Q2 = upuueuuuu ?
Q3 = upupueuuu ?

Réponses :

Q1, oui. Preuve? On développe l'arbre :
Q2, non : il y a un nombre impair de "u", ce qui n'est pas possible
Q3, non : il y a deux "p"

EXERCICE :

Q1 : uuuupuueuuuu est-il un théorème ?

Q2: upuuueuuuu ?

Q3: uuuupuuueuuupeuuuuuu ?

Preuves ?

2.1.3. Moralité

Pour démontrer qu'une expression est un théorème, nous avons une procédure (développer l'arbre) infaillible, qui répond en 2^n/2, n étant la longueur de la chaîne, donc en temps fini.
Par contre, pour démontrer qu'une expression est un non-théorème, il nous faut "tricher". Dans les deux exemples ci-dessus, nous avons fait de l'arithmétique, que faudrait-il faire sur un autre exemple?

Si, pour prouver qu'une expression est un théorème, il "suffit" d'explorer l'ensemble des thèorèmes qui peuvent être générés, il n'est pas possible de faire la même chose pour un non-théorème. En pratique, on utiliserait le raisonnement par l'absurde, en posant que l'expression est un théorème, et en cherchant s'il est possible de trouver les théorèmes qui ont été utilisés avec les règles pour produire ce nouveau théorème.

Supposons pupueuu comme expressoin à décider théorème ou non. Ce théorème peut provenir de l'application de la règle R1 ou R2. La règle R1 ajoute un u au début et à la fin du théorème dérivé. Je ne peux pas enlever un u en début de mot, il ne peut donc y avoir aucun théorème ayant produit celui-ci avec la règle R1. La règle R2 ajoute un u avant et après un e dans un théorème pour en produire un autre. Il est possible de trouver une expression d'origine qui aurait pu produire celle-ci par la règle indiquée : pupeu. Est-ce que cette expression est un théroème ? On peut démontrer facilement que cette expression n'est pas dérivable d'une expression quelconque par la règle R1 ou la règle R2. Il ne peut donc pas s'agir d'un théorème.

Donc les notions de "être un théorème" et de "être un non-théorème" ne sont pas symétriques. Notre système "peu" est semi-décidable : nous avons une procédure qui répond "oui" en temps fini, mais pas de procédure pour répondre "non".

(voir le système MU de Hofstadter).

2.1.4. Deuxième exemple

Considérons le système :

alphabet = l'ensemble des trois symboles "plus " , "egal " , et "un "
p.f.e. = concaténation
axiome = un plus un egal un un
règles :
- R1 : si une expression de la forme A egal B est un théorème (où "A" désigne n'importe quelle suite de "un ", de "plus ", et de "egal ", et B de même), alors l'expression un A egal B un est aussi un théorème
- R2 : si une expression de la forme A egal B est un théorème, alors l'expression A un egal un B est aussi un théorème

Questions :

Q1 = un un plus un un egal un un un un est-il un théorème?
Q2 = un plus un un egal un un un un ?
Q3 = un plus un plus un egal un un un ?

Réponses : oui, non, et non, car les deux systèmes sont isomorphes.

Si nous remplaçons "plus " par "+", "egal " par "=", et "un " par "1", l'axiome s'écrit : 1+1=2 , en base 1 (les chiffres romains, concaténation = addition).
R1 se lit : si A=B, alors 1+A=B+1
R2 : si A=B, alors A+1=1+B
Q1 : 2+2=4 est un théorème Q2 : 1+2=4 est un non-théorème Q3 : 1+1+1 ... est-un non-théorème !

2.1.5. Interprétation

Ce que nous venons de manipuler n'est pas un système formel : le symbole "2" ne fait pas partie de l'alphabet. Ce que nous venons de manipuler est l'interprétation du système formel. "1+1+1=3", dans l'interprétation, est vrai, bien que ce soit un non-théorème.
Une interprétation d'un S.F. n'est en général pas équivalente au S.F., c'est-à-dire que les notions de "être un théorème" et "être un non-théorème" d'une part, et de "être vrai" et "être faux" d'autre part, peuvent ne pas se recouvrir.
Cependant, il ne faut pas rejeter l'interprétation : souvenez-vous, si vous avez étudié un peu de Géométrie, la première fois qu'on vous a demandé "démontrer que le triangle ABC est isocèle". Vous avez soigneusement mesuré les deux cotés, et vous avez dit : "Oui, les deux cotés sont égaux". Et l'enseignant vous a répondu : "NON! Ce n'est pas parce que c'est vrai sur la figure que c'est un théorème". Mais vous n'avez pas pour autant cessé de faire des figures pour résoudre les problèmes, parce qu'elles guident le raisonnement. Nous y reviendrons.

REVENIR SUR LA NOTION D'INTERPRETATION

2.1.6. Synthèse

Considérons un système formel quelconque, et l'ensemble (qui peut être infini) des expressions qu'on peut engendrer dans ce système en appliquant le procédé de formation des expressions. Nous pouvons partitionner cet ensemble en : les expressions qui sont des théorèmes, et celles qui sont des non-théorèmes.
Nous pouvons également partitionner cet ensemble en : ce qu'une procédure peut démontrer en temps fini, et ce qu'elle ne peut pas :
Si la partie ND est vide, le système est dit décidable. Si la partie TND est vide, il est semi-décidable. Si aucune partie n'est vide, il est indécidable.
Nous pouvons par ailleurs partitionner l'ensemble en : les expressions dont l'interprétation est "vrai", et celles dont l'interprétation est "faux" :
Si la partie TF n'est pas vide, nous dirons que notre interprétation est sans intérêt. On montre en revanche que la partie NTV n'est, en général, pas vide.
Lorsqu'une proposition "manifestement vraie" ne peut être démontrée, on est donc en droit de se demander dans laquelle de ces zones on se trouve. Un cas célèbre était la conjecture de Fermat, qui a tenu les mathématiciens en échec pendant trois siècles : il n'existe pas d'entiers positifs x, y et z, et d'entier n supérieur à 2, tels que xⁿ+yⁿ=zⁿ .

2.2. Application aux systèmes à base de connaissances

2.2.1. Un système d'aide au voyageur

alphabet	distance.<.2km distance.<.300km aller.à.pied prendre.le.train prendre.l'avion avoir.le.téléphone aller.à.l'agence téléphoner.à.l'agence acheter.un.billet durée.>.2.jours être.fonctionnaire ( ) non (négation) ^ (et, ou conjonction) -> (implique)
procédé de formation des expressions	expression <= symbole expression <= ( expression ) expression <= non expression expression <= expression₁ ^ expression₂ expression <= expression₁ -> expression₂
axiomes	R1 : distance.<.2km -> aller.à.pied R2 : ((non distance.<.2km) ^ distance.<.300km) -> prendre.le.train R3 : (non distance.<.300km) -> prendre.l'avion R4 : (acheter.un.billet ^ avoir.le.téléphone) -> téléphoner.à.l'agence R5 : (acheter.un.billet ^ (non avoir.le.téléphone)) -> aller.à.l'agence R6 : prendre.l'avion -> acheter.un.billet R7 : (durée.>.2.jours ^ être.fonctionnaire) -> (non prendre.l'avion) F1 : (non distance.<.300km) F2 : avoir.le.téléphone
règle de dérivation	Si A est un théorème, et si A -> B est un théorème, alors B est un théorème Cette règle est connue sous le nom de "modus ponens"

Les R_i ont été obtenues de l'"expert" par le processus de développement incrémental (cf. 3. 1.). C'est la mémoire à long terme, ou base de connaissances du système ; on ne les modifiera que si on y détecte une erreur.
Les F_j représentent un problème qu'on va soumettre au système. C'est sa mémoire à court terme, ou base de faits.
Ni la BdC ni la BdF ne sont programmées : elles sont mises telles quelles dans le système. Le seul programme est le moteur d'inférence, qui réifie la règle de dérivation :

ça marche
tant que ça marche
  ça ne marche pas
  boucle sur les R_i
    boucle sur les F_j
      si R_i est de la forme "F_j -> F_k"
        ajouter F_k à la BdF
        ça marche
      finsi
    finboucle
  finboucle
fintant

Traditionnellement, on représente le système par la "tête de Mickey" :

2.2.2. Déroulement

Lançons le système :

ça ne marche pas
R1 et F1 : rien
R1 et F2 : rien
R2 et F1 : rien
R2 et F2 : rien
R3 et F1 : F3 (prendre.l'avion) et ça marche
R3 et F2 : rien
R3 et F3 : rien
...
R6 et F3 : F4 (acheter.un.billet) et ça marche
...
R7 et F4 : rien
ça ne marche pas
R1 et F1 : rien
R1 et F2 : rien
R1 et F3 : rien
R1 et F4 : rien
...
R4 et F4 et F2 : F5 (téléphoner.à.l'agence)

NON! C'est vrai dans l'interprétation, mais ce n'est pas un théorème du système formel ! Nous n'avons pas écrit, et encore moins programmé :

règle de
dérivation

Si A est un théorème, et si
B est un théorème, alors
A ^ B est un théorème

La distinction entre "et" et "^" n'est pas un snobisme, pas plus que celle que nous faisons entre "si...alors..." et "->" . Corrigeons :

ça marche
tant que ça marche
  ça ne marche pas
  boucle sur les R_i
    boucle sur les F_j
      si R_i est de la forme "F_j -> F_k"
        ajouter F_k à la BdF
        ça marche
      sinon
        boucle sur les F_l
          si R_i est de la forme "F_j ^ F_l ->..."
            ajouter F_m = (F_j ^ F_l) à la BdF
            ça marche
          finsi
        finboucle
      finsi
    finboucle
  finboucle
fintant

Relançons le système :

ça ne marche pas
modus ponens avec R3 et F1 : F3 (prendre.l'avion) et ça marche
modus ponens avec R6 et F3 : F4 (acheter.un.billet) et ça marche
ça ne marche pas
règle du "et" avec F4 et F2 : F5 (acheter.un.billet ^ avoir.le.téléphone) 
                                 et ça marche
ça ne marche pas
modus ponens avec R4 et F5 : F6 (téléphoner.à.l'agence) et ça marche
ça ne marche pas
arrêt

NON! C'est vrai en Logique, mais pas en Informatique ! Notre programme va continuer à produire :

modus ponens avec R3 et F1 : F7 (prendre.l'avion) et ça marche
...

Notre programme ne donne pas la solution en temps fini, car il boucle. Pour éviter cela, nous marquons les F_j au fur et à mesure que nous les utilisons :

ça marche
tant que ça marche
  ça ne marche pas
  boucle sur les R_i
    boucle sur les F_j non marqués
      si R_i est de la forme "F_j -> F_k"
        ajouter F_k à la BdF
        marquer F_j
        ça marche
      sinon
        boucle sur les F_l
          si R_i est de la forme "F_j ^ F_l ->..."
            ajouter F_m = (F_j ^ F_l) à la BdF
            marquer F_j
            ça marche
          finsi
        finboucle
      finsi
    finboucle
  finboucle
fintant

A présent, le programme est correct, et donne la réponse en temps fini, quel que soit l'ordre dans lequel nous écrivons les R_i et les F_j. Nous avons donc réalisé notre objectif : nous pouvons exprimer nos connaissances sans les programmer.

2.2.3. Autre exemple

Reprenons le même système, en changeant un peu la base de faits :

axiomes

R1 : distance.<.2km -> aller.à.pied
R2 : ((non distance.<.2km) ^ distance.<.300km) -> 
       prendre.le.train
R3 : (non distance.<.300km) -> prendre.l'avion
R4 : (acheter.un.billet ^ avoir.le.téléphone) -> 
       téléphoner.à.l'agence
R5 : (acheter.un.billet ^ (non avoir.le.téléphone)) -> 
       aller.à.l'agence
R6 : prendre.l'avion -> acheter.un.billet
R7 : (durée.>.2.jours ^ être.fonctionnaire) ->
       (non prendre.l'avion)
F1 : (non distance.<.300km)
F2 : avoir.le.téléphone
F3 : durée.>.2.jours
F4 : être.fonctionnaire

Lançons le système :

modus ponens avec R3 et F1 : F5 (prendre.l'avion)
modus ponens avec R6 et F5 : F6 (acheter.un.billet)
règle du "et" avec F3 et F4 : F7 (durée.>.2.jours ^ être.fonctionnaire)
règle du "et" avec F4 et F2 : F5 (acheter.un.billet ^ avoir.le.téléphone) 
modus ponens avec R4 et F5 : F6 (téléphoner.à.l'agence)
modus ponens avec R7 et F7 : F8 (non prendre.l'avion)

L'"expert" va s'insurger : notre système a déduit, d'une part, qu'il fallait prendre l'avion (F5), et d'autre part qu'il ne fallait pas (F8).
Alors, sous réserve d'un stockage des déductions, nous pouvons interroger le système :

Q : pourquoi F5?
R : modus ponens avec R3 et F1
Q : pourquoi F8 ?
R : modus ponens avec R7 et F7
Q : pourquoi F7?
R : ègle du "et" avec F3 et F4

Nous savons à présent que l'erreur provient d'une contradiction entre R3 et R7, que nous montrons à l'expert. Comment corriger? En supprimant R3, et en le remplaçant par les bons axiomes, ceux qui traitent tous les cas. Où placer les nouveaux axiomes? N'importe où.
La mise au point ne coute pas $4000, parce que :

le système s'explique, et nous permet de trouver rapidement la cause de l'erreur
la correction n'a pas à tenir compte du reste de la BdC

2.2.4. Terminologie

Dorénavant, nous appellerons "règles" les axiomes de type R_i, c'est-à-dire les axiomes qui contiennent "->", et qui forment la BdC. C'est regrettable, car cela entretient une confusion avec les règles de dérivation, mais c'est l'usage.
Une règle a une partie gauche (LHS) et une partie droite (RHS).
La LHS est une conjonction de prémisses, c'est-à-dire que les prémisses sont reliées par des ^. La partie droite est une conjonction de conséquents.
En Prolog, la partie droite est à gauche, et il n'y a qu'un conséquent.

2.3. Généralisations

2.3.1. De 0 à 0+

Reprenons notre S.F., avec une nouvelle base de faits :

F1 : distance.=.500km
F2 : avoir.le.téléphone

Il ne se passe rien. Le système ne sait pas, à partir du symbole distance.=.500km , affirmer
(non distance.<.300km) . Pour que cela soit possible, il faudrait "casser l'atome" :

Terminologie :

distance est un "truc valuable" (ce n'est pas une variable)
= est un prédicat (une fonction qui renvoie "vrai" ou "faux")
500km est une constante

Nous avons quitté le Calcul des Propositions, ou Logique d'ordre 0, pour une Logique que nous appellerons "0+", dans laquelle apparaissent des "trucs valuables", des constantes, et des prédicats. Le prix à payer est de programmer la sémantique des prédicats, c'est-à-dire d'écrire un programme capable, par exemple, de remplacer "distance = 500km" par "non distance < 300km". D'où la verrue sur le nez de Mickey.

2.3.2. De 0+ à 1

Supposons que le système me "dise" d'aller à l'agence. Ce serait bien qu'il me dise aussi comment aller à l'agence, sachant que la distance est de 1,5km. Mais il ne peut pas, parce que "distance" n'est pas une variable : si j'écrase "distance = 500km" par "distance = 1,5km", je vais obtenir des résultats contradictoires.
Solution : dupliquer le système :

axiomes

R1 : distance.destination < 2km -> aller.à.pied.destination
R1a : distance.agence < 2km -> aller.à.pied.agence
R2 : ((non distance.destination < 2km) 
       ^ distance.destination < 300km) -> 
       prendre.le.train.destination
R2a : ((non distance.agence < 2km) 
       ^ distance.agence < 300km) -> prendre.le.train.agence
...
F1 : distance.destination = 500km
F2 : distance.agence = 1,5km
F3 : non avoir.le.téléphone

Mais supposons maintenant que je veuille travailler sur n objets : je ne peux pas "n-pliquer" mon système. Il faut que je puisse écrire :
R1 : quelle que soit la destination, distance(destination) < 2km -> aller.à.pied(destination)
destination devient alors une variable, et j'ai introduit d'autre part "quelle que soit", qu'on appelle le quantificateur universel, noté

.
Je suis à présent en Calcul des Prédicats du Premier Ordre, ou "Logique d'Ordre 1". Mon moteur d'inférence va se compliquer, puisqu'il va devoir chercher, non plus à faire coller un "F" avec la partie gauche d'un "R", mais chercher quelles valeurs des variables permettent cet appariement.

2.3.3. De 1 à 2

Pour définir qu'une relation R est transitive, il suffit d'écrire :

R (

z (xRy) ^ (yRz) -> (xRz)) -> transitive (R))
Mais on n'a pas le droit! En effet, on fait porter le quantificateur universel sur "R", une variable de relation, alors qu'on n'a le droit de le faire porter que sur une variable d'individu.
On passe alors à la Logique d'Ordre 2... mais ceci est une autre histoire.

2.3.4. Du monotone au non monotone

Supposons à présent que j'écrive :
fenêtre.ouverte ^ courant.d'air -> fermer.la.fenêtre
"fermer.la.fenêtre" est un théorème, qui doit s'entendre : "il faut fermer la fenêtre". Mais ce qui m'interesserait, c'est qu'un robot domotique dispose de telles connaissances, et qu'il aille effectivement fermer la fenêtre avec ses petites mains. "fermer.la.fenêtre" devient alors une action. Mais si mon robot ferme la fenêtre, il y aura contradiction entre l'état du monde et sa Base de Faits, qui contiendra encore "fenêtre.ouverte". Donc, il faut compléter :
fenêtre.ouverte ^ courant.d'air -> fermer.la.fenêtre ^ non fenêtre.ouverte
Ce qui revient à écrire : A ^ ... -> non A ^ ...
Or toute la Logique repose sur l'interdiction d'une telle formule !
Nous créons donc (dans les années 70), les Logiques non monotones, dans lesquelles cela n'est plus interdit. (non monotone, par analogie avec l'Analyse : le nombre de théorèmes n'est plus une fonction non-décroissante du temps).

Nous gagnons en puissance d'expression, mais nous perdons quelque chose de très important : la certitude de terminer en temps fini. En effet, la même situation peut se reproduire (quelqu'un ré-ouvre la fenêtre), et il faudra appliquer à nouveau la même règle aux mêmes faits ; nous ne pouvons donc plus marquer comme au 2.2.2., et donc le système peut boucler.
On remarquera que cette notion de monotonie/non-monotonie est indépendante de l'Ordre de la Logique considérée :

2.3.5. Du non monotone au temporel

Si je dis à présent à mon robot :
oeuf.cru ^ eau.froide -> allumer.le.gaz
Dans 3 minutes, je pourrai affirmer "non oeuf.cru". Mais pendant ces trois minutes? Donc je vais programmer mon système pour qu'il ne fasse aucune déduction à ce propos pendant 3mn. On entre dans les Logiques temporelles.
Si je dis maintenant :
non en.stock(article) ^ besoin(article) -> commander(article)
c'est pareil, sauf que je ne sais pas quand arrivera le livreur.

2.3.6. Du bi-valué au flou

Jusqu'à présent, nous appuyant sur les S.F., dans lesquels une expression est, ou n'est pas, un théorème, nous ne nous sommes intéressés qu'au "vrai" et au "faux". Or, dans la vraie vie, les choses ne sont pas si simples. Il y a des choses dont nous ne savons pas si elles sont vraies ou fausses. On peut donc souhaiter manipuler les 3 valeurs : (V ? F).
Mais cela peut encore sembler trop étroit : on peut avoir besoin d'une graduation plus fine : (Vrai Probable Inconnu Improbable Faux). Et puis pourquoi ne pas continuer? On peut considérer l'intervalle continu [-1 +1]. Mais c'est encore simpliste : à une notion donnée, on peut associer une certitude, comprise entre -1 et +1, et une précision, comprise entre 0 et 1. On entre alors dans le domaine des Logiques floues (fuzzy).

Le problème devient alors :
Si A -> B avec une certitude C_R et une précision P_R,
et si A est connu avec C_A et P_A,
on peut en déduire B, mais combien valent C_B et P_B?

2.3.7. Et après

Jusqu'ici, nous sommes restés "objectifs". Si à présent nous voulons introduire "l'homme dans la boucle", nous pouvons envisager des opérateurs tels que "X croit que Y est vrai", "X sait que Y est vrai", etc. Avec des règles plus ou moins contraignantes. Par exemple, "nul n'est censé ignorer la loi" s'écrira :

A, A -> sait(X A).

2.4. Synthèse

Il n'y a pas une Logique, mais un grand nombre de Logiques. Lorsque vous décidez de résoudre un problème en faisant appel à des connaissances, la première chose à faire est de vous situer dans l'espace à 4 dimensions ci-dessus,... et de regarder si le moteur d'inférence correspondant existe.