Le langage propositionnel

1) Le langage d'opéateurs booléens

Un opérateurs booléens d'arité `n` est une application de `{0,1}^n->{0,1}`. L'opérateur est dit dégénéré s'il existe une de ses entrées qui ne transmet jamais d'information sur le résultat. Car dans ce cas, l'entrée en question peut être enlevée et l'opérateur peut d'être défini avec une arité `(n-1)`.

On choisie comme langage d'opérateurs booléens, les seuls opérateurs non dégénérés d'arité `0`, `1` et `2`. Cela nous donne un langage composé de `14` opérateurs.

`L = {0, 1, `id`, ¬, `=>`, `<=` , `<=>`, `et`, `ou`, ¬`=>`, ¬`<=`, `w`, ¬`et`, ¬`ou`}`

Une formule est une composition close d'opérateurs de `L`. Une formule correspond à un arbre où les noeuds sont des opérateurs booléens d'arité `1` ou `2` possèdant respectivement `1` ou `2` fils, et où les feuilles sont des opérateurs booléens d'arité `0`. Par exemple, considérons la formule suivante :

`(0` ou `1) => ¬(1` et `0)`

Cette formule correspond à l'arbre suivant :

Chaque formule s'évaluent en une valeur booléenne `0` ou `1`.

L'ensemble des opérateurs logiques est désignés par la lettre `L`. L'ensemble des formules engendrées par `L` est noté sous forme d'une extension vide `L[]`. Les crochets `[]` mis ainsi comme suffixe représente la cloture par composition close. Ce symbôle `[]` se comporte un peu comme l'opérateur de Kleene à part qu'il opère sur un ensemble d'opérateurs en les composant de toutes les façons possibles et non sur un ensemble de caractères en les concaténant de toutes les façons possibles.

  Ensemble des opérateurs : `L = {0, 1, `id`, ¬, `=>`, `<=` , `<=>`, `et`, `ou`, ¬`=>`, ¬`<=`, `w`, ¬`et`, ¬`ou`}`
  Ensemble des formules engendrées : `L[] = {0, 1` et `0, 1`=>`0, 1`<=>`(0` ou `1), (1` ou `0) ¬`=>` (0` et `1), ... }`

2) L'introduction des variables booléennes

On ajoute au langage, `n` variables booléennes `{x, y, z, t, ...}`. Une variable booléenne est un opérateur d'arité `0` qui possède une valeur booléenne inconnue `0` ou `1`. Le nombre `n` est appelé la dimension du langage et correspondra à la dimension de l'univers associé.

Notez que la conception de la variable booléenne introduite ici, est classique, c'est à dire définie selon la mécanique classique. A savoir que la variable inconnue possède assurement une valeur et que cette valeur est exclusive parmis `{0,1}`. En particulier, elle ne peut pas être à la fois `0` et `1`, ni être ni `0` ni `1`.

Le langage d'opérateurs `L` augmenté de `4` variables booléennes `x,y,z,t`, et qui se définie par `(L uu {x,y,z,t})[]`, se note sous forme d'une extension élémentaire comme suit :

`L[x,y,z,t]`

C'est le langage engendré par :

`x, y, z, t, 0, 1, `id`, ¬, `=>`, `<=` , `<=>`, `et`, `ou`, ¬`=>`, ¬`<=`, `w`, ¬`et`, ¬`ou

Une formule du langage `L[x,y,z,t]` est une composition close d'opérateurs booléens appartenant à `L uu {x,y,z,t}`. Chaque formule du langage `L[x,y,z,t]` correspond à un nouvel opérateur booléen d'arité `4`, qui, appliqué à un quadruplet de valeurs booléennes, s'évalue en une valeur booléenne 0 ou 1. Une formule ne désigne pas seulement une application de `{0,1}^n->{0,1}`, mais désigne un programme qui calcul cette application.

Une formule est un arbre composé de noeuds binaires, de noeuds unaires et de feuilles.

3) Les symétries

Tout opérateur booléen binaire `P"(.,.)"` admet un symétrique par négation, un symétrique par négation du premier de ses arguments, un symétrique par négation du second de ses arguments, et un symétrique par permutation de ses arguments. On définie formellement ces `4` symétries comme suit :

La permutation `s` est définie par : `s(P)(x,y) = P(y,x)`

La négation `n_1` est définie par : `n_1(P)(x,y) = P(¬x,y)`

La négation `n_2` est définie par : `n_2(P)(x,y) = P(x,¬y)`

La négation `n` est définie par : `n(P)(x,y) = ¬P(x,y)`

Et nous avons :

Symétrie
`s@s=id`
`n@n=id`
`n_1@n_1=id`
`n_2@n_2=id`
Commutativité
`s@n=n@s`
`s@n_1=n_1@s`
`s@n_2=n_2@s`
`n@n_1=n_1@n`
`n@n_2=n_2@n`
`n_1@n_2=n_2@n_1`

Chacune des symétries `n`, `n_1`, `n_2`, `s` peut transformer un noeud de l'arbre. Et si on modifie inversement, son flag de négativité, les flags de négativité de ses fils, ou l'ordre de ses fils, de telle sorte que la modification s'annule, on obtient alors une formule syntaxiquement différente mais sémantiquement identique. L'arbre est modifié syntaxiquement mais ne change pas sémantiquement.

Schéma
Exemples
Symétries génératrices


P = x et y
P = ¬x ¬<= y
P = x ¬=> ¬y
P = ¬x ¬ou ¬y

Q = x ou y
Q = ¬x => y
Q = x <= ¬y
Q = ¬x ¬et ¬y

R = (x et y) ou z
R = (¬x ¬<= y) ou z
R = (x ¬=> ¬y) ou z
R = (¬x ¬ou ¬y) ou z
R = (x ¬et y) => z
R = (¬x <= y) => z
R = (x => ¬y) => z
R = (¬x ou ¬y) => z
R = (x et y) <= ¬z
R = (¬x ¬<= y) <= ¬z
R = (x ¬=> ¬y) <= ¬z
R = (¬x ¬ou ¬y) <= ¬z
R = (x ¬et y) ¬et ¬z
R = (¬x <= y) ¬et ¬z
R = (x => ¬y) ¬et ¬z
R = (¬x ou ¬y) ¬et ¬z

S = x <=> y
S = ¬x w y
S = x w ¬y
S = ¬x <=> ¬y

id
`n`
`n_1`
`n_2`
`s`
`P(x,y)` `¬P(x,y)` `P(¬x,y)` `P(x,¬y)` `P(y,x)`
et
¬et
¬<=
¬=>
et
¬=>
=>
¬ou
et
¬<=
¬<=
<=
et
¬ou
¬=>
w
<=>
<=>
<=>
w
ou
¬ou
=>
<=
ou
¬ou
ou
¬=>
¬<=
¬ou
<=>
w
w
w
<=>
<=
¬<=
¬et
ou
=>
=>
¬=>
ou
¬et
<=
¬et
et
<=
=>
¬et

 

4) Propriétés algèbriques des opérateurs booléens

Chaque opérateur binaire * possède des propriétés algèbriques plus ou moins intéressantes. Voici un tableau répartissant les opérateurs selon quelques propriétés algébriques particulièrement simples et utiles :

Propriété algèbrique
Opérateurs satisfaisant
la propriété algébrique
Associatif
`x**(y**z) = (x**y)**z`
<=>, w, et, ou
Commutatif
`x**y = y**x`
`s(**)=**`
<=>, w, et, ou, ¬et, ¬ou
Symétrique
`x**y = ¬x**¬y`
`(n1@n2)(**)=**`
<=>, w
Contraposée
`x**y = ¬y**¬x`
`(s@n1@n2)(**)=**`
<=>, w, =>, <=, ¬=>, ¬<=

5) Les opérateurs associatifs

Il existe 4 opérateurs booléens binaires qui sont associatifs et, ou, <=>, w :

`(x` et `y)` et `z`
`=`
`x` et `(y` et `z)`
`(x` ou `y)` ou `z`
`=`
`x` ou `(y` ou `z)`
`(x` <=> `y)` <=> `z`
`=`
`x` <=> `(y` <=> `z)`
`(x` w `y`) w `z`
`=`
`x` w (`y` w `z)`

Un opérateur associatif peut être concidéré comme un opérateur d'arité variable, c'est à dire s'appliquant à une liste finie d'arguments, et s'il est de plus commutatif, l'opérateur peut être concidéré comme s'appliquant à un ensemble fini d'arguments. Ici, les 4 opérateurs sont commutatifs. Ils peuvent donc s'appliquer à un ensemble fini `A` d'arguments.

et `A` signifie que toutes les formules appartenant à `A` sont vrai.
ou `A` signifie qu'il existe au moins une formules appartenant à `A` qui est vrai.
<=> `A` signifie qu'il existe exactement un nombre paire de formules appartenant à `A` qui est vrai.
w `A` signifie qu'il existe exactement un nombre impaire de formules appartenant à `A` qui est vrai.

Notez que <=>`{}` est vrai et que w`{}` est faux car zéro est un nombre paire. Notez que et`{}` est vrai et que ou`{}` est faux.

6) L'univers et les mondes

