Représentation des booléens
Définition : Booléens
Se dit d'une variable susceptible de prendre deux valeurs s'excluant mutuellement :
Vrai / Faux
1 / 0
(source : https:larousse.fr/dictionnaires/)
Le nom est issu des théories du mathématicien, philosophe britannique Georges Boole. Il est le créateur de la logique moderne fondée sur structure algébrique et sémantiques : variables, opérateurs et fonctions.
Complément : Cas des mathématiques
En mathématiques une proposition peut être considérée comme un variable booléenne.
Une proposition mathématique est un énoncé déclaratif dont on peut dire s’il est vrai (valeur 1) ou s’il est faux (valeur 0).
Exemple : Exemple en Python
a=True
type(a)
boolb=(2==3)
bFalsetype(b)
boolc=(5<=10)
cTruetype(c)
boolFondamental :
Les circuits des ordinateurs sont fabriqués à partir de portes logiques élémentaires, elles-mêmes construites à partir de transistors où les valeurs booléennes 0 et 1 sont matérialisées par des courants électriques. Les portes logiques permettent de construire des fonctions booléennes arbitraires, telles que des décodeurs ou des additionneurs. Le langage Python permet d'appliquer des opérations bit-à bit sur les représentations en base 2 des entiers.
Remarque : Nota Bene
La notion de portes logiques sera abordée dans le cours sur l'architecture de l'ordinateur.
Les fonctions booléennes élémentaires
Définition :
Une fonction logique est une fonction qui prend un ou plusieurs bits en entrée et qui produit un unique bit en sortie.
Définition : La fonction élémentaire NOT ou NON \(\lnot (x)\)
Elle n'a qu'un seul bit en entrée (x) et son unique bit en sortie \(\lnot (x)\) vaut 1 quand l'entrée vaut 0 et inversement.
la fonction NOT est la négation de x.
Définition : Table logique ou de vérité
Pour représenter le calcul réalisé par cette fonction logique, on utilise une table dit logique ou de vérité qui relie les valeurs de sortie avec les valeurs d'entrées.
Fondamental : Table logique de la fonction NOT
NOT | |
|---|---|
x | \(\lnot(x)\) |
0 1 | |
Méthode : La fonction not en langage Python
for p in (True , False) :
print (p, not(p))
Exemple : Situation en algorithmique
activer désactiver un son, un bouton
Les nombres non nuls : if x !=0
Définition : La fonction AND ou ET
Cette fonction a deux valeurs en entrée et retourne vrai quand les deux valeurs sont vraies et faux dans tous les autres cas.
La fonction AND est la conjonction de x et y.
Fondamental : Table logique de la fonction AND
AND | ||
|---|---|---|
x | y | \(\land (x,y)\) |
0 1 0 1 | 0 0 1 1 | |
Méthode : La fonction AND en langage Python
for p in (True , False ) :
for q in (True , False ) :
print (p, q, p and q)
Exemple : situation en algorithmique
tester si x appartient à ]-2 ;3[
if (x>-2) and (x<3) :
Définition : La fonction OR, OU
Cette fonction a deux valeurs en entrée et retourne vrai quand au moins l'une des deux valeurs est vraie et faux sinon.
La fonction OU est aussi appelée disjonction de x et y.
Exemple : De la vie courante
Ce médicament peut provoquer des troubles de l’équilibre ou de la vue.
Fondamental : Table logique de la fonction OR
OR | ||
|---|---|---|
x | y | \(\lor (x,y)\) |
0 1 0 1 | 0 0 1 1 | |
Méthode : La fonction OR en langage Python
for p in (True , False ) :
for q in (True , False ) :
print (p, q, p or q)
Exemple : situation en algorithmique :
tester si x appartient à \(]-\infty ;-3[ U ]3 ; + \infty[\)
if (x<-3) or (x>3) :
sqrt ({x**2-9)
Autres fonctions booléennes
Fondamental :
Les trois fonctions booléennes élémentaires : \(\lnot(x)\), \(\land (x,y)\), \(\lor (x,y)\) forment une base complète pour la définition des autres fonctions booléennes : toute fonction booléenne est définie par une combinaison de ces trois fonctions.
Table de vérité d'une fonction booléenne
Plus généralement la table de vérité d'une fonction booléenne de n bits en entrée contiendra 2^n ligne correspondant aux 2^n combinaisons possibles des entrées.
Sur les 3 premières fonctions élémentaires on a respectivement 2, 4 et 4 lignes.
Sur 3 entrées on aura 8 lignes :
x | y | z | f(x,y,z) |
|---|---|---|---|
0 0 0 0 1 1 1 1 | 0 0 1 1 0 0 1 1 | 0 1 0 1 0 1 0 1 |
Exemple : La fonction XOR , OU exclusif
La fonction OU exclusif est un opérateur binaire noté \(x \oplus y\). Il correspond à l'utilisation du "ou" dans le langage courant. Comme le cas de la carte d'un restaurant où il est indiqué fromage ou dessert. En fait les deux sont exclusifs d'un de l'autre car peut prendre soit l'un soit l'autre mais pas les deux.
Fondamental : Table logiques de la fonction XOR
XOR | ||
|---|---|---|
x | y | \(x \oplus y\) |
0 1 0 1 | 0 0 1 1 | 0 1 1 0 |
Complément : La fonction XOR comme combinaison de fonction élémentaires
Vérifier les égalités suivantes à l'aide d'une table de vérité.
\(p \oplus q = (p \lor q) \land \lnot( p \land q)\)
\(p \oplus q = (p \land \lnot q) \lor ( \lnot p \land q)\)
Exemple :
Écrire en Python une fonction xor(x,y) qui réalise la fonction booléenne du même nom sur les booléens.
def xor(x,y) :
return (x and not y) or (not x and y)
Exemple :
Définir une fonction booléenne f sur deux variables x et y qui vaut 1 si et seulement si les deux variables ont la même valeur (qu'elle soit 0 ou 1), en utilisant les opérations NON ET OU ou OU exclusif. Donner sa table de vérité.
\(f(x,y) = -(x \oplus y)\) ou \(f(x,y) = (x \land y ) \lor (-x \land -y)\)
avec la table de vérité suivante :
x | y | f(x,y) |
|---|---|---|
0 0 1 1 | 0 1 0 1 | 1 0 0 1 |
Exemple : Application : chiffrement à clé
Voici un exemple numérique de la méthode précédente :
M = 0110101011010100 (message en clair)
K = 0101011011100110 (la clé ; à garder secrète bien évidemment)
Convenons que le symbole ⊕ représente ici l'application de l'opérateur XOR à chacun des bits
Pour chiffrer, il faut utiliser la table de vérité: "M" est votre message et "K" représente la clé secrète.
Donc: M ⊕ K = C. Le "C" représente le message chiffré:
Chiffrement : C = M ⊕ K = 0011110000110010 (message chiffré)
Déchiffrement : M = C ⊕ K = 0110101011010100 (message déchiffré)
Les fonctions élémentaires avec Python
Python dispose d'opérateurs qui agissent directement sur les nombres au niveau des bits. Ces opérateurs sont appelés opérateurs bit-à-bit ou bitwise en anglais.
& réalise un et logique entres les bits de deux nombres.
| réalise un ou logique
^ réalise un ou exclusif
~ réalise le complément à 1 en inversant les bits d'un nombre.
>> et << sont des opérateurs de décalage prenant deux paramètres : le nombre à décaler et le nombre de positions à décaler. Ces opérations sont efficaces pour multiplier ou diviser un nombre par une puissance de 2.
>>>bin(0b0101 & 0b1100)
'0b100'>>> bin(0b0101|0b1100)
'0b1101'>>> bin(0b0101^0b1100)
'0b1001'>>> bin(0b1100>>2)
'0b11'>>> bin(0b1100<<3)
'0b1100000'Exemple : Application : chiffrement à clé
Écrire le programme Python sous la forme d'une fonction qui chiffre un message à l'aide d'une clé comme indiqué dans l'exemple de la partie précédente.
Elle prendra en paramètre le message et la clé sous forme de nombres binaires (on prendra une clé de la même longueur que le message et qui renvoie le message codé sous forme binaire.
fonctions avancées.
codeur / décodeur
Ces fonctions sont utiles en informatique pour passer d'un numéro à un nombre et inversement.
Codeur : une touche du clavier à son codage ASCII
Décodeur : un nombre à un numéro de programme.
Fondamental : Décodeur
Prenons un compteur de 2 bits (4 nombres) il peut générer 4 sorties correspondant à 4 programmes (prélavage, lavage rinçage et essorage sur une machine à laver le linge par exemple)
Sa table logique sera :
\(e_1\) | \(e_0\) | \(s_0\) | \(s_1\) | \(s_2\) | \(s_3\) |
|---|---|---|---|---|---|
0 0 1 1 | 0 1 0 1 | 1 0 0 0 | 0 1 0 0 | 0 0 1 0 | 0 0 0 1 |
Le décodeur peut aussi se définir à partir des fonctions élémentaires :
\(s_0 = \lnot e_0 \land \lnot e_1\) ou \(s_0 = \lnot(e_0 \lor \lnot e_1)\)
\(s_1 = \lnot e_0 \land e_1\)
\(s_2 = e_0 \land \lnot e_1\)
\(s_3 = e_0 \land e_1\)
Un décodeur n bits possédera \(2^n\) sorties. Les n bits en entrées sont utilisés pour :
mettre à 1 la sortie dont le numéro est égal au nombre codé en binaire par les entrées.
mettre les autres sorties à 0
Additionneur
C'est une fonction de base en informatique : l'addition de deux nombres binaires.
Pour additionner des nombres binaires de n bits, il faut déjà un additionneur 1 bit qui réalise l'addition de deux nombres de 1 bit. Lui même est construit à partir de ce qu'on appelle un demi-additionneur.
Fondamental : Demi-additionneur
Il prend en entrée les deux bits \(e_0\) et \(e_1\) et il envoie sur une sortie s la somme \(e_0 + e_1\) et sur un autre sortie c la retenue éventuelle.
Voici la table logique de ce demi-additionneur.
entrées | sorties | ||
|---|---|---|---|
\(e_0\) | \(e_1\) | s | c |
0 0 1 1 | 0 1 0 1 | 0 1 1 0 | 0 0 0 1 |
Donner les deux fonctions booléennes correspondantes respectivement à s et c.
\(s= e_0 \oplus e_1\)
\(c= e_0 \land e_1\)
Additionneur un bit
Pour réaliser l'additionneur 1 bit, il faut prendre en compte la retenue éventuelle \(c_0\) de l'addition des deux bits précédents. Ainsi un additionneur complet prend en entrée les deux bits \(e_0 + e_1\) et la retenue noté \(c_0\) de l'addition précédente. En revanche les sorties sont inchangées.
entrées | sorties | |||
|---|---|---|---|---|
\(e_0\) | \(e_1\) | \(c_0\) | s | c |
0 0 0 0 1 1 1 1 | 0 0 1 1 0 0 1 1 | 0 1 0 1 0 1 0 1 | 0 1 1 0 1 0 0 1 | 0 0 0 1 0 1 1 1 |
Donner les deux fonctions booléennes correspondantes :
à s en fonction de \(e_0, e_1, c_0\)
et c en fonction de \(e_0, e_1, c_0\)
\(s= e_0 \oplus e_1 \oplus c_0\)
\(c= (e_0 \land e_1) \lor ((e_0 \oplus e_1)\land c_0)\)
Méthode :
L'additionneur 1 bit est constitué électroniquement par deux demi-additionneurs :
Le premier demi-additionneur prend en entrée \(e_0 \)et \(e_1\) et renvoie un \(s_0\) et un \(c_1\).
Le deuxième demi-additionneur prend en entrée \(s_0\) et \(c_0\) et renvoie donc \(s\) et \(c_2\).
Enfin la sortie \(c\), retenue finale vaut 1 si \(c_1\) ou \(c_2\) vaut 1.