Bool et binaire

sommaire

 
	Algèbre de bool
	Binaire
	Principes (base 2)
	Bases (base 2, 8, 10, 16)
	Calculs (addition, soustraction, opérateurs logiques ET, OU)

Algèbre de bool

L'algèbre de bool (ou booléene) est une technique de calcul logique avec des affirmations qui sont vraies ou fausse, 1 ou 0.
Les affirmations sont des conditions dont le résultat est binaire.
Exemples :

il pleut : le résultat est vrai ou faux.
il fait froid : le résultat est vrai ou faux.
5 est plus grand que 6 : le résultat est aussi vrai ou faux et pas autre chose (dans un espace euclidien ...).

Les conditions sont remplacées par des lettres comme les nombres en mathématique. Ainsi :

il pleut sera a et
il fait froid sera b.

Connaître l'algèbre de Bool est utile en programmation, pour déterminer les tests qui s'enchaînent

si ciel=bleu et température=chaud ou ciel=noir et … est traduit en binaire

Mais aussi pour des variables binaires :

capteur de ligne = 100 (4) = trop à gauche ; 010 (2) = centré ; 001(1) = trop à droite
état : 001=enregistré, 011 = enregistré+ vu, 111 = enregistré, vu et validé

Et surtout pour le réseau et la détermination des adresse IP, Masques associés, sous-réseaux, etc...

Calculs booléens

les calculs booléens représentent les choix que l'on peut effectuer.
On dispose de trois opérations : le ET (and), le OU (or) et la négation, l'inverse : NON.
Les affirmations avec lesquelles on fait les calculs n'ont que deux possibilités : VRAI ou FAUX. VRAI est représenté par 1 et FAUX par 0.

Opérateur NON booléen

Si a = vrai, NON(a) = faux.

Remarque : dans l'absolu, NON(a) n'est pas égal à "il fait beau" car il peut ne pas pleuvoir mais neiger, ou le temps peut être simplement nuageux. (snif!)

Opérateur ET booléen

Soit la demande suivante : j'ai vraiment envie de me promener et je suis plutôt motivé. Donc, je ne reste chez moi que s'il pleut et qu'il fait froid.
Exemple : si il pleut (a) je reste à la maison, si il ne pleut pas (NON(a)) je peux me promener. Voici les affirmations :

a = il pleut, dans ce cas, je reste à la maison, sinon je peux me promener.
b = il fait froid, dans ce cas, je reste à la maison et sinon je peux me promener. Il pleut ET il fait froid alors je reste chez moi => a ET b.

table de vérité :

a	b	a ET b
il ne pleut pas	il ne fait pas froid	je peux me promener
il pleut	il ne fait pas froid	je peux me promener
il ne pleut pas	il fait froid	je peux me promener
il pleut	il fait froid	je reste à la maison

Je ne reste à la maison que s'il pleut et qu'il fait froid.

Opérateur OU booléen

Soit la demande suivante : S'il fait beau ou s'il fait chaud, je mets un t-shirt.
Voici les affirmations :

a = il fait beau, je mets un t-shirt, sinon je mets autre chose (un ciré, une veste, une chemise ?).
b = il fait chaud, je mets un t-shirt et sinon je mets autre chose (un pull, une veste, un annorak ?).

table de vérité :

a	b	a OU b
il fait ne pas beau	il ne fait pas chaud	je mets autre chose
il fait ne pas beau	il fait chaud	je mets un t-shirt
il fait beau	il ne fait pas chaud	je mets un t-shirt
il fait beau	il fait chaud	je mets un t-shirt

Je mets un t-shirt dès lors qu'il fait beau ou qu'il fait chaud.

Table de vérité complète

Voici tous les cas des opérations logiques ET et OU et leur résultat (0= faux, 1= vrai) : ^Propositions^^Résultats ^^

a b a ET b a OU b NON(a ET b) NON(a OU b)

0 0 0 0 1 1

0 1 0 1 1 0

1 0 0 1 1 0

1 1 1 1 0 0

a	b	a ET b	a OU b	NON(a ET b)	NON(a OU b)
0	0	0	0	1	1
0	1	0	1	1	0
1	0	0	1	1	0
1	1	1	1	0	0

ET : si a et b = vraies, alors r = vrai ; r= faux dans tous les autres cas
OU : si a et b = faux, alors r = faux ; r= vrai dans tous les autres cas

