Chapitre 6 Booléens 1 / 6

Ch 6 LOGIQUE BOOLEENS TS2-ISN Janvier 2019

George Boole, né le 2 novembre 1815 à Lincoln (Royaume-Uni) et mort le8 décembre 1864 à Ballintemple (Irlande), est un logicien, mathématicienet philosophe britannique. Il est le créateur de la logique moderne. Sestravaux posent les bases de ce qu’on nommera plus tard l’algèbre deBoole. En 1847 sort "Mathematical Analysis of Logic". Boole y développeune nouvelle forme de logique, à la fois symbolique et mathématique.Le but : traduire des idées et des concepts en équations, leur appliquercertaines lois et retraduire le résultat en termes logiques. Pour cela, ilcrée une algèbre binaire n’acceptant que deux valeurs numériques : 0 et1. Cette algèbre est définie par la donnée d’un ensemble E (non vide)muni de deux lois de composition interne (le ET et le OU) satisfaisant àun certain nombre de propriétés (commutativité, distributivité...)

Un peu de logiqueOn considère les trois propositions logiques suivantes :

v : « Ma voiture marche » p : « Il pleut » m : « Je prends le métro »La valeur de ces propositions peut être VRAI (dans ce cas elle vaut 1) ou FAUX ( elle vaut 0)A partir de ces propositions on peut définir d’autres propositions, comme :• la négation de la proposition p, notée ¬p ( parfois aussi notée p) : « Il ne pleut pas »

On peut représenter ceci par un tableau (appelé table de vérité)p ¬p1 00 1

• la proposition « Ma voiture marche et il pleut » notée v ∧ p

la proposition v ∧ p n’est vraie que si chacune des deux v et p est vraie d’où

v p v ∧ p0 0 00 1 01 0 01 1 1

• la proposition « Ma voiture marche ou il pleut » notée v ∨ p

la proposition v∨p est vraie lorsque v est vraie ou p est vraie ( ou les deux) d’où

v p v ∨ p0 0 00 1 11 0 11 1 1

• On peut aussi définir des propositions plus complexes comme la proposition :« S’il pleut et ma voiture ne marche pas, je prends le métro » notée p ∧ ¬v =⇒ mLe calcul booléen permet de dresser la table de vérité de toutes ces propositions.

Et l’ordinateur ?On a vu qu’il travaillait avec des 0 et des 1. Le calcul booléen va donc être représentable physiquementpar des mécanismes électroniques ( à l’aide de transistors) 1 tension > 0 et 0 tension nulle. C’est UnitéArithmétique et Logique (U.A.L) de l’ordinateur qui va s’occuper de tout ça. A l’intérieur il y a descircuits logiques :

Chapitre 6 Booléens 2 / 6

Les portes logiquesCe sont les circuits logiques élémentaires

la porte ¬a , parfois aussi notée !a (not a en python) est nommée porte NOTla porte a ou b (a or b en python) est nommée porte ORLa porte a et b (a and b en python) est nommée porte ANDLa porte non (a ou b) not a or b en python) est nommée porte NORLa porte non (a et b) not a and b en python) est nommée porte NAND

Porte XORIl y a une autre porte élémentaire qui est souvent utile la porte XOR c’est le ou exclusif noté a⊕b

Chapitre 6 Booléens 3 / 6

Algèbre booléenneDans le paragraphe précédent, on a représenté les portes élémentaires à l’aide des opérations a + b eta.bOn peut alors définir un nouveau calcul avec ces deux opérations, elles vérifient les propositions sui-vantes :

Element neutre a+ 0 = a a.1 = aCommutatitivité a+ b = b+ a a.b = b.aAssociativité a+ (b+ c) = (a+ b) + c a.(b.c) = (a.b).cElement nul a+ 1 = 1 a.0 = 0distributivité a+ b.c = (a+ b).(a+ c) a.(b+ c) = a.b+ a.c

Avec la négation a = a a+ a = 1 a.a = 0

Idempotence a+ a = a a.1 = aabsortion a+ (a.b) = a a.(a+ b) = a

Lois de Morgan : a+ b = a.b a.b = a+ b

Toutes ces propriétés se démontrent (par exemple à l’aide d’une table de vérité)

Exemple de circuitVoila un circuit où les entrées sont a et b et la sortie s.

Formule :

s = a ∧ b ∧ a ∧ b

En Python :s = not(not( a and not b) and (not (not a and b))

Table de vérité

a b a b a ∧ b a ∧ b a ∧ b ∧ a ∧ b

0 0 1 1 0 0 1

0 1 1 0 0 1 0

1 0 0 1 1 0 0

1 1 0 0 0 0 1

Chapitre 6 Booléens 4 / 6

Un peu d’électronique

Chapitre 6 Booléens 5 / 6

Chapitre 6 Booléens 6 / 6

Questions de cours chapitre 3

Question 1Démontrer les propriétés d’ une algèbre de Boole énoncées page 3

Question 2Ecrire un programme Python qui établisse directement la table de vérité de la formule du circuit logiquede la page 3

Question 3Un peu de logique

1. Quelle est la négation de la proposition « Je suis jeune et beau »2. Quelle est la négation de la proposition « x > 5 ou x < 2 »3. Dire que l’implication p =⇒ q est vraie signifie : lorsque p est vraie, q est vraie

(Donc lorsque p est fausse, l’implication p =⇒ q est toujours vraie )(a) Etablir la table de vérité de l’implication p =⇒ q

(b) Etablir la table de vérité de la proposition ¬p ∨ q

(c) Conclusion ?4. Dans quels cas la proposition « S’il pleut et ma voiture ne marche pas, je prends le métro » de

la page 1 est-elle vraie ?On pourra pour répondre à la question faire une table de vérité ou faire un programme Pythonqui écrit cette table de vérité.

Question 4

1. A partir des trois opérateurs de base : négation (NOT), conjonction (AND), et disjonction(OR), redéfinir l’équivalence ( ⇐⇒) et le ou exclusif (⊕)

2. dessiner un circuit logique avec comme entrée a et b et comme sortie s = a⇐⇒ b et t = a⊕ b

3. Vérifier à l’aide d’un programme Python

Question 5

1. Simplifier les expressions booléennes suivantes :s = a+ b+ c.d t = a.b.c+ d u = a.b+ c+ d

2. Vérifier à l’aide d’un programme Python

Question 6Avec seulement la porte NAND

1. Le circuit est équivalent à une porte élémentaire, laquelle ?

2. Le circuit est équivalent à une porte élémentaire, laquelle ?

3. Comment faire une porte NOT à l’aide de seulement une porte NAND?