La logique combinatoire.

1. Introduction

1.1. La variable logique.

Pour illustrer le concept de variable logique, imaginons que vous disposiez d’un capteur de température et d’un capteur d’hygrométrie. Ces deux capteurs sont indépendants et fournissent des valeurs de deux grandeurs physiques différentes et indépendantes.

En général, de tels capteurs fournissent des valeurs analogiques. Imaginons, à présent, que vous définissiez une variable a de la façon suivante : si la température est supérieure à une valeur de seuil, 15° C, par exemple, cette variable est à 1 (ou Vrai, ou Haut). Dans le contraire, si la température est inférieure à ce seuil, la variable est à 0 (ou Faux, ou Bas).

De façon analogue, vous définissez la variable b relativement à l’hygrométrie comparée à une valeur seuil.

Chacune de ces deux variables ne peut prendre que deux valeurs distinctes. On peut noter ces deux valeurs 0 et 1, mais il faut comprendre alors que dans ce contexte, 0 et 1 n’ont pas valeur de nombre. Ce sont de simples étiquettes qui décrivent l’état logique de la variable.

2. Les fonctions logiques élémentaires.

Les fonctions ou portes élémentaires qui suivent, définissent des fonctions qui élaborent une sortie en fonction des entrées de ces variables logiques.

2.1. La porte NON.

La porte NON, appelée aussi porte inverseuse ou simplement inverseur, possède une entrée unique, notée ici a.

La sortie est notée:

\$s=bar a\$

sa fonction est conforme à la table de vérité ci-dessous :

a	s
0	1
1	0

On dit aussi que la sortie est complémentée. La porte NON est la fonction de complémentation.

Cette porte, pour très simple et basique qu’elle soit, est cruciale puisque nous verrons plus loin que dans les expressions algébriques qui décrivent toute fonction combinatoire, cette fonction ou opération de complémentation est omniprésente.

La représentation symbolique graphique de cette porte existe selon deux normes qu’il faut connaître :

La norme internationale et européenne en vigueur :	La norme américaine
norme internationale, IEEE	théoriquement désuète, mais encore beaucoup utilisée par les praticiens :

La norme internationale et européenne en vigueur :

La norme américaine

AFNOR NON

norme internationale, IEEE

american NOT

théoriquement désuète, mais encore beaucoup utilisée par les praticiens :

2.2. Porte ET/AND à deux entrées.

La porte ET ou AND à deux entrées, notées ici a et b , peut être décrite comme suit : La sortie est notée:

\$s= a . b\$

la sortie est à 1 lorsque les deux entrées sont à 1.

Cette fonction, ou porte, est ainsi définie en langue naturelle. Il est donc aisé d’écrire sa table de vérité :

a	b	s=a.b
0	0	0
0	1	0
1	0	0
1	1	1

Il faut bien comprendre que dans la notation s=a.b, le point représente la fonction logique ET, non la multiplication arithmétique usuelle. Toutefois, lorsqu’on effectue le produit arithmétique usuel sur les variables logiques décrites en 0 et 1, on obtient le même résultat. Il y a un lien avec le produit arithmétique usuel, mais il ne faut toutefois pas faire la confusion.

La norme internationale et européenne en vigueur :	La norme américaine
norme internationale, IEEE	théoriquement désuète, mais encore beaucoup utilisée par les praticiens :

La norme internationale et européenne en vigueur :

La norme américaine

AFNOR ET

norme internationale, IEEE

american AND

théoriquement désuète, mais encore beaucoup utilisée par les praticiens :

2.3. Porte OU/OR à deux entrées.

Avec les mêmes notations, la sortie est notée:

\$s= a + b\$

La sortie est à 1 si une entrée au moins est à 1.

Là encore, la définition de cette porte élémentaire est donnée en langue naturelle.

La table de vérité est immédiate selon :

a	b	s=a+b
0	0	0
0	1	1
1	0	1
1	1	1

Là aussi, la notation +, dans ce contexte, désigne la fonction logique OU et non l’addition arithmétique usuelle. D’ailleurs, si on fait l’addition arithmétique usuelle sur les entrées en 0 et 1, on ne trouve évidemment pas un résultat correct : 1+1=2 en arithmétique usuelle, tandis que 1+1=1 dans le contexte de la logique binaire.

