Mathématiques pour l'informatique 201-N11 • Cégep à Montréal

Fiche de révision : logique booléenne et mathématique (201-N11)

La logique est le premier cours où une phrase française et une expression booléenne doivent dire exactement la même chose. « S'il pleut, je prends mon parapluie » ne dit rien de ce qui se passe quand il ne pleut pas, et c'est précisément ce que la table de vérité rend visible.

Cette fiche rassemble les gestes qui rapportent : nier une implication sans en fabriquer une autre, appliquer De Morgan jusqu'au bout, choisir entre table de vérité et lois de Boole, et grouper dans un Karnaugh sans inventer de rectangle.

Le fil du chapitre

Toute la logique du cours tient dans le sens exact de l'implication : elle n'est fausse que dans un seul cas, sa contraposée lui est équivalente, et sa réciproque n'a aucun rapport avec elle.

Ce chapitre fait partie de Mathématiques pour l'informatique, 201-N11

L'essentiel

L'implication n'est fausse que dans un seul cas

• $p\Rightarrow q$ est fausse UNIQUEMENT sur la ligne $p=1$ , $q=0$ . Partout ailleurs elle est vraie.
• En particulier, elle est vraie à vide dès que $p$ est faux : « si $2+2=5$ alors la Lune est carrée » est une implication VRAIE.
• $p\Rightarrow q=\lnot p\lor q$ , et donc $\lnot(p\Rightarrow q)=p\land\lnot q$ : la négation d'une implication n'est PAS une implication.
• Une table de vérité à $n$ propositions compte $2^{n}$ lignes, et il existe $2^{2^{n}}$ fonctions booléennes de $n$ variables.

La seule ligne où l'implication est fausse est celle où l'hypothèse est vraie et la conclusion fausse ; les trois autres la rendent vraie.

Retenir la ligne fausse plutôt que les trois vraies : c'est la seule à mémoriser, et toutes les autres questions du chapitre s'y ramènent.

Contraposée, réciproque, négation

• Contraposée de $p\Rightarrow q$ : $\lnot q\Rightarrow\lnot p$ . Elle lui est TOUJOURS équivalente, et c'est ce qui autorise la démonstration par contraposition.
• Réciproque : $q\Rightarrow p$ . Elle n'a AUCUN lien de vérité avec l'originale : les deux peuvent être vraies, fausses, ou l'une sans l'autre.
• Négation : $p\land\lnot q$ . Elle affirme l'hypothèse et nie la conclusion, sans aucune flèche.

Le test rapide : la contraposée inverse ET nie les deux membres, la réciproque ne fait qu'inverser. Une seule des deux est équivalente à l'énoncé de départ.

Les lois de Boole qui servent vraiment

• De Morgan : $\overline{AB}=\overline{A}+\overline{B}$ et $\overline{A+B}=\overline{A}\,\overline{B}$ . La barre se distribue en CHANGEANT l'opérateur.
• Distributivité double : $A(B+C)=AB+AC$ , mais aussi $A+BC=(A+B)(A+C)$ , qui n'a pas d'équivalent en algèbre ordinaire.
• Absorption : $A+AB=A$ et $A(A+B)=A$ . Idempotence : $AA=A$ et $A+A=A$ .
• Complément : $A+\overline{A}=1$ et $A\overline{A}=0$ .

L'absorption est la loi la moins utilisée et la plus rentable : elle supprime un terme entier d'un coup, là où la factorisation ne fait que réorganiser.

Quantificateurs et formes normales

• $\lnot(\forall x,\ P(x))=\exists x,\ \lnot P(x)$ et $\lnot(\exists x,\ P(x))=\forall x,\ \lnot P(x)$ : le quantificateur bascule, la propriété se nie.
• Forme canonique en somme de produits : un terme par ligne où la fonction vaut $1$ , avec la variable BARRÉE si elle vaut $0$ sur cette ligne.
• Karnaugh : les groupes sont des rectangles de $2^{k}$ cases, les bords opposés sont voisins, et un groupe de $2^{k}$ cases élimine $k$ variables.

Dans un Karnaugh, un groupe peut recouvrir un autre : cela ne coûte rien et cela agrandit souvent les groupes. Ce qui coûte, c'est un groupe trop petit qu'on aurait pu doubler.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Nier une implication par une autre implication

2 points, et la démonstration par l'absurde qui suit part de faux

Ce qu'il ne faut pas écrire

