223 234
1-4

@0 Préparer une présentation orale résumant 2 à 3 notions abordées lors de la dernière séance de cours :

  1. choisir UNE notion différente par élève au sein de chaque équipe,
  2. se préparer à réaliser, en 5 minutes maximum, sur 1/3 du tableau blanc, un croquis accompagné de mots clés et du titre de la notion abordée pour soutenir la présentation orale,
  3. se préparer à présenter, SANS notes, sa notion en 1,5 minutes maximum.

LOGIQUE BOOLEENE

Dans un ordinateur, le langage au plus proche de la machine n’est composé que de 0 et de 1, de Vrai ou de Faux. Pour concevoir les circuits électroniques effectuant les opérations logiques il a donc fallut “inventer” des outils mathématiques binaires.

George Boole (1815-1864) est un logicien, mathématicien, philosophe britannique. Il est le créateur de la logique moderne, fondée sur une structure algébrique et sémantique, que l’on appelle aujourd’hui algèbre de Boole.

Notons B l’ensemble {0; 1} que nous appellerons ici ensemble des booléens

Nous allons dans ce chapitre manipuler quelques opérateurs booléens, c’est à dire des fonctions d’une ou plusieurs variables dans B et à valeurs dans B.

Nous commençons par définir les opérateurs de base ET, OU, NON. Le nom de ces opérateurs vient de la convention d’associer 0 à Faux et 1 à Vrai.

Les variables python de type booléen peuvent prendre deux valeurs : False, True.

Les opérateurs et leur combinaison peuvent être décrit par une table de vérité, exemple :

Exemple :

Entrée A Entrée B Sortie S
0 0 1
0 1 0
1 0 0
1 1 0

1.1 L’Opérateur NON ( NOT )

Définition : L’opérateur de négation, noté ! ou NOT() ou NON(), est une fonction définie sur B et à valeurs dans B définie par :

@1 A l’aide du site suivant, tester l’opérateur NOT, puis en déduire la table de vérité associée, et recopier le schéma de cablage électronique et sa table de vérité.

Correction :

A S= !A
0 1
1 0

1.2 L’opérateur ET ( AND )

Définition : L’opérateur de conjonction, noté “&” ou “.” ou “AND” ou encore “ET”, est une fonction définie sur B² et à valeurs dans B

Cet opérateur est défini par l’équivalence :

x & y = Vrai si et seulement si x et y sont tous deux Vrai.
Autrement dit (x . y) == Vrai équivaut à (x == Vrai) ET (y == Vrai)

@2 A l’aide du site suivant, tester l’opérateur AND d’équation booléene (a . b = s) puis en déduire la table de vérité associée, et recopier le schéma de cablage électronique ET sa table de vérité.

Correction :

A B S= A.B
0 0 0
0 1 0
1 0 0
1 1 1

@3 A l’aide du site suivant, tester l’opération booléenne !a . !b puis en déduire la table de vérité associée, et recopier le schéma de cablage électronique ET sa table de vérité.

Correction :

A B !A !B S= !A . !B
0 0 1 1 1
0 1 1 0 0
1 0 0 1 0
1 1 0 0 0

@4 A l’aide du site suivant, tester l’expression booléenne !(!a . !b) puis en déduire la table de vérité associée, et recopier le schéma de cablage électronique ET sa table de vérité.

Correction :

A B !A !B U= !A . !B S= !U
0 0 1 1 1 0
0 1 1 0 0 1
1 0 0 1 0 1
1 1 0 0 0 1

On remarque que ce circuit logique allume la lampe si au moins un des deux interrupteurs est allumé. Autrement il suffit que A ou B soit Vrai pour que S soit Vrai… intéressant !!! :full_moon_with_face:

1.3 L’opérateur OU ( OR )

Définition : L’opérateur de disjonction, noté “|” ou “+” ou “OR” ou encore “OU”, est une fonction définie sur B² et à valeurs dans B

Cet opérateur est défini par l’équivalence :
x | y = Vrai si et seulement si au moins une des deux variables est Vrai.
Autrement dit (x + y) == Vrai équivaut à (x == Vrai) OU (y == Vrai)

Le OU "Naturellement" utilisé en logique booléenne est un OU INCLUSIF (fromage ou dessert ou les deux) contrairement au OU “Naturellement” utilisé dans la vie de tous les jours (fromage ou dessert mais pas les deux).