L'univers contient tous les mondes possibles. Un monde détermine la valeur boléenne de chaque variable du langage. Dans un langage de dimension `4`, il y a `4` variables booléennes. Chaque monde précise la valeur de ces 4 variables et correspond donc à un quadruplet de booléens. L'univers est l'ensemble de tous les mondes c'est à dire l'ensemble des quadruplets de booléens possibles `{`0`,`1`}^4`.

Dans un langage de dimension `4` tel que `L[x,y,z,t]`, une formule constitue un programme qu'est le programme d'évaluation de la formule en question sur l'entré `(x,y,z,t)`. Une formule constitue un nouvel opérateur d'arité égale à la dimension du langage. Sa table de vérité est la liste de ses valeurs dans chaque monde, c'est à dire pour chaque valeur possible des variables `(x,y,z,t)`. Cette table est mise sous forme d'une liste de vérité en rangeant les mondes selon l'ordre big-endian.

Ces mondes constituent les modèles classiques du Calcul Propositionnel.

La lecture se fait ici conventionellement de gauche à droite. C'est pourquoi, dans une transmission de caractères notée par exemple par la liste `ABCDEFG`, le premier caractère transmis est `A`. C'est le caractère situé à gauche de la liste. Et le dernier caractère transmis est `G`. C'est le caractère situé à droite de la liste.

 
Liste des
booléens
Liste des couples
de booléens
Liste des triplets
de booléens
Ordre big-endian
`(0, 1)`
`(00, 01, 10, 11)`
`(000, 001, 010, 011, 100, 101, 110, 111)`
Ordre little-endian
`(0, 1)`
`(00, 10, 01, 11)`
`(000, 100, 010, 110, 001, 101, 011, 111)`

L'entier `20` s'écrit en binaire big-endian par `10100`. Big-endian signifie gros bout d'abord. Le premier bit transmis est de poids le plus important, il apporte ici une contribution de `0` ou `2^4` selon qu'il est `0` ou `1`. Inversement, l'entier `20` s'écrit en binaire little-endian par `00101`. Little-endian signifie petit bout d'abord. Le premier bit transmis est de poids le plus faible, il apporte ici une contribution de `0` ou `1` selon qu'il est `0` ou `1`. Le suivant apportera une contribution de `0` ou `2`. Le suivant apportera une contribtion de `0` ou `2^2`, etc..

On dira qu'un monde `(x,y,z,t)` satisfait la formule `varphi`, ou que `varphi` est satisfaite dans le monde `(x,y,z,t)`, ou simplement que `varphi` est vrai dans le monde `(x,y,z,t)` si et seulement si `varphi(x,y,z,t) = 1`, et on notera :

`(x,y,z,t)|==varphi`

Cette notion de satisfaisabilité va nous permettre de définir ce qu'est une vérité sémantique et également ce qu'est une conséquence logique sémantique.

Etant donnée deux formules `T` et `varphi`. On dira que `varphi` est une conséquence logique sémantique de `T` si et seulement si `varphi` est vrai dans tout monde où `T` est vrai, et on notera :

`T|==varphi`

Pour pouvoir écrire cette expression, on généralise la notion de satisfaisabilité `|==` en l'étendant pour son premier membre aux ensembles de mondes. Etant donné `W` un ensemble de mondes appartenant à l'univers, et `varphi` une formule appartenant au langage. On dit que `W` satisfait `varphi` et on note `W|==varphi` si et seulement si tous les mondes appartenant à `W` satisfont `varphi`.

Puis on adopte une conversion implicite. Là où on attend un monde ou un ensemble de monde, si une formule est apportée, elle est interprétée alors comme l'ensemble des mondes la satisfaisant. Ainsi, à gauche du méta-opérateur `|==`, une formule `T` est interprétée comme l'ensemble des mondes satisfaisant `T`.

On remarque qu'en interprétant également le second membre comme un ensemble de mondes et en adoptant la même conversion implicite, alors l'opérateur de conséquence logique sémantique `|==` est identique à l'opérateur d'inclusion `sub` opérant sur les ensembles de mondes. Ainsi l'expression `T|==varphi` signifie que l'ensemble des mondes satisfaisant `T` est inclus dans l'ensemble des mondes satisfaisant `varphi`

Il y a ainsi deux points de vue de la vérité ; un point de vue syntaxique qu'est la formule `varphi` et un point de vue sémantique qui est l'ensemble des mondes la satisfaisant.

Etant donnée une formule `varphi`. On dira que `varphi` est une vérité sémantique si et seulement si `varphi` est vrai dans tout les monde et on notera :

`|==varphi`

Pour pouvoir écrire cette expression, on donne un sens à la formule vide. La formule vide est considérées comme vrai dans tous les mondes de tel sorte que, s'il n'y a pas d'argument à gauche de l'opérateur `|==`, cela correspond à l'argument constitué par la formule vide. La formule vide est équivalente à la formule 1, et cela est interprété comme l'ensemble de tous les mondes. Ainsi l'expression `|==varphi` signifie que `varphi` est vrai dans tous les mondes, et constitue donc une vérité sémantique.

Notez qu'il ne faut pas confondre ensemble vide, `Ø`, et formule vide, 1. En effet, un ensemble vide de mondes satisfait toutes les formules et leur négation car il est inclus dans tout ensemble de mondes, alors que la formule vide représente la formule 1 et donc représente l'ensemble de tous les mondes, et donc ne satisfait que les formules vrais dans tous les mondes à la fois.

7) Les systèmes de démonstration

La formule vide est considérées comme vrai et correspond à la formule `1`. Déjà dans ce choix se pressent le paradigme conjonctif, l'idée de représenter la somme des connaissances comme une conjonction de connaissances, et de considérer ainsi la conjonction et comme la première opération logique de construction des théories. En effet, une conjonction vide est toujours vrai, tandis qu'une disjonction vide est toujours fausse. Nous commençons donc par concevoir cette opération d'accumulation des connaissances comme une conjonction de formules s'agrandissant petit à petit, un ensemble de formules dans lequel on ajoute les nouvelles formules découvertes les unes après les autres.

Une règle d'inférence, et une règle syntaxique de production prenant comme argument un certain nombre de formules parmis les formules déjà démontrées pour produire une nouvelle formule à rajouter parmi les formules déjà démontrées. La plus célèbre des règles d'inférences est le modus ponens :

`(A, A`=>`B) |-> B`

Cette règle de production est définie sous forme d'une fonction prenant deux arguments qui doivent être des formules et qui doivent s'unifier au modèle `(A, A`=>`B)`, et qui retourne comme conclusion la formule `B`. Le modus ponens signifie littéralement : Si dans notre ensemble de connaissances se trouve une formule `A` quelconque et se trouve une seconde formule de la forme `A=>B` alors nous pouvons produire la formule `B` et l'ajouter dans notre ensemble de connaissances.

D'autre règles d'inférences peuvent être construites telle que la suppression de la double négation :

`(¬¬A) |-> A`

Et dans l'autre sens aussi, l'introduction de la double négation :

`A |-> (¬¬A)`

La contraposé par ajout de négation :

`(A`=>`B) |-> (¬B`=>`¬A)`

La disjonction implicative :

`(A` ou `B, A`=>`C, B`=>`C) |-> ((A` ou `B) `=>`C)`

La transitivité de l'implication :

`(A`=>`B, B`=>`C) |-> (A`=>`C)`

Etc...

Une démonstration est un arbre dont chaque noeud représente la résolution d'une règle d'inférence. Chaque noeud retourne une conclusion qui est la formule produite par la règle d'inférence en question. Les fils sont les arguments de la règle d'inférence en question. Les feuilles sont des axiomes ou des hypothèses. Et la racine de l'arbre retourne la conclusion de la démonstration qui est une formule produite par la règle d'inférence associée au noeud racine.

Un système de démonstration est définie par ses axiomes (ou par un énumérateur de ses axiomes car il peut y en avoir une infinité énumérable) et par ses règles d'inférence (ou par un énumérateur de ses règles d'inférence car il peut aussi y en avoir une infinité énumérable).

La prémisse d'une démonstration est constituée par la conjonction de toutes les règles d'inférences et axiomes du système de démonstration, et de toutes les hypothèses choisies par l'utilisateur.

Etant donné un système de démonstration, s'il existe une démonstration utilisant la formule `T` comme seul hypothèse et produisant comme conclusion la formule `varphi`, alors on dit que `T` démontre `varphi` et donc que `varphi` est une conséquence logique syntaxique de `T`, et on note :

