Logique de base/Introduction

Début 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.

Introduction
Icône de la faculté
Chapitre no 1
Leçon : Logique de base
Retour auSommaire
Chap. suiv. :Algèbre de Boole
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Logique de base : Introduction
Logique de base/Introduction
 », n'a pu être restituée correctement ci-dessus.

Fonction logique ou booléenne

modifier

Définitions

modifier


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.

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.


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é

modifier

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

modifier

Définitions

modifier

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 :  ), le ET (noté .) et le OU (noté +).


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é

 

Équation logique

F(a) = a

Autre exemple :   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.



Les opérateurs logiques

modifier
Le complément
modifier

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   ou  

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é

 

Équation logique

F(a) =  

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é

 

Équation logique

L = a . b

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é

 

Équation logique

L = a + b

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

modifier

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

Début d’un principe
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  

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 :  

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

Réduction d'une fonction logique

modifier

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 :  

Puis, nous utiliserons un tableau de Karnaugh.

L'algèbre de Boole

modifier

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 +   = 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  

Début d'une démonstration
Fin de la démonstration

Le tableau de Karnaugh

modifier

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

modifier

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.

2e étape : rassemblement

modifier

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

3e étape : résolution des rassemblements

modifier

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 :  .

  • Avec le rassemblement rouge :

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


La solution finale du tableau est :  

 

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

modifier

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

modifier

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