@5 A l’aide du site suivant, tester l’opérateur OR, d’équation booléene (a + b = s) puis en déduire la table de vérité associée, et recopier le schéma de cablage électronique et sa table de vérité.

Correction :

A B S= A + B
0 0 0
0 1 1
1 0 1
1 1 1

@6 A l’aide du site suivant, tester l’opération booléenne !a + !b puis en déduire la table de vérité associée, et recopier le schéma de cablage électronique ET sa table de vérité.

Correction

A B !A !B S= !A + !B
0 0 1 1 1
0 1 1 0 1
1 0 0 1 1
1 1 0 0 0

@7 A l’aide du site suivant, tester l’expression booléenne !(!a + !b) puis en déduire la table de vérité associée, et recopier le schéma de cablage électronique ET sa table de vérité.

Correction :

A B !A !B U= !A + !B S= !U
0 0 1 1 1 0
0 1 1 0 1 0
1 0 0 1 1 0
1 1 0 0 0 1

On remarque que ce circuit logique allume la lampe uniquement si les des deux interrupteurs sont allumés. Autrement il faut que A et B soient Vrai pour que Ssoit Vrai… intéressant !!! :full_moon_with_face:

1.4 L’opérateur OU EXCLUSIF ( XOR )

Définition : L’opérateur OU EXCLUSIF, noté ⊕ ou XOR, est une fonction définie sur B² et à valeurs dans B

Cet opérateur est défini par l’équivalence :

(x ⊕ y) == Vrai si et seulement si exactement une des deux variables x, y est Vrai mais pas les deux en même temps, autrement dit, si les deux variables ont des valeurs différentes.

Ainsi (x ⊕ y) == Vrai équivaut à x != y

Le OU "Naturellement" utilisé en logique booléenne est un OU INCLUSIF (fromage ou dessert ou les deux) contrairement au OU “Naturellement” utilisé dans la vie de tous les jours (fromage ou dessert mais pas les deux), qui est donc un OU EXCLUSIF.

@8 A l’aide du site suivant, tester l’opérateur XOR d’équation booléene (a ⊕ b = s) puis en déduire la table de vérité associée, et recopier le

Correction

A B S= A ⊕ B
0 0 0
0 1 1
1 0 1
1 1 0

@9 A l’aide du site suivant, tester l’expression booléenne ( A . !B ) + (!A . B ) puis en déduire la table de vérité associée, et recopier le schéma de cablage électronique ET sa table de vérité.

Correction :

A B !A !B U= ( A . !B ) V= (!A . B ) S= U + V
0 0 1 1 0 0 0
0 1 1 0 0 1 1
1 0 0 1 1 0 1
1 1 0 0 0 0 0

1.5 Les fonctions booléenes (généralisation)

Définition : Une fonction booléene est obtenue par combinaison d’opérateurs booléens élémentaires et définie par une expression. On peut extraire de chaque expression booléenne une table de vérité. Celle-ci permet parfois de fournir une expression equivalente de la fonction mais plus “simple”.

Par exemple : l’expression booléene !(!a . !b) décrit la fonction booléene OR et peut s’écrire à l’aide d’une autre expression booléene (a + b).

@10 Sur le site suivant, il existe une porte logique permettant, à elle seule, de réaliser l’expression booléenne !( x . y ). La trouver puis en déduire la table de vérité associée et faire une copie d’écran du schéma de cablage électronique.

Correction :

A B U= A . B S= !U
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0

@11 A l’aide de cette nouvelle porte et d’une autre porte déjà connue, sur le site suivant, réaliser la fonction AND. Faire une copie d’écran du schéma de cablage électronique.

Correction :

A B U= !(A . B) S= !(!(A . B))
0 0 1 0
0 1 1 0
1 0 1 0
1 1 0 1

@12 Toujours à l’aide de cette porte réalisant !( x . y ), et en la combinant avec d’autres portes connues, sur le site suivant, réaliser la fonction OR. Faire une copie d’écran du schéma de cablage électronique.

Correction

A B !A !B S= !(!A . !B)
0 0 1 1 0
0 1 1 0 1
1 0 0 1 1
1 1 0 0 1

On considère le schéma logique ci-dessous définissant une fonction inconnue S(A, B) et sa table de vérité associée :

A B K= !A L= K & B M= L | A N= !B S= M & N
0 0
0 1
1 0
1 1