`T|--varphi`

Le symbole `|--` relate une vérité syntaxique, tandis que le symbole `|==` relate une vérité sémantique :

Lorsqu'il existe une démonstration sans hypothèse qui produit la formule `varphi`, alors on dit que l'on peut démontrer `varphi` et donc que `varphi` est une vérité syntaxique, et on note :

`|--varphi`

Pour pouvoir écrire cette expression, on rappelle le sens de la formule vide. La formule vide est considérées comme toujours vrai, comme une vérité sémantique et syntaxique première. Elle est donc identique à la formule `1`. S'il n'y a pas d'argument à gauche de l'opérateur `|--` cela correspond à l'argument constitué par la formule vide. La formule vide est équivalente à la formule `1`, et cela est interprété comme la valeur logique vrai. Ainsi l'expression `|--varphi` signifie que `varphi` est syntaxiquement vrai sans avoir à poser d'hypothèse supplémentaire, et constitue donc une vérité syntaxique.

On veut que le système de démonstration soient cohérent c'est à dire que la conséquence logique syntaxique entraine la conséquence logique sémantique.

Cohérence : `(A|--B)` => `(A|==B)`

Et réciproquement on veut que le système de démonstration soit complet c'est à dire que la conséquence logique sémantique entraine la conséquence logique syntaxique :

Complétude : `(A|--B)` <= `(A|==B)`

 

 

8) Première simplification

ygjghjghj

On remarque que quelque soit les formules `A, B` du langage, nous avons `A |== B` si et seulement si `|==(A=>B)`.

Le système de démonstration doit vérifie la propriétée suivante `A|--B` si et seulement si `|-(A=>B)` et comme nous avons `(A|==B)` si et seulement si ` |==(A=>B) `, notre exigence peut se réécrire ainsi :

On veut que le système de démonstration soient cohérent c'est à dire que la vérité syntaxique entraine la vérité sémantique. Autrement dit on veut que les démonstrations démontrent des formules qui sont nécessairement vrais.

Cohérence : `(|--A)` => `(|==A)`

Et réciproquement on veut que le système de démonstration soit complet c'est à dire que la vérité sémantique entraine la vérité syntaxique et donc a fortiori que si une formule est vrai elle doit pouvoir être démontrées sans autre hypothèse :

Complétude : `(|--A)` <= `(|==A)`

. `(|--varphi)` <= `(|==varphi)`

Il existe deux systèmes de démonstration courants basée sur des structures algébriques que l'on applique aux booléens, que sont la structure de treillis distributifs et la struture de corps commutatifs. On commencera par décrire ces deux structures.

 

 

8) La structures de corps commutatif

8.1) Notation classique

Un corps commutatif se présente en notation classique sous forme d'une liste de 3 arguments qui est ensuite qualifiée de corps commutatif  :

`C = (E,+,**)` `C` est un corps commutatif

Le premier argument est l'ensemble sous-jacent, le second argument est l'addition, et le troisième argument est la multiplication. Il est d'usage que la multiplication `**` soit notée également par absence de symbole, par exemple `xyz = x**y**z` et il n'y a pas besoin de parenthèse car dans un corps la multiplication est associative.

La théorie du corps commutatif `(E,+,**)` est :

  1. `(E, +)` est un groupe commutiatif
  2. Notons `0` l'élément neutre du groupe `(E, +)`
  3. `(E\{0},**)` est un groupe commutiatif
  4. L'opération `**` est distributive sur l'opération `+`

C'est à dire :

1. Associativité de `+` : `x+(y+z) = (x+y)+z`
2. Commutatif de `+` : `x+y=y+x`
3. L'élement neutre de `+` : Il existe un élément `0` tel que `0+x=x`
4. Les opposés de `+` : Il existe un opérateur unaire `-"(.)"` tel que `x+(-x) = 0`
5. Associativité de `**` : `x(yz) = (xy)z`
6. Commutatif de `**` : `xy=yx`
7. L'élement neutre de `**` : Il existe un élément `1` tel que `1x=x`
8. Les inverses de `**` : Il existe un opérate urunaire `1"/".` tel que `x(1"/"x) = 0`
9. Distributivité de `**` sur `+` : `x(y+z)=xy+xz`

Souvent on désignera par la même lettre le corps et son ensemble sous-jacent. Et donc, dans l'exression `E = (E,+,**)`, il faut voir le premier `E` comme désigant une structure, et le second `E` comme désigant un ensemble sous-jacent. On laissera le soin au contexte de lever l'ambiguité.

8.2) Notation programmative

Un corps commutatif se présente en notation programmative sous forme d'une liste de `6` arguments, qui est libéllée par l'expression Corps commutatif, suivi d'une éventuelle extension par `1`, `n` ou une infinité énumarable d'éléments générateurs, puis quotienté par une théorie d'égalité :

`E = `Corps commutatif `"("+ , 0, - , **, 1," / )"[a,b,c...]" / "{...}`

Le premier argument désigne l'addition, le second argument désigne l'élément neutre de l'addition, le troisième argument désigne l'opposé `-x` et aussi la soustraction `x-y` comme étant égale à `x + (-y)`, le quatrième argument désigne la multiplication, le cinquième argument désigne l'élément neutre de la multiplication et le sixième argument désigne l'inverse `x^-1` et aussi la division `x"/"y` comme étant égale à `x(y^-1)`. Notez que l'inverse est définie sur `E"\"{0}`.

La notation programmative permet de définir des corps aux théories incomplètes. Par exemple considérons le corps définie par :

`E = `Corps commutatif `"("+ , 0, - , **, 1," / ) / "{1+1+1 = 0 " ou " 1+1=0}`

Ce corps est à la fois le corps `Z"/"2Z` et le corps `Z"/"3Z`. Tout se passe comme si la question n'était pas tranchée. C'est à dire que la théorie du coprs `E`, que l'on désigne par la même lettre, ne peut pas démontrer ni `1+1+1=0` ni `1+1=0`, mais parcontre, peut démontrer `1+1+1 = 0 " ou " 1+1=0`.

`E  ⊬  1+1+1 = 0`
`E  ⊬  1+1 = 0`
`E  |--  1+1+1 = 0 " ou " 1+1=0`

9) La structures de treillis

Un demi-treillis `(G, ^^)`

  1. `(G, ^^)` est un demi-groupe commutatif
  2. Notons `<=` la relation de E sur E définie par `x^^y=y`
  3. <= est une relation d'ordre dans G

C'est à dire :

1. Associativité de `^^` : `x^^(y*^^z) = (x^^y)^^z`
2. Commutatif de `^^` : `x^^y=y^^x`
3. Reflexivité de <= : `x^^x=x`
4. Antisymétrie de <= : `x^^y=y => `
     
     

 

9.1) Notation classique

Un treillis distributif se présente en notation classique sous forme d'une liste de 2 arguments qui est ensuite qualifiée de treillis distributif  :

`E = (E,<=)` `E` est un treillis distributif

Le premier argument est l'ensemble sous-jacent et le second argument est la relation d'ordre partilel. On définis Il est d'usage que la multiplication `**` soit notée également par absence de symbole, par exemple `xyz = x**y**z` et il n'y a pas besoin de parenthèse car dans un corps la multiplication est associative.

La théorie du treillis distributif `(E,<=)` est :

  1. `(E, <=)` est un ordre
  2. Notons `0` l'élément neutre du groupe `(E, +)`
  3. `(E\{0},**)` est un groupe commutiatif
  4. L'opération `**` est distributive sur l'opération `+`

 

 

9) L'algèbre de Bool

La structure de corps étant une structure sur laquelle nous avons beaucoup de connaissance, on commence par regarder comment munir l'ensemble des booléens `{0,1}` d'une structure de corps. Et il y a exactement deux façons possibles de munir cet ensemble d'une structure de corps. Cela produit deux corps symétriques l'un de l'autre que l'on note selon un code couleur :

`C_2 = ({0,1},`w`,`et`)`
`C_2``= ({0,1},<=>, `ou`)`
`C_2` est un corps
`C_2` est un corps

Il existe un isomorphisme entre ces deux corps qui est la négation :

`¬ : C_2->``C_2`
         `x|->¬x`

Les corps sur l'ensemble sous-jacent `{0,1}` sont construit en choisissant un éléments neutre pour l'opération `+`. L'autre éléments est alors l'élément neutre pour la multiplication. Car dans un corps les éléments neutres de l'addition et de la multiplication sont nécessairement distincts.

En notation programmative, les opérateurs n'ont pas de définitions et sont donc libres en dehors des contraintes portés par le patron, le patron de corps commutatif. On construit le corps commutatif petit à petit.