La norme internationale et européenne en vigueur :	La norme américaine
norme internationale, IEEE	théoriquement désuète, mais encore beaucoup utilisée par les praticiens :

La norme internationale et européenne en vigueur :

La norme américaine

AFNOR OU

norme internationale, IEEE

american OR

théoriquement désuète, mais encore beaucoup utilisée par les praticiens :

2.4. Porte NAND à deux entrées.

En combinant la porte ET*et la porte *NON, on définit une nouvelle fonction logique élémentaire, la porte NON-ET plutôt désignée par son équivalent anglais, la porte NAND. On l’obtient par l’équation:

nand

Pour obtenir sa table de vérité, on commence par faire le ET logique entre les deux entrées, puis on complémente le tout. On obtient :

a	b	a.b	s
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

La norme internationale et européenne en vigueur :	La norme américaine
norme internationale, IEEE

La norme internationale et européenne en vigueur :

La norme américaine

AFNOR NON ET

norme internationale, IEEE

american NAND

2.5. Porte NOR à deux entrées.

De façon analogue, on peut introduire la porte NON-OU ou NOR, comme combinaison de la porte OU et de la porte NON. Elle est ainsi définie par l’équation

nor

Pour obtenir sa table de vérité, on commence par faire le OU logique entre les deux entrées, puis on complémente le tout. On obtient :

a	b	a+b	s
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

La norme internationale et européenne en vigueur :	La norme américaine
norme internationale, IEEE

La norme internationale et européenne en vigueur :

La norme américaine

AFNOR NON OU

norme internationale, IEEE

american NOR

2.6. Porte OU-exclusif ou XOR.

La porte XOR est définie en langue naturelle par la définition suivante : la sortie est à 1 si une entrée et une seule est à 1. On obtient facilement la table de vérité :

\$s= ao+b\$

Pour obtenir sa table de vérité, on commence par faire le OU logique entre les deux entrées, puis on complémente le tout. On obtient :

a	b	s
0	0	0
0	1	1
1	0	1
1	1	0

Cette nouvelle fonction ou porte peut être écrite sous forme d’expression booléenne comme combinaison des fonctions ET, OU et NON. Toutefois, nous verrons ces éléments dans la prochaine partie.

La norme internationale et européenne en vigueur :	La norme américaine
norme internationale, IEEE

La norme internationale et européenne en vigueur :

La norme américaine

AFNOR X OU

norme internationale, IEEE

american XOR

2.7. Travail à faire : Equations logiques

Exercice 1

Donner les équations de S1 et S2

exo1

Rechercher sur un brouillon et vous pouvez ensuite vous aider de la correction.

Ecrire les équations partielles à chaque sortie.

Correction

$ S1=\overline{(a.b).c} $
$ S2=\overline{\overline{(a.b)}.\overline{(b+c)}} $

Exercice 2

Déterminer l’équation du circuit de la figure suivante :
Dresser la table de vérité de ce circuit
Quelle est la fonction logique réalisée et quel est son symbole?

Correction