@13 Compléter la table de vérité ci-dessus (SANS l’aide du simulateur de circuits logiques), puis en déduire l’expression booléene complète S= ((!... & ...) | ....). !... et une version “simplifiée” S= ... . !.... Et enfin, vérifier les deux expressions logiques (complète et simplifiée) sur le simulateur.

Correction :
A B K= !A L= K & B M= L | A N= !B S= M & N
0 0 1 0 0 1 0
0 1 1 1 1 0 0
1 0 0 0 1 1 1
1 1 0 0 1 0 0

Cette expression numérique complexe S= ((!A & B) | A). !B peut se simplifier puisque l’on voit que S est Vrai uniquement quand A est Vrai et B est NON(Vrai)(donc Faux).

L’expression équivalente mais plus simple devient donc S= A. !B

A B !B S= A. !B
0 0 1 0
0 1 0 0
1 0 1 1
1 1 0 0

… comme le montre le circuit suivant (cliquer sur l’image)
:

@14 Sur le site suivant réaliser l’expression booléenne 0 . x autrement écrit Faux & x. Puis en déduire la table de vérité associée et la résumer en une phrase écrite.

Correction :
0 x S= 0 . x S= 0
0 0 0 0
0 1 0 0

L’expression booléenne 0 . x autrement écrit Faux & x est tout simplement égale à Faux quelle que soit la valeur de x. Ce qui signifie que le bouton est inutile !

@15 Sur le site suivant réaliser l’expression booléenne 1 . x autrement écrit Vrai & x. Puis en déduire la table de vérité associée et la résumer en une phrase écrite.

Correction :
1 x S= 1 . x S= x
1 0 0 x
1 1 1 x

L’expression booléenne 1 . x autrement écrit Vrai & x est tout simplement égale à la valeur de x quelle que soit sa valeur. Ce qui signifie que la porte logique est inutile ! Un simple fil électrique ferait pareil.

@16 Sur le site suivant réaliser l’expression booléenne 1 + x autrement écrit Vrai | x. Puis en déduire la table de vérité associée et la résumer en une phrase écrite.

Correction :
1 x S= 1 + x S= 1
1 0 1 1
1 1 1 1

L’expression booléenne 1 + x autrement écrit Vrai | x est tout simplement égale à Vrai quelle que soit la valeur de x. Ce qui signifie que le bouton est inutile !

@17 Sur le site suivant réaliser l’expression booléenne 0 + x autrement écrit Faux | x. Puis en déduire la table de vérité associée et la résumer en une phrase écrite.

Correction :
0 x S= 0 + x S= x
0 0 0 x
0 1 1 x

L’expression booléenne 0 + x autrement écrit Faux | x est tout simplement égale à la valeur de x quelle que soit sa valeur. Ce qui signifie que la porte logique est inutile ! Un simple fil électrique ferait pareil.

@18 On considère la fonction multiplexeur, notée muxet définie par mux(Sel, D0, D1) = ((!Sel) & D0) | (Sel & D1).

Correction :
Sel D0 D1 !Sel u= (!Sel) & D0 v= Sel & D1 mux(Sel, D0, D1) = u | v
0 0 0 1 0 0 0
0 0 1 1 0 0 0
0 1 0 1 1 0 1
0 1 1 1 1 0 1
1 0 0 0 0 0 0
1 0 1 0 0 1 1
1 1 0 0 0 0 0
1 1 1 0 0 1 1

Le multiplexeur permet d’afficher en sortie de ciruit la valeur de D0 ou de D1 suivant la valeur du bit de selection Sel.

Sel D0 D1 !Sel u= (!Sel) & D0 v= Sel & D1 mux(Sel, D0, D1) = u | v
0 0 0 1 D0 0 D0
0 0 1 1 D0 0 D0
0 1 0 1 D0 0 D0
0 1 1 1 D0 0 D0
1 0 0 0 0 D1 D1
1 0 1 0 0 D1 D1
1 1 0 0 0 D1 D1
1 1 1 0 0 D1 D1

On peut d’ailleurs simplifier la table de vérité ainsi :

Sel D0 D1 !Sel u= (!Sel) & D0 v= Sel & D1 mux(Sel, D0, D1) = u | v
0 D0 D1 1 D0 0 D0
1 D0 D1 0 0 D1 D1
Sel D0 D1 !Sel u= (!Sel) & D0 v= Sel & D1 mux(Sel, D0, D1) = u | v
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

