Le langage se définie par un ensemble d'opérateurs générateurs. Par exemples
L = {a, f(.), g(.,.)}
A chaque langage correspond une structure libre de même nom qui comprend tout les termes clos exprimables par le langage.
L = <a,f(.),g(.,.)>
L = {a, f(a), g(a,a), g(a,f(a)), g(f(a),a), g(f(a),f(a)), g(a,g(a,a)), g(a,g(a,f(a)))...}
Les crochets <...> expriment la cloture par composition close.
Les intuitionnistes ne s'intéressent qu'à ce qui est calculable et qui peut être construit, car démontrer signifie construire. En somme, les intuitionnistes, appelés ici les élémentariens, ne font que calculer...
Dans cette approche, l'élément mentionné dans une formule constitue le signifiant et non le signifié. Il fait partie du langage, et à ce titre, il obéit aux loix du langage comme toute formule ou théorie exprimable. Le statut de l'élément est, pour ce qui est de sa partie calculable, identique à celui des théories. Aussi les règles de construction des éléments sont de même nature que les règles de construction des démonstrations.
Les intuitionnistes ne considèrent que des ensembles énumérables et réfutent l'axiome du choix. L'existence des ensembles non énumérables ne peut pas être prouvé sans l'axiome du choix.
On se place dans un langage d'opérateurs comprenant :
Les structures sont de type fini lorsqu'ils sont engendrées par un ensemble fini d'élements et d'opérateurs.
Les structures libres, appelée aussi langages d'opérateurs, jouent un rôle fondamental dans la fondation des mathématiques contemporaines et de l'informatique. Les entiers en font partie.
On définie le méta-opérateur de cloture <...>. Il prend en argument des éléments et opérateurs, formant ce que l'on appel une présentation, et retourne en résultat l'ensemble des éléments constructibles par composition close. C'est un méta-opérateur d'arité variable. Cette définition respecte les préceptes intuitionnistes car l'ensemble en question est énumérable, la structure définie par ses opérateurs générateurs peut en effet programmer un énumérateur de ses éléments.
S'il n'y a pas de définition préalable des opérateurs, alors ils sont comme libres. C'est à dire que chaque terme clos distinct optenu par composition d'opérateurs appartenant à la présentation et en un nombre de fois quelconque, désigne nécessairement un élément distinct. Autrement dit, ils sont injectifs et indépendants, et forment donc une structure libre. Exemples :
<a> = {a}
<a,b> = {a,b}
<a,s(.)> = {a, s(a), s(s(a)), s(s(s(a)))...}
<a,g(.,.)> = {a, g(a,a), g(a,g(a,a)), g(g(a,a))...}
<a,b,s(.),f(.)> = {a, b, s(a), s(b), f(a), f(b), s(s(a)), s(s(b)), s(f(a))...}
On définie la signature d'une structure libre de type fini comme étant une suite finie d'entiers (n0, n1, n2, n3...). L'entier n0 désigne le nombre d'éléments générateurs, l'entier n1 désigne le nombre d'opérateurs unaires générateurs, l'entier n2 désigne le nombre d'opérateurs binaires générateurs, l'entier n3 désigne le nombre d'opérateurs d'arité 3 figurant dans la présentation, et ainsi de suite. Par exemples :
Signature (<a, b>) = (2)
Signature (<a, f(.)>) = (1,1)
Signature (<a,b, g(.,.)>) = (2,0,1)
Signature (<a,b,c,f(.),g(.),h(.,.)>) = (3,2,1)
Les structures libres, pour chaque signature, sont uniques à isomorphisme près.
Si des opérateurs de base possèdent des définitions, alors ils seront trés probablement non libres. C'est à dire que deux termes clos distincts pourront désigner un même élément, un même terme évalué. Pour le savoir, il faut évaluer le terme, en évaluant les opérateurs qui possèdent une définition partout ou ils apparaissent. Mais si l'évaluation ne s'achèvent pas en un temps fini, son interprétation est plus complexe et nécessite de préciser des règles de raisonnement, c'est à dire d'en adopter des supplémentaires, des axiomes supplémentaires....
Chaque terme se met sous forme d'une chaine de caractères, appelée mot, en enlevant les parenthèses et les virgules. L'arité des opérateurs étant préalablement connue et définie dans la présentation, les parenthèses et les virgules n'apporte aucune information supplémentaire. Par exemple le terme h(a,b,f(a)) sera désigné par le mot habfa. Le terme est donc une liste d'opérateurs. Et chaque opérateur a une adresse relative dans cette liste c'est à dire dans le terme. Par convention le premier opérateur du terme a pour adresse zéro, et les opérateurs suivants ont une adresse incrémenté de un.
Pour définir la complexité d'un terme, on introduit la notion de partage. Un même sous-terme peut être partagé c'est à dire que son évaluation n'est faite qu'une fois, le résultat est mis en mémoire et est réutilisé plusieurs fois dans l'évaluation du terme. Cela s'implémente grâce à des opérateurs spéciaux appelés liens qui sont des entiers. Un tel opérateur désigne simplement l'adresse d'une racines d'un sous-terme partagé.
Le terme clos se présente comme un arbre. Et on autorise ainsi, le fait qu'un noeud de cet arbre puisse avoir comme fils, un lien vers un autre noeud de l'arbre. L'arbre est alors transformé en un graphe orienté. Mais on interdit les liens récurcifs.
La complexité du terme est égale aux nombres d'opérateurs utilisées, en ne comptant qu'une seul fois un même calcul et en ajoutant 1 pour chaque lien vers ce calcul. Autrement dit, tous les opérateurs de base sont considérés comme ayant une complexité égale à 1, et chaque lien est considéré comme une opération de complexité égale à 1. Exemples :
On définie trois mesures sur l'ensemble des termes clos que sont la taille, le niveau et la complexité.
La taille est le nombre d'opérateurs dont est composé le terme.
taille("a") = 1
taille("f(a)") = 2
taille("g(a,f(a))") = 4
Le niveau est le nombre d'emboitement le plus important contenue dans le terme, en commençant par 1.
niveau("a") = 1
niveau("f(a)") = 2
niveau("g(a,f(a))") = 3
La complexité est le nombre d'opérateurs restant après factorisation c'est à dire après la mise en partage maximale.
complexité("a") = 1
complexité("f(a)") = 2
complexité("g(a,f(a))") = 4
complexité("g(f(a),f(a))") = 4 taille("g(f(a),1)") = 4
complexité("g(g(f(a),f(a)),g(f(a),f(a)))") = 6 taille("g(g(f(a),2),1)" = 6
Une structure libre de type fini est énumérable. Elle peut programmer un énumérateur. Par exemple considérons la structure libre <a, b, f(.), g(.,.), h(.,.,.)>. Cette structure peut programmer un opérateur r(.) tel que nous ayons l'égalité suivante :
<a, r(.)> = <a, b, f(.), g(.,.), h(.,.,.)>
Cela signifie que les deux structures ont le même ensemble sous-jacent. L'énumérateur est défini par la structure <a, r(.)>. L'énumérateur induit un ordre total.
<a, r(.)> = {a,r(a), r(r(a)), r(r(r(a)))....}
<a, r(.)> = {rn(a) / n∈⓵}
L'énumération peut se faire selon la taille des mots. Considérons la présentation suivante <a, f(.), g(.,.)>. L'énumération des mots se fait par taille et par ordre des opérateurs tels qu'ils apparaissent dans la présentation. (a, f, g)* = (a, f, g, aa, af, ag, fa, ff, fg, ga, gf, gg, aaa, aaf...). L'énumérateur des mots de n caractères peut se programmer en n boucles "for" imbriquées, mais le plus astucieux consiste à programmer un incrémenteur. Puis on adapte l'algorithme d'énumération des mots pour n'énumérer que les termes clos, en ajoutant à chaque boucle ou à chaque incrémentation les conditions minimales et maximales sur l'arité. On désigne l'ensemble des termes clos de taille inférieur ou égale à 4 par le méta-opérateur <...>t4 . Nous avons :
<a, f,(.,), g(.,.)>t4 = {
}
L'énumérateur des termes de niveau d'emboitement inférieur à n peut se programme récurcivement, en créant autant de procédures qu'il existe d'opérateurs générateurs. On désigne l'ensemble des termes clos de niveau inférieur ou égale à 3 par le méta-opérateur <...>n3 . Nous avons :
<a, f,(.,), g(.,.)>n3 = {
}
L'énumérateur des termes de complexté inférieur à n peut se programme récurcivement, en créant autant de procédures qu'il existe d'opérateurs générateurs, et en parcourant à chaque fois tous les liens possibles. On désigne l'ensemble des termes clos de complexité inférieur ou égale à 5 par le méta-opérateur <...>c5 . Nous avons :
<a, f,(.,), g(.,.)>c5 = {
}
Il y a un terme non factorisé g(f(a),f(a)) qui correspond au terme g(f(a),1) et qui pourra donc être écarter.
Pour définir dans le langage L, une composition d'opérateurs produisant un opérateur d'arité 3, on utilise 3 variables muettes x,y,z.. L'opérateur défini par l'expression (x,y,z) --> g(x,g(z,x)) sera désigné par le terme g(x,g(z,x)) qui est un terme clos du langage L étendu par l'ajout de ces 3 variables et que l'on note L[x,y,z].
L = <a,f(.),g(.,.)>
L[x,y,z] = <x,y,z,a,f(.),g(.,.)>
Sur la structure libre L, l'ensemble des opérateurs unaires constructibles par composition correspond à la structure libre L[x]. Un terme clos tel que par exemple g(x,f(x)) désigne l'opérateur défini par x --> g(x,f(x)). On dira que L construit par composition cet opérateur, ou plus simplement qu'il compose cet opérateur, ou que cet opérateur est composable dans L, ou de façon abrégé à l'anglaise que l'opérateur est L-composable.
De même, l'ensemble des opérateurs binaires constructibles par composition correspond à la structure libre L[x,y]. Un terme clos tel que par exemple g(y,f(x)) désigne l'opérateur défini par (x,y) --> g(y,f(x)). L'ensemble des opérateurs ternaires constructibles par composition correspond à la structure libre L[x,y,z]. Un terme clos tel que par exemple g(y,g(x,z)) désigne l'opérateur défini par (x,y,z) --> g(y,g(x,z)). Et ainsi de suite.
Ainsi L détermine un langage de programmation par composition, en ajoutant un nombre de variables muettes égal à l'arité de l'opérateur devant être programmé.
L'arité des opérateurs étant fixés préalablement dans la définition d'un langage, il est inutile de noter les parenthèses et les virgules. On remplace le terme clos appartenant à L[x,y] par une suite de caractères appellée mot, où chaque caractère désigne un opérateur. Par exemple l'opérateur définie par (x,y)-->g(y,g(y,x)) est désigné par le terme g(y,g(y,x)), lui-même désigné par le mot gygyx. Et ce mot constitue un programme en logique polonaise. L'évaluation du terme s'obtient en exécutant le programme sur une entré (a,b) en remplaçant x par a et y par b, puis en executant les opérateurs dans le sens inverse, de droite à gauche.
L'exécution d'un programme met en oeuvre un procédé mécanique exacte que l'on apppel l'implémentation. Mais le procédé n'est jamais complètement décrit. L'implémentation est alors un interface entre deux niveaux de protocoles. Elle précise comment le programme fonctionne à patrir d'un ensemble de sous-programmes. Chaque opérateurs générateurs correspond à un sous-programme. Et l'évaluateur, qui est le programme principal, va lire le mot dans le sense inverse.
Le terme se traduit en un mot qui correspond à un programme. L'exécution du programme va évaluer le terme. On parlera d'algorithme d'évaluation. Il existe un algorithme simple d'évaluation selon la logique polonaise qui fonctionne comme suit : L'algorithme d'évaluation lit le mot a l'envers de droite à gauche, il compte le nombre d'opérateurs d'arité zéro lus, puis lorsqu'il lit un opérateur d'arité supérieur, il vérifie si l'arité de cet opérateur correspond bien au nombre d'opérateurs d'arité zéro préalablement lu. Si ce n'est pas le cas, c'est qu'il y a une erreur de syntaxe, sinon il remplace l'opérateur avec ses arguments, par le résultat de son évaluation, et recommence.
Cette implémentation n'exploite pas le partage de sous-termes. C'est pourquoi nous ne la retiendrons pas. Nous utiliserons l'implémentation suivante :
Cette implémentation utilise la structure de graphe orienté du terme. Chaque opérateur est une procédure qui appel l'évaluation de ses fils, et qui après l'évaluation de ses fils, exécute son programme d'évaluation, un programme qui correspond à sa définition. Chaque fils pouvant être partagé, un flag signal s'il a déjà été évalué pour ne pas refaire le calcul plusieurs fois, et le graphe orienté mémorise se calcul à sa place.
L'évaluation d'un terme s'obtient en évaluant l'opérateur racine du terme. Cela va lancer un processus récurcive demandant à chaque noeud de l'arbre de s'évaluer une et une seul fois selon l'ordre d'emboitement.
Nous pouvons maintenant repenser la hierachie des langages de caractères de Chomsky, dans les langage d'opérateurs. Mais il convient dans notre approche généraliste d'aborder un autre aspect de la logique élémentarienne que sont les axiomatiques.
Etant donné un langage d'opérateurs L. Lorsque L peut composer un opérateurs v, c'est à dire construire v par composition d'opérateurs de L et d'un nombre de variables muettes égale à l'arité de v, on dit que v est L-composable et cette propriété se note :
L ⊢ v
On utilise le symbole de démonstration, car en logique intuitionniste, dire que L construit v, signifie que L démontre v. Et on utilise le symbole de négation L ⊬ u pour signifier qu'il n'y a pas de composition de langage L qui calcule u.
Délors il est possible de définir la notion d'axiomatique d'opérateurs. On définie la relation ⊢ entre deux ensembles d'opérateurs. A |- B signifie que A peut construire B, c'est à dire que tous les opérateurs de B sont composables dans le langage A, ou autrement dit qu'ils peuvent être obtenu par des termes composés exclusivement d'opérateurs appartenants à A et de variables muettes en nombre égal à leur arité. Puis A ⊬ B signifie qu'il existe au moins un opérateur appartenant à B qui n'est pas composable dans le langage A.
On définie une axiomatique d'opérateurs comme étant un ensemble minimal d'opérateurs A, c'est à dire tel que :
∀x∈A (A-{x}) ⊬ x
Un opérateur ternaire v composable dans L est un terme de L[x,y,z]. On définie la L-taille, le L-niveau et la L-complexité d'un opérateur v comme étant respectivement la taille, le niveau, la complexité minimale des compositions dans L calculant v.
Etant donné un langage L = {a, f(.), g(.,.)} que l'on étend en ajoutant deux variables muettes L[x,y]. L'opérateur que l'on nomme v : (x,y) --> g(g(y,f(x)),g(y,f(x))) est une composition dans L. Il correspond au terme g(g(y,f(x)),g(y,f(x))) qui est de taille 9, de niveau 4 et de complexité 6. On note par L-taille(v), la taille minimale des compositions dans L calculant v. On note par L-niveau(v), le niveau minimum des compositions dans L calculant v. Et on note par L-complexité(v), la complexité minimale des compositions dans L calculant v. Lorsque v n'est pas L-composable, la L-taille, le L-niveau, la L-complexité sont alors considérés comme valant l'infini. Par exemple, dans la structure libre L = <a, f(.), g(.,.)>, nous avons assurement :
L-taille(v) = 9
L-niveau(v) = 4
L-complexité(v) = 6
On enrichie le symbole de démontrabilité en mettant en indice, la taille maximale autorisée préfixée par le symbole "t", ou le niveau maximum autorisée préfixée par le symbole "n", ou la complexité maximale autorisée préfixée par le symbole "c". Par exemple dans la structure libre L nous avons : :
L ⊢t9 v
L ⊢n4 v
L ⊢c6 v
Cela signifie que l'on peut produire v dans le langage L par un terme de taille inférieur ou égale à 9, de niveau inférieur ou égale à 4, et de complexité inférieur ou égale à 6.
Ces relations se définissent également entre ensembles d'opérateurs. A ⊢t9 B signifie que A peut construire B à l'aide de termes de taille inférieur ou égale à 9. Puis A ⊬t9 B signifie qu'il existe au moins un opérateur appartenant à B qui n'est pas composable dans le langage A par un terme de taille inférieur ou égale à 9. Autrement dit, il existe un opérateur u appartenant à B tel que A-taille(u) > 9 ou que A-taille(u) = ∞.
Nous pouvons maintenant rehercher les axiomatiques d'opérateurs booléens pour procéder à une classification pertinente des opérateurs booléens.
Mais il convient tout d'abord dans notre approche généraliste, d'aborder le langage propositionnel et les modèles finis qui constituent une introduction de la combinatoire dans la logique.
Sujet :
Le langage d'opérateurs
Structure libre. Partage et complexité.Taille, niveau et complexité. Enumération. Composition d'opérateurs. Implémentation selon la logique polonaise. Implémentation récursive. Les axiomatiques d'opérateurs. L-taille, L-niveau et L-complexité.
Sujets liés :
La logique
Opérateurs booléens. Liste exhaustive des opérateurs booléens d'arité 0, 1 et 2. La logique booléenne. Nombre d'opérateurs d'arité 3,4,5,6. Codage des opérateurs booléens. L'adressage indirecte. Classification des opérateursLe langage propositionnel
Symétrie opérées par négation et permutation des arguments. Propriétés algèbriques des opérateurs. Axiomatique d'opérateurs. NomenclatureL'univers et les mondes
Les univers. Le produit d'univers. Le codage des mondes. La satisfaction d'une formule dans un monde. Totologie, contradiction et cohérence. Les formes normales disjonctive et conjonctive. Les formes normales polynomiales.Les règles de raisonnements
Les extensions intérieurs. La qualité. Le système axiomatique de Hilbert. La règle d'inférence dite du Modus Ponens. Les 3 shémats d'axiomes. La déduction naturelle. Les 9 règles d'inférences
Etant donné un langage d'opérateur {a,b,f(.),g(.,.)}. Les termes sont les éléments de la structure libre que l'on nomme L = <a,b,f(.),g(.,.)> . Et il n'y a pas de variable, tout terme est un élément constant.
On ajoute par extension des opérateurs x, y, z d'arité nulle qui seront amenés à jouer le rôle de variables contenant un terme de langage L. On obtient ainsi le langage L[x,y,z] = <a,b,x,y,z,f(.),g(.,.)>. Mais la présentation ici ne spécifie pas que x, y, z sont des opérateurs variables, et tout semble se comporter comme une extension élémentaire par l'ajout de 3 nouvelles constantes, de 3 nouveaux éléments qui ne contiennent pas de valeur mais dont la valeur est définie par eux-même.
Pour spécifier que x, y, z doivent jouer le rôle de variable intérieur et non d'élément libre rajouté, on peut les définire simplement comme des termes variables, des variables contenant un terme :
(x,y,z) ∈ L°3
Puis on réitère une seconde extension intérieur, qui sera alors du second ordre en créant un deuxième type de variable. Ces variables auront pour rôle de contenant une formule du langage L c'est à dire un terme de L[x,y,z]. On ajoute de la même façon par extension des opérateurs A, B, C, d'arité nulle qui seront amenés à jouer le rôle de variables contenant les formules. On obtient ainsi le langage L[x,y,z][A,B,C] = <a,b,x,y,z,A,B,C,f(.),g(.,.)>. Et on définie les opérateurs x, y, z, A, B, C comme suit :
(x,y,z) ∈ L3
(A,B,C) ∈ L[x,y,z] 3
Puis on réitère une troisième extension intérieur, qui sera alors du troisième ordre en créant un troisième type de variable. Ces variables auront pour rôle de contenant un shémat du langage L c'est à dire une formule de L[x,y,z] c'est à dire un terme de L[x,y,z][A,B,C]. On ajoute de la même façon par extension des opérateurs U, V, W, d'arité nulle qui seront amenés à jouer le rôle de variables contenant les schémas. On obtient ainsi le langage L[x,y,z][A,B,C][U,V,W] = <a,b,x,y,z,A,B,C,U,V,W, f(.),g(.,.)>. Et on définie les opérateurs x, y, z, A, B, C, U, V, W comme suit :
(x,y,z) ∈ L3
(A,B,C) ∈ L[x,y,z] 3
(U,V,W) ∈ L[x,y,z][A,B,C] 3
On a aussi définie trois niveaux d'objets mathématiques contenue par trois types de variable :
Variable de type 1 :
Les termes de L sont les compositions closes d'opérateurs de L, par exemple, f(a).
La variable x peut contenir le terme f(a), dans ce cas nous avons, x=f(a).
La variable x représente un terme variable de L.
Variable de type 2 :
Les formules de L sont les termes de L[x,y,z], par exemple, g(x,b).
La variable A peut contenir la formule g(x,b), dans ce cas nous avons, A=g(x,b).
La variable A représente une formule variable de L.
Variable de type 3 :
Les schémas de L sont les termes de L[x,y,z][A,B,C], par exemple, g(a,g(A,x)).
La variable U peut contenir le schéma g(a,g(A,x)), dans ce cas nous avons, U=g(a,g(A,x)).
La variable U représente un schéma variable de L.
Le type d'une variable est identifié à l'ensemble des valeurs que peut prendre la variable. Le type de la variable x est inclus dans le type de la variable A qui est inclus dans le type de la variable U , autrement dit :
L ⊂ L[x,y,z] ⊂ L[x,y,z][A,B,C]
Puis il existe un moyen plus radical, dit récurcif, de procéder à une extension intérieur. On ajoute par extension des opérateurs x, y, z d'arité nulle qui seront amenés à jouer le rôle de variables contenant non pas un terme de langage L mais un terme du langage obtenue L[x,y,z], c'est à dire une formule de L. On définie les opérateurs x, y, z, comme suit :
(x,y,z) ∈ L[x,y,z] 3
Il se peut alors qu'une variable est une définition récurcive telle que x = g(a,x). L'interpretation en est plus délicate et ouvre différentes possibilitées incompatibles entres elles de compléter l'axiomatique du raisonnement. On commencera par poser les règles minimals nous permettant de définir l'unification de formules. L'avantage de ce langage récurcif est de pouvoir mettre en oeuvre en son sein un procédé d'unification entre plusieurs formules par un programme de complexité linaire.