Calculs Booléens

Booléens

 

Un booléen est une variable informatique à deux états logiques : Vrai ou Faux, ou bien 1 ou 0. Le calcul booléen fut inventé par George Boole en XIXe siècle.

 

Exemple :

La proposition $1 > 2$ est une proposition fausse. 
La proposition $1 neq 2$ est une proposition vraie. 

D’une manière générale en informatique, les opérateurs de comparaison retournent une valeur booléenne. Les variables booléennes permettent de formaliser les raisonnements logiques pratiqués en informatique.

 

Les opérateurs logiques

 

Soient $x$ et $y$ deux propositions,
Il est possible de définir différents opérateurs logiques :

la négation de $x$, noté $overline{x}$, que l’on appelle not $x$. Cette proposition prend la valeur logique opposée à celle de $x$

Exemple :

Lorsque $x$ est fausse, $overline{x}$ est vraie. 
Lorsque $x$ est vraie, $overline{x}$ est fausse. 

 

la conjonction de $x$ et $y$, notée $x$ ET $y$ ou $x.y$. Cette proposition est vraie uniquement lorsque $x$ et $y$ sont simultanément vraies.

Exemple :

Si $x$ est fausse et $y$ est vraie, alors $x.y$ est fausse.

 

la disjonction de $x$ et $y$ que l’on note $x$ OU $y$, $x + y$. Il est aussi possible de définir cet opérateur à l’aide de la négation et de la conjonction $overline{overline{x}.overline{y}}$.

Exemples :

Considérons que $x$ et $y$ sont fausses, alors $overline{x}$ et $overline{y}$ sont vraies, donc $overline{x}.overline{y}$ est vraie. Or la négation d’une proposition vraie est une proposition fausse, donc $overline{overline{x}.overline{y}}$ est fausse. Ainsi, $x+y$ est fausse.
Considérons que $x$ est vraie et que $y$ est fausse, alors $overline{x}$ est fausse et $overline{y}$ est vraie, donc $overline{x}.overline{y}$ est fausse. Or la négation d’une proposition fausse est une proposition vraie, donc $overline{overline{x}.overline{y}}$ est vraie. Ainsi, $x+y$ est vraie.
On fera cependant attention que $+$ n’a pas toujours le sens d’une addition au sens mathématique du terme.
En effet, si $x$ et $y$ sont vraies et valent donc $1$, alors $x+y$ est vraie aussi et vaut $1$.
De plus, on peut remarquer que le OU n’a pas toujours le même sens qu’en français. Il s’agit en effet d’un OU inclusif : quand $x$ et $y$ sont toutes deux vraies, $x$ OU $y$ est vraie. 
On retiendra que la disjonction n’est fausse uniquement lorsque $x$ et $y$ sont fausses.

 

– l’implication, que l’on note $x Rightarrow y$, qui correspond par définition à la proposition $overline{x}+y$.

Exemple :
Supposons que $x$ et $y$ sont fausses, alors $overline{x}$ est vraie donc $overline{x}+y$ est vraie. Ainsi, $x Rightarrow y$ est vraie.
On remarque que dès lors que l’hypothèse initiale est fausse, l’assertion totale est juste. On retiendra que l’implication est toujours vraie sauf lorsque $x$ est vraie et $y$ fausse. 

 

– la disjonction exclusive de $x$ et $y$, que l’on note $x oplus y$, qui correspond au OU exclusif en français : les deux propositions ne peuvent pas être vraies en même temps.

Exemple :

Supposons $x$ vraie et $y$ fausse, alors $xoplus y$ est vraie.
Supposons $x$  et $y$ vraies, alors $xoplus y$ est fausse.

 

On regroupe l’ensemble des résultats précédents dans la table de vérité suivante 

$x$ $y$ $overline{x}$ $x.y$ $x+y$ $x Rightarrow y$ $xoplus y$
0 0 1 0 0 1 0
0 1 1 0 1 1 1
1 0 0 0 1 0 1
1 1 0 1 1 1 0

Exemple :

On se propose ici d’appliquer à un exemple concret les différents opérateurs décrits précédemment.
Soient $x$ la proposition “je suis sec” et $y$ la proposition “je suis mouillé”,
On peut remarquer que si je ne suis pas sec, alors je suis mouillé, ce qui signifie que $y$ est la négation de $x$ et réciproquement, ce que l’on écrit en mathématiques $overline{x} = y$ et $overline{y} = x$.
La proposition “je suis sec OU je suis mouillé” est vraie car toute personne est forcément dans l’un des deux états, ainsi $x+y =1$. 
La proposition “je suis sec ET je suis mouillé” est fausse car toute personne ne peut pas être dans le même état simultanément, ainsi $x.y =0$. 

 

Plus généralement, on peut remarquer que :

– la proposition $x$ ou $overline{x}$ est fausse, c’est à dire $x.overline{x} = 0$ : c’est ce qu’on appelle le principe de non-contradiction. 
– la proposition $x$ et $overline{x}$ est vraie, c’est à dire $x + overline{x} = 1$ : c’est ce qu’on appelle le principe du tiers exclu.
– la négation de la négation prend les mêmes valeurs logiques que la proposition initiale.
– l’implication $x Rightarrow y$ prend les mêmes valeurs logiques que l’implication $overline{y} Rightarrow overline{x}$ : c’est la contraposée. 
En effet, supposons par exemple que l’assertion “s’il pleut alors j’ai mon parapluie” est vraie. Alors, “si je n’ai pas mon parapluie alors il ne pleut pas” est vraie car si il avait plu j’aurai eu mon parapluie. 
– la négation de la disjonction de $x$ ou $y$ prend les mêmes valeurs logiques que la conjonction de $overline{x}$ et $overline{y}$. On note donc : $overline{x+y} = overline{x} . overline{y}$.
– de même, la négation de la conjonction de $x$ et $y$ prend les mêmes valeurs logiques que la disjonction de $overline{x}$ ou $overline{y}$. On note donc : $overline{x.y} = overline{x} + overline{y}$.
Enfin, on s’intéresse à la négation de l’implication $x Rightarrow y$, qui vaut par définition $overline{overline{x}+y}$. D’après une propriété précédente, $overline{overline{x}+y} = overline{overline{x}}.overline{y}$. Enfin, $overline{overline{x}} = x$ donc $overline{overline{x}}.overline{y} = x.overline{y}$

 

Les fonctions booléennes peuvent être réalisées par des circuits électroniques. 

booléens_1

 

Tu veux réviser 2x plus vite ?

Découvre les offres des Bons Profs avec :