Logique Boléenne :¶

Un peu d'histoire :¶

En 1847, le Britanique George Boole développe un algèbre binaire pour traduire des raisonnements logiques sous forme d'équations dites booléennes.

En 1938, l'Américain Claude Shannon prouve que les circuits électriques peuvent résoudre tous les problèmes que l'algèbre de Boole peut résoudre.

Ceci et les travaux d'Alan Turing de 1936 constituent les fondements de l'informatique.

Algèbre de Boole :¶

Un booléen ne peut prendre que deux valeurs distinctes :

• soit True = 1 (Vrai) ;
• soit False = 0 (Faux).

On peut affecter un booléen à une variable. Il s'agit alors d'une variable binaire.

In [1]:

continuer = True
type(continuer)

continuer = True type(continuer)

Out[1]:

bool

Les conditions, comparaisons et tests d'égalité, sont des expressions qui produisent un résultat booléen

In [2]:

while continuer:              #la condition est vraie, on exécute le bloc de la boucle while
    print("demat")
    poursuivre = input("Voulez-vous continuer ? o/n : ")
    if poursuivre.lower() == 'n':
        print("kenavo")
        continuer = False     #la condition est fausse, on sort de la boucle

while continuer: #la condition est vraie, on exécute le bloc de la boucle while print("demat") poursuivre = input("Voulez-vous continuer ? o/n : ") if poursuivre.lower() == 'n': print("kenavo") continuer = False #la condition est fausse, on sort de la boucle

demat
Voulez-vous continuer ? o/n : o
demat
Voulez-vous continuer ? o/n : n
kenavo

Les opérations fondamentales de l'algèbre de Boole) sont :

• la conjonction, ET, se note : and, $\bullet$, $\&$ , $∧$
• la disjonction, OU, se note : or, $+$, $|$ , $∨$
• la négation : NON, se note : not, $\bar{ }$, ~, $¬$

Avec ces opérateurs de base, nous allons pouvoir définir des fonctions logiques, exprimer des conditions qui combinent plusieurs tests.

In [3]:

x = 5
if (x >= 0) and (x <= 10):
    print("Ce nombre appartient à l'intervalle [0 ; 10]")
else:
    print("Ce nombre n'appartient pas à l'intervalle [0 ; 10]")

x = 5 if (x >= 0) and (x <= 10): print("Ce nombre appartient à l'intervalle [0 ; 10]") else: print("Ce nombre n'appartient pas à l'intervalle [0 ; 10]")

Ce nombre appartient à l'intervalle [0 ; 10]

Ici, les parenthèses permettent de mieux visualiser les tests.

L'algèbre de Boole répond à des règles#Propri%C3%A9t%C3%A9s), ainsi l’opérateur and est prioritaire sur l’opérateur or mais il vaut mieux utiliser des parenthèses pour plus de clarté : $ a + b \bullet c = a + (b \bullet c)$

Table de vérité :¶

Pour chaque fonction logique, on peut établir une table de vérité. Un tableau qui présente toutes les combinaisons de valeurs possibles pour une ou plusieurs variables, et la valeur associée de la fonction décrite. Le nombre de combinaisons est $2^n$ avec $n$ le nombre de variables booléennes combinées.

Fontion ET (AND):¶

La conjonction dont l'expression booléenne) est a and b, est réalisée lorsque les conditions a et b sont toutes deux réalisées :

a	b	ET
0	0	0
0	1	0
1	0	0
1	1	1

Equation booléenne : $a \bullet b = a \& b = a ∧ b$

A faire vous-même :

Modifier le programme suivant pour obtenir une table de vérité avec le même ordre de combinaisons logiques que ci-dessus.

In [122]:

# Table de vérité en Markdown par Python de l'opérateur ET :
from IPython.display import Markdown
    
table ='''|  a  |  b  |  ET |
|:---:|:---:|:---:|\n'''