$ S=\overline{\overline{(a} + \overline{b}} $

a	b	s
0	0	0
0	1	0
1	0	0
1	1	1

La fonction logique réalisée est: le ET logique (AND), son symbole est:

AFNOR ET

Exercice 3

3. Fonctions avancées.

Nous allons voir maintenant des fonctions avancées construites avec des portes élémentaires. Ces fonctions sont utilisées dans les systèmes numériques.

3.1. Travail à faire : Le décodeur

Ce type de décodeur permet de faire correspondre à un code présent en entrée sur n lignes une sortie et une seule active parmi les N = 2ⁿ sorties possibles.

On le désigne aussi par décodeur m lignes vers n lignes.

Pour comprendre le principe d’un tel décodeur, étudions le décodeur 1 parmi 4 ou 2 vers 4:

decodeur1

Remplir la table de vérité ci-dessous sur votre cahier d’exercice.

$ a _1 $	$a_0 $	$S_3 $	$S_2 $	$S_1 $	$S_0 $
0	0
0	1
1	0
1	1

Ecrire les équations de chaque sortie.

Correction

$ a _1 $	$a_0 $	$S_3 $	$S_2 $	$S_1 $	$S_0 $
0	0	0	0	0	1
0	1	0	0	1	0
1	0	0	1	0	0
1	1	1	0	0	0

$ S_0=\overline{a_1}.\overline{a_0}$
$ S_1=\overline{a_1}.a_0$
$ S_2=a_1.\overline{a_0}$
$ S_3=a_1.a_0$

On peut citer comme exemple le double décodeur vendu sous la référence 74LS156 dont le brochage et la table de fonction sont donnés à la figure suivante:

Symbole norme IEEE.
Diagramme logique.
Table de fonctionnement.

le niveau actif des sorties est le 0, pour ce composant, c’est souvent le cas.
Des entrées de validation comme G ou E permettant de sélectionner le circuit ont été rajoutées.

3.2. Travail à faire : Décodeur BCD – 7 segments

Ce type de décodeur permet de convertir le code BCD 4bits à l’entrée pour obtenir à la sortie un code 7 segments permettant de commander un afficheur 7 segments permettant l’écriture de tous les chiffres et aussi d’autres symboles comme le montre la figure suivante :

Afficheur 7 segments

Pour mettre en équation ce type de décodeur, il faut dresser la table de vérité suivante :

table de vérité du décodeur 7 segments.

7st

Compléter le schéma du décodeur :
- Trouver l’équation logique du segment $ a $
- Proposer une réalisation matérielle à l’aide de porte ET et OU
- Simuler le fonctionnement sur circuitverse.org après avoir dupliqué le projet sur votre compte (Se créer un compte si nécessaire). Pour dupliquer le projet, cliquer sur Made with CircuitVerse puis sur fork et enfin Launch Simulator.

3.3. Travail à faire : Le multiplexeur

Un multiplexeur permet de sélectionner une entrée parmi 2ⁿ pour transmettre l’information portée par cette ligne à un seul canal de sortie.

La sélection de l’entrée se fait alors à l’aide de n lignes d’adressage (commande).

Multiplexeur 8 voies, sélectionnées par 3 bits d’adresse.

mux

La technique de commutation des signaux électroniques numériques est très importante et trouve de nombreuses applications comme la téléphonie mobile.

Pour comprendre le principe d’un multiplexeur, étudions le multiplexeur 4 voies suivant:

mux2

Remplir la table de vérité ci-dessous sur votre cahier d’exercice.

$c_1 $	$c_0 $	$S$
0	0
0	1
1	0
1	1

Ecrire les équations de chaque sortie.

Correction

$c_1 $	$c_0 $	$S$
0	0	e_0
0	1	e_1
1	0	e_2
1	1	e_3

$ S=\overline{c_1}.\overline{c_0}.e_0 + \overline{c_1}.c_0.e_1 + c_1.\overline{c_0}.e_2 + c_1.c_0.e_3 $

On peut citer comme exemple le multiplexeur 8 vers 1 vendu sous la référence 74LS151:

Symbole norme IEEE.
Diagramme logique.
Table de fonctionnement.

3.4. Autres fonctions.

Il existe de nombreuses autres fonctions réalisées à partir de ces portes élémentaires comme les démultiplexeurs, les comparateurs, additionneurs…

Il faut bien comprendre qu’elles sont les briques de base de notre technologie actuelle.

Cependant les avancées de la miniaturisation ont permis d’intégrer toujours plus de ces fonctions sur une même puce. Cela a permis la création de microprocesseurs et de "system on chip", mais cela est une autre histoire que nous vérons dans les prochains parcours de formation.

4. Résolutions de projets simples.

Avec les portes logiques élémentaires nous pouvons résoudre quelques projets élèmentaires.

4.1. Exercice expliqué : Serrure d’un coffre

Quatre responsables d’une société (A, B, C et D) peuvent avoir accès à un coffre. Ils possèdent chacun une clé différente et il a été convenu que :

A ne peut ouvrir le coffre que si au moins un des responsables B ou C est présent.
B, C et D ne peuvent l’ouvrir que si au moins deux des autres responsables sont présents.

Donner l’équation logique de la serrure de coffre S.

Démarches:

Dessiner une table de vérité avec 4 entrées (les 4 responsables ou 4 clefs) et une sortie S. Vous devez indiquer toutes les combinaisons 2⁴ =16 dans l’ordre de 0 à 16 en binaire.

D	C	B	A
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

Bien lire le cahier des charges et indiquer pour chaque combinaison des entrées si la sortie S est vrai (mettre un 1 dans la colonne de S) ou fausse mettre un zéro.

Correction

Il faut maintenant sortir l’équation de cette table de vérité. Pour cela, il faut prendre chaque ligne ou S=1 et écrire la combinaison de toutes les entrées en sachant que si cette entrée est à 1 alors on écrit dans l’équation le nom de l’entrée, si elle est à zéro alors on écrit le nom de l’entrée complémentée (barre). On sépare chaque variable d’une même ligne par un point (ET logique).
Si plusieurs 1 se trouvent dans la colonne de S on recommense l’opération en séparant chaque solution par un OU (+).

Correction

$ S=\overline{D}.\overline{C}.B.A + \overline{D}.C.\overline{B}.A + \overline{D}.C.B.A + D.\overline{C}.B.A + D.C.\overline{B}.A + D.C.B.\overline{A} + D.C.B.A $

4.2. Travail à faire : Amplification sonore

Les trois haut-parleurs d’une salle de cinéma (a, b et c) peuvent être branchés sur un amplificateur qui possède deux sorties : la première d’impédance 4 Ω (S4) et la deuxième d’impédance 8 Ω (S8).

Lorsqu’un seul haut-parleur est utilisé, il doit être relié à la sortie de 8 Ω.
Lorsque deux haut-parleurs sont utilisés, ils doivent être reliés tous les deux à la sortie de 4 Ω (ils sont alors montés en parallèle).
Le fonctionnement simultané des trois haut-parleurs est interdit.

Déterminer les équations logiques des sorties S4 et S8 en fonction de a, b et c.

Correction partielle.

Correction

5. Algèbre de Boole avec Python

5.1. Variable booléenne

Une variable booléenne est une variable qui ne peux prendre que deux valeurs : VRAI ou FAUX. En Python, le type d’une telle variable est bool, les deux valeurs possibles sont True ou False. Expressions booléennes

Une expression booléenne a deux valeurs possibles : True ou False. Python attribue à une expression booléenne la valeur False si c’est :

la constante False
la constante None
une séquence ou une collection vide
une donnée numérique de valeur 0. Tout le reste vaut True.

>>> type(False)
<class 'bool'>
>>> type(True)
<class 'bool'>
>>> False
False
>>> bool(None)
False
>>> bool(' ')
True
>>> bool('')
False
>>> bool(0)
False
>>> bool(156.87)
True

5.2. Opérateurs relationnels ou de comparaison

Ce sont les opérateurs == , != , > , >= , < et ⇐.

Table 1. Illustration pour x = 7 et y = 17
Opérateur	Expression	Signification	Valeur
==	x == y	Égal	False
!=	x != y	Non égal	True
>	x > y	Plus grand que	False
<	x < y	Plus petit que	True
>=	x >= y	Plus grand ou égal à	False
⇐	x ⇐ y	Plus petit ou égal à	True
is	x is y	est le même objet	False
is not	x is not y	n’est pas le même objet	True
in	x in [i for i in range(y)]	x est dans la liste [0, .., 16]	True

Cela donne dans le shell de Python :

>>> x=7
>>> y=17
>>> x==y
False
>>> x!=y
True
>>> x>y
False
>>> x>=y
False
>>> x<y
True
>>> x<=y
True
>>> x is y
False
>>> x is not y
True

Illustration avec deux chaînes de caractères

>>>a='encyclopédie1'
>>>b='encyclopédie2'
>>>a==b
False
>>>len(a)
13
>>>a[:12]==b[:12]
True

5.3. Travail à faire : Comparaison de deux entiers

Ecrire un programme qui demande à l’utilisateur de fournir 2 entiers puis :
- Vérifie que les deux entrées sont bien des entiers (réponse :True ou False)
- Indique si les deux entiers sont égaux (réponse :True ou False)
- Indique si le premier entier est plus grand que le second (réponse :True ou False)
- Indique si le second entier est plus grand que le premier (réponse :True ou False)

Correction

a = int(input("a = "))
b = int(input("b = "))

print(f"a est untier : {type(a)==int}")
print(f"b est untier : {type(b)==int}")
print(f"a = b : {a==b}")
print(f"a > b : {a>b}")
print(f"a < b : {a<b}")

5.4. Travail à faire : Bon anniversaire

La structure de test if évalue une expression booléene :

Écrire un programme qui demande votre date d’anniversaire et affiche Bon anniversaire ! si nous sommes à la bonne date ou Bonne journée sinon.

Correction

aujourdhui_str = input("Quel jour somme nous (jj/mm/aaaa)? ")
anniv_str = input("Quel est la date de ton anniversaire (jj/mm/aaaa)? ")

aujourdhui = aujourdhui_str.split("/")
anniv = anniv_str.split("/")

bonanniv = False

if aujourdhui[1] == anniv[1]:
	if aujourdhui[0] == anniv[0]:
		bonanniv = True
if bonanniv:
  print("Bon anniversaire !")
  print(f"Tu as {int(aujourdhui[2])-int(anniv[2])} ans")
else:
	print("Bonne journée")

5.5. Les 3 opérateurs logiques

Les expressions avec un opérateur logique sont évaluées à True ou False.

5.5.1. Le NON (négation, contraire)

$p$ étant un booléen : $ \lnot p = p - 1 $

En Python

p = 1
not p
>>> 0

p = 0
not p
>>> 1

L’opérateur NON p est noté en logique $ \huge \lnot p $

5.5.2. Le OU logique (disjonction)

$p $ et $ q$ étant deux booléens : p or q vaut True si p vaut True. Si p est False, l’expression est évaluée à la valeur booléenne de q
Si p est faux, retourne q, sinon retourne p

En Python

p = 1
q = 1
p or q
>>> 1

p = 1
q = 0
p or q
>>> 1

p = 0
q = 1
p or q
>>> 1

p = 0
q = 0
p or q
>>> 0

$p ~ ou ~ q$ est noté en logique $ \huge p \lor q$

5.5.3. Le ET logique (disjonction)

$p $ et $ q$ étant deux booléens : p and q vaut True si p vaut True et si q vaut True
Si p ou q est faux, retourne faux.
Si p et q est vrai, retourne vrai.

En Python

p = 1
q = 1
p and q
>>> 1

p = 1
q = 0
p and q
>>> 0

p = 0
q = 1
p and q
>>> 0

p = 0
q = 0
p and q
>>> 0

$p ~ et ~ q$ est noté en logique $\huge p \land q$

5.6. Travail à faire : Appartient à un ensemble

Ecrire un programme qui demande à l’utilisateur de fournir 1 entier n, une liste d’entiers successifs entre deux valeurs a et b et une liste d’entiers successifs entre deux valeurs c et d puis :
- Vérifie que $ n \in [a,b] $ (réponse :True ou False)
- Vérifie que $ n \notin [c,d] $ (réponse :True ou False)
- Vérifie que $ n \in [a,b] \cap [c,d] $ (réponse :True ou False)
- Vérifie que $ n \in [a,b] \cup [c,d] $ (réponse :True ou False)

Correction

n = int(input("n = "))
a = int(input("a = "))
b = int(input("b = "))
c = int(input("c = "))
d = int(input("d = "))

l1 = [e for e in range(a,b+1)]
l2 = [e for e in range(c,d+1)]

print(f"{n} appartient à [{a},{b}] : {n in l1}")
print(f"{n} appartient à [{c},{d}] : {n in l2}")
print(f"{n} appartient à [{a},{b}] Union [{c},{d}] : {n in l1 or n in l2}")
print(f"{n} appartient à [{a},{b}] Intersection [{c},{d}] : {n in l1 and n in l2}")

6. Webographie.

https://openclassrooms.com/fr/courses/5439146-faites-vos-premiers-pas-dans-le-monde-de-l-electronique-numerique/exercises/3045 https://irem.univ-reunion.fr/spip.php?article593

\( a _1 \)	\(a_0 \)	\(S_3 \)	\(S_2 \)	\(S_1 \)	\(S_0 \)
0	0
0	1
1	0
1	1

D	C	B	A
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

\(c_1 \)	\(c_0 \)	\(S\)
0	0
0	1
1	0
1	1

D	C	B	A
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

D	C	B	A
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1