Logique de base/Introduction

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Dans cette leçon, nous allons définir la notion de fonction logique (ou fonction booléenne) avec ses opérateurs et pour finir, nous introduirons les méthodes permettant la simplification de ce type de fonction.

Fonction logique ou booléenne

Définitions

Définition

On appelle valeur logique ou valeur booléenne ou encore valeur binaire toute valeur notée par deux symboles. On choisit souvent les couples de valeurs suivants : {0,1}, {vrai, faux}, {true, false}. On utilisera essentiellement {0,1} par la suite.

Exemple : un interrupteur peut être ouvert ou fermé. Son état peut donc être qualifié de booléen.

Cette définition nous permet de définir la notion de variable booléenne.

Définition

Une variable booléenne (ou variable logique) est une grandeur représentée par un nom et pouvant prendre des valeurs booléennes.

Il n'y a aucune règle sur le choix des noms des variables booléennes.

Exemple : donnez un nom à un interrupteur et il devient une variable booléenne.

Il est grand temps de définir maintenant l’objet de nos études, les fonctions logiques.

Définition

Une fonction logique est une fonction d'une ou plusieurs variables booléennes. Les variables sur lesquelles porte la fonction seront appelées variables d'entrées (ou simplement entrées). L'affectation d'une fonction permet quant à elle de définir une variable de sortie.

Par exemple, dans l'écriture y=F(a,b), y est une sortie et a et b sont des entrées. On pourra ainsi représenter une fonction par un schéma.

Exemple : reprenons l'interrupteur qui nous a servi de guide et ajoutons lui une ampoule. L'état de l'ampoule peut aussi être booléen allumé ou éteint. L'entrée est donc l'interrupteur et la sortie la lampe. Vous avez ainsi réalisé une fonction logique entre un interrupteur (entrée) et une ampoule (sortie).

Exemple 2 : si nous voulons réaliser une fonction logique plus complexe, vous pouvez chercher dans votre maison deux interrupteurs montés en va et vient. Avec ces deux interrupteurs, vous avez donc quatre états possibles et une lampe qui en possède toujours deux (états).

Une fonction sera représentée par un dessin comme ci-dessous :

Cette fonction comporte deux entrées a et b et une sortie y. Cette distinction entre entrées et sorties est bien visible dans le schéma ci-dessus.

Représentation sous forme d'une table de vérité

Comment savoir ce que fait une fonction booléenne ? Tout simplement en énumérant toutes les possibilités sur ses entrées et en regardant la sortie correspondante : c’est ce que l’on appelle une table de vérité si l’on représente cette information dans un tableau. Contrairement aux fonctions rencontrées en analyse, fonctions sur des nombres réels, on va s'intéresser à des fonctions logiques sur une, deux, trois (ou plus) variables.

Avec cette table on connaît parfaitement la fonction F. Voici un exemple.

Exemple :

Table de vérité

Entrées		Sortie
a	b	y
0	0	0
0	1	0
1	0	0
1	1	1