for a in [False,True]:
    for b in [False,True]:
        table += f"|  {a}  |  {b}  |  {a and b}  |\n"
        
Markdown(table)

# Table de vérité en Markdown par Python de l'opérateur ET : from IPython.display import Markdown table ='''| a | b | ET | |:---:|:---:|:---:|\n''' for a in [False,True]: for b in [False,True]: table += f"| {a} | {b} | {a and b} |\n" Markdown(table)

Out[122]:

a	b	ET
False	False	False
False	True	False
True	False	False
True	True	True

Fontion OU (OR) :¶

La disjonction dont l'expression booléenne) est a or b, est réalisée lorsqu'au moins l'une des conditions a ou b est réalisée :

a	b	OU
0	0	0
0	1	1
1	0	1
1	1	1

Equation booléenne : $a + b = a | b = a ∨ b$

A programmer vous-même :

In [123]:

# Table de vérité en Markdown par  Python de l'opérateur OU :
from IPython.display import Markdown

table ='''|  a  |  b  |  OU |
|:---:|:---:|:---:|\n'''

for a in [False,True]:
    for b in [False,True]:
        table += f"|  {a}  |  {b}  |  {a or b}  |\n"
        
Markdown(table)

# Table de vérité en Markdown par Python de l'opérateur OU : from IPython.display import Markdown table ='''| a | b | OU | |:---:|:---:|:---:|\n''' for a in [False,True]: for b in [False,True]: table += f"| {a} | {b} | {a or b} |\n" Markdown(table)

Out[123]:

a	b	OU
False	False	False
False	True	True
True	False	True
True	True	True

Fontion NON (NOT) :¶

La négation dont l'expression booléenne) est not a, est réalisée lorsque la condition a n'est pas réalisée :

A	NON
0	1
1	0

Equation booléenne : $\bar{a} =$ ~$a = ¬a$

A programmer vous-même :

In [139]:

# Table de vérité en Markdown par Python de l'opérateur NON :
from IPython.display import Markdown

table ='''|  a  |  NON  |
|:---:|:---:|\n'''

for a in [False,True]:
        table += f"|  {a}   |  {not a}   |\n"
        
Markdown(table)

# Table de vérité en Markdown par Python de l'opérateur NON : from IPython.display import Markdown table ='''| a | NON | |:---:|:---:|\n''' for a in [False,True]: table += f"| {a} | {not a} |\n" Markdown(table)

Out[139]:

a	NON
False	True
True	False

Autres Fonctions logiques :¶

A partir des trois fonctions de bases ET, OU, NON, on peut en construire d'autres telles que :

Fonction OU-Exclusif (XOR) :¶

A	B	NOR
0	0	0
0	1	1
1	0	1
1	1	0

A programmer vous-même :

Vérifier que les expressions booléennes) ((not a) and b) or (a and (not b)) et a ^ b sont équivalentes.

In [147]:

# Table de vérité en Markdown par Python de l'opérateur OU-Exclusif :
from IPython.display import Markdown

table ='''|  a  |  b  |  NOR |
|:---:|:---:|:---:|\n'''

for a in [False,True]:
    for b in [False, True]:
        table += f"|  {a}  |  {b}  |  {((not a) and b) or (a and (not b))}  |\n"
        
Markdown(table)

# Table de vérité en Markdown par Python de l'opérateur OU-Exclusif : from IPython.display import Markdown table ='''| a | b | NOR | |:---:|:---:|:---:|\n''' for a in [False,True]: for b in [False, True]: table += f"| {a} | {b} | {((not a) and b) or (a and (not b))} |\n" Markdown(table)

Out[147]:

a	b	NOR
False	False	False
False	True	True
True	False	True
True	True	False

Fonction NON-ET (NAND) :¶

A	B	NAND
0	0	1
0	1	1
1	0	1
1	1	0

A programmer vous-même :

Vérifier que les expressions booléennes) not (a and b) et (not a) or (not b) sont équivalentes.

In [154]:

