Outils d'utilisateurs
boole_et_morgan
Différences
Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.
|
boole_et_morgan [2015/06/30 03:55] gbdivers |
boole_et_morgan [2016/07/05 18:53] (Version actuelle) gbdivers |
||
|---|---|---|---|
| Ligne 1: | Ligne 1: | ||
| - | ^ [[nombres_reels|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[virgule_fixe|Chapitre suivant]] ^ | + | ^ [[string|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[complex|Chapitre suivant]] ^ |
| - | ====== Algèbre de Boole ====== | + | ====== [Aller plus loin] L'algèbre de Boole ====== |
| Vous avez vu dans les chapitres précédents comment utiliser les booléens et les opérations de base : ET, OU, NON et OU-EXCLUSIF. En fait, l'utilisation des booléens est plus riche et complexe que cela. Ils sont à la base d'une branche des mathématiques, appelée [[https://fr.wikipedia.org/wiki/Alg%C3%A8bre_de_Boole_(logique)|Algèbre de Boole]], en l'honneur de son créateur, le mathématicien George Boole. | Vous avez vu dans les chapitres précédents comment utiliser les booléens et les opérations de base : ET, OU, NON et OU-EXCLUSIF. En fait, l'utilisation des booléens est plus riche et complexe que cela. Ils sont à la base d'une branche des mathématiques, appelée [[https://fr.wikipedia.org/wiki/Alg%C3%A8bre_de_Boole_(logique)|Algèbre de Boole]], en l'honneur de son créateur, le mathématicien George Boole. | ||
| Ligne 10: | Ligne 10: | ||
| ===== Quelques rappels ===== | ===== Quelques rappels ===== | ||
| - | Pour rappel, un booléen est une variable logique, qui peut prendre deux valeurs. Peu importe comment sont nommées ces valeurs, vous rencontrer parfois : "vrai" et "faux", "oui" et "non", "haut" et "bas", "positif" et "négatif", 0 et 1, "Titi" et "Grosminet", etc. | + | Pour rappel, un booléen est une variable logique, qui peut prendre deux valeurs. Peu importe comment sont nommées ces valeurs, vous rencontrez parfois : "vrai" et "faux", "oui" et "non", "haut" et "bas", "positif" et "négatif", 0 et 1, "Titi" et "Grosminet", etc. |
| Le C++ utilise les mots-clés ''true'' (//vrai//) et ''false'' (//faux//) pour représenter les booléens. | Le C++ utilise les mots-clés ''true'' (//vrai//) et ''false'' (//faux//) pour représenter les booléens. | ||
| - | Certaines valeurs dans la liste ont un sens historique. En particulier, "vrai" et "faux" correspond au fait que les booléens représentent le résultat d'une proposition logique. Par exemple "la terre est plus grosse que le soleil", "l'homme court plus vite que | + | Certaines valeurs dans la liste ont un sens historique. En particulier, "vrai" et "faux" correspond au fait que les booléens représentent le résultat d'une proposition logique. Par exemple "la terre est plus grosse que le soleil". |
| En C++, une proposition logique (que l'on appelle aussi expression logique) sera écrite en utilisant les opérateurs logiques (que vous avez déjà vu) : | En C++, une proposition logique (que l'on appelle aussi expression logique) sera écrite en utilisant les opérateurs logiques (que vous avez déjà vu) : | ||
| Ligne 23: | Ligne 23: | ||
| | NON | Négation | ''!'' | | | NON | Négation | ''!'' | | ||
| - | Pour rappel, voici la table de vérité de ces opérateurs (elle est redonnée pour vous éviter de retourner dans le chapitre [[logique_et_calcul_booleen]], mais il faudra la connaitre par cœur par la suite. Mais pas d’inquiétude, vous la connaîtrez à force de l'utiliser) : | + | Pour rappel, voici la table de vérité de ces opérateurs (elle est redonnée pour vous éviter de retourner dans le chapitre [[logique_et_calcul_booleen]], mais il faudra la connaître par cœur par la suite. Mais pas d’inquiétude, vous la connaîtrez à force de l'utiliser) : |
| ^ ''a'' ^ ''b'' ^ ''!a'' ^ ''a && b'' ^ ''a || b'' ^ | ^ ''a'' ^ ''b'' ^ ''!a'' ^ ''a && b'' ^ ''a || b'' ^ | ||
| Ligne 36: | Ligne 36: | ||
| * NON-ET (//NAND//) correspond à ''!(a && b)'' ; | * NON-ET (//NAND//) correspond à ''!(a && b)'' ; | ||
| * OU-Exclusif (//XOR//) correspond à ''(a && !b) || (!a && b)'' ; | * OU-Exclusif (//XOR//) correspond à ''(a && !b) || (!a && b)'' ; | ||
| - | * NON-OU-Exclusif (//XNOR//) correspond à ''!((a && !b) || (!a && b))''. | + | * NON-OU-Exclusif (//XNOR//) correspond à ''!( (a && !b) || (!a && b) )''. |
| Ces opérateurs n'ont pas d'équivalent direct en C++, mais il est facile de les écrire en utilisant les opérateurs de base du C++. | Ces opérateurs n'ont pas d'équivalent direct en C++, mais il est facile de les écrire en utilisant les opérateurs de base du C++. | ||
| Ligne 42: | Ligne 42: | ||
| ===== Propriétés des opérateurs logiques ===== | ===== Propriétés des opérateurs logiques ===== | ||
| - | L’algèbre de Boole définie un certains nombres de propriétés. Il est assez facile d’écrire un code C++ pour les vérifier. Un code d'exemple est donné pour la première propriété, vous devrais écrire les codes C++ correspondant aux autres propriétés comme exercices. | + | L’algèbre de Boole définit un certain nombre de propriétés. Il est assez facile d’écrire un code C++ pour les vérifier. Un code d'exemple est donné pour la première propriété, vous devrez écrire les codes C++ correspondant aux autres propriétés comme exercice. |
| ==== Ordre d’évaluation ==== | ==== Ordre d’évaluation ==== | ||
| Ligne 49: | Ligne 49: | ||
| * les opérateurs sont évalués dans l'ordre : NÉGATION, ET puis OU ; | * les opérateurs sont évalués dans l'ordre : NÉGATION, ET puis OU ; | ||
| - | * lorsque les opérateurs sont identiques, ils sont évalues de gauche a droite. | + | * lorsque les opérateurs sont identiques, ils sont évalués de gauche à droite. |
| Par exemple : | Par exemple : | ||
| Ligne 75: | Ligne 75: | ||
| </code> | </code> | ||
| - | Ces règles s'appliquent aux opérateurs logiques. Vous avez déjà vu que les opérateurs arithmétiques ont aussi un ordre d’évaluation spécifique (multiplication et division avant addition et soustraction). Vous verrez par le suite les règles d’évaluation pour l'ensemble des opérateurs existant en C++. | + | Ces règles s'appliquent aux opérateurs logiques. Vous avez déjà vu que les opérateurs arithmétiques ont aussi un ordre d’évaluation spécifique (multiplication et division avant addition et soustraction). Vous verrez par la suite les règles d’évaluation pour l'ensemble des opérateurs existant en C++. |
| Dans tous les cas, il est plus simple et moins ambiguë d'utiliser les parenthèses pour exprimer clairement une expression. | Dans tous les cas, il est plus simple et moins ambiguë d'utiliser les parenthèses pour exprimer clairement une expression. | ||
| Ligne 96: | Ligne 96: | ||
| ==== Complémentarité ==== | ==== Complémentarité ==== | ||
| - | Dans certains cas, l'utilisation de l’opérateur négation peut se simplifier. Le cas le plus simple est la double-négations, qui donne le même résultat : | + | Dans certains cas, l'utilisation de l’opérateur négation peut se simplifier. Le cas le plus simple est la double-négation qui donne le même résultat : |
| <code cpp> | <code cpp> | ||
| Ligne 123: | Ligne 123: | ||
| ==== Idempotence ==== | ==== Idempotence ==== | ||
| - | La première notion est relativement simple : appliquer un opérateur en utilisant deux fois la même valeur est équivalent à utiliser directement la variable. Si on regarde le tableau de vérité précédent, on peut remarquer que lorsque ''a'' et ''b'' sont égaux, alors le résultat des opérations logiques aura la même valeur : | + | La première notion est relativement simple : appliquer un opérateur en utilisant deux fois la même valeur est équivalent à utiliser directement la variable. Si on regarde la table de vérité précédente, on peut remarquer que lorsque ''a'' et ''b'' sont égaux, alors le résultat des opérations logiques aura la même valeur : |
| | ''a'' | ''b'' | ''a && b'' | ''a || b'' | | | ''a'' | ''b'' | ''a && b'' | ''a || b'' | | ||
| Ligne 146: | Ligne 146: | ||
| ^ 1 ^ 1 ^ 1 ^ | ^ 1 ^ 1 ^ 1 ^ | ||
| - | Pour l'opérateur OU, ça sera la valeur ''false'' qui est l'élément neutre : | + | Pour l'opérateur OU, ça sera faux qui est l'élément neutre : |
| | ''a'' | ''b'' | ''a || b'' | | | ''a'' | ''b'' | ''a || b'' | | ||
| Ligne 159: | Ligne 159: | ||
| $$ \text{A} ~ \text{OU} ~ \text{Faux} ~ = ~ \text{A} $$ | $$ \text{A} ~ \text{OU} ~ \text{Faux} ~ = ~ \text{A} $$ | ||
| - | Ces relations permettent de simplifier une expression. Si vous démontrez qu'une opérande est toujours vraie ou toujours faux, vous pouvez simplifier certaines expressions, en supprimant l'opérateur et l'opérande. | + | Ces relations permettent de simplifier une expression. Si vous démontrez qu'une opérande est toujours vraie ou toujours fausse, vous pouvez simplifier certaines expressions en supprimant l'opérateur et l'opérande. |
| ==== Absorption ==== | ==== Absorption ==== | ||
| - | L'absorption peut être considéré comme l'inverse de l'élément neutre : si ''a'' est faux, le résultat de l'opérateur ET sera toujours faux. | + | L'absorption peut être considérée comme l'inverse de l'élément neutre : si ''a'' est faux, le résultat de l'opérateur ET sera toujours faux. |
| | ''a'' | ''b'' | ''a && b'' | | | ''a'' | ''b'' | ''a && b'' | | ||
| Ligne 184: | Ligne 184: | ||
| $$ \text{A} ~ \text{OU} ~ \text{Vrai} ~ = ~ \text{Vrai} $$ | $$ \text{A} ~ \text{OU} ~ \text{Vrai} ~ = ~ \text{Vrai} $$ | ||
| - | Cette propriété est particulièrement intéressant en C++, puisque cela permet de ne pas évaluer une expression, si possible. Comme expliqué dans le chapitre [[logique_et_calcul_booleen]], le C++ utilise la //lazy evaluation// lorsque c'est possible. Pour évaluer les expressions suivantes : | + | Cette propriété est particulièrement intéressante en C++, puisque cela permet de ne pas évaluer une expression, si possible. Comme expliqué dans le chapitre [[logique_et_calcul_booleen]], le C++ utilise la //lazy evaluation// (évaluation paresseuse) lorsque c'est possible. Pour évaluer les expressions suivantes : |
| $$ \text{A} ~ \text{ET} ~ \text{Expression complexe} $$ | $$ \text{A} ~ \text{ET} ~ \text{Expression complexe} $$ | ||
| $$ \text{B} ~ \text{OU} ~ \text{Expression complexe} $$ | $$ \text{B} ~ \text{OU} ~ \text{Expression complexe} $$ | ||
| - | Si ''A'' est faux, le résultat sera toujours faux, quelque soit la valeur de l'expression complexe. Le programme C++ va donc évaluer la valeur de ''A'' dans un premier temps. Si cette valeur est faux, le programme n'évaluera pas l'expression complexe et retournera directement faux. De même, si ''B'' est vrai, le programme n'évaluera pas l'expression complexe et retournera directement vrai. | + | Si ''A'' est //faux//, le résultat sera toujours //faux//, quelle que soit la valeur de l'expression complexe. Le programme C++ va donc évaluer la valeur de ''A'' dans un premier temps. Si cette valeur est //faux//, le programme n'évaluera pas l'expression complexe et retournera directement //faux//. De même, si ''B'' est //vrai//, le programme n'évaluera pas l'expression complexe et retournera directement //vrai//. |
| ==== Commutativité ==== | ==== Commutativité ==== | ||
| - | La commutativité signifie que l'on peut changer l'ordre des valeurs (opérandes) dans une expression, sans changer le résultat. Cette propriété est valide pour les opérateurs binaires (qui prennent deux opérandes, donc les opérateurs ET et OU), mais pas pour NON (opérateur unaire, qui prend qu'une opérande). | + | La commutativité signifie que l'on peut changer l'ordre des valeurs (opérandes) dans une expression, sans changer le résultat. Cette propriété est valide pour les opérateurs binaires (qui prennent deux opérandes, donc les opérateurs ET et OU), mais pas pour NON (opérateur unaire, qui ne prend qu'une opérande). |
| En utilisant une écriture plus formelle, on peut donc écrire : | En utilisant une écriture plus formelle, on peut donc écrire : | ||
| Ligne 226: | Ligne 225: | ||
| </code> | </code> | ||
| - | **Exercice** : écrire les trois autres lignes, correspondant a A vrai et B faux, a A faux et B vrai et a A vrai et B vrai. | + | **Exercice** : écrire les trois autres lignes, correspondant à A vrai et B faux, à A faux et B vrai et à A vrai et B vrai. |
| ==== Associativité ==== | ==== Associativité ==== | ||
| - | Comme vu précédemment, les opérateurs identiques sont évalués de gauche a droite. En fait, les opérateurs logiques sont associatifs et l'ordre d’évaluation ne change pas le résultat : | + | Comme vu précédemment, les opérateurs identiques sont évalués de gauche à droite. En fait, les opérateurs logiques sont associatifs et l'ordre d’évaluation ne change pas le résultat : |
| <code cpp> | <code cpp> | ||
| Ligne 238: | Ligne 237: | ||
| </code> | </code> | ||
| - | **Exercice** : compléter les tables de vérité correspondantes : | + | **Exercice** : compléter les tables de vérité suivantes : |
| ^ ''a'' ^ ''b'' ^ ''c'' ^ ''a && b'' ^ ''(a && b) && c'' ^ ''b && c'' ^ ''a && (b && c)'' ^ | ^ ''a'' ^ ''b'' ^ ''c'' ^ ''a && b'' ^ ''(a && b) && c'' ^ ''b && c'' ^ ''a && (b && c)'' ^ | ||
| | 0 | 0 | 0 | ... | ... | ... | ... | | | 0 | 0 | 0 | ... | ... | ... | ... | | ||
| + | | ... | ... | ... | ... | ... | ... | ... | | ||
| ^ ''a'' ^ ''b'' ^ ''c'' ^ ''a || b'' ^ ''(a || b) || c'' ^ ''b || c'' ^ ''a || (b || c)'' ^ | ^ ''a'' ^ ''b'' ^ ''c'' ^ ''a || b'' ^ ''(a || b) || c'' ^ ''b || c'' ^ ''a || (b || c)'' ^ | ||
| | 0 | 0 | 0 | ... | ... | ... | ... | | | 0 | 0 | 0 | ... | ... | ... | ... | | ||
| + | | ... | ... | ... | ... | ... | ... | ... | | ||
| ==== Distributivité ==== | ==== Distributivité ==== | ||
| Ligne 257: | Ligne 257: | ||
| </code> | </code> | ||
| - | Note : il est classique de noté l'opérateur ET comme une multiplication et l'opérateur OU comme une addition, du fait de leur similarité. Avec cette écriture, les opérateurs logiques deviennent : | + | Note : il est classique de noter l'opérateur ET comme une multiplication et l'opérateur OU comme une addition, du fait de leur similarité. Avec cette écriture, les opérateurs logiques deviennent : |
| $$ ( \text{A} ~ \text{OU} ~ \text{B} ) ~ \text{ET} ~ \text{C} \iff ( \text{A} ~ + ~ \text{B} ) ~ \times ~ \text{C} $$ | $$ ( \text{A} ~ \text{OU} ~ \text{B} ) ~ \text{ET} ~ \text{C} \iff ( \text{A} ~ + ~ \text{B} ) ~ \times ~ \text{C} $$ | ||
| - | Sous cette forme, on reconnait plus facilement la propriété : "le produit d'une somme est égal à la somme des produits". Celle-ci est connu sous le nom de "distributivité de la multiplication par rapport à l'addition" et permet d'écrire : | + | Sous cette forme, on reconnaît plus facilement la propriété : "le produit d'une somme est égal à la somme des produits". Celle-ci est connue sous le nom de "distributivité de la multiplication par rapport à l'addition" et permet d'écrire : |
| $$ ( \text{A} ~ + ~ \text{B} ) ~ \times ~ \text{C} \iff \text{A} ~ \times ~ \text{C} ~ + ~ \text{B} ~ \times ~ \text{C} $$ | $$ ( \text{A} ~ + ~ \text{B} ) ~ \times ~ \text{C} \iff \text{A} ~ \times ~ \text{C} ~ + ~ \text{B} ~ \times ~ \text{C} $$ | ||
| - | Si on revient aux opérateur logiques, on obtient finalement : | + | Si on revient aux opérateurs logiques, on obtient finalement : |
| $$ \text{A} ~ \times ~ \text{C} ~ + ~ \text{B} ~ \times ~ \text{C} \iff ( \text{A} ~ \text{ET} ~ \text{C} ) ~ \text{OU} ~ ( \text{B} ~ \text{ET} ~ \text{C} ) $$ | $$ \text{A} ~ \times ~ \text{C} ~ + ~ \text{B} ~ \times ~ \text{C} \iff ( \text{A} ~ \text{ET} ~ \text{C} ) ~ \text{OU} ~ ( \text{B} ~ \text{ET} ~ \text{C} ) $$ | ||
| Ligne 277: | Ligne 277: | ||
| ^ ''a'' ^ ''b'' ^ ''c'' ^ ''a && b'' ^ ''(a && b) || c'' ^ ''a || c'' ^ ''b || c'' ^ ''(a || c) && (b || c)'' ^ | ^ ''a'' ^ ''b'' ^ ''c'' ^ ''a && b'' ^ ''(a && b) || c'' ^ ''a || c'' ^ ''b || c'' ^ ''(a || c) && (b || c)'' ^ | ||
| | 0 | 0 | 0 | ... | ... | ... | ... | ... | | | 0 | 0 | 0 | ... | ... | ... | ... | ... | | ||
| + | | ... | ... | ... | ... | ... | ... | ... | | ||
| ^ ''a'' ^ ''b'' ^ ''c'' ^ ''a || b'' ^ ''(a || b) && c'' ^ ''a && c'' ^ ''b && c'' ^ ''(a && c) || (b && c)'' ^ | ^ ''a'' ^ ''b'' ^ ''c'' ^ ''a || b'' ^ ''(a || b) && c'' ^ ''a && c'' ^ ''b && c'' ^ ''(a && c) || (b && c)'' ^ | ||
| | 0 | 0 | 0 | ... | ... | ... | ... | ... | | | 0 | 0 | 0 | ... | ... | ... | ... | ... | | ||
| + | | ... | ... | ... | ... | ... | ... | ... | | ||
| ===== Lois de De Morgan ===== | ===== Lois de De Morgan ===== | ||
| Ligne 293: | Ligne 295: | ||
| ===== Exercices ===== | ===== Exercices ===== | ||
| - | 1. Ecrire les opérateurs NON-ET, NON-OU, OU-Exclusif et NON-OU-Exclusif avec les opérateurs de base du C++. | ||
| - | 2. Ecrire tous les opérateurs en utilisant uniquement l'opérateur NON-ET. | ||
| - | 3. Ecrire un additionner à un bit. Un additionner va prendre deux valeurs booléennes et retourne la somme et la retenu de ces valeurs, suivant la table de vérité suivante : | + | * Écrire les opérateurs NON-ET, NON-OU, OU-Exclusif et NON-OU-Exclusif avec les opérateurs de base du C++. |
| + | * Écrire tous les opérateurs en utilisant uniquement l'opérateur NON-ET. | ||
| + | * Écrire un additionneur à un bit. Un additionneur va prendre deux valeurs booléennes et retournera la somme et la retenue de ces valeurs, suivant la table de vérité suivante : | ||
| - | ^ a ^ b ^ Somme ^ Retenu ^ | + | ^ a ^ b ^ Somme ^ Retenue ^ |
| - | | 0 | 0 | 0 | 0 | | + | | 0 | 0 | 0 | 0 | |
| - | | 0 | 1 | 1 | 0 | | + | | 0 | 1 | 1 | 0 | |
| - | | 1 | 0 | 1 | 0 | | + | | 1 | 0 | 1 | 0 | |
| - | | 1 | 1 | 0 | 1 | | + | | 1 | 1 | 0 | 1 | |
| __ faire un schéma __ | __ faire un schéma __ | ||
| - | 4. Ecrire un additionner quatre bits. | ||
| - | |||
| - | 5. Ecrire un multiplicateur 4x4 bits. | ||
| - | 6. Ecrire un multiplexeur. | + | * Écrire un additionneur quatre bits. |
| + | * Écrire un multiplicateur 4x4 bits. | ||
| + | * Écrire un multiplexeur. | ||
| - | ^ [[nombres_reels|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[virgule_fixe|Chapitre suivant]] ^ | + | ^ [[string|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[complex|Chapitre suivant]] ^ |
| - | {{tag> Cours C++}} | ||
boole_et_morgan.1435629331.txt.gz · Dernière modification: 2015/06/30 03:55 par gbdivers
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante : CC Attribution-Noncommercial-Share Alike 3.0 Unported
