Fonctions logiques

Une fonction logique est une fonction mathématique qui opère sur des informations binaires, et fait appel à des variables booléennes.

Soit une fonction logique \(F\) associant à un n-uplet de booléens \((e_0, e_1, … , e_n)\) un autre booléen :

 

\(\large{F:\begin{align}
\{0,1\}^n & \rightarrow\{0,1\}\\
(e_0, e_1, … , e_n) &\mapsto F(e_0, e_1, \ldots , e_n)
\end{align}}\)

 

 

Expression algébrique

On peut représenter une fonction logique par son expression algébrique, en utilisant les opérateurs de l’algèbre de Boole.

Exemples :

  • \(F(a, b, c)= a + b\cdot \overline{a+b}\)
  • \(G(a, b)= a \cdot \overline{b}\)

 

Table de vérité

Une expression logique contenant un nombre fini de variables booléennes (\(a_1, …, a_n\)), et chaque variable ne pouvant prendre qu’un nombre fini de valeurs (0 ou 1), il existe un nombre fini de combinaisons de ces variables, et par conséquent un nombre fini de valeurs pour l’expression. On peut représenter l’ensemble des combinaisons et des valeurs dans un tableau appelé table de vérité :

\(\forall i \in[1,n],\;A=f(a_1, …, a_n)\)
\(a_1\) \(a_2\) \(a_n\)   \(A\)
0 0 0    
0 0 1    
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)    
1 1 1    

 

pour calculer

On peut utiliser une table de vérité pour décomposer les calculs algébriques, en procédant par étapes :

Exemples :

  • \(A=a+\bar b\)
    \(a\) \(b\) \(\bar b\) \(A=a+\bar b\)
    0 0 1 1
    0 1 0 0
    1 0 1 1
    1 1 0 1
  • \(B=\overline{a+b}\cdot c\)
    \(a\) \(b\) \(c\) \(a+b\) \(\overline{a+b}\) \(B=\overline{a+b}\cdot c\)
    0 0 0 0 1 0
    0 0 1 0 1 1
    0 1 0 1 0 0
    0 1 1 1 0 0
    1 0 0 1 0 0
    1 0 1 1 0 0
    1 1 0 1 0 0
    1 1 1 1 0 0

 

Activité
  • Utiliser une table de vérité pour évaluer l’ensemble des valeurs possibles des expressions suivantes :
    • \(X=\overline{(a\cdot b)}+\bar c\)
    • \(Y=\overline{(a+\bar c)}+\overline{(b\cdot c)}\)

 

pour vérifier une équation

On peut aussi utiliser une table de vérité pour vérifier si deux expressions logiques sont équivalentes :

Activité
  • Montrer que \(a+(\bar a\cdot b)=a+b\)
  • Simplifier l’expression \((a+b)\cdot(a+\bar b)\)
  • Utiliser une table de vérité pour démontrer la propriété d’absorption de l’algèbre de Boole.

 

pour établir une expression

On peut encore utiliser une table de vérité pour obtenir une expression logique à partir d’une combinaison (complète ou pas) de valeurs logiques :

Méthode :

  1. Pour une variable de sortie \(S\), on repère la valeur la moins fréquente dans la table :
    Si les 1 sont plus fréquents que les 0, on exprime \(S=…\)

    dans le cas contraire, on exprime \(\bar{S}=…\)

  2. On écrit l’expression sous forme « brute » (ou canonique) :
    somme de produit : \(\_\cdot\_\cdot\_\;+\;\_\cdot\_\cdot\_\;+\;\ldots\;+\;\_\cdot\_\cdot\_\)

    produit de somme : \(\left(\_+\_+\_\right)\cdot\left(\_+\_+\_\right)\cdot\ldots\cdot\left(\_+\_+\_\right)\)

  3. On simplifie à l’aide des propriétés de l’algèbre de Boole.

Exemple :

\(S\) vaut 1 dans 3 cas sur 8, on exprimera donc la valeur de \(S\) :

  • Sous forme de somme de produits :
    • \(S=\bar{a}\cdot\bar{b}\cdot c+\bar{a}\cdot b\cdot \bar{c}+a\cdot b\cdot \bar{c}\)
  • Sous forme de produit de sommes :
    • \(\bar{S}=(a+b+\bar{c})\cdot(a+\bar{b}+c)\cdot(\bar{a}+\bar{b}+c)\)

 

 

 

Activité
  • A partir de la table de vérité de la fonction XOR, déterminer une expression logique à base d’opérateurs élémentaires.
  • Déterminer l’expression logique de \(F\) grâce à la table de vérité ci-dessous :
    \(a\) \(b\) \(c\) \(F(a, b, c)\)
    0 0 0 0
    0 0 1 1
    0 1 0 1
    0 1 1 0
    1 0 0 1
    1 0 1 1
    1 1 0 1
    1 1 1 0
  • Déterminer l’expression logique de V à partir de la table de vérité ci-dessous :
    b h p V
    0 0 0 0
    0 0 1 1
    0 1 0 1
    0 1 1 1
    1 0 0 0
    1 0 1 0
    1 1 0 1
    1 1 1 0

 

Chronogrammes

Un chronogramme est une représentation temporelle des variables d’entrée et des variables de sortie d’un système logique.

Exemple : chronogramme de la fonction ET

 

 

Activité

  • Déterminer la table de vérité, puis l’expression logique de la fonction représentée à l’aide du chronogramme ci-contre.
    a b G
         
         
         
         
  • Déterminer la table de vérité, puis l’expression logique de la fonction représentée à l’aide du chronogramme ci-contre.

 

Schéma logique

Un schéma logique est le schéma d’une association d’opérateurs logiques, décrivant une équation logique.

Activité

Déterminer les expressions logiques de 1Y et 2Y à partir du schéma logique ci-dessous

 


Règles et syntaxe dans les langages informatiques

  Python C/C++
Valeurs
booléennes
True False true false
Opérateurs booléens
NON not a !a
ET a and b a&&b
OU a or b a||b
XOR a^b a!=b
Comparaison
Tous les types peuvent être comparés, une comparaison renvoie toujours un booléen.
égalité ==  
différence !=  
inférieur ou égal <=  
strictement inférieur <  
supérieur ou égal >=  
strictement supérieur >  
     

Remarques :
Python et C++ évaluent les expressions logiques de manière paresseuses (on parle de lazy evaluation). Les opérateurs sont de type court-circuit :

  • OR n’évalue le deuxième argument que si le premier est faux.
  • AND n’évalue le deuxième argument si le premier est vrai.

Exemple, en Python :

  • True or x : est vrai quelle que soit la valeur de x : la valeur de x n’est pas lue dans la mémoire et l’opération or n’est pas effectuée en entier.
  • False and not y : est faux quelle que soit la valeur de y : la valeur de y n’est pas lue dans la mémoire et l’opération and n’est pas effectuée en entier, l’opération not n’est pas effectuée du tout.

 

Activité
  • Ouvrir une console Python et montrer le caractère « lazy » de l’évaluation des expressions booléennes en incluant une erreur dans l’expression booléenne.
    Exemple : a>0 provoque une erreur si la variable a n’est pas définie auparavant.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *