La logique Booléenne

Nous avons vu précédemment que les tests se font via des expressions logiques.

Mais qu’est-ce que la logique ? N’est-ce pas un élément inné ?

Fondamentalement, la logique est universelle et peut même se représenter mathématiquement. Or, un ordinateur est logique de par sa conception. Il est logique et stupide, ce qui signifie que s’il fait quelque chose d’illogique, c’est que vous lui avez demandé.

220px-george_boole_colorGeorge Boole a formalisé la logique en proposant une approche symbolique et mathématique de celle-ci, basée sur deux valeurs numériques, le 0 et le 1. Il(ré)invente le binaire. Notez que ce bon George découvre ça en 1847, soit près d’un siècle avant l’informatique ! Toutefois, sa logique booléenne restera théorique pendant de longues années, jusqu’à ce que Claude Shannon le met en pratique dans le traitement de l’information, prémices de l’informatique actuelle.

Boole développe également une algèbre booléenne, composée de lois et de théorèmes, utilisée principalement en électronique, en informatique, en mathématique et en logique. Tout ce que possède un ordinateur !

L’algèbre permet d’effectuer des opérations sur des variables logiques en utilisant des techniques algébriques.

Pour mieux comprendre la logique booléenne, prenons l’exemple suivant :

« S’il fait beau et que j’ai fini d’étudier, j’irai manger une glace »

Dans quels cas j’irai manger une glace ? Pour le savoir, nous allons formaliser cette affirmation. Nous avons deux variables pouvant être vraies ou fausses (fait-il beau ? Ais-je fini d’étudier ?). Nous pouvons donc tracer un tableau de ce genre :

Fait-il beau ? Ais-je fini d’étudier ? Résultat
NON NON Pas de glace  😥  (il fait pas beau et j’ai pas fini mon algorithmique)
NON OUI Pas le glace 😥 (vu le temps, moi je bouge pas !)
OUI NON Pas de glace 😥 (quel est le prof qui a posé cette interro ?)
OUI OUI Une boule chocolat et une boule mokka dans un cornet, avec de la chantilly !  😛

La table que nous venons de constituer se nomme une table de vérité. Ce type de table permet de lister tous les résultats possible d’une affirmation logique.

Tables de vérité et tables de Karnaugh