On muni l'ensemble `{0,1}` de l'addition `+` avec `0` comme élément neutre, et on rend cette addition interne en posant la caractéristique `2` c'est à dire que `1+1=0`. On muni l'ensemble `{0,1}` de la multiplication `**` avec `1` comme élément neutre, et avec `0` comme élément absorbant, pour former le corps `C_2`. Et donc l'addition `+` correspond au ou exclusif noté w. L'opposé correspond à l'identité `id`. La multiplication `**` correspond au et. L'inverse correspond à l'identité `id|` restreinte au seul élément `1`.

`C_2 = `Corps `"("+ , 0, `id` , **, 1, `id|`")"`
`C_2 = `Corps `"("` w`, 0,` id`,` et`, 1,` id| `")"`
`x +1=¬x`
`x+y = x` w `y`
`x**y = x` et `y`

Symétriquement, dans le corps `C2`. L'addition `+` correspond à l'équivalence <=>. La multiplication `**` correspond au `"ou"`.

`C_2``= `Corps `"("``+``,``0``,`id`,``**``,``1``,`id|`")"`
`C_2`` = `Corps `"("`<=>`,1,`id`,`ou`,0,`id|`")"`

`x` `+ 1``=`` ¬``x`
`x``+``y =  x` <=> `y`
`x``**``y =  x` ou `y`

Ces deux corps sont symétriques l'un de l'autre. La négation `¬` est l'isomorphisme entre ces deux corps.

`¬0 =``0`
`¬1 =``1`
`¬(x + y) = ¬x` `+`` ¬y`
`¬(x` w `y) = ¬x <=> ¬y`
`¬(x ** y) = ¬x` `**``¬y`
`¬(x` et `y) = ¬x` ou `¬y`

`¬``0`` = 0`
`¬``1`` = 1`
`¬(x``+``y) = ¬x + ¬y`
`¬(x <=> y) = ¬x` w `¬y`
`¬(x``**``y) = ¬x ** ¬y`
`¬(x` ou `y) = ¬x` et `¬y`

Pour un opérateur quelconque `f` et pour un opérateur unaire quelconque `u`, la conjugaison de `f` par `u` se note `f^u` et est l'opérateur appliquant d'abord`u^-1` à chaque argument, puis appliquant `f` à la liste des arguments résultants, puis appliquant `u` au résultat. Tandis que la négation de `f` se note `¬f`.

Description
Notation
Définition
Affirmation de `f `
`f` :
`(x,y,z,...)->f(x,y,z,...)`
Négation de `f`
`¬f` :
`(x,y,z,...)->¬(f(x,y,z,...))`
Conjugaison de `f` par `u`
`f^u` :
`(x,y,z,...)->u(f(u^-1(x),u^-1(y),u^-1(z),...))`

Lorsque `"u"` est la négation, alors `"f"^"u"` désigne l'opérateur dual de `"f"`. Ainsi le dual de `f` est `f^¬`. L'isomorphisme entre les deux corps s'étend à l'ensembles de tous les opérateurs en la conjugaison par la négation :

`0^¬`
`=`
`¬0`
`1^¬`
`=`
`¬1`
`"+"^¬`
`=`
`"+"`
`"*"^¬`
`=`
`"*"`
`"et"^¬`
`=`
`"ou"`
`"ou"^¬`
`=`
`"et"`
`"w"^¬`
`=`
`"<=>"`
`"<=>"^¬`
`=`
`"w"`
`"=>"^¬`
`=`
`"¬<="`
`"<="^¬`
`=`
`"¬=>"`
`x^¬`
`=`
`¬x`
`y^¬`
`=`
`¬y`

Cette conjugaison (appellée isomorphisme étendu) permet de définir les opérateurs duaux quelques soit leur arité.

 

 

 

 

9) L'anneaux de polynomes

Etant donné le corps `C_2` et étant donné 4 variables booléennes `x,y,z,t`, on définie l'anneaux de polynômes par extension élementaire : `C_2[x,y,z,t]`

----- 22 décembre 2016 ----

 

Dans un corps de caractéristique `2`, c'est à dire tel que `x*x=x`, les monomes sont des sous-ensembles de l'ensemble des variables.

 

 

----- 17 décembre 2016 ----

10) Le treilli

 

 

On donne les définitions des 16 opérateurs binaires dans les deux corps `C2 = ({0,1},+,**)` et `C_2 = ({0,1},+,**)` :

Code
Opérateur
binaire
Définition
dans C2
Code
maxien
Code
minien
Définition
dans C2
Code
maxien
Code
minien
0000
0
`x` 0 `y`
0
0000
0
0000
0
`1`
0001
1
1000
8
0001
1
`x` et `y`
`xy`
1000
8
0001
1
`xy``+``x``+``y`
1110
14
0111
7
0010
2
`x "¬"`=> `y`
`xy``+``x`
1100
12
0101
5
`xy``+``y` `+ 1`
1011
11
1011
11
0011
3
`x` g `y`
`x`
0100
4
0100
4
`x`
0100
4
0100
4
0100
4
`x "¬"`<= `y`
`xy``+``y`
1010
10
0011
3
`xy``+``x` `+ 1`
1101
13
1101
13
0101
5
`x` d `y`
`y`
0010
2
0010
2
`y`
0010
2
0010
2
0110
6
`x` w `y`
`x``+``y`
0110
6
0110
6
`x``+``y` `+ 1`
0111
7
1110
14
0111
7
`x` ou `y` 
`xy``+``x``+``y`
1110
14
0111
7
`xy`
1000
8
0001
1
1000
8
`x "¬"`ou `y` 
`xy``+``x``+``y``+`1
1111
15
1111
15
`xy` `+ 1`
1001
9
1001
9
1001
9
`x` <=> `y`
`x``+``y``+`1
0111
7
1110
14
`x``+``y`
0110
6
0110
6
1010
10
`x "¬"`d `y`
`y``+``1`
0011
3
1010
10
`y` `+ 1`
0011
3
1010
10
1011
11
`x` <= `y`
`xy``+``y``+`1
1011
11
1011
11
`xy``+``x`
1100
12
0101
5
1100
12
`x "¬"`g `y`
`x``+`1
0101
5
1100
12
`x` `+ 1`
0101
5
1100
12
1101
13
`x` => `y`
`xy``+``x``+`1
1101
13
1101
13
`xy``+``y`
1010
10
0011
3
1110
14
`x "¬"`et `y`
`xy``+`1
1001
9
1001
9
`xy``+``x``+``y` `+ 1`
1111
15
1111
15
1111
15
`x` 1 `y`
1
0001
1
1000
8
`0`
0000
0
0000
0

La multiplication se note parfois par absence de symbôle. Il faut alors faire attention à bien distinguer la multiplication utilisée dans `C2` qui est l'opérateur `"*"`, de la multiplication utilisée dans `C2` qui est l'opérateur `"*"`.

 

Les pôlynomes à deux variables `x, y`, dans un corps de caractéristique 2, peuvent se mettent sous la forme :

`b_0"*"x"*"y + b_1"*"x + b_2"*"y + b_3"*"1`

Les mônomes sont rangées du degré le plus grand au degré le plus petit en respectant l'ordre des noms de variables `(x, y)`. Le n-uplet de booléens `(b_0, b_1, b_2, b_3)` ainsi défini s'appel le code maxien. Mais on peut choisir de ranger les monomes du degrés le plus petit au degrés le plus élevé tout en respectant l'ordre des noms de variables `(x, y)`. Les pôlynomes se mettent alors sous la forme :

`a_0"*"1 + a_1"*"x + a_2"*"y + a_3"*"x"*"y`

Et le n-uplet de booléens `(a_0, a_1, a_2, a_3)` ainsi défini s'appel le code minien. Le principe du code big-endian ne permet pas vraiment de trancher lequel des deux codes est le plus pertinents.

Chaque opérateur booléen correspond à un polynôme dans le corps `C2` et à un polynome dans le corps `C2`, et possède donc un code minien et maxien pour chacun des deux corps. Cela se généralise pour un opérateurs d'arité `n` en utilisant `n` variables.

 

 

 

 

---- 13 décembre 2016 ----

 

 

3) La suppression des opérateurs id, 0, 1

L'opérateur unaire, id, n'ayant aucun effet, id`(x) = x`, chaque noeud id peut être supprimé de l'arbre. On considère un aspect, un protocole de bas niveau, qui va résoudre systématiquement ces cas, de tel sorte que l'arbre ne contiendra plus de noeud id.

A chaque fois que se trouve une feuille 0 ou une feuille 1 dans un noeud de l'arbre, l'arbre peut se simplifier. En effet un opérateur binaire dont une entrée est connue et constante se transforme en un opérateur unaire. On considère un second aspect (un protocole de bas niveau) qui va résoudre systématiquement ces cas, de tel sorte que l'arbre ne contiendra plus de noeud contenant 0 ou 1 comme fils.

