Précédent
 
Suivant

Logique et informatique
Les grammaires-schèmes

 

1) Introduction

On considère un langage algébrique défini par une liste d'éléments générateurs et d'opérateurs générateurs. Chaque terme de ce langage constitue une proposition. On considère des variables muettes, `X,Y,Z,....` Une grammaire schème est un ensemble de règles de production où les arguments sont des couples composées d'une proposition et d'une valeur logique, et ou le résultat est un couple composé d'une proposition et d'unb valeur logique. Exemple :

Considèrons le langage algébrique de présenation :

` "<"a,b,c,f("."),g(".,.")">"`

Considèrons des valeurs logiques :

`"A","B","C"`

Considèrons une règle de production :

`g(X,Y)^"A", g(Y,f(X))^"B" |-- g(X,X)^"C"`

La définition littérale de cette règle est :

Si une proposition `alpha` de valeur logique `"A"` et une proposition `beta` de valeur logique `"B"` existent telles que l'unification de `(alpha,beta)` avec `(g(X,Y),g(Y,f(X))` aboutit, alors la règle produit la proposition `g(X,X)` de valeur logique `"C"` où on a remplacé `X` par sa valeur obtenue lors de l'unification.

2) Algorithme de résolution

Considérons les valeur logiques `"A","B","C","D",...`. On initialise à vide les ensembles de propositions de chaque valeur logique que l'on note pareillement que la valeur logique mais penché : `A,B,C,D,...`

`A:={ }`
`B:={ }`
`C:={ }`
`D:={ }`

On initialise à vide les ensembles des nouvelles propositions de chaque valeur logique que l'on note pareillement mais avec une côte : `A',B',C',D',...`

`A':={ }`
`B':={ }`
`C':={ }`
`D':={ }`

Pour chaque règle de dimension zéro, c'est à dire de la forme `|--alpha^"A"` faire :

`A' = A' + {alpha}`

Puis on répète indéfiniment les instrructions suivantes :

  1. On initialise à vide les ensembles `A',B',C'` des toutes nouvelles propositions de chaque valeur logique `A'', B'', C''` :
    1. `A':={ }`
      `B':={ }`
      `C':={ }`
      `D':={ }`
       
  2. Pour chaque règles de dimension `1` c'est à dire de la forme `alpha^"A"|--beta^"B"`
     
    1. Pour chaque proposition appartenant à `A'` unifiable à `alpha`.
       
    2. Le résultat `beta` en remplaçant les variables muettes par leur valeur issue de l'unification, est mis dans `B''` s'il n'est pas déjà dans `B` ou `B'` ou `B''`. C'est à dire :
       
      `B'' = B'' + ({p"*"alpha}-(BuuB'))`
       
  3. Pour les règles de dimension `2` c'est à dire de la forme `alpha^"A", beta^"B"|--gamma^"C"`
     
    1. Pour chaque proposition `p` appartenant à `A'` et pour chaque proposition `q` appartenant à `B` telle que `(p,q)` unifiable à `(alpha,beta)`,
    2. Pour chaque propostion `q` appartenant à `B'` et pour chaque propostion `p` appartenant à `A` telle que `(p,q)` unifiable à `(alpha,beta)`,
    3. Pour chaque proposition `p` appartenant à `A'` et pour chaque proposition `q` appartenant à `B'` telle que `(p,q)` unifiable à `(alpha,beta)`,
       
    4. Le résultat `gamma` en remplaçant les variables muettes par leur valeur issues de l'unification, est mis dans `"C''"` s'il n'est pas déjà dans `C` ou `C'` ou `C''`. C'est à dire :
       
      `C'' = C'' + ({(p,q)"*"(alpha,beta)}-(CuuC'))`
       
  4. Pour les règles de dimension `3` c'est à dire de la forme `alpha^"A", beta^"B", gamma^"C" |-- delta^"D" `
     
    1. Pour chaque nouvelle propostion `p` appartenant à `A'` et pour chaque propostion `q` appartenant à `B`, et pour chaque propostion `r` appartenant à `C`, telles que `(p,q,r)` unifiable à `(alpha,beta,gamma)`,
    2. Pour chaque nouvelle propostion `q` appartenant à `B'` et pour chaque propostion `r` appartenant à `C`, et pour chaque propostion `p` appartenant à `A`, telles que `(p,q,r)` unifiable à `(alpha,beta,gamma)`,
    3. Pour chaque nouvelle propostion `r` appartenant à `C'` et pour chaque propostion `p` appartenant à `A`, et pour chaque propostion `q` appartenant à `B`, telles que `(p,q,r)` unifiable à `(alpha,beta,gamma)`,
    4. Pour chaque nouvelle propostion `p` appartenant à `A'` et pour chaque propostion `q` appartenant à `B'`, et pour chaque propostion `r` appartenant à `C`, telles que `(p,q,r)` unifiable à `(alpha,beta,gamma)`,
    5. Pour chaque nouvelle propostion `q` appartenant à `B'` et pour chaque propostion `r` appartenant à `C'`, et pour chaque propostion `p` appartenant à `A`, telles que `(p,q,r)` unifiable à `(alpha,beta,gamma)`,
    6. Pour chaque nouvelle propostion `r` appartenant à `C'` et pour chaque propostion `p` appartenant à `A'`, et pour chaque propostion `q` appartenant à `B`, telles que `(p,q,r)` unifiable à `(alpha,beta,gamma)`,
    7. Pour chaque nouvelle propostion `p` appartenant à `A'` et pour chaque propostion `q` appartenant à `B'`, et pour chaque propostion `r` appartenant à `C'`, telles que `(p,q,r)` unifiable à `(alpha,beta,gamma)`,
    8. Le résultat delta en remplaçant les variables muettes par leur valeur issues de l'unification, est mis dans `D''` s'il n'est pas déjà dans `D` ou `D'` ou `D''`. C'est à dire :
       
      `D'' = D'' + ({(p,q,r)"*"(alpha,beta,gamma)}-(DuuD'))`  
       
  5. `A:= A+A`
    `B:=B+B`
    `C:=C+C`
    `D:=D+D`

     
  6. `A':=A''`
    `B':=B''`
    `C':=C''`
    `D':=D''`

A chaque itération on énumère les couples composées d'une proposition et d'une valeur logique, `alpha^A`, qui peuvent être produit à partir de l'itération précédente en utilisant juste une règle. L'algorithme est donc en mesure de donner pour chaque couple `alpha^A`, une démonstration en profondeur d'arbre de règles appliquées la plus courte.

Une optimisation consiste à classer chaque ensemble de propositions en autant de partie qu'il y a de sorte de terme à unifier dans les règles.

3) Le système de Hilbert

Le système de Hilbert propose 4 règles de production de propositions, pemettant de produire exactement toutes les propositions tautologiques au sens classique, dans langage logique réduit à `"<"⊥,"→>"`

`"R1"` :     `|-- X "→"(Y"→"X)`

`"R2"` :     `|-- (X"→"(Y"→"Z))"→"((X"→"Y)"→"(X"→"Z))`

`"R3"` :     `|-- ((X"→⊥")"→"(Y"→⊥")) "→"(Y"→"X)`

`"MD"` :     `X, X"→"Y |-- Y`

Voyons comment s'écrit l'algorithme d'énumération des productions (qui seront donc des tautologies en logique classique). Il y a deux valeurs de vérité notées {0,1} mais

 

 

 

 

Précédent
 

 


Dominique Mabboux-Stromberg
Avril 2026