1.6 Les circuits NAND

Nous avons vu que l’on peut créer de multiples fonctions en combinant différentes portes logiques entre elles.

Nous allons voir qu’en réalité nous pouvons faire tout cela en combinant un seul type de portes.

Ce qui veut dire aussi que l’on peut créer des portes OU, NON, ET, XOR… etc en combinant plusieurs portes d’un seul et même type.

C’est un peu comme si, au lieu de combiner 4 / 5 aliments différents pour faire un gâteau, il suffisait de combiner 4 / 5 fois de manières différentes le même aliment !!! Ca simplifierait les courses et le rangement dans le placard :smile:

En informatique c’est une réalité et grâce à cela on peut fabriquer des microprocesseurs composés de millions de portes logiques différentes par cm2 à l’aide d’une seule porte générique… la porte NAND !!!

@19 Tenter de réaliser le meilleur score au jeu NANDGAME.

Coup de pouce 1 : Cabler une porte NOT = NON

Coup de pouce 2 : Cabler une porte AND = ET

Solution

Logique séquentielle et automates cellulaires

Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » parmi un ensemble fini d’états (souvent deux états seulement : 0 et 1).

Cet état évolue au cours du temps suivant des règles précises.

L’état d’une cellule à un instant t est fonction de l’état à l’instant précédent t−1 des cellules voisines.

À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente.

Exemple du “Jeu de la Vie” (automate à 2 dimensions)

Il s’agit de l’automate cellulaire le plus connu, inventé par le mathématicien John Conway.

Ici, les cellules sont disposées sur une surface quadrillée et évoluent d’une génération
à l’autre selon les règles suivantes (les voisines d’une cellule sont les cellules qui occupent
les huit cases touchant la sienne) :
• si une cellule a 2 ou 3 voisines vivantes, elle survit au tour suivant,
• si une cellule a moins de 2 voisines vivantes, elle meurt de solitude au tour suivant,
• si une cellule a plus de 3 voisines vivantes, elle meurt d’étouffement au tour suivant,
• une cellule naît dans une case vide si cette case est entourée de précisément 3 cellules vivantes.

C’est l’analogie entre ces règles et certains critères d’évolution de populations de bactéries qui a conduit à donner à cet automate le nom de jeu de la vie.

Simulateurs :

Fabriquons un automate cellulaire à une dimension

Pour réaliser un automate cellulaire élémentaire, nous allons considérer des cases disposées en ligne. Chaque case peut être soit blanche, soit noire. Au démarrage de notre simulation, nous allons supposer qu’une seule case est noire, comme sur le schéma ci-dessous.

Puis nous allons faire évoluer notre système, en définissant des règles qui vont conditionner comment la couleur des cases change à chaque étape de la simulation. Pour faire au plus simple, nous allons supposer que la nouvelle couleur d’une case dépend de sa couleur actuelle et de celle de ses voisines. Voici une règle de ce genre :

On peut facilement représenter cette règle graphiquement, car il n’existe que 8 cas à considérer :

Dans le milieu des spécialistes d’automates cellulaires on considère que cette règle porte le numéro 254 » … Pourquoi à votre avis ?

Si on applique cette règle à notre situation de départ avec une seule case noire, voici ce que l’on obtient à chaque pas de temps :

On peut représenter l’évolution d’un automate cellulaire élémentaire sur plusieurs centaines d’itérations en superposant les différentes lignes obtenues, comme ci-dessous :

En modifiant un seul cas on obtient la règle dite « numéro 250 », qui est représentée ci-dessous à gauche (le changement est souligné en rouge ).

En modifiant un autre cas on obtient la règle dite « numéro 190 », représentée ci-dessous à droite avec un dessin assez semblable au précédent mais avec des bandes blanches et noires alternées.

Voici une animation pas à pas du calcul de chaque nouvelle cellule à partir d’une ligne initiale :

https://en.wikipedia.org/wiki/Elementary_cellular_automaton#/media/File:One-d-cellular-automate-rule-30.gif

Sauf que la cellule “centre” obtenue sera réutilisée au tour suivant en entrée de porte logique, un peu comme l’accumulateur est réutilisé en entrée de l’Unité Arithmétique et Logique au calcul suivant, au fil des séquences d’instructions.

Voilà pourquoi on parle de logique séquentielle.