I : Introduction à la logique *
I-2 : Nécessité d’un outil *
II : Propositions logiques *
II-2 : Définition *
II-3 : Fonctions logiques *
II-3-a : Négation : fonction NON *
II-3-b : Somme logique : fonction OU *
II-3-c : Produit logique : fonction ET *
II-3-d : Fonctions complexes *
III : Algèbre binaire : algèbre de BOOLE *
Négation (complémentation) *
Somme logique (ou inclusif) *
Produit logique (et) *
III-2 : Postulats de l’algèbre binaire *
III-3 : Théorèmes de l’algèbre binaire *
III-3 : Principe de dualité *
III-4 : Les fonctions binaires *
III-4-a : Définitions *
III-5 : Utilisation de l’algèbre binaire *
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.
II-3-a : Négation : fonction NON
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.
II-3-b : Somme logique : fonction OU
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 :
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.
II-3-c : Produit logique : fonction ET
Examinons la phrase : " j’irai me promener s’il fait plus de 25°C et s’il ne pleut pas. ".
Soient les propositions :
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 OU 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 :
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.
III : Algèbre binaire : algèbre de BOOLE
Boole, George (1815-1864), mathématicien et logicien anglais, qui développa l'algèbre booléenne. Autodidacte dans une large mesure, Boole fut nommé, en 1849, professeur de mathématiques au Queen's Collège de Cork, en Irlande. En 1854, Recherches sur les lois de la pensée, Boole décrivit un système algébrique qui devint plus tard connu sous le nom d'algèbre booléenne.
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 :
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 :
III-2 : Postulats de l’algèbre binaire
On peut montrer que l’ensemble E muni des lois (+,.) satisfait aux propriétés suivantes, quels que soient A et B appartenant à E :
Somme (+) : OU |
Produit (.) : ET |
|
| Commutativité | A+B = B+A |
A.B = B.A |
| Identité | A+0 = A |
A.1 = A |
| Complémentarité | A+A = 1 |
A.A = 0 |
| Distributivité | A+(B.C) = (A+B).(A+C) |
A.(B+C)=(A.B)+(A.C) |
On dit alors que {E,+,.} est une algèbre, appelée algèbre binaire.
III-3 : Théorèmes de l’algèbre binaire
Les théorèmes suivant s’établissent à partir des postulats de l’algèbre binaire :
Somme (+) OU |
Produit (.) ET |
|
| Idempotence | A+A=A |
A.A=A |
| Elément neutre | A+1=1 |
A.0=0 |
| Absorbtion | A+(A.B)=A |
A.(A+B)=A |
| Associativité | (A+B)+C=A+(B+C) |
(A.B).C=A.(B.C) |
| De Morgan | A+B=A.B |
A.B=A+B |
| involution | A=A |
|
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 élements ‘0’ et ‘1’.
Le dual de tout théorème d’algèbre binaire est un théorème d’algèbre binaire.
III-4 : Les fonctions binaires
Soit une fonction f de E3 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 :
| (0,0,0) | (0,0,1) | (0,1,0) | (0,1,1) |
| (1,0,0) | (1,0,1) | (1,1,0) | (1,1,1) |
Elles sont au nombre de 8 (23).
Pour un multiplet de n variables (n-uplet) il y a 2n 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.
III-4-b : Expression algébrique
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 :
S=f(C,B,A)=((C.B)+A).((C.A)+B)
III-5 : Utilisation de l’algèbre binaire
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 :
Propositions logiques |
Algèbre binaire |
FAUX |
0 |
VRAI |
1 |
Proposition (P) |
Variable (A) |
Négation (NON P) |
Complément (A) |
Somme (P1 OU P2) |
Somme (A+B) |
Produit (P1 ET P2) |
Produit (A.B) |
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.