« $\lnot(p\Rightarrow q)=p\Rightarrow\lnot q$ . »

Ce qu'il faut écrire

« $\lnot(p\Rightarrow q)=p\land\lnot q$ : on affirme l'hypothèse et on nie la conclusion, sans flèche. »

Les deux colonnes ne coïncident que sur la deuxième ligne : sur les trois autres, la fausse négation dit le contraire de la vraie.

Pourquoi : Nier « si $p$ alors $q$ » revient à exhiber un contre-exemple : un cas où $p$ est vrai et $q$ faux. Une implication, elle, resterait vraie dès que $p$ est faux.

2. Prendre la réciproque pour la contraposée

2 points, et c'est l'erreur de raisonnement la plus notée du cours

Ce qu'il ne faut pas écrire

« Si un nombre est divisible par $4$ alors il est pair ; donc s'il est pair alors il est divisible par $4$ . »

Ce qu'il faut écrire

« La contraposée est : s'il n'est pas pair, il n'est pas divisible par $4$ . La réciproque, elle, est fausse : $6$ est pair sans être divisible par $4$ . »

Pourquoi : La contraposée inverse ET nie ; la réciproque ne fait qu'inverser. Seule la première conserve la valeur de vérité, et c'est elle qui sert dans les démonstrations.

3. Appliquer De Morgan sans changer l'opérateur

1,5 point, et toute la simplification qui suit

Ce qu'il ne faut pas écrire

« $\overline{A+B}=\overline{A}+\overline{B}$ . »

Ce qu'il faut écrire

« $\overline{A+B}=\overline{A}\,\overline{B}$ : la barre se distribue en transformant le OU en ET. »

Pourquoi : « Ni l'un ni l'autre » n'est pas « pas l'un ou pas l'autre ». Le test à deux lignes suffit : pour $A=1$ et $B=0$ , le premier vaut $0$ , le second vaudrait $1$ .

4. Oublier la seconde distributivité

1 point, et une expression deux fois plus longue que nécessaire

Ce qu'il ne faut pas écrire

« $A+BC$ ne se factorise pas, on le laisse tel quel. »

Ce qu'il faut écrire

« $A+BC=(A+B)(A+C)$ : en algèbre de Boole, le OU se distribue aussi sur le ET. »

Pourquoi : C'est la loi qui n'a pas d'équivalent en algèbre ordinaire, donc celle que personne ne pense à essayer. Elle sert surtout à faire apparaître une absorption.

5. Grouper trois cases dans un tableau de Karnaugh

2 points, et l'expression obtenue ne correspond à aucun circuit

Ce qu'il ne faut pas écrire

« Ces trois cases voisines valent $1$ , j'en fais un groupe. »

Ce qu'il faut écrire

« Un groupe compte $1$ , $2$ , $4$ ou $8$ cases et forme un rectangle : je prends un groupe de $2$ et un groupe de $2$ qui se recouvrent. »

À gauche un carré de quatre cases, qui élimine deux variables ; à droite trois cases en L, qui ne forment aucun terme et doivent être recouvertes par deux groupes de deux.

Pourquoi : Chaque doublement de la taille d'un groupe élimine exactement une variable. Un groupe de trois cases n'élimine rien du tout, il ne correspond à aucun terme.

6. Nier un quantificateur sans le faire basculer

2 points, et l'énoncé nié dit tout autre chose

Ce qu'il ne faut pas écrire

« La négation de « tous les serveurs répondent » est « aucun serveur ne répond ». »

Ce qu'il faut écrire

« C'est « il existe au moins un serveur qui ne répond pas » : le $\forall$ devient $\exists$ et la propriété se nie. »

Pourquoi : Nier une affirmation universelle demande un seul contre-exemple, pas un renversement complet. « Aucun » est la négation de « au moins un », pas celle de « tous ».

7. Écrire une forme canonique sans barrer les variables nulles

1,5 point, et un terme qui vaut $1$ sur la mauvaise ligne

Ce qu'il ne faut pas écrire

« La ligne $A=1$ , $B=0$ , $C=1$ donne le terme $ABC$ . »

Ce qu'il faut écrire

« Elle donne $A\overline{B}C$ : une variable qui vaut $0$ sur la ligne apparaît BARRÉE dans le terme. »

Pourquoi : Un terme de la forme canonique doit valoir $1$ sur SA ligne et $0$ partout ailleurs. Sans la barre, il vaudrait $0$ précisément sur la ligne qu'il est censé décrire.