équations booléennes remarquables

 
	a ET a = a
	a ET non(a) = faux
	a OU non(a) = vrai
 
	Commutativité de ET et OU : a ET b = b ET a ; a OU b = b OU a
	Priorité de ET sur OU : a ET b ou c = (a ET b) OU c
	Distributivité de ET sur OU : a ET (b ou c) = (a OU b) ET (a OU c)
 
	non (a ET b) = NON(a) OU NON(b)
	non (a OU b) = NON(a) ET NON(b)
 

On peut assimiler le comportement de ET et OU aux opérations décimales x et +.

Numération binaire, Pourquoi ?

Le binaire n'est pas important en soi. Mais il permet de mieux comprendre le fonctionnement des ordinateurs. Principalement il servira pour la compréhension de l'adressage IP mais aussi pour la définition des conditions dans les tests et boucles. Nous verrons ici :

la définition des bases de numération en mathématique (le retour)
une approche de l'algèbre de bool
la numération binaire de base
les conversions et leur usage en réseau
les calculs binaires avancés

Bases de numération

En informatique, on utilise plusieurs systèmes de base de numération :

la base dix, le système décimal,
la base 2, le binaire,
la base 8, système octal et
la base 16, hexadécimal.

Une base de numération défini le nombre de symboles différents permettant de compter jusqu'à la base.
Exemples :

base 10 = 10 symboles, de 0 à 9,
base 6 = 6 symboles, de 0 à 5 (les doigts de la main),
base 2 = 2 symboles, 0 et 1 (ON/OFF, une lampe, le courant électrique est là ou non),
base 16 = 16 symboles ???!! en base 16, on utilise les symboles de 0 à 9 et on continue avec les lettres A à F pour représenter les "chiffres" de 10 à 15,

A partir du moment où on dépasse le nombre maxi de symboles, il faut en ajouter un second, à gauche, pour marquer ce dépassement.
Exemples :

En base 10 : 9+1 = 10. C'est à dire ...
- 9+1=0 et
- je retiens 1 que j'ajoute au second chiffre à gauche, la dizaine.
- on obtient bien : unité = 9+1= 0 et dizaine = 0+la retenue de 1 = 1 soit 1 0 (prononcer un-zéro).
- Noter que le maximum avec 2 chiffres est de 99. audelà, il faut un 3ème chiffre : 100
En base 6 : 5 doigts +1 doigt = 10 aussi. Impossible de représenter 6 avec une seule main. C'est à dire ...
- 5 doigts +1 doigt = 0 doigts à la main droite et
- je retiens 1 que j'ajoute à la main gauche, la "sizaine".
- on obtient bien : unité = 5+1= 6 avec 1 doigt à la main gauche et 0 doigts à la main droite soit 1 0 (prononcer un-zéro).
- Maintenant, le maximum avec 2 mains est de 55. au delà, il faut emprunter une main à quelqu'un d'autre : 100
En base 2 : 1+1 = 10 aussi.
- 1+1 = 0 et je retiens 1
- et j'ajoute la retenue au bit de gauche, la "deuzaine".
- on obtient bien : 1+1 = 10 (prononcer un-zéro).
En base 16 : F+1 = 10 aussi.
- F+1 = 0 et je retiens 1
- et j'ajoute la retenue au chiffre de gauche, la "seizaine".
- on obtient bien : F+1 = 10 (prononcer un-zéro).
- Preuve : F=15, 1=1, 10(16)=16(10).

Chaque chiffre correspond à une puissance de la base.
Ainsi, en base dix, 123 = 3x10^0 + 210^1 + 110^2 = 3 + 20 + 100 = 123. cqfd Dans les autres bases, c'est aussi le cas :

base 2 : 101 = 12^0 + 02^1 + 12^2 = 1+0+4 = 5 en base 10.
base 16 : 14B = B16^0 + 416^1 + 116^2 = 11+64+256 = 331 en base 10. (Rappel : A=10, B=11)

Petit quizz

Combien de symboles a-t-on si on considère les doigts des deux mains ?
Jusqu'à combien peut-on compter en base 2 avec 8 positions binaires ?
Jusqu'à combien peut-on compter en base 16 avec 2 positions hexadécimales ?

Opérations de calculs

Les opérations sur des bases numériques de calcul sont comme en base 10 : addition, soustraction, multiplication et division.
Je ne présente que l'addition en plusieurs bases, pas les autres du fait de leur peu d'intérêt.

Addition