Cette table de vérité comporte quatre lignes (après les entêtes) car elle spécifie une fonction de deux variables. Il en sera toujours ainsi pour toutes les fonctions de deux variables. Une autre manière de dire les choses, c’est que la partie entrée (ou partie gauche ou encore partie SI) est complètement établie à partir du moment où l’on connaît le nombre de variables de la fonction (le nombre d'entrées pour nous). Par exemple, avec trois entrées une table de vérité composée aura 8 lignes :

Entrées			Sortie
a	b	c	y
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Représentation sous forme algébrique

Définitions

Chaque fonction booléenne peut être écrite sous forme algébrique à l'aide de trois opérateurs, le complément (noté avec une barre au-dessus : ${\bar {q}}$), le ET (noté .) et le OU (noté +).

Définition

On appelle forme algébrique ou expression algébrique toute écriture utilisant les opérateurs complément, OU et ET précédemment cités.

Par exemple : F(a)= a est la fonction de base la plus simple puisque la logique de sortie est égale à la logique de l'entrée. On nomme cette fonction : la fonction OUI. Cette fonction représente le fonctionnement d'un circuit avec comme entrée l'interrupteur et la sortie la lampe.

Schéma électrique	Représentation graphique
Table de vérité ${\begin{array}{|c||c|}a&L\\\hline 0&0\\1&1\\\end{array}}$	Équation logique F(a) = a

Autre exemple : ${\bar {a}}.b+((a+{\bar {b}}).(a+b))$ est aussi une expression algébrique mais pour le moment, vous ne savez pas très bien ce qu'elle représente mais c’est normal.

Remarque

Il existe une autre notation en mathématique des opérateurs logiques (notation utilisée dans certains articles WIKI) :

• OU (noté $A\lor B$) tandis que notre notation sera A + B
• ET (noté $A\land B$) tandis que notre notation sera A . B ou même AB
• complément logique (noté $\neg {A}$) tandis que notre notation sera ${\bar {A}}$.

Remarque

Il existe encore une autre notation en informatique des opérateurs logiques qui est plus simple à écrire avec un clavier d'ordinateur :

• OU est noté A

Les opérateurs logiques

Le complément

La fonction NON (NOT en anglais) est un opérateur logique de l'algèbre de Boole. À un opérande, qui peut avoir la valeur VRAI ou FAUX, il associe un résultat qui a lui-même la valeur inverse de celle de l'opérande.

La fonction peut s'écrire $F(a)={\bar {a}}$ ou $L={\bar {a}}$

La fonction de base NON est la complémentaire de la fonction OUI. La logique de sortie est égale à l'inverse de la logique de l'entrée.

Schéma électrique	Représentation graphique ou
Table de vérité ${\begin{array}{|c||c|}a&L\\\hline 0&1\\1&0\\\end{array}}$	Équation logique F(a) = ${\overline {a}}$

ET

La fonction ET (AND en anglais) est un opérateur logique de l'algèbre de Boole. À deux opérandes, qui peuvent avoir chacun la valeur VRAI ou FAUX, il associe un résultat qui a lui-même la valeur VRAI seulement si les deux opérandes ont la valeur VRAI.

La fonction ET s'écrit : F(a,b) = a . b qui est équivalent à L = a . b ou encore L = ab

Vous pouvez voir ci-dessous les différentes représentations de cette fonction.

Schéma électrique	Représentation graphique ou
Table de vérité ${\begin{array}{|c|c||c|}a&b&L\\\hline 0&0&0\\0&1&0\\1&0&0\\1&1&1\\\end{array}}$	Équation logique L = a . b

OU

La fonction OU ou OU inclusif (OR en anglais) est un opérateur logique de l'algèbre de Boole. À deux opérandes, qui peuvent avoir chacun la valeur VRAI ou FAUX, il associe un résultat qui a lui-même la valeur VRAI seulement si au moins un des deux opérandes a la valeur VRAI.

La fonction OU s'écrit : F(a,b) = a + b ou encore L = a + b

Vous pouvez voir ci-dessous les différentes représentations de cette fonction.

Schéma électrique	Représentation graphique ou
Table de vérité ${\begin{array}{|c|c||c|}a&b&L\\\hline 0&0&0\\0&1&1\\1&0&1\\1&1&1\\\end{array}}$	Équation logique L = a + b

Conversion d'une table de vérité en forme algébrique élémentaire

Pour obtenir une fonction sous forme algébrique à partir d'une table de vérité :

Début d’un principe

Principe

On cherche les 1 dans la partie sortie de la table de vérité (partie droite) et à chaque 1 trouvé correspond un terme réalisé à l'aide de la partie entrée de cette même table. Chacun des termes est alors séparé par un OU (+). Les termes sont des ET entre les variables (complémentées si elles sont à 0 et non complémentées si elles sont à 1). On obtient une forme élémentaire de notre fonction.

Fin du principe

Exemple : dans la table de vérité de la fonction ET, il y a un seul 1 dans la partie sortie, donc un seul terme formé par a . b car il y a un 1 pour chacune des variables (d'entrée).

Prenons un autre exemple.

Exemple :

Autre table de vérité

Entrées		Sortie
a	b	y
0	0	0
0	1	1
1	0	1
1	1	1

C'est la table de vérité d'une fonction qui s’appelle OU inclusif. L'équation correspondante est $y={\bar {a}}.b+a.{\bar {b}}+a.b$

Vous avez probablement remarqué que cette fonction a la même table de vérité que la fonction OU. Le OU inclusif et le OU sont en réalité la même fonction. Comme en mathématique, une fonction logique peut prendre plusieurs formes : $a+b={\bar {a}}.b+a.{\bar {b}}+a.b$

La forme élémentaire d'une fonction logique peut bien souvent être réduite.

Réduction d'une fonction logique

Dérivée des mathématiques, l'algèbre de Boole permet de réduire les équations logiques pour éviter de prendre trop de place dans les mémoires d'automates programmables ou pour simplifier l'écriture des conditions logiques dans les programmes informatiques. Cependant également comme en mathématique, la résolution d'équation avec des dizaines de variables n’est pas toujours facile pour le commun des mortelles ainsi des astuces ont été inventées pour faciliter ce travail comme avec les tableaux de Karnaugh.

Nous allons démontrer avec l'algèbre de Boole que : $FonctionOU(a,b)={\bar {a}}.b+a.{\bar {b}}+a.b=a+b$

Puis, nous utiliserons un tableau de Karnaugh.

L'algèbre de Boole

Par exemple pour réduire la fonction élémentaire du OU inclusif, l'algèbre de Boole nous offre, entre autres :

• les propriétés de la somme :
  • a + a = a
  • a + ${\bar {a}}$ = 1
• la propriété de la distributivité : a . ( b + c ) = a.b + a.c
• la propriété de la commutativité : a + b = b + a
• etc.(voir la leçon suivante pour voir les propriétés de l’algèbre de Boole)

Avec ces quatre propriétés, nous pouvons démontrer que $a+b={\bar {a}}.b+a.{\bar {b}}+a.b$

Début d'une démonstration

Démonstration

La propriété de la somme, nous permet d'écrire que :

${\begin{aligned}L&={\bar {a}}.b+a.{\bar {b}}+a.b\\&={\bar {a}}.b+a.{\bar {b}}+a.b+a.b\\&={\bar {a}}.b+a.b+a.{\bar {b}}+a.b\end{aligned}}$

Puis, la propriété de la distributivité va nous permettre de factoriser la formule :

${\begin{aligned}L&=(a+{\bar {a}}).b+a.({\bar {b}}+b)\end{aligned}}$

Sachant que $a+{\bar {a}}=1$ et $a.1=a$ donc :

${\begin{aligned}L&=(a+{\bar {a}}).b+a.({\bar {b}}+b)\\&=(1).b+a.(1)\\&=b+a\end{aligned}}$

Et la propriété de la commutativité, pour terminer :

${\begin{aligned}L&=b+a\\&=a+b\end{aligned}}$

CQFD : $a+b={\bar {a}}.b+a.{\bar {b}}+a.b$

Fin de la démonstration

Le tableau de Karnaugh

Un tableau de Karnaugh (développé par Maurice Karnaugh) sert à simplifier des équations logiques ou à trouver l'équation logique correspondant à une table de vérité. La méthode utilisée est graphique et simple.

1er étape : construire le tableau

Reprenons notre exemple avec la fonction OU.

Les variables se répartissent sur les 2 côtés du tableau.

Exemple : Si l’on a 2 variables a et b :

• a est placé en colonne,
• b sera placé en ligne,

ce qui donne le tableau suivant :

De ce fait, on se retrouve avec 4 cases vides, correspondant aux 4 combinaisons possibles de 2 variables pouvant prendre 2 états.

Avec notre exemple, Voilà ce que donne le tableau rempli :

F		a
		0	1
b	0	0	1
	1	1	1

À partir du moment où le tableau est correctement rempli, on peut commencer à résoudre le système.

2^e étape : rassemblement

Le but est très simple. Il faut effectuer des regroupements de 1 ou de X ; par paquets de 1, 2, 4 ,8, 16....2^n. Ces regroupements doivent être des rectangles ou des carrés, jamais de travers, et les plus grands possible sachant qu'un élément déjà utilisé peut être repris. Attention : ne pas oublier que le tableau de Karnaugh est écrit sur un cylindre.

Avec notre exemple : on peut faire ces 2 rassemblements :

F		a
		0	1
b	0	0	1
	1	1	1

F		a
		0	1
b	0	0	1
	1	1	1

3^e étape : résolution des rassemblements

Maintenant que l’on a pu, avec différentes sélections, prendre tous les 1, on essaie de résoudre les rassemblements. Pour cela, il faut que les variables participants au rassemblement concerné ne changent pas.

• Avec le rassemblement vert :

La variable a est toujours à 1
La solution verte donne : $a$.

• Avec le rassemblement rouge :

La variable b est toujours à 1
La solution rouge donne : $b$.

La solution finale du tableau est : $F=a+b$

Nous savons que c’est effectivement la fonction réduite au maximum.

Cet exemple avait pour but de vous faire découvrir cette méthode mais il vous faudra lire la leçon de la méthode pour savoir réellement l'appliquer. L'algèbre de Boole est souvent largement suffisant pour les fonctions de deux variables mais à partir de 3 variables les tableaux de Karnaugh deviennent très utiles.

Conclusion

Dans cette leçon, vous avez pu :

• découvrir les fonctions logiques,
• convertir une table de vérité en une formule algébrique élémentaire,
• et réduire la forme d'une fonction très simple avec l’algèbre de Boole et les tableaux de Karnaugh.

Dans les leçons suivantes, nous reviendrons sur l’algèbre de Boole et les tableaux de Karnaugh pour apprendre à les utiliser.

Références

Électronique numérique : Fonctions logiques élémentaires