I : Introduction à la logique *

II : Propositions logiques *

III : Algèbre binaire : algèbre de BOOLE *

Soit un système de détection de présence, une alarme par exemple. Ce système possède un capteur indiquant que quelqu’un marche sur le sol. L’information provenant de ce capteur est donc soit VRAIE (quelqu’un marche) ou FAUSSE (personne ne marche). Le système ne possède donc que deux états : on dit qu’il est binaire.

Nombreux sont les systèmes tels que celui décrit ci-dessus qui produisent ou utilisent une information binaire.

D’autre part, les outils de traitement automatique de l’information, (ordinateurs…) utilisent des composants électroniques (transistors) qui traitent cette information sous forme binaire. (dans un transistor, le courant passe ou ne passe pas) Ces composants sont appelés circuits logiques. Les systèmes qui utilisent ces composants sont appelés systèmes logiques.

La nature binaire de ces informations nécessite de disposer d’un outil mathématique approprié.

Si l’on reprend l’exemple de l’alarme, le système logique traite une information en entrée, et donne une information de sortie. Ces informations, binaires, peuvent s’écrire sous la forme de propositions logiques, comme " une personne marche sur le sol " pour l’information d’entrée, et " police alertée " pour l’information de sortie. Ces deux propositions ne peuvent être que VRAI ou FAUX, mais pas les deux à la fois.

Le système (ici l’alarme) logique consiste à produire une ou plus information(s) de sortie en fonction d’une ou plus information(s) d’entrée.

Toute information binaire pour être représentée par une proposition logique qui ne peut être que VRAIE ou FAUSSE.

Elle peut être simple (" il fait plus de 25°C " ) ou complexe (" il fait plus de 25°C ET il NE pleut PAS ").

L’action exercée par le système logique sur la(les) information(s) de sortie est appelée fonction logique. Elle établit une équivalence logique entre les informations d’entrée et celles de sortie.

Dans le cas de l’alarme, on a " police alertée " SI " une personne marche sur le sol ", donc les deux propositions sont VRAIES en même temps, et FAUSSES en même temps. On a donc " police alertée " =  " une personne marche sur le sol ".

Cette fonction est appelée identité ou encore OUI.

Soient les propositions " j’irai me promener " et " il pleut ". Le système doit déterminer quand sortir, la logique du problème est : " j’irai me promener s’il ne pleut pas ". On peut donc dire que " j’irai me promener "= NON " il pleut ", car NON  " il pleut " = " il ne pleut pas ".

Cette fonction est appelée négation ou fonction NON.

Fréquemment les systèmes possèdent plusieurs entrées logiques, donc plusieurs propositions. Par exemple, un four doit s’arrêter si la température voulue est atteinte ou si le temps prévu est écoulé. Les propositions logiques peuvent être :

• P1 : " la température est supérieure à T₀ "
• P2 : " le temps est supérieur à t₀ "
• P3 : " le four doit s’arrêter "

On peut écrire :

P3 est vraie si P1 est vraie OU si P2 est vraie.

Donc on a

P3=P1 OU P2.

La fonction s’appelle somme logique ou fonction OU.

N.B. on remarque que si P1 et P2 sont toutes deux vraies, P3 est vraie également. On parle de OU inclusif.

Examinons la phrase : " j’irai me promener s’il fait plus de 25°C et s’il ne pleut pas. ".

Soient les propositions :

• P1 : "j’irai me promener "
• P2 : " il fait plus de 25°C "
• P3 : " il ne pleut pas ".

Pour que la proposition P1 soit vraie, il faut que les deux propositions P2 et P3 soient vraies simultanément.

On peut donc écrire :

P1 est vraie si P2 est vraie ET P3 est vraie.

Ou encore :

P1 = P2 ET P3.

Cette fonction s’appelle produit logique ou fonction ET.

Il arrive que l’on ait besoin de la conjonction de plusieurs de ces fonctions :

Etudions le cas : " j’irai me promener s’il fait plus de 25°C et qu’il ne pleut pas, ou si ma copine le veut. "

Soient les propositions :

• P1 : " j’irai me promener "
• P2 : " il fait plus de 25°C "
• P3 : " il pleut "
• P4 : " ma copine veut se promener "

Le problème se décrit par :

P1 est vraie si P2 est vraie ET P3 est fausse, ou si P4 est vraie.

Soit :

P1=(P2 ET NON P3) OU P4.

On remarque vite le besoin d’un formalisme mathématique pour décrire, traiter, et résoudre des problèmes logiques.

L’algèbre binaire, ou algèbre de Boole, est un outil mathématique permettant de formaliser les propriétés relatives aux systèmes logiques.

Soit l’ensemble E constitué de deux éléments :

• L’un est appelé élément nul et est noté : ‘0’
• L’autre est appelé élément unité et est noté : ‘1’

On a donc : E={0,1} 

Un élément quelconque de E est désigné par un symbole, par ex. une lettre A,B,C… qui peut prendre la valeur 0 ou 1. Ces symboles sont des variables logiques.

On définit sur cet ensemble E les lois suivantes :

C’est une loi unaire (elle ne concerne qu’une seule variable) notée " barre " telle que :

C’est une loi de composition interne (elle ne fait intervenir que des éléments de E) qui se note ‘+’ et qui se lit ‘ou’ telle que :

C’est une loi de composition interne (elle ne fait intervenir que des éléments de E) qui se note ‘.’ et qui se lit ‘et’ telle que :

On peut montrer que l’ensemble E muni des lois (+,.) satisfait aux propriétés suivantes, quels que soient A et B appartenant à E :

On dit alors que {E,+,.} est une algèbre, appelée algèbre binaire.

Les théorèmes suivant s’établissent à partir des postulats de l’algèbre binaire :

Le dual d’un énoncé quelconque d’un théorème de l’algèbre binaire est obtenu en permutant les opérateurs ‘+’ et ‘.’ et les éléments ‘0’ et ‘1’.

Le dual de tout théorème d’algèbre binaire est un théorème d’algèbre binaire.

Soit une fonction f de E³ dans E :

C’est une fonction binaire de trois variables.

(C,B,A) est un triplet ordonné.

La connaissance de la fonction f permet d’associer une valeur (0 ou 1) à chacune des valeurs du triplet. Toutes les valeurs possibles pour ce triplet sont :

Elles sont au nombre de 8 (2³).

Pour un multiplet de n variables (n-uplet) il y a 2ⁿ valeurs possibles.

Le multiplet est désigné mot binaire ou combinaison binaire. Il est en général noté %CBA pour (C,B,A). La valeur du multiplet est appelée état binaire. Par exemple, si C=0, B=1 et A=0, on note : %CBA=%010. Le ‘%’ indique que les variables et les valeurs sont binaires.

Toute fonction binaire peut s’exprimer à partir des variables binaires d’entrée (mot binaire d’entrée) en n’utilisant que la négation, la somme et le produit logiques. Par exemple :

L’algèbre binaire peut se substituer à l’utilisation des propositions logiques, et on l’emploie chaque fois que la complexité des systèmes logiques l’exige.

La transposition des propositions logiques à l’algèbre binaire est la suivante :

Les propriétés et les théorèmes de l’algèbre binaire permettront une approche plus simple et systématique des problèmes logiques complexes.