Avant d’aller plus loin, je tiens à définir une autre notion. Nous venons de voir l’élaboration d’une table de vérité. Il existe un autre formalisme à cette table de vérité, plus compacte, et qui permet de faire de belles choses (que nous ne verrons pas ici, malheureusement :(). C’est la table de Karnaugh.

La table de Karnaugh fonctionne si nous avons un maximum de 4 variables logiques. Elle se construit selon les règles suivantes:

  • Il faut tracer un tableau de 2^n cases, n étant le nombre de variables. Si on reprend l’exemple ci-dessus, nous avons deux variables, il nous faut donc un tableau de 4 cases.
  •  Chaque case correspond à l’état d’une combinaison des variables. Les cases seront positionnée de manière à ce que une et une seule variable soie modifiée en changeant de case.
  • Le résultat sera noté en binaire.

Voici à quoi va ressembler le tableau. Posons a comme étant la première affirmation et b la seconde.

a\b 0 1
0 0 0
1 0 1

C’est quand même plus concis, non ?

Les opérateurs logique

la loi ET

Commençons par cette loi, aussi nommée conjonction.Elle s’énonce ainsi:

 a ET b est VRAI si et seulement si a est VRAI et b est VRAI.
. Elle s’écrit de manière mathématique [pmath]a . b[/pmath] et se lit a ET b

Traçons la table de Karnaugh de cette loi.

table de Karnaugh de la loi ET
a\b 0 1
0 0 0
1 0 1

La loi OU

Seconde loi importante, la loi de disjonction, plus connu sous le nom de OU Inclusif. Elle s’énonce ainsi :

a OU b est vrai si et seulement si a est vrai OU b est vrai
Elle s’écrit de manière [pmath]a+b[/pmath] et se lit a OU b.

Avec cette affirmation, tracez sa table de Karnaugh.

table de Karnaugh de la loi OU
a\b 0 1
0 0 1
1 1 1

Notez que la dernière affirmation est correcte. Si les deux variables sont vraies, le résultat l’est également.

Attention, même si l’algèbre booléenne utilise les mêmes symboles que l’algèbre décimale, les résultats sont totalement différents ! La fonction ET utilise le [pmath].[/pmath], car on peut dire que [pmath]0 .x = 0[/pmath]. Par contre, la fonction OU utilise le [pmath]+[/pmath], mais en logique booléenne [pmath]1+1=1[/pmath]

La négation

La négation est aussi une affirmation logique :  

Le contraire de a est FAUX si et seulement si a est VRAI
. Elle s’écrit [pmath]overline{a}[/pmath] et se lit a barre. Je vous donne la table de vérité tout de suite, elle n’est pas compliquée.

a [pmath]overline{a}[/pmath]
0 1
1 0

Les autres fonctions logiques

Grâce à ces trois lois fondamentales de l’algèbre booléenne, nous pouvons maintenant créer d’autres fonctions logiques. Elles sont moins employées en algorithmique et en programmation, mais sont la base essentielle de votre processeur.

Non-Et (NAND)

Comme son nom l’indique, nous allons coupler les lois NON et ET.  Cette fonction logique se nomme la NAND (Non-ET) et s’écrit [pmath] overline{a.b}[/pmath] Tracez la table de Karnaugh de cette affirmation.

table de Karnaugh de la loi NAND
a\b 0 1
0 1 1
1 1 0

Eh oui, il suffit d’inverser les 0 et les 1 de la table du ET !

Non-Ou (NOR)

Faites de même pour la fonction logique Non-Ou (Nor). Comment s’écrira-t-elle ?

table de Karnaugh de la loi NOR
a\b 0 1
0 1 0
1 0 0

Eh oui, il suffit d’inverser les 0 et les 1 de la table du OU ! elle s’écrira [pmath]overline{a+b}[/pmath]

Ou Exclusif (XOR)

Ici, c’est un peu plus compliqué. L’affirmation gérant le OU exclusif est la suivante : il faut que a soit vrai ou que b soit vrai, mais pas les deux en même temps ! En logique booléenne, on devra écrire : a OU b ET PAS a ET B. Ça tombe bien, nous venons de voir toutes ses fonctions ! On pourra donc écrire : [pmath](a+b).overline{(a.b)}[/pmath]. Je vous laisse faire la table de Karnaugh ?

table de Karnaugh de la loi XOR
a\b 0 1
0 0 1
1 1 0

Bon, je vous fais grâce de la démonstration mathématique (oui, il y a aussi ça en algèbre binaire !), mais la fonction XOR va s’écrire de deux façons : [pmath]overline{a} .b+a. overline{b}[/pmath], ou plus simplement [pmath]a⊕b[/pmath]. Nous verrons l’utilité du XOR dans le cours de Structure…

Non-Ou Exclusif (ou Équivalence)

C’est le contraire du OU exclusif, que l’on peut noter [pmath]overline{a⊕b}[/pmath]. La table de Karnaugh parle d’elle-même.

table de Karnaugh de la loi XNOR
a\b 0 1
0 1 0
1 0 1

Les lois de De Morgan

Plutôt que de vous démontrer ces lois de De Morgan, nous allons faire 4 petits exercices : Tracer les tables de vérité ou de Karnaugh de ces différentes affirmations :

  • [pmath]overline{a.b}[/pmath]
  • [pmath]overline{a+b}[/pmath]
  • [pmath]overline{a} . { overline{b}} [/pmath]
  • [pmath]overline{a} + { overline{b}}[/pmath]
Lois de De Morgan
[pmath]overline{a.b}[/pmath] 0 1 [pmath]overline{a+b}[/pmath] 0 1 [pmath]overline{a} .  {overline{b}}[/pmath] 0 1 [pmath]overline{a} + { overline{b}}[/pmath] 0 1
0 0 0 0
1 1 1 1

Que remarquez-vous ? Que certaines tables sont équivalentes ? SI elles sont équivalentes, c’est que mathématiquement, les affirmations sont elles aussi équivalentes ! Vous avez (re)découvert les lois de De Morgan. Ces lois sont très utiles pour changer le signe d’une affirmation.

Lois de De Morgan
  • [pmath]overline{a.b}[/pmath] = [pmath]overline{a} + { overline{b}}[/pmath]
  • [pmath]overline{a+b}[/pmath] = [pmath]overline{a} .  { overline{b}}[/pmath]

Exercices

Exercice 1

Créer la table de vérité pour les exercices suivant :

  1. Si je réside en Belgique et quil ne pleut pas, je prends mon parapluie et je vais travailler à pied, tandis que sil pleut, je mets mon imperméable et je prends le bus.
    Si je réside à l’étranger, je mets toujours mon imperméable, je prends toujours mon parapluie et je prends un taxi.
  2. Si le code article est A, le transport se fera gratuitement pour tous les montants égaux ou supérieurs à 6,20 , pour un montant inférieur le coût sera de 1,25 .
    Si le code article est différent de A, le transport coûtera 2,5 plus 1% du montant si celui-ci est égal ou supérieur à 6,20 ; pour un montant inférieur et que le transport se fasse par courrier, son coût est de 1,5% du montant ; si le transport se fait par un autre moyen, celui-ci est gratuit.
  3. Une entreprise commerciale livre des marchandises de stock. Quand celui-ci est épuisé, la commande est mise en attente.
    De plus, chaque client a un crédit limité qui, en principe, ne peut être dépassé. Cependant, si les paiements sont réguliers, la commande est accepté
  4. Dans une entreprise, une prime est accordée si lancienneté est supérieure à 5 ans ou si lancienneté est supérieure à 3 ans et la catégorie supérieure à
  5. Lorsquun client paie comptant, il obtient un escompte de 2% du montant de la facture.
    Pour les factures de moins de 100 euros, on compte une somme de 1,25 euros pour le port, dans les autres cas, le port est gratuit.
  6. Un étudiant inscrit aux examens et ayant passé tous ces examens a réussi sil obtient au moins 10/20 dans toutes les branches, sinon il est ajourné.
    L’étudiant inscrit aux examens et qui ny participe pas ou les interrompt est ajourné s’il fournit une justification écrite. Dans le cas contraire, il est considéré comme nayant pas ré
    Déterminer le sort de chaque étudiant.
  7. Un client reçoit une réduction si la quantité commandée est dau moins 10 articles.
    Cette réduction est dau moins 5% si la distance entre la firme et le client est inférieure ou égale à 50 Km.
    Si cette distance est inférieure ou égale à 100 Km, la réduction est de 2%.
    Si la quantité est supérieure ou égale à 15 articles, la réduction est de 10% et 5% pour les distances comprises entre 50 inclus et 100 Km inclus.
    Les réductions ne sont pas cumulables.

Exercice 2

Cet algorithme est destiné à prédire l’avenir, et il doit être infaillible !
Il lira au clavier lheure et les minutes, et il affichera lheure quil sera une minute plus tard. Par exemple, si l’utilisateur tape 21 puis 32, l’algorithme doit répondre :

« Dans une minute, il sera 21 heure(s) 33 ».

NB : on suppose que l’utilisateur entre une heure valide. Pas besoin donc de la vérifier.

Exercice 3

De même que le précédent, cet algorithme doit demander une heure et en afficher une autre. Mais cette fois, il doit gérer également les secondes, et afficher l’heure qu’il sera une seconde plus tard.
Par exemple, si l’utilisateur tape 21, puis 32, puis 8, l’algorithme doit répondre : « Dans une seconde, il sera 21 heure(s), 32 minute(s) et 9 seconde(s) ».

NB : là encore, on suppose que l’utilisateur entre une date valide.

Exercice 4

Un magasin de photocopies facture 0,10 les dix premières photocopies, 0,09 les vingt suivantes et 0,08 au-delà. Ecrivez un algorithme qui demande à l’utilisateur le nombre de photocopies effectuées et qui affiche la facture correspondante.

Exercice 5

Les habitants de Zorglub paient l’impôt selon les règles suivantes :

  • les hommes de plus de 20 ans paient l’impôt
  • les femmes paient l’impôt si elles ont entre 18 et 35 ans
  • les autres ne paient pas d’impôt

Le programme demandera donc l’âge et le sexe du Zorglubien, et se prononcera donc ensuite sur le fait que lhabitant est imposable.

Exercice 6

Les élections législatives, en Guignolerie Septentrionale, obéissent à la règle suivante :

  • lorsque l’un des candidats obtient plus de 50% des suffrages, il est élu dès le premier tour.
  • en cas de deuxième tour, peuvent participer uniquement les candidats ayant obtenu au moins 12,5% des voix au premier tour.

Vous devez écrire un algorithme qui permette la saisie des scores des quatre candidats au premier tour. Cet algorithme traitera ensuite le candidat numéro 1 (et uniquement lui) : il dira s’il est élu, battu, s’il se trouve en ballottage favorable (il participe au second tour en étant arrivé en tête à l’issue du premier tour) ou défavorable (il participe au second tour sans avoir été en tête au premier tour).

Print Friendly, PDF & Email