# Table de vérité en Markdown par Python de l'opérateur NON-ET :
from IPython.display import Markdown

table ='''|  a  |  b  |  NAND |
|:---:|:---:|:---:|\n'''

for a in [False,True]:
    for b in [False, True]:
        table += f"|  {a}  |  {b}  |  {not (a and b)}  |\n"
        
Markdown(table)

# Table de vérité en Markdown par Python de l'opérateur NON-ET : from IPython.display import Markdown table ='''| a | b | NAND | |:---:|:---:|:---:|\n''' for a in [False,True]: for b in [False, True]: table += f"| {a} | {b} | {not (a and b)} |\n" Markdown(table)

Out[154]:

a	b	NAND
False	False	True
False	True	True
True	False	True
True	True	False

In [156]:

from IPython.display import Markdown

table ='''|  a  |  b  |  NAND |
|:---:|:---:|:---:|\n'''

for a in [False,True]:
    for b in [False, True]:
        table += f"|  {a}  |  {b}  |  {(not a) or (not b)}  |\n"
        
Markdown(table)

from IPython.display import Markdown table ='''| a | b | NAND | |:---:|:---:|:---:|\n''' for a in [False,True]: for b in [False, True]: table += f"| {a} | {b} | {(not a) or (not b)} |\n" Markdown(table)

Out[156]:

a	b	NAND
False	False	True
False	True	True
True	False	True
True	True	False

Fonction NON-OU (NOR) :¶

A	B	NOR
0	0	1
0	1	0
1	0	0
1	1	0

A programmer vous-même :

Vérifier que les expressions booléennes) not (a or b) et (not a) and (not b) sont équivalentes.

In [157]:

# Table de vérité en Markdown par Python de l'opérateur NON-OU :
from IPython.display import Markdown

table ='''|  a  |  b  |  NAND |
|:---:|:---:|:---:|\n'''

for a in [False,True]:
    for b in [False, True]:
        table += f"|  {a}  |  {b}  |  {not (a or b)}  |\n"
        
Markdown(table)

# Table de vérité en Markdown par Python de l'opérateur NON-OU : from IPython.display import Markdown table ='''| a | b | NAND | |:---:|:---:|:---:|\n''' for a in [False,True]: for b in [False, True]: table += f"| {a} | {b} | {not (a or b)} |\n" Markdown(table)

Out[157]:

a	b	NAND
False	False	True
False	True	False
True	False	False
True	True	False

In [158]:

from IPython.display import Markdown

table ='''|  a  |  b  |  NAND |
|:---:|:---:|:---:|\n'''

for a in [False,True]:
    for b in [False, True]:
        table += f"|  {a}  |  {b}  |  {(not a) and (not b)}  |\n"
        
Markdown(table)

from IPython.display import Markdown table ='''| a | b | NAND | |:---:|:---:|:---:|\n''' for a in [False,True]: for b in [False, True]: table += f"| {a} | {b} | {(not a) and (not b)} |\n" Markdown(table)

Out[158]:

a	b	NAND
False	False	True
False	True	False
True	False	False
True	True	False

Les lois de De Morgan :

$$\overline{a \bullet b} = \overline{a} + \overline{b}$$$$\overline{a + b} = \overline{a} \bullet \overline{b}$$

Exemple : Le contraire d'être riche et célèbre ne pas être riche ou ne pas être célèbre.

Application à l'addition binaire :¶

In [143]:

from metakernel import register_ipython_magics
register_ipython_magics()

from metakernel import register_ipython_magics register_ipython_magics()

In [145]:

%%tutor

n = [0, 1, 0]
p = [0, 1, 1]
r = []

c = False
for i in range(2, -1, -1):
    a = n[i]
    b = p[i]
    unite = (a and not(b) and not(c)) or\
        (not(a) and b and not(c)) or\
        (not(a) and not(b) and c) or\
        (a and b and c)
    r = [int(unite)] + r
    c = (a and b) or (b and c) or (a and c)