Les seuls feuilles autorisées sont alors les variables booléennes sauf pour la racine, car en effet il se peut que l'arbre soit à lui tout seul la formule 0 ou la formule 1.

Les opérateurs booléens générateurs retenus sont :

`L = {¬, `=>`, `<=` , `<=>`, `et`, `ou`, ¬`=>`, ¬`<=`, `w`, ¬`et`, ¬`ou`}`

Les opérateurs 0 et 1 ne sont plus considéré comme opérateurs générateurs mais comme deux formules spéciales.

Le principe de construction du langage peut se décrire par la structure suivante : :

`L[] uu {`0`,`1`}`

À cette étape il n'y a que deux seuls formules possibles que sont les formules spéciales 0, 1.

4) La réduction des couples d'opérateurs affirmatif-négatifs

Le seul opérateur unaire restant, `¬`, étant son propre inverse `¬¬x = x`, il peut être traité comme un flag venant se greffer sur les noeuds et les feuilles. Un troisième aspect va résoudre la composition de deux négations successives par leur suppression dès quelles apparaissent quelque part dans l'arbre de tel sorte que l'arbre ne contiendra plus de double négation. La formule est donc perçue comme un arbre composée de noeuds binaires et de feuilles, chaque noeud et feuille ayant en plus un flag affirmatif ou négatif.

Ainsi un noeud correspond à un opérateur binaire avec un flag affirmatif ou négatif. Il faut donc choisir pour chacun des `5` couples d'opérateurs affirmatif-négatifs `(`=>`, ¬`=>`)`, `(`<=` , ¬`<=`)`, `(`et`, ¬`et`)`, `(`ou`, ¬`ou`)`, `(`<=>`, `w`)` lequel est considéré comme ayant un flag affirmatif et l'autre un flag négatif. Et les choix canoniques ne coïncident pas avec les choix pratiques. Nous sommes pragmatiques, nous faisons le choix pratique en sachant qu'il n'est pas canonique, c'est à dire qu'il faudra apporter la même importance aux opérateurs possèdant un flag négatif. Le langage d'opérateurs sous-jacent que nous utilisons ne comporte plus que `6` opérateurs.

`L = {¬, `=>`, `<=`, `<=>`, `et`, `ou`}`

Par exemple, l'opérateur `¬`et  sera considéré comme la combinaison du flag négatif `¬` et de l'opérateur et, l'opérateur w (c'est le "ou exclusif") sera considéré comme la combinaison du flag négatif `¬` et de l'opérateur <=>.

`x  ¬`et  `y`
`=`
`¬(x` et  `y)`
`x` w `y`
`=`
`¬(x` <=>  `y)`

Le principe de construction du langage se complexifie encore, puisque maintenant la composition de deux opérateurs `¬` est interdite. Pour un langage de dimension 4, cela peut se décrire par la structure suivante :

`L[x,y,z,t] uu {`0`,`1`}`/`{¬¬x=x}`

Ou bien cela peut se décrire par la grammaire suivante :

`A = { {¬,epsilon}B(A,A), {¬,epsilon}C, 0, 1}`
`B = { `=>`, `<=`, `<=>`, `et`, `ou` }`
`C = { x, y, z, t }`

La grammaire utilise des ensembles d'alternatives.
Le méta-élément `epsilon` désigne le rien.
La méta-variable `C` désigne les variables booléennes de l'univers.
La méta-variable `B` désigne les `5` opérateurs binaires booléens pris comme générateurs.
La méta-variable `A` désigne toutes les formules du langage.
Par exemple la règle de grammaire `{¬,epsilon}x` désigne les 2 formules `¬x` et `x`.

5) La réduction du couple d'opérateurs non commutatifs

Parmi les `5` opérateurs binaires il existe deux opérateurs non commutatifs, symétriques l'un de l'autre `(`=>`, `<=`)`

`x`=>`y  =  y`<=`x`

Il faut donc en choisir un et considérer l'autre comme obtenue par permutation des arguments. Et il n'y a pas de choix canoniques. Nous faisons un choix pratique en gardant l'opérateur d'implication =>, en sachant qu'il n'est pas canonique, c'est à dire qu'il faudra apporter la même importance à l'opérateur symétrique <=. Le langage d'opérateurs sous-jacent que nous utilisons ne comporte plus que `5` opérateurs.

`L = {¬, rArr, hArr, `et`, `ou`}`

Le langage correspond toujours à la structure suivante :

`L[x,y,z,t] uu {`0`,`1`}`/`{¬¬x=x}`

On a simplement retiré un opérateur générateur de l'ensemble `L`

 

 

9) Les opérateurs binaires associatifs

Il existe 4 opérateurs booléens binaires qui sont associatifs et, ou, <=>, w :

`(x` et `y)` et `z   =   x` et `(y` et `z)`
`(x` ou `y)` ou `z   =   x` ou `(y` ou `z)`
`(x` <=> `y)` <=> `z   =   x` <=> `(y` <=> `z)`
`(x` w `y`) w `z   =   x` w (`y` w `z)`

Un opérateur associatif peut être concidérée comme un opérateur d'arité variable, c'est à dire s'appliquant à une liste finie d'arguments, et s'il est de plus commutatif, l'opérateur peut être concidéré comme s'appliquant à un ensemble fini d'arguments. Et ici, les 4 opérateurs sont commutatifs. Ils peuvent donc s'appliquer à un ensembles fini `A` d'arguments.

et `A` signifie que toutes les formules appartenant à `A` sont vrai.
ou `A` signifie qu'il existe au moins une formules appartenant à `A` qui est vrai.
<=> `A` signifie qu'il existe exactement un nombre paire de formules appartenant à `A` qui est vrai.
w `A` signifie qu'il existe exactement un nombre impaire de formules appartenant à `A` qui est vrai.

Notez que <=>`{}` est vrai et que w`{}` est faux car zéro est un nombre paire.
Notez que et`{}` est vrai et que ou`{}` est faux.

 

11) Les 2 corps de booléens

 

 

 

 

 

 

Les langages d'opérateurs {1, w, et} et {0, <=>, ou}constituent deux axiomatiques d'opérateurs. On peut donc exprimer toutes les opérations booléenne du langage L dans ces deux langages. Cela correspond aux deux corps C2 et C2.

Opération
binaire
Taduction
dans {1, w, et}
Taduction
dans {0, <=>, ou}
x 0 y
1 w 1
0
x et y
x et y
(x ou y) <=> x <=> y
x ¬=> y
(x et y) w x
(x ou y) <=> y <=> 0
x g y
x
x
x ¬<= y
(x et y) w y
(x ou y) <=> x <=> 0
x d y
y
y
x w y
x w y
x <=> y <=> 0
x ou y 
(x et y) w x w y
(x ou y)
x ¬ou y 
(x et y) w x w y w 1
(x ou y) <=> 0
x <=> y
x w y w 1
x <=> y
x ¬d y
y w 1
y <=> 0
x <= y
(x et y) w y w 1
(x ou y) <=> x
x ¬g y
x w 1
x <=> 0
x => y
(x et y) w x w 1
(x ou y) <=> y
x ¬et y
(x et y) w 1
(x ou y) <=> x <=> y <=> 0
x 1 y
1
0 <=> 0

Le langage d'opérateurs {¬, et, ou} constitue une axiomatique d'opérateurs. On peut donc exprimer toutes les opérations booléennes du langage L dans ce langage. Cela correspond à une structure de treillis. La négation d'un terme dans ce langage s'obtient en remplaçant les "et" par des "ou" et les "ou" par des "et", et en négativant tous les littéraux.

Opération
binaire
Traduction
dans {¬, et, ou}
x 0 y
x et ¬x
x et y
x et y
x ¬=> y
x et ¬y
x g y
x
x ¬<= y
¬x et y
x d y
y
x w y
(x et ¬y) ou (¬x et y)
x ou y 
x ou y
x ¬ou y 
¬x et ¬y
x <=> y
(x et y) ou (¬x et ¬y)
x ¬d y
¬y
x <= y
 x ou ¬y
x ¬g y
¬x
x => y
¬x ou y
x ¬et y
¬x ou ¬y
x 1 y
x ou ¬x

Le langage d'opérateurs {¬, =>} constitue une axiomatique d'opérateurs. On peut donc exprimer toutes les opérations booléennes du langage L dans ce langage. Ce langage est utilisé dans le système des démonstrations axiomatiques

Opération
binaire
Traduction
dans {¬, =>}
x 0 y
¬(x =>x)
x et y
 
x ¬=> y
 
x g y
 
x ¬<= y
 
x d y
 
x w y
 
x ou y 
 
x ¬ou y 
 
x <=> y
 