8. Refuser une implication vraie à vide

1,5 point, et deux lignes de table de vérité

Ce qu'il ne faut pas écrire

« $p$ est faux, donc $p\Rightarrow q$ n'a pas de sens, on ne peut rien dire. »

Ce qu'il faut écrire

« Quand $p$ est faux, $p\Rightarrow q$ est VRAIE, quelle que soit $q$ : la promesse n'a pas été rompue. »

Pourquoi : L'implication ne prétend rien lorsque son hypothèse est fausse. C'est ce qui rend vraie toute propriété affirmée « pour tout élément » d'un ensemble vide.

9. Barrer un seul terme sous une porte NAND

2 points, et le circuit dessiné ne réalise pas la fonction demandée

Ce qu'il ne faut pas écrire

« La sortie d'une porte NAND vaut $\overline{A}\cdot B$ . »

Ce qu'il faut écrire

« Elle vaut $\overline{A\cdot B}$ , c'est-à-dire $\overline{A}+\overline{B}$ : la barre porte sur TOUT le produit. »

Pourquoi : La barre longue est un opérateur à part entière : elle s'évalue après le produit. C'est aussi ce qui fait de la NAND une porte universelle, capable de reconstruire NON, ET et OU à elle seule.

Quelle méthode choisir

Simplifier une expression booléenne

On regarde la forme de l'expression, et le nombre de variables.

Si un terme est contenu dans un autre, comme $A+AB$ → absorption : le terme long disparaît

Exemple : $A+AB=A$

c'est la simplification la plus rentable, à chercher en premier
Si une barre porte sur une parenthèse entière → De Morgan, en changeant l'opérateur à chaque descente

Exemple : $\overline{A+BC}=\overline{A}(\overline{B}+\overline{C})$
Si un facteur commun apparaît dans plusieurs termes → factoriser, puis chercher $X+\overline{X}=1$

Exemple : $AB+A\overline{B}=A(B+\overline{B})=A$
Si trois ou quatre variables, et une table de vérité disponible → tableau de Karnaugh, groupes de $2^{k}$ cases aussi grands que possible

Exemple : quatre minterms donnant $AB+AC+BC$
Si plus de quatre variables → revenir aux lois de Boole : le Karnaugh devient illisible

Exemple : cinq variables donneraient $32$ cases

Une simplification se VÉRIFIE toujours sur la table de vérité complète : deux expressions égales doivent coïncider sur les $2^{n}$ lignes, pas seulement sur celles qu'on a regardées.

Nier un énoncé, morceau par morceau

On repère le connecteur principal, celui qui structure l'énoncé.

Si l'énoncé est une implication $p\Rightarrow q$ → sa négation est $p\land\lnot q$ , sans flèche

Exemple : « si le badge est valide alors la porte s'ouvre » se nie par « le badge est valide ET la porte ne s'ouvre pas »
Si l'énoncé est une conjonction $p\land q$ → $\lnot p\lor\lnot q$

Exemple : nier « grand et rapide » donne « pas grand ou pas rapide »
Si l'énoncé est une disjonction $p\lor q$ → $\lnot p\land\lnot q$

Exemple : nier « rouge ou bleu » donne « ni rouge ni bleu »
Si l'énoncé commence par « pour tout » → « il existe au moins un... qui ne... pas »

Exemple : un seul contre-exemple suffit à nier un énoncé universel
Si l'énoncé commence par « il existe » → « pour tout..., non... »

Exemple : nier « il existe une solution » demande de les écarter toutes

Quand plusieurs quantificateurs s'enchaînent, on les fait basculer un par un, de gauche à droite, sans changer leur ORDRE : intervertir un $\forall$ et un $\exists$ change l'énoncé.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Prouver que deux expressions booléennes sont équivalentes

Quand l'utiliser : L'énoncé demande de montrer une identité, ou de vérifier une simplification.

1 Choisir la méthode et l'annoncer : table de vérité complète, ou chaîne de lois.
2 Par table : dresser les $2^{n}$ lignes, une colonne par sous-expression, et comparer les deux colonnes finales.
3 Par les lois : partir du membre le plus COMPLIQUÉ et le transformer, en nommant la loi utilisée à chaque ligne.
4 Conclure par une phrase, en rappelant que l'égalité vaut sur toutes les lignes.

Phrase de conclusion

« $A+AB=A(1+B)=A\cdot 1=A$ , par distributivité puis par $1+B=1$ : les deux expressions sont équivalentes. »

