Système formel

• Nous avons introduit : signes de variables (x, y, z, …), de constantes (0, 1), d’opérations (+, ), de relations (=, )

• Axiomes : ce sont des propositions correctement formées obtenues au moyen de ces signes (en utilisant des règles bien définies), ex: la commutativité de + (x + y = y + x) est un axiome, de même que ce que Boole appelle la loi fondamentale de la pensée: x2 = x.

suite

• À partir de ces axiomes et par des déductions, nous pouvons déduire d’autres propositions bien formées, qu’on appelle des théorèmes.

• Par exemple, nous avons obtenu la deuxième forme de la distributivité comme un théorème, de même pour le principe de non-contradiction, qui peut s’écrire:

• x(1-x) = 0

suite

• Le fait d’ « interpréter » ou de « ne pas interpréter » les x, y, z, … ou bien 1 et 0 n’a pas de rôle dans ces déductions,

• On aurait pu utiliser et au lieu de 1 et de 0 ! Les seules choses à garder en ce cas auraient été les axiomes:

+x = ; x = x+x = x; x =

suite

• On aurait même pu aller plus loin et oublier toutes références à l’addition et à la multiplication, en utilisant des symboles autres pour les opérations: par exemple € et £…et ∞ au lieu de =

• Les axiomes précédents seraient devenus: €x∞; £x∞x €x∞x; £x∞

• Avec en plus évidemment toutes les traductions d’axiomes comme commutativité, idempotence etc.

• Les mêmes déductions auraient été possibles.

suite

• Il faudrait maintenant donner une présentation plus précise du système formel implicite chez Boole…

• Y a-t-il des axiomes non explicitement formulés? (que Boole utiliserait sans le dire)

• N’y a-t-il pas quelque redondance dans les axiomes? (certains pouvant s’obtenir à partir d’autres au titre de théorèmes)

• Le nombre d’axiomes donnés est-il minimal?• Ce sont les questions « système formel »

Interprétation

• Une fois que nous avons un système formel, nous pouvons essayer de donner une interprétation aux signes introduits, par exemple, nous interprétons comme « le nombre 0 », comme « le nombre 1»,

• Mais nous ne pouvons pas donner des interprétations aux signes indépendamment les uns des autres… il faut une cohérence. Si nous interprétons x, y, z comme des nombres quelconques, alors nous voyons bien que certaines propriétés exprimées par des axiomes ou des théorèmes vont être en échec…

suite

• Si et sont interprétés comme 0 et 1 respectivement, il ne s’agit pas exactement des 0 et 1 courants de l’arithmétique… c’est le 0 et le 1 d’une algèbre particulière

• De ce fait, + et ont aussi une interprétation particulière, qui ne consiste pas dans l’addition et la multiplication des entiers par exemple! (car 1+1=2 pour les entiers, alors que 1+1=1 dans notre cas!)

• Il faut donc maintenant définir rigoureusement l’interprétation des opérations de ce système.

• Ce sont des questions d’interprétation, ou de théorie des modèles.

Théorie des modèles

• L’interprétation que nous construisons doit bien sûr nous être utile… il faut par exemple que tout ce que nous pouvons trouver vrai dans l’interprétation corresponde à ce qu’on peut démontrer comme théorèmes dans le système formel

• (complétude)• Et il faut aussi bien sûr la réciproque: que tout

ce qui est démontrable soit vrai dans l’interprétation

• (consistance)

Interprétation • Le domaine de l’interprétation est, par définition, un ensemble

non vide,• Ici, nous devons au minimum donner une interprétation aux

constantes, que nous avons notées provisoirement et , donc le domaine de l’interprétation doit contenir au moins deux objets distincts,

• Choisissons comme domaine de l’interprétation l’ensemble {0, 1}• Cela signifie que les constantes sont interprétées comme éléments

de cet ensemble ( 0; 1) et que les variables ont pour valeurs des éléments de cet ensemble (on appelle de façon générale variable booléenne une variable à valeurs dans {0, 1})