x ¬d y
 
x <= y
 
x ¬g y
 
x => y
 
x ¬et y
 
x 1 y
 

Le langage d'opérateur {¬et} constitue une axiomatique d'opérateurs. On peut donc exprimer toutes les opérations booléennes du langage L dans ce langage.

Opération
binaire
Traduction
dans {¬et}
x 0 y
x ¬et x
x et y
 
x ¬=> y
 
x g y
 
x ¬<= y
 
x d y
 
x w y
 
x ou y 
 
x ¬ou y 
 
x <=> y
 
x ¬d y
 
x <= y
 
x ¬g y
 
x => y
 
x ¬et y
 
x 1 y
 

5) Nomenclature

Un littéral est composé d'une éventuelle opération de négation ¬ suivie d'une valeur logique 0 ou 1 ou bien d'une variable booléenne {x,y,z,t...}. Exemples : ¬x, y, 0, 1 sont 4 littéraux.

Une clause est une disjonction de littéraux. Exemple : x ou ¬y ou z. La clause vide vaut 0.

Un état est une conjonction de littéraux. Exemple : x et ¬y et z. L'état vide vaut 1.

Un terme est une composition close d'opérateurs parmi le langage d'opérateurs L = {0, 1, ¬, =>, <=, <=>, et, ou, ¬=>, ¬<=, w, ¬et, ¬ou}. Le terme s'évalue en une valeur booléenne.

Une formule est une composition close d'opérateurs de L[x,y,z,t...] où le nombre de variables rajouté au langage L s'appel la dimension du langage. La formule admet une forme simplifié qui est une composition close d'opérateur parmi le langage {1, ¬, =>, <=, <=>, et, ou} augmenté des variables {x,y,z,t...} où toutes les compositions ¬¬ apparaissant à l'intérieur de la formule sont enlevées.

Une proposition est la signification logique d'une formule c'est à dire sa table de vérité. La proposition désigne une formule à équivalence près.


Dominique Mabboux-Stromberg, 2014

Sujet :

Le 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. Nomenclature

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érateurs

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é.

L'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


3) Langage d'opérateurs booléens

La règle programmative fonde la règle logique.

Un opérateur est booléen s'il opère sur des booléens pour produires un booléen. Un langage d'opérateurs booléens engendre une logique d'ordre 0, car chaque variable ne pouvant avoir qu'un nombre fini d'états, ici 2, toutes les formules peuvent être remplacés par des tables de vérité sans variable.

Dans un langage d'opérateurs booléens, chaque opérateur booléen est préalablement défini, et il existe donc un procédé mécanique permettant de calculer la valeur booléenne de chaque terme. chaque terme peut être remplacé par sa valeur booléenne qui est 0 ou 1.

Considérons par exemple le langage d'opérateurs booléens L = <0, 1, ¬(.), et(.,.)>. Le langage ne comprend que des opérateurs booléens connus puisqu'ils doivent être préalablement définis.

Considérons des variables (x,y,z) ∈ L 3 qui représentent des termes variables. L'utilisation de ses variables va produire des formules dont le résultats logique sera plus complexes que pour les termes. La formule et(x,y) ne peut pas être résolue en un booléen sans connaitre la valeur booléenne des variables x et y. Dans ce cas, on considère que l'évaluation de et(x,y) sera la formule et(x,y) et non une valeur booléenne.

Considérons des variables (A,B,C) ∈ L[x,y,z] 3 qui représentent des formules variables. Si nous posons A = et(x,y) et que les variables x et y n'ont pas de valeur définie, alors l'évaluation de A sera la formule et(x,y) et non une valeur booléenne. L'utilisation de ses variables va produire des schémats dont le résultats logique sera plus complexes que pour les formules. Par exemple, le schéma et(A,B) ne peut pas être résolue ni en un booleen ni en une formule sans connaitre la valeur des variables A et B

Considérons des variables (U,V,W) ∈ L[x,y,z][A,B,C] 3 qui représentent des schémas variables. Si nous posons U = et(A,B), et que A et B n'ont pas de valeur définie, alors l'évaluation de U sera le schémat et(A,B) et non une valeur booléenne, ni même une formule. Par contre si A est égale à une formule telle que A=et(x,y) alors U s'évalura en un shémat et(et(x,y),B).

On définie la qualité d'un terme comme étant sa valeurs booléennes. Les qualités possibles des termes sont les valeurs booléennes {1,0} que l'on nomme respectivement {vrai, faux}.

On définie la qualité d'une formule comme étant l'ensemble des valeurs booléennes parcourues par la formule lorsque l'ensemble des variables booléenne (variable de type 1) de l'univers parcourent leurs différentes valeurs booléennes possibles. Il y a alors autant de qualités possibles qu'il y a de sous-ensemble non vide de {0,1} soit 3 qualités possible {{0}, {0, 1}, {1}} que l'on nomment respectivement {tautologique, indéterminé, contradictoire} et qui correspondent à :

Qualité
Ensemble de
sous-qualités
Exemple de
formule ayant
cette qualité
tautologique
{vrai}
{1}
1
indéterminé
{vrai, faux }
{1,0}
x
contradictoire
{faux}
{0}
0

Chaque configuration des variables booléennes de l'univers correspond à un monde possible.

On définie la probabilité d'une formule comme la somme des probabilités de chaque monde où la formule est vrai, en posant par défaut l'équiprobabilité des mondes.

On définie la qualité d'un schémat comme étant l'ensemble des qualités parcourues par le schéma lorsque l'ensemble des variables de type 2 parcourent toutes les formules possibles. Il y a alors autant de qualités possibles qu'il y a de sous-ensemble non vide de {tautologique, indéterminé, contradictoire} soit 7 qualités possibles que l'on nomme {faux, vrai, bivalant, nonfaux, nonvrai, nonbivalant, libre} et qui correspondent à :

Qualité
Ensemble de
sous-qualités
Exemple de
schéma ayant
cette qualité
faux
{contradictoire}
{{0}}
0
vrai
{tautologique}
{{1}}
1
bivalant
{indéterminé}
{{0,1}}
x
nonfaux
{tautologique, indéterminé}
{{1}, {0,1}}
A ou x
nonvrai
{contradictoire, indéterminé}
{{0}, {0,1}}
A et x
nonbivalant
{tautologique, contradictoire}
{{0}, {1}}
libre
{tautologique, contradictoire, indéterminé}
{{0}, {0,1}, {1}}
A

Sur ces 7 qualités, seulement 6 sont rencontrées.

 

11) L'extention naturelle de la logique d'ordre 0 à la logique d'ordre 1.

L'extention naturelle de la logique d'ordre zéro à la logique d'ordre 1 consiste à prendre comme variable les propositions. De telles variables désignants des propositions logiques d'ordre zéro, utilisent un nombre fini mais non borné de variables booléennes, et peuvent donc avoir un nombre infini de valeurs possibles. Elles constituent des variables universelles, leurs quantificateurs quel que soit et il existe ne peuvent pas être remplacés par une énumération finie de possibilité.

Les formules dans cette logique d'ordre 1 sont appelée shémas. Ici, le terme de proposition est réservé à la logique d'ordre zéro. Décrivons les qualités que peuvent prendre un shéma ainsi décrit mais sans quantificateur quel que soit ni il existe. Les variables propositionelles sont remplacées par des constantes propositionelles inconnues. Cette opération est appelé skolémisation et consiste à remplacer les inconnues par des constantes supplémentaires ajoutées au langage. (Noter que ces constantes n'ont pas le même type que les constante booléennes.)

Considérons un shémas K utilisant n variables propositionnelles {A1, A2, A3 ..., An}et trois variables booléennes {x,y,z}dites non muettes. Le langage utilisé sera une extention de la logique d'ordre zéro précédement décrite, obtenue en ajoutant sous forme de constante ces n variables propositionnelles et ces trois variables booléennes non muettes. On obtient le langage {¬, et, ou, =>, <=, <=>, w, +, *, x, y, z, A1, A2, A3 ..., An}. x est une constante booléenne. A1 est une constante propositionelle. K est un shéma. Lors d'une évaluation, A1 peut prendre comme valeur toute proposition logique sur un nombre fini quelconque de variables booléennes muettes supplémentaire au langage présent, ou déja existantes dans l'instantiation d'une autre variable propositionnelle utilisée, ou soit non muettes.

Cela signifit que l'on ne peut pas concidérer une à une les variables propositionnelles d'un shéma, car elle sont potentiellements liées entre elles. Nous parlerons donc d'instantiation du jeux complet des n variables propositionnelles {A1, A2, A3 ..., An}dans le langage infini {¬, et, ou, =>, <=, <=>, w, +, *, x, y, z, x1, x2, x3, x4 ...}, mais où chaque valeur propositionnelle est de taille finie.

11.1) Les sept qualités possibles d'un schéma

