BOOLE George, anglais, 1815-1864

Autodidacte, brillant latiniste, instituteur (il ouvrit une école privée), Boole s'initie aux mathématiques en étudiant les œuvres de Lagrange et de Laplace et se fait connaître par de premières publications dans le Cambridge mathematical Journal. Encouragé par de Morgan, il est à l'origine de la notion d'ensemble et du "calcul" sur ces ensembles (classes d'objets : classes of things) liant la logique mathématique au calcul algébrique (The Mathematical Analysis of Logic, 1847).

Boole résolut ainsi un des problèmes fondamentaux de formalisation du langage et du raisonnement, que se posaient les mathématiciens depuis Leibniz. La pertinence de ses travaux lui permirent l'obtention (1849) d'une chaire de mathématiques au Queen's Collège de Cork (Irlande du sud).

On considère souvent Boole comme le créateur de la logique moderne. Son algèbre de la logique, L'algèbre de Boole, qu'il exprime en 1854 dans son traité An investigation of the laws of thought (sur les lois de la pensée), est aussi utilisée de nos jours en électricité, en électronique et dans la mise au point des algorithmes des machines automatiques. L'année suivante, il épousait Boole Mary Everest, nièce de George Everest qui donna son nom au célèbre mont népalais (8848 m), dont il fut un des professeurs particuliers. Il meurt prématurément d'une pneumonie à l'âge de 49 ans.

Cours issu de : http://www.courstechinfo.be/MathInfo/FctLogiques1.html

Logique booléenne

Introduction

La logique, si l'on considère l'histoire des sciences, est une discipline très ancienne dont les traces les plus éloignées remontent aux philosophes Grecs. Logos en grec se traduit par parole et/ou raison. Aristote, parait-il, s'amusait à voir comment étaient construits les faux raisonnements ... Mais, ce n'est pas de cette logique là que nous traiterons ici.

La logique qui va nous occuper dans les pages suivantes concerne l'étude de fonctions logiques élémentaires qui traitent des variables binaires par des méthodes aussi systématiques que les mathématiques. Le but est ici de comprendre et démystifier autant que se peut la manière dont les ordinateurs effectuent les opérations logiques de base puis d'entrevoir comment ces fonctions peuvent être combinées pour obtenir des résultats de plus en plus complexes comme par exemple les opérations arithmétiques.

Variables logiques

Dans les systèmes digitaux (systèmes informatiques et autres automatismes numériques) toutes les données sont traitées et enregistrées à partir d'éléments d'informations binaires.

Ces informations binaires à la manière des contacts électriques n'ont que deux états possibles : un contact électrique est ouvert ou fermé, de même le bit est une information élémentaire qui ne peut prendre que deux valeurs 0 et 1.

Dans la suite de ce cours les variables logiques sont représentées par des lettres. Les valeurs de ces variables sont à priori indéterminées, elles sont « variables ». Ainsi, si l'on écrit l'équation logique « S = A » cela signifie que la variable logique S a exactement la même valeur que la variable A mais rien ne précise quelle est la valeur de A ( 0 ou 1 ?) On dira que A est une variable binaire puisqu'elle ne peut prendre à un instant donné qu'une des deux valeurs 0 ou 1.

NB. Un parallèle peut être fait avec les variables algébriques comme par exemple dans la fonction algébrique « y = 2x + 5 » Elle nous indique comment calculer y pour chaque valeur de x mais la valeur de x n'est pas figée. C'est ici une variable algébrique.

Les opérations logiques sont en informatique aussi courantes si pas plus que les opérations arithmétiques. La logique combinatoire tout comme l'arithmétique repose sur quelques opérations élémentaires.

• En arithmétique, ces opérations sont l'addition, la soustraction, la multiplication et la division ( +, -, *, / ). Il est possible à partir de là d'imaginer toutes les autres opérations telles que les exposants, les racines, les logarithmes etc.
• En logique, les opérations fondamentales sont le ET, le OU et le NON.
• Nous utiliserons des signes particuliers pour représenter ces trois opérations fondamentales lors d'écriture d'équations logiques. C'est George Boole, un mathématicien britannique, qui le premier eu l'idée de reprendre des notations algébriques pour créer les bases de ce qui sera la logique informatique. Nous ferons donc de la logique booléenne et aussi de l'algèbre booléenne en écrivant des équations logiques pour exprimer les relations entre les variables logiques appellées aussi variables booléennes.

Cette logique a trouvé après George Boole ses premières applications dans les circuits électriques. C'est Claude Shannon , un autre père fondateur des théories à la base de l'informatique, qui entreprit de mettre en équation les circuits électriques où des relais électriques considérés comme des variables logiques en agissent sur des contacts ouverts (0) ou fermé (1).

Fonctions logiques de base

La manière la plus simple de comprendre les fonctions logiques est de se les représenter par des schémas électriques qui comportent un ou plusieurs contactss et une lampe. Cette lampe s'allume "à condition" que les contacts électriques y laissent passer le courant. C'est dans l'expression de cette condition que va intervenir la logique.

Le schéma ci-dessous traduit la condition la plus simple :

La lampe s'allume si le bouton poussoir A est actionné.

Autrement dit ( S = 1) si ( A = 1) .

Le fonctionnement de ce circuit s'exprime par l' équation logique S = A.

Il n'y a que deux cas possibles. Ils sont représentés dans cette table de vérité.

Une table de vérité a pour le rôle de montrer la correspondance entre la sortie et toutes les combinaisons de valeurs que peuvent prendre la ou les entrées.