• + et sont interprétées comme des lois de composition interne sur {0, 1} que nous allons définir (tables)

• Cette interprétation est « la plus petite » que nous pouvons donner à notre système formel

suite

• Afin d’avoir une chance que les vérités de l’interprétation correspondent aux théorèmes et aux axiomes… il faut faire un choix judicieux des valeurs attribuées par + et aux couples d’éléments de {0, 1}

• 0 étant élément neutre de +, on a:• 0 + 0 = 0 et 0 + 1 = 1 + 0 = 1• 1 étant élément absorbant de +, on a:• 1 + 1 = 1

+

• D’où la première table:

+ 0 1

0 0 1

1 1 1

Remarque

• Le texte de Boole nous a invité à utiliser le symbole « – » pour marquer une opération de pseudo-opposée par rapport à +, en fait, 1-x devait être compris comme la classe complémentaire de x. Pour éviter cette « soustraction », on peut considérer 1-x comme le résultat d’une opération unaire sur x, qu’on notera par exemple x, avec la définition: 0 1

1 0

X

• De même, on a:

• 1 X 1 = 1; 1 X 0 = 0 X 1 = 0

• 0 X 0 = 0

• D’où la deuxième table:

X 0 1

0 0 0

1 0 1

Formules vraies dans l’interprétation (tautologies)

• Verifier que les formules suivantes sont vraies (ce qui signifie que dans tous les cas de valeurs pour x, y, z… les deux côtés du signe = prennent la même valeur):

• x(y+z) = xy + xz ; x+yz = (x+y)(x+z)• x(1 – x) = 0 ; x + (1 – x) = 1• x + y = xy + x(1-y) + (1-x)(1-y) + (1-x)y• 1–(x+y) = (1-x)(1-y) ; 1-xy = (1-x)+ (1-y)

(ou: (x+y) = xy ; (xy) = x+y)

Retour au système formel

• Nous prenons volontairement des symboles distincts de +, etc. afin de bien marquer l’indépendance du système formel par rapport à son interprétation.

• Des symboles souvent utilisés sont, pour les opérations: et , pour les constantes: et T. Nous introduisons également le symbole

axiomes

• (i) pour tout x et tout y: xy = yx ; xy = yx,

• (ii) pour tout x, tout y et tout z: x(yz) = (xy)z ; x (yz) = (xy)z

• (iii) élément neutre pour , T élément neutre pour ,• (iv) pour tout x, tout y et tout z,

x(y z) = (xy) (x z)x (y z) = (x y) (x z)

• (v) pour tout x, il existe x tel que:x x = T; x x =

Théorème 1:idempotence

• Démontrer:• Pour tout x, xx = x et xx = x• solution:

x = x = x(xx) = (xx) (xx) = (xx) T = xx

Théorème 2:éléments absorbants

• Démontrer que:

• Pour tout x, x T = T et x = • solution:

xT = x(xx)

= (xx)x

= xx = T

Théorème 3:unicité de la négation

• Démontrer que :

• pour x donné, x est unique

• solution: soit x’ tel que x’x = et x’x = T, alors:

x’= x’T= x’(x x) = (x’x) (x’x)

= (x’x) = (xx) (x’x) =

(xx’)x = Tx = x

Théorème 4:lois de De Morgan

• Démontrer que:• Pour tout x et tout y:

(xy) = xy (xy) = xy

• solution: il faut utiliser le résultat précédent! Pour cela, démontrer que:(xy)(xy) = et que(xy)(xy) = T

Théorème 5 : loi de double négation

• Démontrer que:

• Pour tout x, (x) = x

Logique de l’inclusion

• Démontrer:

• xy z si et seulement si x z et y z

• x yz si et seulement si x y et x z

• x y si et seulement si y x

• x y si et seulement si xy =

• xy est la borne supérieure de x et de y

• xy est la borne inférieure de x et de y