Dans ce nouveau langage permettant de définir les schémas, il y a deux types de constantes ; Celles correspondantes aux variables booléennes qui ont deux valeurs possibles {0,1}correspondant aux deux qualités possibles {vrai, faux}, et celles correspondants aux variables propositionnelles qui ont une infinité de valeurs possibles, mais possédant trois qualités possibles {contradictoire, indéterminé, tautologique} selon qu'une fois développé, leur polynôme associé est nul, non trivial, ou égale à 1, et qui correspond aux sous-ensembles des qualités rencontrées lorsqu'on évalue la proposition pour chaque valeur possible de ses variables booléennes. C'est à dire tautologique = {vrai}, indéterminé = {vrai, faux}, contradictoire = {faux}

Pour une valeur donnée des n constantes propositionnelles, le schéma K(x,y,z,A1,A2,A3...,An) possède une des qualités ; contradictoire, indéterminé, ou tautologique, selon qu'une fois développé, K(x,y,z,A1,A2,A3...,An) est un polynôme nul, ou possédant au moins une variable booléennes (muettes ou non), ou égale à 1.

Dans l'univers des schémas, Il y a autant de qualité qu'il y a de partie non vide de l'ensemble {contradictoire, indéterminé, tautologique}, soit 7 qualités possibles que l'on nomme {absurde, trivial, bivalant, nonabsurde, nontrivial, nonbivalant, libre}et qui correspondent aux sous-ensembles des qualités rencontrées lorsqu'on évalue le schéma pour chaque valeur possible de ses variables propositionnelles. C'est à dire absurde = {contradictoire}, trivial = {tautologique}, bivalant = {indéterminé}, nonabsurde = {tautologique, indéterminé}, nontrivial = {contradictoire, indéterminé}, nonbivalant = {tautologique, contradictoire}, libre = {tautologique, contradictoire, indéterminé}.

Sur ces 7 qualités, seulement 6 sont rencontrées. Voici les exemples canoniques pour les six, et une solution pour la septième.

  1. Absurde {contradictoire} exemple : 0
  2. Trivial  {tautologique} exemple : 1
  3. Bivalant  {indeterminé} exemple : x
  4. Libre {tautologique, contradictoire, indéterminé} exemple : A
  5. Nontrivial {contradictoire, indéterminé} exemple : A et x
  6. Nonabsurde {tautologique, indéterminé} exemple : A ou x
  7. Nonbivalant {tautologique, contradictoire} exemple : A |- 0

Cette logique d'ordre 1 ne possède pas de possibilité d'expression supérieure à notre logique d'ordre 0. Il est nécessaire d'adjoindre de nouveaux opérateurs pour étendre sous domaine d'expression, en tout cas pour atteindre la septième qualité manquante. Cette dernière est atteinte en définissant l'opérateur de démontrabilité |-.

11.2) Le méta opérateur de démontrabilité

On définit le méta opérateur binaire constant, |- , qui représente la relation de démontrabilité, par le procédé récursif suivant :

Soit K, G deux schémas n'utilisant pas l'opérateur |-. Pour chaque valeur possible de leurs variables propositionnelles, nous posons : (K |- G) retourne 1 si (K et ¬G) est contradictoire, c'est à dire une fois développé, est égale au polynôme nul. (K |- G) retourne 0 si (K et ¬G) n'est pas contradictoire, c'est à dire tautologique ou indéterminé, c'est à dire une fois développé, est différent du polynôme nul.

Si l'opérateur |- est appliqué plusieurs fois de façon emboîtée, il faut d'abord évaluer les opérateurs |- appliqué à des schémas sans opérateur |-, et remonter ainsi de suite.

Puis il faut intégrer toutes les valeurs possibles des variables propositionnelles et procéder à la réunion de toutes les qualités produites possibles. Ce qui donne une définition non constructible du méta opérateur |-.

Schéma
Schéma
Schéma évalué
Qualité
du Schéma
(A |- 0)
c(A)
A est contradictoire
Nonbivalant
(¬A |- 0)
c(¬A)
A est tautologique
Nonbivalant
(A |- 1)
c(0)
1
Trivial
(¬A |- 1)
c(0)
1
Trivial
(0 |- A)
c(0)
1
Trivial
(0 |- ¬A)
c(0)
1
Trivial
(1 |- A)
c(¬A)
A est tautologique
Nonbivalant
(1 |- ¬A)
c(A)
A est contradictoire
Nonbivalant
¬(A |- 0)
¬c(A)
A est tautologique ou indéterminé
Nonbivalant
¬(¬A |- 0)
¬c(¬A)
A est contradictoire ou indéterminé
Nonbivalant
¬(A |- 1)
¬c(0)
0
Absurde
¬(¬A |- 1)
¬c(0)
0
Absurde
¬(0 |- A)
¬c(0)
0
Absurde
¬(0 |- ¬A)
¬c(0)
0
Absurde
¬(1 |- A)
¬c(¬A)
A est contradictoire ou indéterminé
Nonbivalant
¬(1 |- ¬A)
¬c(A)
A est tautologique ou indéterminé
Nonbivalant
(A |- A)
c(0)
1
Trivial
(A |- ¬A)
c(A)
A est contradictoire
Nonbivalant
(¬A |- A)
c(¬A)
A est tautologique
Nonbivalant
(¬A |- ¬A)
c(0)
1
Trivial
¬(A |- A)
¬c(0)
0
Absurde
¬(A |- ¬A)
¬c(A)
A est tautologique ou indéterminé
Nonbivalant
¬(¬A |- A)
¬c(¬A)
A est contradictoire ou indéterminé
Nonbivalant
¬(¬A |- ¬A)
¬c(0)
0
Absurde
(A |- B)
c(A et ¬B)
(A et ¬B) est contradictoire
Nonbivalant

Nous pouvons également définire d'autre méta opérateurs :






4) Le système axiomatique de Hilbert

Le système des démonstrations axiomatiques de Hilbert utilise le langage d'opérateurs L = {¬, =>} qui constitue une axiomatique d'opérateurs, et à laquelle on ajoute les variables booléennes de l' Univers (x,y,z,t...).

On considère l'extension intérieur du troisième ordre suivante :

L[x,y,z...][A,B,C...][U,V,W...]

(x,y,z...) ∈ Ln
(A,B,C...) ∈ L[x,y,z...] n
(U,V,W...) ∈ L[x,y,z...][A,B,C...] n

Le premier type de variable dite "booléenne" notée en minuscule x, y, z... contient un terme de L évaluable en une qualité booléenne. Le second type de variable dite "propositionnelle" notée en majuscule A,B,C... contient une formule de L, c'est à dire un terme de L[x,y,z...], évaluable en une qualité ternaire. Le troisième type de variable dite "schématique" notée en majuscule intalique U,V,W,... contient un schéma de L, c'est à dire un terme de L[x,y,z...][A,B,C...], évaluable en une qualité septenaire..

4.1) Règle du Modus Ponens

Hilbert utilise la règle du Modus Ponens. Cette règle permet de construire la formule B, à partir du couple de formules (A, A=>B). Les variables A et B contiennent des formules quelconques. Cette règle met en oeuvre un procédé d'unification entre le couple de schémas (A, A=>B) et les couples de formules déjà démontrés. Si l'unification réussie la règle construit la formule contenu dans B, sinon elle ne produit rien, c'est à dire 1 dans une conjonction.

À l'aide du méta-opérateur binaire , on note C•D le résultat de la règle du Modus Ponens appliqué aux deux formules contenues dans la varibale C et la variable D dans un sens ou dans l'autre. Si les arguments ne satisfont pas la règle, alors l'opération returne la formule 1, sinon l'opération retourne la formule produite par la règle. Voici quelques exemples :

x • y = 1  
(x => y) • x    =    y
(x => y) • ¬x    =    1
(¬x => y) • ((¬x => y) => ¬z)     =     ¬z

L'ensemble des formules démontrables à partir du Modus Ponens et de quelques formules initiales F, G, H se note alors par <F, G, H, •>.

Mais il nous faut davantage que simplement noter la règle, il nous faut la programmer, écrire son programme. Cela peut ce faire en utilisant l'opérateur d'unification ~u~(...), la séquence d'instructions, l'opérateur FAIL, une condition, et l'instruction qui retourne le résultat.

• : (X,Y) --> (~u~(X, A), ~u~(Y, A=>B), si FAIL return 1 sinon retourne B)

Puis dans un langage de programmation plus évolué cela peut s'écrire par

• : (A, A=>B), B | 1

L'appel de la fonction procède à deux unifications et retourne B et si elle échoue alors elle retourne 1.

Cette seul règles du Modus Ponens ne suffit pas à épuiser toutes les formes de raisonnement en logique propositionnelle. On doit ajouter des axiomes supplémentaires.

