Systèmes formels et interprétations Logique - 1. Système formel Nous avons introduit : signes de...

Systèmes formels et interprétations

Logique - 1

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.

À 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

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 =

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.

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

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