recevoir les news :: signaler une erreur :: statistiques visiteurs :: imprimer

ALGORITHMES | FRACTALS | ALGEBRE DE BOOLE | CRYPTOGRAPHIE |

Il serait préférable avant de commencer la lecteur de ce chapitre, de parcourir la partie traitant de la logique au chapitre de la théorie de la démonstration et des structures algébriques dans la sections respectives d'arithmétique et de théorie des ensembles.

OPERATEURS LOGIQUES FONDAMENTAUX

Tout triplet   dans lequel  est un ensemble, (ET)  et  (OU) deux opérations internes sur , forme un anneau de Boole (voir les structures algébriques dans le chapitre de théorie des ensembles de la section d'arithmétique) si: 

- Les opérations  et sont commutatives

- Les opérations  et admettent chacune un élément neutre tel que le chiffre 1 est l'élément neutre de  et le chiffre 0 l'élément neutre de

-  est distributive par rapport à  et inversement

- Tout élément  de  admet un complément dans  noté (NON)  ou :

 et

Table de vérité ET ()

Table de vérité OU ()

Toutes les autres fonctions logiques peuvent être composées de ces fonctions fondamentales. Telles que:

NON-OU (NOR) : NON (a OU b)

NON-ET (NAND) : NON (a ET b)

OU EXCLUSIF (XOR) : [a OU b] ET [ NON (a ET b) ]

Table de vérité XOR

où a et b sont des variables (ou "bit" de Binary Digit) pouvant prendre arbitrairement les valeurs binaires 0 ou 1.

PROPRIETES

Nous identifions à partir de ce qui a été défini préalablement, les propriétés suivantes:

- L'idempotence:

- La complémentarité:

- Élément neutre

- L'involution:

- La commutativité:

- L'associativité:

- Distributivité:

Il s'ensuit que l'ensemble binaire  constitue donc bien par rapport aux lois  un "groupe abélien".

Il s'ensuit:

 étant un groupe abélien, la loi  étant associative et distributive par rapport à ,  est un "anneau commutatif unitaire" (vu que possède un élément neutre pour la loi ).

Le lecteur vérifiera sans trop de peine (sinon quoi il peut toujours me contacter) que le OU EXCLUSIF (XOR) est également une loi de groupe.

Si je spécifie cette propriété du XOR, c'est qu'il est particulièrement utilisé en cryptographie et que ce sujet est abordé dans cette section sous le chapitre "Cryptographie".

THEOREMES

- L'absorption:

- Théorèmes de de Morgan

A partir des outils que nous avons définis précédemment, nous pouvons nous permettre de faire une petite incursion pratique dans l'informaitque et voir le principe de la méthode de calcul d'un ordinateur.

Les opérations d'addition et de soustraction de valeurs binaires positives et entières (bits, bytes, word, long word) sont à faire bit par bit en utilisant les lois de groupe ET et OU (XOR), l'inverse (Non) et XOR  tels que:

- lors d'une somme S bit (a) à bit (b) on fasse colonne par colonne (on détermine ces relations grâce aux tables de Karnaugh):

RS=(a ET b) OU (a ET RC) OU (b ET RC)

S=a XOR b XOR RC

où RS est le retenue (pour la colonne) suivante et RC la retenue de la colonne en cours d'utilisation (on commence sur la première colonne avec RC=0 !)

- lors d'une soustraction on fasse identiquement que pour la somme, à la différence que tous les bits de la valeur à soustraire seront inversés et qu'il y sera ajouté la valeur décimale "1" après quoi on procédera à une simple addition telle que on l'a définie précédemment.. Une fois la somme effectuée, on rejette le bit se trouvant à l'extrimité gauche.

La multiplication n'est au fait qu'une succession d'additions pour la machine et réciproquement la division une succession de soustractions. Je ne pense pas qu'il soit nécessaire de trop s'attarder sur ce sujet, c'est plus de l'ingénierie que des mathématiques.

Dans les écoles, on apprend aux étudiants un méthode qui permet de se soustraire de cette dernière (celle qu'utilise l'électronique dans votre ordinateur) non-optimale lors d'exercice ou d'épreuves sur papier.

On a donc une idée formelle de la procédure que suite un ordinateur composé de portes logiques ET et OU pour faire des calculs élémentaires. Mais comment fait-il pour savoir si un nombre (sous forme binaire) est plus grand qu'un autre lors d'un division (soustraction successives) ?

Eh bien, il est facile de contrôler que le bit la valeur du bit le plus à gauche est toujours plus grande que la somme de tous les bits situés à sa droit. Ainsi, on peut par détermination de l'emplacement du "bit de poids fort" de deux valeurs binaires différentes déterminer laquelle est la plus grande. 

Au besoin, rappelons que (cela a déjà été démontré dans la section arithmétique du site) tout nombre entier positif peut être représenté dans une base b sous forme de somme, où les coefficients  sont multipliés chacun par leur poids respectif . Tel que:

Autrement écrit:

avec  et

Ainsi en base deux on a pour habitude a faire de petits tableau tel que celui ci-dessous:

 Ce qui donne pour le byte (ou octet en français) 10010111 la valeur décimale:

128+16+4+2+1=151

J'espère n'avoir pas a redémontrer (ce qui a déjà été fait dans la section d'arithmétique du site) qu'un nombre quelconque à la puissance nulle vaut 1 !