Fonctions logiques composées et lois de l’algèbre booléenne

Merci !

Fiches
Classe(s) : 1re Générale | Thème(s) : Représentation des données : types et valeurs de base
 

Les propriétés et les lois de l’algèbre de Boole sont utiles pour travailler sur des fonctions plus complexes combinant les opérations fondamentales de l’algèbre booléenne.

I Les lois de l’algèbre de Boole

Les lois suivantes sont facilement démontrables à l’aide de tables de vérités.

Propriété

Signification

Commutativité

x | y = y | x et x & y = y & x

Associativité

x | (y | z) = (x | y) | z et x & (y & z) = x & (y & z)

Distributivité

x & (y | z) = (x & y) | (x & z)

et x | (y & z) = (x | y) & (x | z)

Élément neutre

x | F = x et x & V = x

Élément absorbant

x & F = F

Involution

~(~x) = x

Tiers-exclus

~x | x = V

Non-contradiction

~x & x = F

Idempotence

x & x = x et x | x = x

Lois de De Morgan

~(x | y) = ~x & ~y et ~(x & y) = ~x | ~y

II Les fonctions composées

Toutes les opérations booléennes peuvent s’écrire en n’utilisant que les trois opérateurs &, | et ~. Mais en pratique on utilise aussi d’autres fonctions logiques, qui s’obtiennent à partir des opérations fondamentales.

1 Disjonction exclusive (ou exclusif, xor)

x ^ y = (x & ~y) | (~x & y)

PB_Bac_05230_numerique1_TT_p009-044_C01_Groupe_Schema_19

2 Non Et (nand)

x ↑ y = ~(x & y)

PB_Bac_05230_numerique1_TT_p009-044_C01_Groupe_Schema_17

3 Non Ou (nor)

x ↓ y = ~(x | y)

PB_Bac_05230_numerique1_TT_p009-044_C01_Groupe_Schema_18

à noter

On peut montrer que toutes les fonctions logiques précédentes peuvent s’obtenir à partir de la seule fonction Nand.

III Opérations bit à bit

On peut généraliser les opérations précédentes à des chaînes de bits.

Exemples :

Addition posée

Avec Python

1011011

& 1010101

--------------------

1010001

>>> bin(0b1011011 & 0b1010101)

'0b1010001'

1011011

| 1010101

--------------------

1011111

>>> bin(0b1011011 | 0b1010101)

'0b1011111'

1011011

^ 1010101

--------------------

0001110

>>> bin(0b1011011 ^ 0b1010101)

'0b1110'