Exercice 1 / 8Facile
Propositions et connecteurs
À toi
On note P : « le port 443 est le port par défaut de HTTPS » et Q : « le nombre 300 tient sur un octet ».
Donne la valeur de vérité de P, de Q, puis de chaque proposition composée.
Logique et algèbre de Boole
Les connecteurs et leurs notations
| Connecteur | Logique | Algèbre de Boole | Code (C#, Java, JavaScript) |
|---|---|---|---|
| non | ¬P | a̅ | !a |
| et | P ∧ Q | ab ou a · b | a && b |
| ou (inclusif) | P ∨ Q | a + b | a || b |
| ou exclusif | P ⊕ Q | a ⊕ b | a ^ b |
Le et ne vaut vrai (1) que si les deux le sont ; le ou ne vaut faux (0) que si les deux le sont ; le ou exclusif vaut vrai quand exactement un des deux l'est. L'implication P ⇒ Q n'est fausse que dans un cas : P vraie et Q fausse. En algèbre de Boole, + veut dire « ou » : 1 + 1 = 1.
Construire une table de vérité
Avec n variables, il y a 2ⁿ lignes, rangées comme un comptage en binaire (000, 001, 010… 111). On ajoute une colonne par sous-expression, de l'intérieur vers l'extérieur. Exemple, a ⊕ b = a̅b + ab̅ :
| a | b | a̅b | ab̅ | a̅b + ab̅ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
Les règles de calcul
| Règle | Forme « produit » | Forme « somme » |
|---|---|---|
| Complémentarité | aa̅ = 0 | a + a̅ = 1 |
| Neutre et absorbant | a · 1 = a ; a · 0 = 0 | a + 0 = a ; a + 1 = 1 |
| Idempotence | aa = a | a + a = a |
| Absorption | a(a + b) = a | a + ab = a |
| Absorption du complément | a(a̅ + b) = ab | a + a̅b = a + b |
| Distributivité | a(b + c) = ab + ac | a + bc = (a + b)(a + c) |
La mise en facteur donne la règle clé des simplifications : xy + xy̅ = x(y + y̅) = x.
Les lois de De Morgan
non(a + b) = a̅ b̅ et non(ab) = a̅ + b̅ : quand la barre se casse, le signe change. On les applique de l'extérieur vers l'intérieur : non(ab̅ + c) = non(ab̅) · c̅ = (a̅ + b)c̅. En code, !(x && y) équivaut à !x || !y, et en SQL NOT (p OR q) à NOT p AND NOT q.
De la table à l'expression
Un minterme est un produit des trois variables, chacune barrée si elle vaut 0 sur la ligne : la ligne a = 1, b = 0, c = 1 donne ab̅c. La forme canonique d'une fonction est la somme des mintermes des lignes où elle vaut 1.
Le tableau de Karnaugh à trois variables
a en ligne, bc en colonne dans l'ordre de Gray 00, 01, 11, 10 : deux cases voisines ne diffèrent que d'un bit, et les colonnes 00 et 10 sont voisines elles aussi (le tableau se referme en cylindre).
- On regroupe des 1 voisins par rectangles de 1, 2, 4 ou 8 cases, les plus grands possible, le moins de groupes possible ; une case peut servir deux fois.
- Un groupe donne le produit des variables qui gardent la même valeur dans toutes ses cases (barrée si elle vaut 0). Les autres disparaissent.
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
Ici, un seul groupe de 4 (colonnes 00 et 01) : a et c changent, b vaut 0 partout. La fonction vaut b̅.
Du circuit à l'expression
On écrit la sortie de chaque porte, de l'entrée vers la sortie : ET donne un produit, OU une somme, NON une barre. Une porte OU sur a et b suivie d'une porte NON donne non(a + b) = a̅b̅.
Tu es bloqué ?
Ouvre les indices un par un, le corrigé en dernier.
Indice 1
Un octet va de 0 à 255.
Indice 2
P ∧ Q n'est vraie que si les deux sont vraies ; P ∨ Q n'est fausse que si les deux sont fausses.
Indice 3
P ⇒ Q n'est fausse que dans un cas : P vraie et Q fausse.
Voir le corrigé
Connecte-toi pour voir le corrigé
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données
Pour revoir la notion : chapitre 6 du cours Algèbre de Boole, Algèbre de Boole : définition, règles et propriétés.
Tes réponses
Connecte-toi pour faire cet exercice
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données