Leçons de niveau 11

Logique de base/Introduction

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
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
Icon falscher Titel.svg
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.

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[modifier | modifier le wikicode]

Définitions[modifier | modifier le wikicode]


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 :

Function logic.svg

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 | modifier le wikicode]

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 | modifier le wikicode]

Définitions[modifier | modifier le wikicode]

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

Interrupteur simple.png

Représentation graphique

IEC BUF.svg

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 | modifier le wikicode]

Le complément[modifier | modifier le wikicode]

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
Non schema.svg
Représentation graphique

IEC NOT.svg

ou

NOT ANSI.svg

Table de vérité

Équation logique

F(a) =

ET[modifier | modifier le wikicode]

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
Conmuta2.svg
Représentation graphique

AND IEC.svg

ou

AND ANSI.svg

Table de vérité

Équation logique

L = a . b

OU[modifier | modifier le wikicode]

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
Conmuta.svg
Représentation graphique

OR IEC.svg

ou

OR ANSI.svg

Table de vérité

Équation logique

L = a + b

Conversion d'une table de vérité en forme algébrique élémentaire[modifier | modifier le wikicode]

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 | modifier le wikicode]

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 | modifier le wikicode]

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 | modifier le wikicode]

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 | modifier le wikicode]

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 :

K-map 2x2 empty.svg

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 | modifier le wikicode]

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 | modifier le wikicode]

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 :

K-map 2x2 2,3,4.svg

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 | modifier le wikicode]

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 | modifier le wikicode]

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