base 10 : 6+7 = 10+3 : on compte selon 6+7 = 3 "et je retiens 1 que j'ajoute à la dizaine". Soit 6+7= 3 +110
base 2 : 0+0=0 ; 0+1=1 ; 1+0=1. Jusque là, tout va bien mais ... 1+1=0 !!! en fait, 1+1=0 et je retiens 1 que j'ajoute à la "deuzaine" supérieure. c'est à dire 1+1 = 10 !
base 16 : 6+7 = D (13) : on compte de 1 à F!
base 16 : 8+8 = 10. eh oui, 8+8=16 en base 10 mais 1x16^1+0x16^0=10 en base 16.

Soustraction

Là, il vaut mieux poser le calcul :

base 2 : 0-0=0, 1-0=1, 1-1=0 et 0-1 = - et je retiens 1 à soustraire à la deuzaine supérieure soit l'opération binaire suivante :

 
11 0011 (= 51)
-   101 (= 5)
_1_1__) retenue négative
10 1110 (=32+8+4+2=46 = 51-5 cqfd)

Multiplication

Très simple, c'est comme une multiplisation normale sauf qu'on a que des 1 ou des 0.
On reprend la base du calcul comme en classe de 6ème et on comprend que ce sont des multiplications par 1 ou 0 puis des additions.