Le piège : Transformer les deux membres à la fois et se rejoindre au milieu sans le dire : la copie devient illisible et le correcteur ne suit plus la chaîne.

Barème : 1 point la méthode annoncée, 1 point par loi correctement nommée, 1 point la conclusion.

Traduire un cahier des charges en expression booléenne

Quand l'utiliser : Un énoncé décrit en français les conditions d'ouverture d'une porte, d'allumage d'une alarme ou de validation d'une saisie.

1 Nommer chaque condition par une lettre et écrire à côté sa signification en toutes lettres.
2 Repérer les mots qui portent les connecteurs : « et », « ou », « sauf si », « à moins que », « seulement si ».
3 Écrire la table de vérité complète plutôt que de deviner l'expression.
4 Simplifier par Karnaugh, puis vérifier sur deux lignes choisies de la table.

Phrase de conclusion

« $F=AB+AC+BC$ : la porte s'ouvre lorsque au moins deux des trois autorisations sont présentes. »

Le piège : Traduire « $A$ seulement si $B$ » par $B\Rightarrow A$ : c'est $A\Rightarrow B$ , l'inverse.

Barème : 1 point les notations, 2 points la table, 1 point la simplification, 1 point la phrase de retour au contexte.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Deux lignes bien choisies de la table

Après une simplification, tester l'expression de départ et l'expression finale sur une ligne où elles valent $1$ et une où elles valent $0$ .

$A=1$ , $B=0$ , $C=0$ : la majorité vaut $0$ , et $AB+AC+BC$ vaut aussi $0$ .
Le compte de lignes et de termes

Une table à $n$ variables a $2^{n}$ lignes, et la forme canonique compte autant de termes que de lignes à $1$ .

Quatre lignes à $1$ sur huit : la forme canonique a exactement quatre termes.
La taille des groupes de Karnaugh

Relire chaque groupe : $1$ , $2$ , $4$ ou $8$ cases, en rectangle. Un groupe de $2^{k}$ cases doit faire disparaître exactement $k$ variables du terme.

Un groupe de $2$ cases qui laisse trois variables sur trois : le terme n'a pas été réduit.
Le sens de la barre

Vérifier sur quoi porte chaque barre : une variable seule, ou toute une expression. Une barre longue s'évalue en dernier.

$\overline{AB}$ vaut $1$ pour $A=1$ , $B=0$ , alors que $\overline{A}B$ vaut $0$ .

L'exercice type décortiqué

Contrôle d'accès : au moins deux autorisations sur trois

Une salle serveur s'ouvre lorsque au moins deux des trois responsables $A$ , $B$ et $C$ ont présenté leur badge.

Établir la table de vérité, écrire la forme canonique, puis simplifier par un tableau de Karnaugh.

Les trois groupes de deux cases donnent les trois termes

BC

AC

AB

: chaque groupe de

2

cases élimine une variable sur les trois.

Étape 1

Table de vérité : $F=1$ sur les lignes $011$ , $101$ , $110$ et $111$ , soit quatre lignes sur huit.

Pourquoi

On dresse la table AVANT de deviner l'expression : « au moins deux sur trois » n'a pas de traduction directe en connecteurs, et toute tentative d'écriture immédiate se trompe.

Étape 2

Forme canonique : $F=\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC$ .

Pourquoi

Un terme par ligne à $1$ , avec les variables nulles barrées. Quatre lignes donnent quatre termes : le compte se vérifie d'un coup d'œil.

Étape 3

Karnaugh : trois groupes de deux cases, qui se recouvrent sur la case $ABC$ .

Pourquoi

Le recouvrement ne coûte rien et permet à chaque groupe d'atteindre la taille $2$ . Refuser de recouvrir laisserait des groupes d'une seule case, donc des termes de trois variables.

Étape 4

Lecture des groupes : $F=AB+AC+BC$ .

Pourquoi

Chaque groupe de $2^{1}$ cases élimine une variable, celle qui change à l'intérieur du groupe. On passe de quatre termes de trois lettres à trois termes de deux lettres.

Étape 5

Vérification sur deux lignes : pour $A=1$ , $B=0$ , $C=0$ , $AB+AC+BC=0$ ; pour $A=1$ , $B=1$ , $C=0$ , il vaut $1$ .

Pourquoi

Une ligne à $0$ et une ligne à $1$ suffisent à attraper la quasi-totalité des erreurs de groupement, en dix secondes.