r = [int(c)] + r

print(r)

%%tutor n = [0, 1, 0] p = [0, 1, 1] r = [] c = False for i in range(2, -1, -1): a = n[i] b = p[i] unite = (a and not(b) and not(c)) or\ (not(a) and b and not(c)) or\ (not(a) and not(b) and c) or\ (a and b and c) r = [int(unite)] + r c = (a and b) or (b and c) or (a and c) r = [int(c)] + r print(r)

Opération booléenne bit à bit :¶

Dans beaucoup de langages, and et or sont écrits && et ||.

Ces symboles existent égalemant en Python, mais ils sont là pour réaliser des opérations binaires bit à bit :

In [5]:

masque = 0b00001111
resultat = 0b10011101 & masque
resultat, bin(resultat), hex(resultat)

masque = 0b00001111 resultat = 0b10011101 & masque resultat, bin(resultat), hex(resultat)

Out[5]:

(13, '0b1101', '0xd')

Les 1 du masque définissent les bits qui seront conservés dans le résultat.

In [6]:

bin(0b10011101 | 0b00001111)

bin(0b10011101 | 0b00001111)

Out[6]:

'0b10011111'

In [7]:

bin(0b10011101 ^ 0b00001111)

bin(0b10011101 ^ 0b00001111)

Out[7]:

'0b10010010'

A faire vous-même :

• Calculer les opérations binaires suivantes : la conjonction, ET, se note : and, ∙ , & , ∧ la disjonction, OU, se note : or, + , | , ∨ la négation : NON, se note : not, ¯ , ~, ¬

# calcul A
   1100
&  0111
----------
  11011

# calcul B
   1100
|  0111
----------
   1100

# calcul C
   1100
^  0111
----------
   11011

# calcul D
~  1100
&  0111
----------
   0111

• Vérifier vos résultats avec Python en décimal, puis en binaire et en hexadécimal :

In [8]:

# calcul A
12 & 7

# calcul A 12 & 7

Out[8]:

4

In [9]:

# calcul B
12 | 7

# calcul B 12 | 7

Out[9]:

15

In [10]:

# calcul C
12 ^ 7

# calcul C 12 ^ 7

Out[10]:

11

In [11]:

# calcul D
~12 & 7

# calcul D ~12 & 7

Out[11]:

3

Le OU exclusif (XOR) est une méthode de cryptographie moderne qui s'est développée avec l'avènement de l'informatique. Elle consiste à chiffrer un message en binaire avec une clé répétée par une multiplication par OU Exclusif.

Ainsi le chiffrement de la chaine de caractères 'NSI' avec la clé 'f' produit '(5/'...

Caractère séquentiel (shortcuts) :¶

En Python, les opérateurs and et or sont séquentiels : L'opérande de droite n'est évaluée que si l'opérande de gauche ne permet pas de trouver le résultat. On parle d'évaluation fainéante...

Pour a and b :

• Si a est False, inutile d'évaluer b, ce sera False ;
• Si a est True, alors il faudra évaluer b pour savoir.

Pour a or b :

• si a est True, inutile d'évaluer b, ce sera True ;
• si a est False, il faudra évaluer b pour savoir.

Illustration : http://sametmax.com/quelques-astuces-a-propos-de-and-et-or/

Applications :¶

France IOI - Zones de couleurs :

Coller ci-dessous le code de votre programme qui a permis sur France IOI de résoudre le besoin suivant :

Ce que doit faire votre programme :

Sur une table est placée une feuille de papier rectangulaire de 90 cm de large et 70 cm de haut, composée de zones de différentes couleurs, comme le décrit la figure ci-dessous. Un certain nombre de personnes placent l'une après l'autre un jeton où elles le souhaitent sur la table, à l'exception des frontières entre les différentes zones.