4.2) Les 3 shémats d'axiomes

Hilbert ajoute à son système, une infinité énumérable d'axiomes. Il le fait en utilisant ces trois schémas comme procédé de construction de formules :

A => (B => A)
(¬A => ¬B) => (B => A)
(A => (B => C)) => ((A => B) => (A => C))

Chacun des trois schémas génère, sans se préoccuper des autres schémas, une liste infini énumérable de formules, lorsque (A,B,C) parcours L[x,y,z...] 3 .

D'une manière générale, un schéma désigne un ensemble énumérable de formules, regroupant toutes les formules que l'on peut constituer en remplaçant dans le schèma les variables A,B,C... par des formules quelconques de L. On peut alors y appliquer un des opérateurs "et", "ou". Un tel opérateur regroupe tous ses arguments en un ensemble, et peut être considéré comme un opérateur unaire s'appliquant à cet ensemble. Par exemple

et{ A=>(B=>A) } =  et{ x=>(y=>x), ¬x=>(y=>¬x), y=>(x=>y), (x=>((y=>z)=>x)... }
                             =  (...(((x=>(y=>x) et ¬x=>(y=>¬x)) et y=>(x=>y)) et (x=>((y=>z)=>x)) et...)

Ainsi les trois shémas d'axiomes doivent être noté comme suit :

et{ A => (B => A) }
et{ (¬A => ¬B) => (B => A) }
et{ (A => (B => C)) => ((A => B) => (A => C)) }

ou ce qui revient au même par :

(A,B,C)∈L[x,y,z...] 3

A => (B => A)
(¬A => ¬B) => (B => A)
(A => (B => C)) => ((A => B) => (A => C))

 

---- 24 août 2014 ----

 

 

 

 

 

Et on note {A,B}|-C si il est possible de construire C à l'aides des termes de l'ensemble {A,B} en utilisant une ou plusieurs fois la règle de production du Modus Ponens. Nous avons par exemples :en utilisant le méta-opérateur |- par la propriété suivante :

{A, A=>B} |- B

le méta-opérateur |- prend deux arguments une formule ou un ensemble fini de formules ce qui correspond à une conjonction finie de formules

La démonstration est l'expression (y y=>x) • (z z=>(x=>t))  où les termes en rouge sont les éléments du langage de programmation, et la conclusion t en est l'évaluation. La démonstration est de taille 7, de niveau 3, et de complexité 7.

On peut ainsi définir la taille, le niveau d'emboitement, le partage et la complexité des constructions dans le langage de programmation, telles quelles sont définies au chapitres III.4. Il y a deux niveaux de construction, celle des éléments que sont les termes logiques, et celle des démonstrations.

On peut définir les axiomatiques, des ensembles de termes minimals tel que défini au chapitres III.9.

Etant donné un ensemble fini de termes logiques A. Noter que cet ensemble fini constitue un terme égale à la conjonction de tous ses termes élément. On peut définir la A-taille, le A-niveau et la A-complexité d'un terme U tel que défini au chapitres III.10. La logique propositionnelle ne rencontre pas de difficulté, tant quelle est fini, pour définir ces complexités minimales.

A = {y, y=>x, z, z=>(x=>t)}

A-taille(t) = 7
A-niveau(t) = 3
A-complexité(t) =7

A |-t7 t   
A |-n4 t  
A |-c6 t  

Et nous pouvons également considérer que A = et{y, y=>x, z, z=>(x=>t)}.

Le moteur générateur des démonstrations n'est constitué que de d'une seul règle de construction qu'est la règle du Modus Ponens. Il faut alors ajouter des termes logiques de départs, sinon on ne peut pas appliquer la règle de construction et on ne peut rien construire. Hilbert propose une axiomatique permettant de déduire toutes les totologies du calcul propositionnelle. Elle contient 3 termes appelés axiomes.

5) Les conséquence logique

6) La déduction naturelle

6.1) Les 9 règles d'inférences

  1. Les conjonctions de clauses
  2. Les disjonctions d'états
  3. Le corps perçu par les conjonctions de clauses de validité impaire
  4. Le corps perçu par les disjonctions d'état d'invalidité paire
"Logique et raisonnement", Michael Freud, ellipse 2011









 

 

La 0-complexité d'une formule est la complexité de son calcul lorsqu'elle est implémentée par un arbre et en supposant que l'évaluation de chaque opérateur générateur porte une complexité élémentaire de valeur `1`. La complexité des formules implémentées sous forme d'arbre est donc égale à leur taille, c'est à dire au nombre d'opérateurs qu'elles contiennent. Pour l'exemple

`varphi    =   (0` ou `1) => ¬(1` et `0)`

La formule `varphi` possède une 0-complexité de 8.

L'étude de la complexité nous amène à considérer le partage des données. Une données calculés une fois n'a pas besoin d'être recalculée et peut être réutilisée plusieurs fois à différent endroits de la formule. On introduit un mécanisme de partage de données dans l'implémentation des formules, transformant leur représentation sous forme d'arbre, en représentation sous forme de graphes orientés sans boucle dit arbres partagés.

La 1-complexité d'une formule est la complexité de son calcul lorsqu'elle est implémentée par un arbre partagé qui partage tous ses noeuds de valeur identique. La 1-complexité de `varphi ` vaut 1 car `varphi ` vaut une valeur booléenne déterminée, ici `1`. Autre exemple

`phi    =   (x` ou `y) => ¬(y` ou `x)`

La 1-complexité de `phi ` vaut 6. Et la formule s'écrit `phi    =   (x` ou `y)_a => ¬(a)` ou l'indice `a` indique qu'il y a partage.



3.1) Les systèmes axiomatiques à la Hilbert

Un système axiomatique à la Hilbert est un ensemble de schémas d'axiomes qui ajouté à la seul règle du modus ponens permet de définir l'ensembles des règles de déduction propre au langage propositionnelle. Si par soucis de simplification on se restreint au langage `{`=>`,¬,x,y,z,t,...}`, alors les shémas d'axiomes à considérer sont les suivants :

`A`=>`(B`=>`A)`
`(A`=>`(B`=>`C)) `=>` ((A`=>`B)`=>`(A`=>`C))`
`(¬A `=>` ¬B) `=>` (B`=>`A)`

Chaque schéma d'axiomes est un énumérateur d'axiomes où `A, B, C` parcourent toutes les formules écrivables, qu'elles soient satisfaisables ou non. Si on ajoute au langage la formule vide symbolisée par la formule 1, alors il faut ajouter l'axiome suivant `1`.

alors il faut ajouter le shéma d'axiome suivant `¬1`=>`A` qui est la définition du vrai car le faux implique tout.

3.2) La Déduction Naturelle

 

 

On étudira plus tard, en logique du premier ordre, comment faire opérer ces deux opérateurs "et", "ou", sur des ensembles infinis énumérables d'arguments.



La différence dans ces extensions tient dans la définition de la structure `L` qui porte les principes de construction du langage et qui incorpore les nouveaux aspects décrits (Suppression de 0, 1, `id`, Suppresion de la double négation, Réduction des couples d'opérateurs affirmatif-négatifs, Réduction du couple d'opérateurs non commutatifs).

 

Si on se restreint à notre langage défini en §5, dont l'aspect correspond à la règle `¬¬x  ->  x`, l'ensemble des ces symétries qui modifient l'arbre syntaxiquement mais ne le changent pas sémantiquement, est équivalent à l'ensemble des règles de transformation suivantes, applicables à un noeud quelconque de l'arbre et appliquées un nombre de fois quelconque :

Commutativité du ou :
`x` ou `y` 
`=`
`y` ou `x`
Commutativité du <=> :
`x` <=> `y`
`=`
`y` <=> `x`
Transformation du ou en => :
`x` ou `y`
`=`
`¬x` => `y`
Contraposé avec => :
`x` => `y`
`=`
`¬y` => `¬x`
Contraposé avec <=> :
`x` <=> `y`
`=`
`¬x` <=> `¬y`
Négation du ou :
`¬(x` ou `y)` 
`=`
`¬x` et `¬y`
Négation du et :
`¬(x` et `y)` 
`=`
`¬x` ou `¬y`
Négation du => :
`¬(x` =>`y)` 
`=`
`x` et `¬y`
Négation du <=> :
`¬(x` <=>`y)` 
`=`
`¬x` <=> `y`

 

 


Si on se restreint à notre langage défini en §5 alors nous avons :

P = x et y

S = x <=> y
S = ¬x <=> ¬y

Q = x ou y
Q = ¬x => y
Q = ¬y => x

R = (x et y) ou z
R = (y => ¬x) => z
R = (x => ¬y) => z
R = (¬x ou ¬y) => z
R = ¬z => (x et y)