Étape 6

En portes NAND : $F=\overline{\overline{AB}\cdot\overline{AC}\cdot\overline{BC}}$ .

Pourquoi

Une somme de produits se réalise avec deux niveaux de NAND, par double négation. C'est la forme demandée dès qu'un circuit doit être construit avec un seul type de porte.

Conclusion rédigée

« La fonction de contrôle d'accès se simplifie en $F=AB+AC+BC$ : la porte s'ouvre dès que deux des trois responsables au moins ont badgé. »

L'erreur classique sur cet exercice : Écrire $F=ABC$ en lisant « deux sur trois » comme une conjonction, ou grouper les trois cases de la rangée $A=1$ en un seul groupe de trois.

À savoir par cœur

• $p\Rightarrow q$ n'est FAUSSE que sur la ligne $p=1$ , $q=0$ ; elle est vraie à vide dès que $p$ est faux.
• $\lnot(p\Rightarrow q)=p\land\lnot q$ : la négation d'une implication n'est pas une implication.
• La contraposée $\lnot q\Rightarrow\lnot p$ est équivalente ; la réciproque $q\Rightarrow p$ ne l'est pas.
• De Morgan : la barre se distribue en CHANGEANT l'opérateur, dans les deux sens.
• Absorption : $A+AB=A$ et $A(A+B)=A$ . Seconde distributivité : $A+BC=(A+B)(A+C)$ .
• Négation d'un quantificateur : le $\forall$ devient $\exists$ , et réciproquement, en niant la propriété.
• Karnaugh : rectangles de $1$ , $2$ , $4$ ou $8$ cases, bords opposés voisins, et un groupe de $2^{k}$ cases élimine $k$ variables.

Questions fréquentes

Pourquoi une implication est-elle vraie quand l'hypothèse est fausse ?

Parce qu'une implication ne promet quelque chose que dans le cas où son hypothèse se réalise. Si elle ne se réalise pas, la promesse n'a pas été rompue, donc l'énoncé n'est pas faux. C'est ce qui rend vraie toute propriété affirmée pour tous les éléments d'un ensemble vide.

Quelle différence entre la contraposée et la réciproque ?

La contraposée inverse les deux membres et les nie tous les deux ; elle est toujours équivalente à l'énoncé de départ, ce qui permet de démontrer l'un en démontrant l'autre. La réciproque se contente d'inverser les deux membres sans les nier, et elle n'a aucun lien de vérité avec l'énoncé initial.

Comment nier une implication ?

En affirmant l'hypothèse et en niant la conclusion, sans aucune flèche dans le résultat. Nier revient à exhiber un contre-exemple : un cas où l'hypothèse est vraie et la conclusion fausse. Écrire une autre implication comme négation est l'erreur la plus fréquente du chapitre.

Combien de cases peut contenir un groupe dans un tableau de Karnaugh ?

Une, deux, quatre ou huit, et le groupe doit former un rectangle, les bords opposés du tableau étant considérés comme voisins. Chaque doublement de la taille élimine une variable du terme obtenu. Un groupe de trois cases ne correspond à aucun terme et n'est jamais autorisé.

Faut-il utiliser une table de vérité ou les lois de Boole ?

La table de vérité prouve toujours, mais elle devient longue au-delà de trois variables, avec seize lignes pour quatre. Les lois de Boole sont plus rapides quand une absorption ou un De Morgan saute aux yeux. Pour trois ou quatre variables, le tableau de Karnaugh combine les deux avantages.

Passer à la pratique

Exercices corrigés : Logique booléenne et mathématique

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
150 minutes

Faire les exercices

Fiche suivante Systèmes de numération informatique

Ce chapitre resservira dans

Les chapitres qui le réclament en amont, plus tard dans l'année ou dans les années suivantes.

Théorie des ensembles et relations

Voir aussi

Toutes les fiches Tous les exercices Tutorat au cégep Tuteur maths pour l'informatique (201-N11)Systèmes de numération (201-N11)Ensembles et relations (201-N11)Cours de mathématiques

Vous suivez le cours 201-N11 en informatique au cégep ?

Contactez-moi pour une première séance. Bachelier en informatique de McGill et maître en informatique appliquée de Concordia, je traite la logique booléenne comme elle sera utilisée ensuite : dans les conditions d'un programme, dans les requêtes de base de données et dans les circuits.

Me contacter WhatsApp

Site par Studio Squalli