On vous donne en entrée le nombre de jetons qui ont été déposés, puis, pour chaque jeton, ses coordonnées sur la feuille par rapport à l'origine en haut à gauche, sous la forme d'une abscisse et d'une ordonnée entre −1 000 et 1 000.

Votre programme devra qualifier chaque jeton avec l'un des textes suivants, en fonction de la couleur sur laquelle il se trouve :

• « En dehors de la feuille »
• « Dans une zone jaune »
• « Dans une zone bleue »
• « Dans une zone rouge »

Essayez d'écrire votre programme de sorte qu'il y ait au maximum une condition par possibilité de texte affiché.

Exemple

entrée :

4
16
12
30
22
64
62
-5
86

sortie :

Dans une zone bleue
Dans une zone jaune
Dans une zone rouge
En dehors de la feuille

Commentaires

Dans l'exemple, on a 4 jetons, de coordonnées (16 ; 12), (30 ; 22), (64 ; 62) et (-5 ; 86).

In [1]:

# Votre code France-IOI
nbJetons = int(input())
   

for jeton in range(nbJetons):
   x = int(input())
   y = int(input())
   

   if (x < 0 or y < 0 or x > 90 or y > 70):
        print("En dehors de la feuille")
   else:
        if ((x >= 10 and x <= 85 and y >= 10 and y <= 55)
            and not(x >= 25 and x <= 50 and y >= 20 and y <= 45)):
            print("Dans une zone bleue")
        elif (((x >= 15 and x <= 45) or (x >= 60 and x <= 85))
            and (y >= 60 and y <= 70)):
            print("Dans une zone rouge")
        else:
            print("Dans une zone jaune")

# Votre code France-IOI nbJetons = int(input()) for jeton in range(nbJetons): x = int(input()) y = int(input()) if (x < 0 or y < 0 or x > 90 or y > 70): print("En dehors de la feuille") else: if ((x >= 10 and x <= 85 and y >= 10 and y <= 55) and not(x >= 25 and x <= 50 and y >= 20 and y <= 45)): print("Dans une zone bleue") elif (((x >= 15 and x <= 45) or (x >= 60 and x <= 85)) and (y >= 60 and y <= 70)): print("Dans une zone rouge") else: print("Dans une zone jaune")

3
11
3
Dans une zone jaune
4
3
Dans une zone jaune
8
56
Dans une zone jaune

Animation avec ipycanvas :

Coder avec le module ipycanvas une animation graphique qui illustre la logique booléenne à l'image du gif de Google en hommage à George Boole :

Si vous ne connaissez pas ce module, il vous faut donc préalablement le prendre en main en faisant, par exemple, les activités de ipycanvas-Le_BN_pour_dessiner.ipynb...

De plus certaines autres fonctionnalités d'ipycanvas pourraient s'avérer utiles dans ce cas d'application :

• Les textes : https://ipycanvas.readthedocs.io/en/latest/drawing_text.html

• Le style dessin à main levé avec RoughCanvas : https://ipycanvas.readthedocs.io/en/latest/rough_canvas.html

• Les boucles d'animation : https://ipycanvas.readthedocs.io/en/latest/animations.html

In [ ]:

# Votre code d'animation avec ipycanvas

# Votre code d'animation avec ipycanvas

---

Références aux programmes :¶

Contenus	Capacités attendues	Commentaires
Valeurs booléennes : 0,1. Opérateurs booléens : and, or, not. Expressions booléennes.	Dresser la table d’une expression booléenne.	Le ou exclusif (xor) est évoqué. Quelques applications directes comme l’addition binaire sont présentées. L’attention des élèves est attirée sur le caractère séquentiel de certains opérateurs booléens.

Pour Aller plus loin :¶

• https://python.developpez.com/cours/DiveIntoPython/php/frdiveintopython/power_of_introspection/and_or.php
• https://docs.python.org/fr/3/library/operator.html

Ce document est mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International.

Pour toute question, suggestion ou commentaire : eric.madec@ecmorlaix.fr

In [ ]: