Fonctions logiques

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}}\)

Il existe plusieurs façons d’exprimer une fonction logique :

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 comporte un nombre fini de variables booléennes (\(a_1, …, a_n\)), et chaque variable ne peut prendre qu’un nombre fini de valeurs (0 ou 1),

Par conséquent, il existe un nombre fini de combinaisons de ces variables, et donc 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é :

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

pour vérifier une équation

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

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)\)

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

 

L’axe des abscisses (temps) n’a pas besoin d’être à l’échelle pour plupart des chronogrammes : seule la chronologie est importante.

Construire un chronogramme

On construit un chronogramme à partir d’une description d’un comportement attendu (CdCF) ou observé d’un système.

Voici quelques règles à observer :

Schéma logique

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

Exemple :

Règles et syntaxe dans les langages informatiques

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.