Algèbre de boole (logique)

Algèbre de boole (logique)

Algèbre de Boole (logique)

Algèbre de Boole des valeurs de vérité

Fonctions logiques

Arbre d'expression

Voir aussi

Lien externe

Dictionnaires et Encyclopédies sur 'Academic'

Conjonction

Disjonction

Négation

Propriétés

Fonctions logiques fondamentales

Fonctions logiques composées

Exemple de fonctions logiques à trois ou quatre variables

Minimisation d'une expression

Regardez d'autres dictionnaires:

Associativité

Commutativité

Distributivité

Idempotence

Élément neutre

Élément nullité

Absorption

Simplification

Redondance

Complémentarité

Structure

Priorité

Théorème de De Morgan

Disjonction exclusive

Équivalence

Implication

Inhibition

Fonction logique à trois variables

Fonction logique à quatre variables

Pour les articles homonymes, voir Algèbre de Boole.

L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l'électronique qui s'intéresse aux opérations et aux fonctions sur les variables logiques. Plus spécifiquement, l'algèbre booléenne permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs du calcul des propositions. Elle fut initiée par le mathématicien britannique du milieu du XIX^e siècle George Boole.

Aujourd'hui, l'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques. Elle fut utilisée la première fois pour les circuits de commutation téléphoniques par Claude Shannon.

L'algèbre de Boole des fonctions logiques permet de modéliser des raisonnements logiques, en exprimant un « état » en fonction de conditions. Par exemple :

Communication = Émetteur ET Récepteur

Communication est « VRAI » si Émetteur actif ET Récepteur actif (c'est une fonction logique dépendant des variables Émetteur et Récepteur)

Décrocher = ( Décision de répondre ET Sonnerie ) OU décision d'appeler

Décrocher est « VRAI » si on entend la sonnerie ET que l'on décide de répondre OU si l'on décide d'appeler.

L'algèbre de Boole étant un domaine commun à trois disciplines, on rencontre des notations différentes pour désigner un même objet. Dans le reste de l'article, on indiquera les diverses notations, mais on en privilégiera une pour conserver une certaine homogénéité.

On appelle B l'ensemble constitué de deux éléments appelés valeurs de vérité {VRAI, FAUX}. Cet ensemble est aussi noté

B = {1, 0}
B = $\{\top , \perp \}$ .

On privilégiera dans la suite la notation B = {1, 0}.

Sur cet ensemble on peut définir deux lois (ou opérations ou foncteurs), les lois ET et OU et une transformation appelée complémentaire, inversion ou contraire.

Articles connexes : Fonction ET et Conjonction logique.

Elle est définie de la manière suivante : a ET b est VRAI si et seulement si a est VRAI et b est VRAI. Cette loi est aussi notée

$\cdot \,$
$\wedge$
« & » ou « && » dans quelques langages de programmation (Perl, C, PHP...)
« AND » dans certains langages de programmation (Ada, Pascal, Python, PHP ...)
« ∧ » dans quelques notations algébriques, ou en APL

On privilégiera dans la suite la notation $\cdot \,$

On peut construire la table de cette loi (comme une table d'addition ou de multiplication de notre enfance) mais on ne la confondra pas avec une table de vérité.

Table de la loi ET
b\a	0	1
0	0	0
1	0	1

Articles connexes : Fonction OU et Disjonction logique.

Elle est définie de la manière suivante : a OU b est VRAI si et seulement si a est VRAI ou b est VRAI. (si a est vrai et que b est vrai aussi, alors a OU b est vrai.) Cette loi est aussi notée

$+ \,$
$\vee$
« | » ou « || » dans quelques langages de programmation
« OR » dans certains langages de programmation
« ∨ » dans quelques notations algébriques ou en APL.
« < » très rarement.

On privilégiera dans la suite la notation $+ \,$ mais on prendra garde que cette loi n'a pas de rapport avec l'addition que l'on connaît.

Cependant, en mathématiques et en logique mathématique, on n'utilise pas cette notation pour le ou inclusif dans les algèbres de Boole, à cause de la confusion avec l'addition des anneaux de Boole, Z/2Z, pour ce qui est du présent article. Dans ce cas l'addition correspond au ou exclusif.

Table de la loi OU
b\a	0	1
0	0	1
1	1	1

Articles connexes : Fonction NON et Négation logique.

Le contraire de "a" est VRAI si et seulement si a est FAUX. Le contraire de a est noté

non-a
$\bar{a}$
$\neg (a)$
« ! » dans quelques langages de programmation (C, C++,...)
« NOT » dans certains langages de programmation (ASM,...)
« <> » dans certains langages de programmation (Basic,...)
« ~ » dans quelques notations algébriques ou en APL.

On privilégiera dans la suite la notation $\bar{a}$ .

On obtient alors $\bar{0}=1$ et $\bar{1}=0$

Comme avec les opérations habituelles, certaines parenthèses sont inutiles:
$(a + b) + c = a + (b + c) = a + b + c$
$(a . b). c = a .(b . c) = a . b . c$

L'ordre est sans importance:
$a + b = b + a$
$a . b = b . a$

Comme avec les opérations habituelles, il est possible de distribuer :
$a .(b + c) = a . b + a . c$
Attention : comportement différent par rapport aux opérateurs + et * habituels :
$a + (b . c) = (a + b).(a + c)$

$a + a + a + [...] + a = a$
$a . a . a .[...]. a = a$

$a + 0 = a$
$a .1 = a$

$0. a = 0$
$1 + a = 1$

$a + a . b = a$
$a .(a + b) = a$

$a + \overline{a} . b = a + b$
$a . ( \overline{a} + b ) = a . b$

$a . b + \overline{a} . c = a . b + \overline{a} . c + b . c$

$a = \overline{\overline{a}}$

(« La lumière est allumée » = « la lumière n'est pas non allumée »)

$a + \overline{a} = 1$

(« VRAI » SI lumière_allumée OU SI lumière_non_allumée → c'est toujours le cas → vrai dans tous les cas → toujours VRAI, donc =1)

$a . \overline{a} = 0$

(« VRAI » SI lumière_allumée ET SI lumière_non_allumée → impossible → faux dans tous les cas → toujours FAUX donc =0)

On retrouve alors toutes les propriétés qui confèrent à B une structure d'algèbre de Boole

Pour faciliter leur compréhension, il a été décidé que ces opérations seraient soumises aux mêmes règles que les opérations « de tous les jours », la fonction ET (multiplication logique) est ainsi prioritaire par rapport à la fonction OU (somme logique) ; on peut, pour s'aider, placer des parenthèses dans les opérations.

Exemple :

a = 0; b = 1; c = 1

On cherche

a . b + c = ???

D'abord on calcule

a . b

a . b = 0.1

0.1 = 0

Puis, on calcule

0 + c

0 + c = c

c = 1

Le résultat final est donc:

a . b + c = 1

Fonction

Table de vérité/Table de fonctionnement

$\overline{ a + b } = \overline{a} . \overline{b}$

Dans les deux cas, l'expression ne sera VRAIE que si a et b sont fausses.

Fonction

Table de vérité/Table de fonctionnement

$\overline{ a . b } = \overline{a} + \overline{b}$

Dans les deux cas, l'expression ne sera FAUSSE que si a et b sont vraies.

Article détaillé : Fonction logique.

Mathématiquement, une fonction logique ou opérateur logique est une application de Bⁿ dans B.

En électronique, une fonction logique est une boîte noire qui reçoit en entrée un certain nombre de variables logiques et qui rend en sortie une variable logique dépendant des variables d'entrée. L'article fonction logique précise comment construire les boîtes noires de quelques fonctions fondamentales.

Une table de vérité permet de préciser l'état de la sortie en fonction des états des entrées.

On démontre que toute fonction logique peut se décrire à l'aide des trois opérations de base.

$+\,$
$\cdot\,$
$\bar{}\,$

Elles sont issues des trois opérations de base et définissent alors

une fonction de B dans B : le complémentaire ou inversion
deux fonctions de B² dans B qui sont la somme (ou OU) et le produit (ou ET)

Table de vérité de l'inverse
a	$\bar a$
0	1
1	0

Table de vérité de la somme
a	b	a $+ \,$ b
0	0	0
0	1	1
1	0	1
1	1	1

Table de vérité du produit
a	b	a $\cdot \,$ b
0	0	0
0	1	0
1	0	0
1	1	1

Ce sont les fonctions logiques à deux variables. Parmi celles-ci, on en dénombre certaines suffisamment intéressantes pour qu'on leur donne un nom.

L'équivalence (notée EQV) est vraie si les deux entrées ont la même valeur et fausse sinon. Elle est appelée aussi «non-ou exclusif » Elle se compose comme suit :

$a\ \operatorname{EQV}\ b = \overline{(a+b)}+(a.b)$

On peut aussi dire que :

$a\ \operatorname{EQV}\ b = \overline{a\ \operatorname{XOR}\ b}$

Table de vérité de EQV
a	b	a $\Leftrightarrow$ b
0	0	1
0	1	0
1	0	0
1	1	1

Il arrive que l'équivalence soit notée par le signe $\Leftrightarrow$ , bien que ce choix ne soit pas recommandé compte-tenu des autres sens possibles attachés à ce signe.

Elle peut aussi être notée "==" dans certains langages (C, C++, PHP…).

L'implication (notée IMP) s'écrit de la manière suivante :

$a\ \operatorname{IMP}\ b = \overline{a}+b$

Cette opération n'est pas commutative. a est une condition suffisante pour b, qui, elle, est une condition nécessaire pour a.

Mais $a\ \operatorname{IMP}\ b = \overline{b}\ \operatorname{IMP}\ \overline{a}$

Illustration : de l'affirmation

"S'il fait beau, j'irai me promener."

on peut conclure

"Si je ne vais pas me promener, il ne fait pas beau."

mais on ne peut pas en déduire

"S'il ne fait pas beau, je ne vais pas me promener."

car on ne sait pas si je n'aime pas me promener aussi sous la pluie.

Table de vérité de IMP
a	b	a $\Rightarrow$ b
0	0	1
0	1	1
1	0	0
1	1	1

L'inhibition (notée INH) se compose comme suit :

$a\ \operatorname{INH}\ b = a.\overline{b}$

Cette opération n'est pas commutative.

Table de vérité de INH
a	b	$a.\overline{b}$
0	0	0
0	1	0
1	0	1
1	1	0

Si l'on reprend l'exemple du téléphone, on se trouve en présence de 3 variables :

a = "le téléphone sonne"
b = "on a envie de répondre"
c = "on a envie d'appeler quelqu'un"

la variable d = "on décroche" est fonction logique des 3 précédentes. On écrira que

d = a . b + c

car on décroche quand ça sonne et qu'on a envie de répondre ou quand on a envie d'appeler quelqu'un.

La table de vérité de cette fonction d est alors la suivante :

Table de vérité de décrocher
a	b	c	d
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

L'observation de la table montre que notre analyse première comportait une situation absurde: le téléphone sonne, on a envie d'appeler quelqu'un, mais on n'a pas envie de répondre et on décroche quand même. Cela n'est certainement pas le comportement souhaité, il est donc préférable de modifier la fonction décrocher de façon à ce qu'on obtienne le tableau suivant:

Table de vérité de décrocher2
a	b	c	d2
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

En lisant le procédé de la simplification des expressions ci-dessous, vous verrez que la formule de décrocher2 correspond à $d2 =\bar a.c + a.b$ .

Un bon élève s'interroge s'il est sage de sortir un soir. Il doit décider en fonction de quatre propositions :

a = il a assez d'argent
b = il a fini ses devoirs
c = le transport en commun est en grève
d = l'auto de son père est disponible

Cet élève pourra sortir si :

il a assez d'argent, a = vrai
il a fini ses devoirs, donc b = vrai
le transport en commun n'est pas en grève, donc c = faux
ou si l'auto de son père est disponible, donc d = vrai

Donc l'expression logique de sortir en fonction de l'état des variables a, b, c et d ; et elle peut s'écrire ainsi :

Sortir = $a.b.({\bar c}+d)$

Une fonction logique peut être déterminée

soit sous forme d'une expression faisant intervenir les 3 opérations ( $+\,$ , $\cdot\,$ , $\bar{}\,$ )
soit sous forme de sa table de vérité. Dans ce cas il sera toujours possible d'écrire cette fonction comme une somme de produits.

Exemple: Dans l'exemple de "téléphoner2", on s'aperçoit que le résultat est à 1 quand (a, b, c) = (0, 0, 1) ou (0, 1, 1) ou (1, 1, 0) ou (1, 1, 1).

Cela permet de définir d2 par $d2 =\bar a.\bar b.c + \bar a.b.c + a.b.\bar c + a.b.c$

Il est alors intéressant de trouver une expression minimisant le nombre de termes et le nombre de lettres dans chaque terme. C'est l'objectif de certaines techniques comme la méthode de Quine-Mc Cluskey, les diagrammes de Karnaugh…

Exemple (suite) : la somme précédente peut être réduite en

$d2 =\bar a.c + a.b$

par factorisation des deux premiers termes par $\bar a.c$ et factorisation des deux derniers termes par $a.b \,$

Les expressions logiques sont souvent représentées en informatique sous forme d'arborescence. Cette dernière comporte un sommet (la racine en fait) auquel sont rattachés différents sous-arbres (ou branches). Les bifurcations sont des sommets internes. Le nombre de sous-arbres reliés à un même sommet est appelé arité. Les sommets sans issue sont appelés feuilles. Chaque sommet interne est identifié par un opérateur booléen alors que les feuilles représentent les variables qui subissent ces opérations.

Wikibooks propose un ouvrage abordant ce sujet : la logique combinatoire.

Wikibooks propose un ouvrage abordant ce sujet : la logique séquentielle.

Fonction logique
Calcul des propositions
Système de numération
Électronique numérique
Neurone
George Boole
Opérations sur les bits
Le wikilivre architecture des ordinateurs : comment synthétiser des portes logiques par assemblage de transistors CMOS ?

Opérations binaires

Numériques	En ensemble ordonné	Structurelles	Autres

Élémentaires $+$ Addition $-$ Soustraction $\times$ Multiplication $\div$ Division $\hat{}$ Puissance Arithmétiques $div$ Quotient euclidien $\mod$ Reste euclidien $pgcd$ PGCD $ppcm$ PPCM Combinatoires $()$ Coefficient binomial $A$ Arrangement	Ensembles de parties $\cup$ Union $\backslash$ Complémentation $\cap$ Intersection $Δ$ Différence symétrique Ordre total $min$ Minimum $max$ Maximum Treillis $\wedge$ Borne inférieure $\vee$ Borne supérieure	Ensembles $\times$ Produit cartésien $\dot{\cup}$ Somme disjointe $\hat{}$ Puissance ensembliste Groupes $\oplus$ Somme directe $\ast$ Produit libre $\wr$ Produit en couronne Modules $\otimes$ Produit tensoriel $Hom$ Homomorphisme $Tor$ Torsion $Ext$ Extension Arbres $\vee$ Enracinement Variétés connexes $\#$ Somme connexe Espaces pointés $\vee$ Bouquet $\wedge$ Smash produit $\ast$ Joint	Fonctionnelles $\circ$ Composition de fonctions $\ast$ Produit de convolution Vectorielles $\cdot$ Produit scalaire $\wedge$ Produit vectoriel Algébriques $[,]$ Crochet de Lie ${,}$ Crochet de Poisson $\wedge$ Produit extérieur Homologiques $\smile$ Cup produit $\cdot$ Produit d'intersection Séquentielles $+$ Concaténation

Logique booléenne : $\land$ ET (conjonction) • $\lor$ OU (disjonction) • $\oplus$ OU exclusif • $\Rightarrow$ IMP (implication) • $\Leftrightarrow$ EQV (équivalence)

Portail de la logique
Portail des mathématiques

Ce document provient de « Alg%C3%A8bre de Boole (logique) ».

Catégories : Algèbre | Fonction logique

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algèbre de boole (logique) de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Algebre de Boole (logique) — Algèbre de Boole (logique) Pour les articles homonymes, voir Algèbre de Boole. L algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l électronique qui s intéresse aux opérations et aux fonctions sur les… … Wikipédia en Français
Algèbre De Boole (Logique) — Pour les articles homonymes, voir Algèbre de Boole. L algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l électronique qui s intéresse aux opérations et aux fonctions sur les variables logiques. Plus… … Wikipédia en Français
Algèbre de Boole (logique) — Pour les articles homonymes, voir « Algèbre de Boole ». L algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l électronique qui s intéresse aux opérations et aux fonctions sur les variables… … Wikipédia en Français
Algebre de Boole (structure) — Algèbre de Boole (structure) Pour les articles homonymes, voir Algèbre de Boole. En mathématiques, une algèbre de Boole ou un treillis booléen est un type de structure algébrique. Sommaire 1 Définition … Wikipédia en Français
Algèbre De Boole (Structure) — Pour les articles homonymes, voir Algèbre de Boole. En mathématiques, une algèbre de Boole ou un treillis booléen est un type de structure algébrique. Sommaire 1 Définition … Wikipédia en Français
Algèbre de boole (structure) — Pour les articles homonymes, voir Algèbre de Boole. En mathématiques, une algèbre de Boole ou un treillis booléen est un type de structure algébrique. Sommaire 1 Définition … Wikipédia en Français
Algèbre de la logique — ● Algèbre de la logique théorie créée simultanément par Boole et De Morgan en 1847 et développée par Schröder à la fin du XIXe s. (Elle repose sur l idée que des formules algébriques peuvent exprimer des relations logiques entre des concepts [à… … Encyclopédie Universelle
Algebre de Boole — Algèbre de Boole Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Une algèbre de Boole est une structure algébrique utile en particulier en logique mathématique. En informatique et en électronique, l… … Wikipédia en Français
Algèbre De Boole — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Une algèbre de Boole est une structure algébrique utile en particulier en logique mathématique. En informatique et en électronique, l algèbre de Boole… … Wikipédia en Français
Algèbre de boole — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Une algèbre de Boole est une structure algébrique utile en particulier en logique mathématique. En informatique et en électronique, l algèbre de Boole… … Wikipédia en Français

$\overline{ a + b }$

$\overline{ a }$

$\overline{ b }$

$\overline{a} . \overline{b}$