Un univers est un ensemble de mondes possibles obéissant à un schéma.... Dans la suite de l'exposé, on ne parlera que des seuls univers cartésiens booléens finis.
Le schéma d'un univers est constitué d'une liste de n bits, c'est à dire une liste de n variables booléennes. L'entier n est apellé la dimension de l'univers. Un monde de cet univers est une liste de n valeurs booléennes que l'on appelle liste de vérité et qui fixe la valeur de chaque variable schématique dans le monde en question. L'univers est l'ensemble de tous les mondes possibles s'inscrivant dans ce schéma de n bits. Par exemple nous pouvons définir l'univers Ω de dimension n=3 comme suit :
Ω = Univers (x,y,z)
Ω = {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}
(x,y,z) est le schéma de l'univers. Il nomme des variables booléennes qui auront une valeur spécifique dans chaque monde. Les listes de vérité déterminent les valeurs des variables nommées par le schéma dans les différents mondes possibles. L'univers Ω possède 3 variables booléennes shématiques x, y, z, et possède 23 mondes possibles.
La notion d'univers définit une logique du deuxième ordre, c'est à dire avec deux types de variable, des variables de premier ordre dites shématiques, et des variables de second ordre désignant les mondes. Dans le cas fini cela ne change pas la nature de la logique, mais l'intuition qu'elle porte nous permettra d'entrevoir plus loin.
On définie le produit de deux univers A×B comme étant l'univers constitué des couples de mondes possibles, le premier monde appartenant à l'univers A, et le second monde appartenant à l'univers B. Les univers sont caractérisés de manière unique, à bijection près des schémas, par leur dimension.
En mécanique classique, le bit est une mémoire possédant deux états possibles, exclusifs et exhaustifs. Il est représenté par une case contenant soit 0 soit 1. Le bit constitue un univers élémentaire noté O. Cet univers possède une unique variable booléenne, et possède 2 mondes possibles :
O = Univers (x)
O = {0,1}
L'univers Ω = Univers (x,y,z) se décompose en produit d'univers plus petit. Il correspond à 3 bits. Il se construit par produit de 3 bits.
Ω = O×O×O
Ω = Univers (x0, x1, x2)
Etant donné un monde m. Si le schéma est (x, y, z, t) alors on note m.x, m.y, m.z, m.t, la valeur de x, y, z, t dans le monde m. Nous avons :
m = (m.x, m.y, m.z, m.t)
m = {x=m.x, y=m.y, z=m.z, t=m.t}
Un monde peut se définir par une égalité telle que m = (a,b,c,d) qui s'écrit aussi m = {x=a, y=b,z=c,t=d}. Dés lors nous avons m.x = a, m.y=b, m.z=c, m.t=d.
Les mondes sont codés en des entiers, selon l'endianess big-endian. Le monde m = (x,y,z,t) est codé par l'entier code(m) = x*23 + y*22 + z*21 + t*20.
On adopte un autre nom des variables de l'univers qui est (x0, x1, x2, x3) et par convention les valeurs de ces variables dans le monde m sont notées m0, m1, m2, m3. Ainsi nous avons :
m = (m0, m1, m2, m3)
m = {x0=m0, x1=m1, x2=m2, x3=m3}
m = {x=m0, y=m1, z=m2, t=m3}
code(m) = m0*23 + m1*22 + m2*21 + m3*20
Une formule est une compositiobn close dans le langage L = {0, 1, ¬, =>, <=, <=>, et, ou, ¬=>, ¬<=, ¬<=>, ¬et, ¬ou} augmenté des variables schématiques de l'univers. Par exemple dans l'univers Ω = Univers (x,y,z), on définie la propostition A suivante :
A = x et (y => z)
Un monde spécifie la valeur de chaque variable schématique et donc spécifie la valeur de chaque formule ou proposition. On dira que m satisfait A, ou que A est satisfait dans m, si et seulement si A est vrai dans m, c'est à dire, si A a pour valeur résultat 1 dans m, et on notera :
m ⊨ A
Inversement si A est faux dans m, on notera
m ⊭ A
La totologie, la contradiction et la cohérence se définissent comme suit :
Dans tous les mondes possibles A est vrai. Dans tous les mondes possibles A est faux. Il existe au moins un monde m où A est faux.
Il existe au moins un monde m où A est vrai.
Une conjonction complète est une conjonction où toutes les variables de l'univers apparaissent une et une seul fois, soit affirmativement, soit négativement. Par exemple dans l' Univers (x,y,z,t), la conjonction x et ¬y et z et t est complète. L'ordre n'a pas d'importance, mais un ordre particulier est choisi qui est celui des variables définies dans l'univers c'est à dire selon l'ordre x, y, z, t. La conjonction complète est identique à une liste de vérité, et est identique à un monde.
Par dualité on définie les disjonctions complètes comme étant les négations des conjonctions complètes. La disjonction complète est une disjonction où toutes les variables de l'univers apparaissent une et une seul fois, soit affirmativement, soit négativement. elle désigne un monde complémentaire, mais cela ne constitue pas un monde, cela constitue l'ensemble de tous les mondes autres que le monde dont elle veut désigner le complémentaire.
Les conjonctions et disjonctions complètes sont codables comme les mondes, en rangeant les variables selon l'ordre de l'univers, et selon l'endianess big-endian. Par exemple dans l' Univers (x,y,z,t), le monde (0,1,0,1) qui s'écrit également {x=0, y=1, z=0, t=1}, correspond à la conjonction complète ¬x et y et ¬z et t, et est codé par le nombre binaire 0101 puis par l'entier 0*23 + 1*22 + 0*21 + 1*20 = 5. Sa négation est la disjonction complète x ou ¬y ou z ou ¬t, et est codé par le nombre binaire 1010 puis par l'entier 1*23 + 0*22 + 1*21 + 0*20 = 10.
¬x et y et ¬z et t = conj(0101 en base 2)
¬x et y et ¬z et t = conj(5)
x ou ¬y ou z ou ¬t = disj(1010 en base 2)
x ou ¬y ou z ou ¬t = disj(10)
Toute proposition définie un opérateur booléen et se définie par sa table de vérité. Chaque ligne de la table de vérité est une conjonction complète. Et on ne s'intéresse qu'aux seuls lignes de la table de vérité produisant 1. La proposition est alors équivalente à la disjonction de ces conjonctions complètes. Cette forme est appelée la forme normale disjonctive. Elle est unique à l'ordre près, autrement dit, en respectant l'ordre des conjonctions complètes selon leur code.
Puis on ne s'intéresse maintenant aux seuls lignes de la table de vérité produisant 0. La proposition est alors équivalente à la négation d'une disjonction de ces conjonctions complètes. Cette négation se met sous une forme normale conjonctive. Elle est unique à l'ordre près, autrement dit, en respectant l'ordre des disjonctions complètes selon leur code.
On définie l'ordre des variables tel qu'il est définie dans l' Univers (x,y,z).
On définie l'ordre des conjonctions complètes selon l'endianess big-endian de 0 à 23-1. Et on définie l'ordre des disjonctions de conjonctions complètes toujours selon l'endianess big-endian comme on rangerait les listes finies d'entiers croissants. La forme normale disjonctive respectant ces trois ordres, est une expression unique.
On définie l'ordre des disjoncions complètes selon l'endianess big-endian de 0 à 23-1. Et on définie l'ordre des conjonctions de disjonctions complètes toujours selon l'endianess big-endian comme on rangerait les listes finies d'entiers croissants. La forme normale conjonctive respectant ces trois ordres, est une expression unique.
Par exemple considérons la proposition suivante :
P = x et (y => z)
On établit sa table de vérité, chaque ligne correspond à un monde :
On construit sa forme normale disjonctive qui liste tous les mondes dans lequel le résultat vaut 1 : P = (x et ¬y et ¬z) ou (x et ¬y et z) ou (x et y et z) Puis en codant les conjonctions complètes en binaire : P = conj(100) ou conj(101) ou conj(111) Puis en codant les listes de vérité en entier : P = conj(4) ou conj(5) ou conj(7) Puis en codant la forme normale disjonctive en une listes d'entiers croissants : P = disj_conj(4, 5, 7) |
| | | | | | | | | | | | | | | | | | | | |
On construit la forme normale disjonctive qui liste tous les mondes ou le résultat vaut 0 : ¬P = (¬x et ¬y et ¬z) ou (¬x et ¬y et z) ou (¬x et y et ¬z) ou (¬x et y et z) ou (x et y et ¬z) Puis on développe la négation en permuttant les et et les ou et en inversant les littéraux, pour obtenir la forme normale conjonctive : P = (x ou y ou z) et (x ou y ou ¬z) et (x ou ¬y ou z) et (x ou ¬y ou ¬z) et (¬x ou ¬y ou z) Puis en codant les disjonctions complètes en binaire : P = disj(111) et disj(110) et disj(101) et disj(100) et disj(001) Puis en codant les disjonctions complètes en entier : P = disj(7) et disj(6) et disj(5) et disj(4) et disj(1) Puis en codant la forme normale conjonctive en listes d'entiers croissants : P = conj_disj(1,4,5,6,7) |
On considère les deux corps suivant C2 et C2 :
C2 = Corps (0, 1, w, et)
C2 = Corps (0, 1, +, *)C2 = Corps (1, 0, <=>, ou)
C2 = Corps (0, 1, +, *)
Nous avons :
¬x = x + 1
x + y = x w y
x * y = x et y0 = 1
1 = 0
¬x = x + 1
x + y = x <=> y
x * y = x ou y
dans C2
dans C2
Les propositions se traduisent dans chaque corps par des polynômes et admettent donc dans chacun d'eux, une forme normale polynomiale. Les mônomes sont rangées du degré le plus grand au degré le plus petit en respectant l'ordre des variables de l'univers et l'endianess big-endian. Par exemple :
P = x et (y => z)
P = x*(y*z + y +1)
P = x*y*z + x*y + x
P = x et (y => z)
P = x*(y*z + z) + x + (y*z + z)
P = x*y*z + x*z + x + y*z + z
P = x*y*z + x*z + y*z + x + z
Sujet :
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.
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 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é.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. NomenclatureLes 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