I : Introduction à la logique *
I-2 : Nécessité dun 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 lalgèbre binaire *
III-3 : Théorèmes de lalgèbre binaire *
III-3 : Principe de dualité *
III-4 : Les fonctions binaires *
III-4-a : Définitions *
III-5 : Utilisation de lalgè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 quelquun marche sur le sol. Linformation provenant de ce capteur est donc soit VRAIE (quelquun marche) ou FAUSSE (personne ne marche). Le système ne possède donc que deux états : on dit quil est binaire.
Nombreux sont les systèmes tels que celui décrit ci-dessus qui produisent ou utilisent une information binaire.
Dautre part, les outils de traitement automatique de linformation, (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 dun outil mathématique approprié.
Si lon reprend lexemple de lalarme, 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 linformation dentrée, et " police alertée " pour linformation de sortie. Ces deux propositions ne peuvent être que VRAI ou FAUX, mais pas les deux à la fois.
Le système (ici lalarme) logique consiste à produire une ou plus information(s) de sortie en fonction dune ou plus information(s) dentré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 ").
Laction 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 dentrée et celles de sortie.
Dans le cas de lalarme, 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 " jirai me promener " et " il pleut ". Le système doit déterminer quand sortir, la logique du problème est : " jirai me promener sil ne pleut pas ". On peut donc dire que " jirai 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 sarrê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 sappelle 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 : " jirai me promener sil fait plus de 25°C et sil 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 sappelle produit logique ou fonction ET.
Il arrive que lon ait besoin de la conjonction de plusieurs de ces fonctions :
Etudions le cas : " jirai me promener sil fait plus de 25°C et quil 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 dun 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.
Lalgè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 lensemble 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 :
Cest une loi unaire (elle ne concerne quune seule variable) notée " barre " telle que :
Cest 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 :
Cest 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 lalgèbre binaire
On peut montrer que lensemble 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 lalgèbre binaire
Les théorèmes suivant sétablissent à partir des postulats de lalgè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 dun énoncé quelconque dun théorème de lalgèbre binaire est obtenu en permutant les opérateurs + et . et les élements 0 et 1.
Le dual de tout théorème dalgèbre binaire est un théorème dalgèbre binaire.
III-4 : Les fonctions binaires
Soit une fonction f de E3 dans E :
Cest une fonction binaire de trois variables.
(C,B,A) est un triplet ordonné.
La connaissance de la fonction f permet dassocier 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 sexprimer à partir des variables binaires dentrée (mot binaire dentrée) en nutilisant 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 lalgèbre binaire
Lalgèbre binaire peut se substituer à lutilisation des propositions logiques, et on lemploie chaque fois que la complexité des systèmes logiques lexige.
La transposition des propositions logiques à lalgè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 lalgèbre binaire permettront une approche plus simple et systématique des problèmes logiques complexes.