Exemple : l'opération binaire 515 :

 
   11 0011 (= 51)
 x     101 (= 5)
 _________	=> multiplication avec décalage selon la position des chiffres
           (retenues de l'addition)
   11 0011 (= 51)
        0  (= 0 )
 1100 11   (= 51*4)
 __________ (retenues de l'addition)
 1111 1111 (= 128+64+32+16+8+4+2+1 = 255)

Division

 
1111 1111 | 101      "en 1, combien de fois va 1 ? ..."
          |_______   
          |
          |

Je vous laisse faire ...

Petit quizz

Calculer :

11011101 + 11100
123 + 456 en base 8 et en base 16

Conversions de base (2 et 16)

*** Ce savoir est obligatoire. ***

C'est la plus compliqué et en même temps le plus utile.
Pour faire la conversion, il existe (au moins) deux méthodes dans chaque sens. À vous de choisir celle que vous préférez.

les puissances de 2

Il est nécessaire de connaître les puissances de 2 pour effectuer les calculs (au moins de 0 à 10).
Calculatrice ou de tête ? Clairement, de tête on va plus vite. Voici les puissances de 2 qui correspondent aux rangs des chiffres en commençant par la droite (les unités).

rang	puissance	rang	puissance
0	1	8	256
1	2	9	512
2	4	10	1024
3	8	11	2048
4	16	12	4096
5	32	13	8192
6	64	14	16384
7	128	15	32768

2^16 = 65 536 = nombre de couleurs pour un pixel en 4 octets : rvb+n = qualité des images d'une imprimante classique ...

Conversion base 2 à 10

On effectue la conversion suivante : 11001010(2) -> ?(10)

Méthode 1

Commencer à droite : compter la position des 1 et additionner les puissances de 2 de ces positions (on commence à 0)

On utilise la position en partant de la droite vers la gauche pour
Calculer les puissances de 2 de chaque position,
Chaque puissance est multipliée par le chiffre binaire 0 ou 1 de la position et
On additionne le tout pour obtenir le résultat en base 10.

Méthode 2

Commencer à gauche : multiplier le résultat de n-1 et ajouter le bit n. (le + rapide ?)

a chaque chiffre du nombre binaire,
on ajout 0 ou 1 au résultat précédent,
on fait une multiplication par 2.
le total final est le nombre converti.

Sous forme algébrique :

	R= ((((((1*2+1)*2+0)*2+0)*2+1)*2+0)*2+1)*2+0

Méthode 3

Cette méthode est plus rapide mais ici, il faut connaître ses tables de multiplication et de conversion …

 
	Décomposer le binaire en deux quartets : 11001010 = 1100 0000 + 0000 1010 = 192+10 = 202
	explications : 1100 =12, 1010=10, r=12*16 + 10 = 160+32 + 10 = 202. cqfd

Exercice

Convertir de base 2 à 10 (méthode au choix)

111
1110
10101010
11001100

Conversion base 10 à 2

Effectuer la conversion de : 166(10) => ?(2).

Méthode 1

Méthode : Soustraire des puissances de 2 par ordre décroissant.

Prérequis : connaître les puissances de 2.

si le résultat est positif, on indique un 1, sinon un zéro et
on reporte le résultat en dessous
fin du calcul quand on a atteint le rang 2^0

lire de HAUT en BAS

Méthode 2

Méthode : effectuer des divisions entières successives jusqu'à un résultat de zéro.

Prérequis : connaître la division par 2

Effectuer une division entière par 2,
Indiquer le reste et reporter le résultat en dessous
Fin du calcul quand on a atteint un résultat de 0.

lire de BAS en HAUT

À la fin, compléter par des 0 à gauche du résultat pour avoir des octets. /ex. : 5010= 1100102 => 0011 0010

La division entière est une division normale mais le reste n'est pas divisé si inférieur à 1. Exemple : 11%5 = 2 et il reste 1 (5x1 = 10, 10+1 = 11)

Exercice

Convertir de base 10 à 2 (méthode au choix)

Conversions en base hexadécimale

Rappels :

base 16 : 16 symboles de 0 à 9 et A à F
base 2 : 2 symboles => 0 et 1
base 10 : 10 symboles => de 0 à 9

Remarque : la conversion de base 10 en 16 et inversement est plus facile si on passe par le binaire, au moins pour les lettres.
En effet, l'hexadécimal est en fait une représentation condensée du binaire, : A=1010, B= 1011, F=1111
De la même façon, il est très avantageux de présenter les nombre binaires sous forme de quartets, groupes de 4 bits.

Conversion de 2 à 16 ou 16 à 2

Conversion assez facile de 2 à 16 et 16 à 2 :

Séparer le nombre binaire en quartets (4 bits)
Compléter les quartets
Convertir chaque quartet individuellement de tête ou avec l'abaque donnée en fin de ce document.

Normalement, on complète aussi les octets en plaçant autant de zéros que nécessaire devant le nombre pour obtenir un nombre de bits multiple de 8, de 16, etc...

Conversion de 10 à 16 ou 16 à 10

Un peu plus compliquée ! donc passer par le binaire :

convertir chaque chiffre hexa en binaire : A = 1010, 5 = 0101, B = 1011
convertir le résultat binaire en décimal : 1010 0101 1011

Une autre méthode est d'utiliser la méthode 3 de 2 à 10 mais avec des puissances de 16 ... à la calculatrice !

rang	puissance	rang	puissance
0	1	3	4096
1	16	4	65536
2	256

Abaques de conversion

Les conversions représentées ci-dessous sont à apprendre par coeur.
C'est nécessaire car ils sont hyper courants dans l'adressage réseau et dans les claculs binaires.

Décimal	Binaire	Hexadécimal	Décimal	Binaire	Hexadécimal
0	0000 0000	0	8	0000 1000	8
1	0000 0001	1	9	0000 1001	9
2	0000 0010	2	10	0000 1010	A
3	0000 0011	3	11	0000 1011	B
4	0000 0100	4	12	0000 1100	C
5	0000 0101	5	13	0000 1101	D
6	0000 0110	6	14	0000 1110	E
7	0000 0111	7	15	0000 1111	F

Décimal Binaire Hexadécimal Décimal Binaire Hexadécimal

16 0001 0000 10 127 0111 1111 7F

31 0001 1111 1F 128 1000 0000 80

32 0010 0000 20 254 1111 1110 FE

33 0010 0001 21 255 1111 1111 FF

Décimal	Binaire	Hexadécimal	Décimal	Binaire	Hexadécimal
16	0001 0000	10	127	0111 1111	7F
31	0001 1111	1F	128	1000 0000	80
32	0010 0000	20	254	1111 1110	FE
33	0010 0001	21	255	1111 1111	FF

Opération et nombres remarquables

Décimal	Binaire	Hexadécimal	Décimal	Binaire	Hexadécimal
0	0000 0000	00	1	0000 0001	01
127	0111 1111	7F	2	0000 0010	02
128	1000 0000	80	4	0000 0100	04
192	1100 0000	C0	8	0000 1000	08
224	1111 0000	F0	16	0001 0000	10
240	1111 1000	F8	32	0010 0000	20
248	1111 1100	FC	64	0100 0000	40
254	1111 1110	FE	96	0110 0000	60
255	1111 1111	FF	160	1010 0000	A0
			10	0000 1010	0A

Quizz final

Effectuer les opérations suivantes dans la base proposée et vérifier en convertissant les nombres et résultats en décimal

Binaire :
- 10 + 10
- 1010 - 1
- 1001001+111001
- 1001001 OU 111001
- 1001001 ET 111001
Hexadécimal :
- 10 + 10
- 7F + 1
- 39 + 73
- 39 + 37