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
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 :
- 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}=…\)
- 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)\)
- 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 :
- Il est physiquement impossible que deux entrées indépendantes changent simultanément :
- Chaque changement d’une sortie (effet) doit être provoqué par le changement d’une entrée (cause) :
Schéma logique
Un schéma logique est le schéma d’une association d’opérateurs logiques, décrivant une expression logique.
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.