Le contenu de la table de vérité s'obtient en imaginant toute les configurations possibles pour le contact A (0 = contact relâché, 1 = bouton pressé). A chacun des états du contact A on vérifie d'après le schéma électrique ou d'après l'équation logique si la lampe est éteinte (0) ou allumée (1).

Plaçons maintenant deux contacts dans le circuit. La condition nécessaire pour allumer la lampe dépend de la manière dont les contacts sont connectés. Suivant les cas, la condition pour allumer la lampe fait appel aux opérateurs logiques ET ou OU.

La fonction ET

La lampe s'allume si on active simultanément les contacts A et B. (S = 1) si (A = 1) ET (B = 1) .

On a donc S = A . B.

L'opérateur ET est représenté dans l'équation logique par un point. Ce signe convient parfaitement puisque la fonction ET donne le même résultat qu'une multiplication.

Le contenu de la table de vérité s'obtient en imaginant toute les configurations possibles pour le contact A (0 = contact relâché, 1 = bouton pressé). A chacun des états du contact A on vérifie d'après le schéma électrique ou d'après l'équation logique si la lampe est éteinte (0) ou allumée (1).

La fonction OU

La lampe s'allume si on active le contact A ou le contact B. (S = 1 ) si ( A = 1) OU ( B = 1).

On a donc S = A + B.

L'opérateur OU est représenté dans l'équation logique par un signe plus surmonté d'un point. Observons les trois premières ligne de la table de vérité, le résultat de l'opération OU y est semblable au résultat d'une addition. Le résultat de 1 ou 1 diffère cependant de 1+1. Nous mettons un point au-dessus du signe '+' pour indiquer que l'opération n'est pas analogue à une addition.

La fonction NON

Les contacts que nous avons utilisés jusqu'ici, sont des contacts "normalement ouverts". Quand le bouton poussoir est relâché ( quand A = 0) le courant ne passe pas.

Nous utilisons maintenant un contact "normalement fermé" pour illustrer la fonction NON. Au repos, le courant passe mais il se coupe quand le contact est activé (quand A = 1).

Soit "S = Non A".

Combinaisons de fonctions logiques

Combinaisons des 3 fonctions de base

Les trois fonctions de base AND, OR et NOT se combinent de multiples façons. Ces combinaisons peuvent facilement être illustrées par des montages de contacts électriques.

Correspondance entre schémas et équations logiques

A chaque schéma imaginable correspond une équation. La correspondance entre un schéma et une fonction logique est systématique :

- Des montages en parallèle correspondent à la fonction OU

- Des montages en série correspondent à la fonction ET

- Un contact normalement fermé représente la fonction NON

Exemples :

Tables de vérité

Pour tracer la table de vérité, que ce soit à partir d'un schéma ou d'une équation, il faut commencer par dénombrer les variables. Les exemples ci-dessus comportent chacun 3 variables (A, B et C).

Il faut remarquer qu'une même variable peut intervenir plusieurs fois dans une équation ou sur plusieurs contacts dans le schéma. C'est le cas de la variable A dans le troisième exemple.

On trace ensuite une table avec toutes les combinaisons possibles des n variables. Cela donne 2ⁿ combinaisons. 8 = 2³ dans nos exemples. Le plus facile est de noter toutes ces combinaisons en considérant qu'elles forment des nombres écrits en binaire et des les aligner une à une comme si l'on comptait en base 2. On est alors certain en faisant de la sorte de n'avoir oublier aucun cas.

Reste maintenant de déduire les valeurs à indiquer dans la colonne de droite.

Elles résultent du fonctionnement du schéma de contacts ou du calcul de ce que donne l'équation logique.

• Déduction à partir du schéma de contacts :
• On considère qu'un contact est actionné si la variable correspondante vaut 1. Le contact est dans sa position de repos (comme représenté sur le schéma) lorsque la variable correspondante vaut 0. Attention à ne pas confondre le fait qu'un contact soit actionné et le fait qu'il soit fermé. Un contact normalement ouvert laisse passé le courant quand il est actionné mais un contact normalement fermé laisse passer le courant quand il n'est pas actionné.
• Calcul à partir de l'équation logique : on substitue les variables par les valeurs qui leurs sont attribuées aux différentes ligne de la table de vérité.

Les portes logiques

Nous avons jusqu'ici utilisé des boutons poussoirs et une lampe pour illustrer le fonctionnement des opérateurs logiques. En électronique digitale, les opérations logiques sont effectuées par des portes logiques. Ce sont des circuits qui combinent les signaux logiques présentés à leurs entrées sous forme de tensions. On aura par exemple 5 V pour représenter l'état logique 1 et 0 V pour représenter l'état 0.

Fonctions logiques de base

Porte AND

Porte OR

Porte NOT

Combinaisons des fonctions logiques de base

Porte NAND

Porte NOR

Porte XOR

La fonction "OU Exclusif" est en principe d'une fonction de deux variables :

S = A XOR B

La sortie est à 1 si une seule des deux entrées vaut 1.

Porte XOR à plusieurs entrées

Pour calculer le résultat de S = A XOR B XOR C, il faut d'abord faire l'opération entre deux termes, puis refaire un ou exclusif entre le résultat obtenu et le troisième terme.

Ce qui se traduit par S = ( A XOR B) XOR C ou par S = A XOR ( B XOR C)

On constate que l'appellation "Ou exclusif" n'est tout à fait exacte que pour deux variables. Avec trois variables, le résultat vaut 1 si une d'entre elles ou toutes les trois valent 1.

Le résultat est en fin de compte un bit de parité. Il vaut 1 si le nombre d'entrées à 1 est impair.

Règles de base de l'algèbre de Boole