Algèbre de Boolebliaudet.free.fr/IMG/pdf/IPI-Mat-130-Algebre-de-Boole.pdf · Mathématiques appliquées à l’informatique – Logique - page 5/41 Variable booléenne Une variable

Mathématiques appliquées à l’informatique – Logique - page 1/41

Algèbre de Boole

Bertrand LIAUDET

SOMMAIRE

SOMMAIRE 1Références 3

ALGEBRE DE BOOLE – 1 – EXPRESSION DE BASE 4Définitions 4

L’algèbre de Boole 4Valeur booléenne 4Variable booléenne 5Fonction logique 5

Opérateurs booléens 6Présentation 6La négation : ¬p 6La conjonction : p et q 7La disjonction : p ou q 8

Compléments 9Priorité des opérateurs 9Table de vérité et évaluation d’une expression complexe 9Donner une valeur à une variable 10Expression booléenne 11

Exercices (avec ou sans code Python – série 1 12Préambule 12Evaluation simple 12Table de vérité 13

ALGEBRE DE BOOLE – 2 – PROPRIETE – TAUTOLOGIE 14Propriétés importantes 14

Présentation 14Commutativité et associativité 14Propriétés sur un seul élément – simplification d’expression avec une seule variable 14

Tautologie 16Propriétés = tautologies 16L’équivalence : p <=> q 16Table de vérité et démonstration des propriétés 17


Exercices (avec ou sans code Python) – série 2 18Evaluation simple 18Calcul et développement 18Calcul et démonstration 19

ALGEBRE DE BOOLE – 3 – FND – TABLEAU DE KARNAUGH 20Forme Normale Disjonctive - FND 20

Présentation 20Eléments nécessaires : Forme Conjonctive et Forme Disjonctive 20Forme Normale Disjonctive : FND 21Forme Normale Disjonctive Totalement Développée : FND-TD 21Propriétés 21Méthodes pour trouver une FND et la FND-TD 22Exercices de FND – série 3 22

Tableaux de Karnaugh 23Utilité 23Tableau à 2 variables : a et b 23Tableau à 3 variables : a, b et c 24Tableau à 4 variables : a, b, c et d 26Tableau à plus de 4 variables 26Exercices de tableaux de Karnaugh – Série 4 26

ALGEBRE DE BOOLE – 4 – GENERALISATION – LES 16 OPERATEURS BINAIRES 27Généralisations : les 16 opérateurs binaires 27

Généralisation : les 16 opérateurs binaires 27Autres opérateurs courant : xor, nand, nor, => 28

La disjonction : p xor q 28Le nand : p nand q : négation du et 29Le nor : p nor q : négation du or 29L’implication : p => q 30Exercices sur l’implication 32

Tous les autres opérateurs 34Présentation 34Usages 34

ALGEBRE DE BOOLE – 5 – APPLICATIONS 35Analyse d’un mot de passe 35Circuit à relais 36

Notion de relais 36Circuit ET 36Circuit OU 36


Circuit complexe en OU 36Circuit complexe en ET 36Simplification 37Exercices de circuits à relais 37

Circuit électronique 38Circuit de l’additionneur bit a bit 38Table de vérité l’additionneur 1 bit 38FND de Z et de r 38Transformation supplémentaire 39Conclusion 39Circuit électronique de l’additionneur 1 bit 39

En jaune : là où sont les exercices

Références Mathématique pour l’informatique – BTS SIO – Dunod – 2015 Méthodes mathématiques pour l’informatique – IUT-Licence-Ecole d’ingénieurs-CNAM – Dunond 2013. Notions de Logique – Philippe Thiry – De Boeeck Université – 1997 Site http://exo7.emath.fr/ Dernière édition : septembre 2018


ALGEBRE DE BOOLE – 1 – EXPRESSION DE BASE

Définitions

L’algèbre de Boole L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique. Elle fut lancée en 1854 par le mathématicien britannique George Boole. Aujourd'hui, l'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques. Elle fut utilisée la première fois pour les circuits de commutation téléphoniques par Claude Shannon en 1938. L’algèbre des nombres correspond à une théorisation mathématique de l’arithmétique. C’est la théorie des opérations qu’on peut appliquer aux nombres. L’algèbre des nombres, introduit les notions de variables, d’opérateurs et de fonctions. De même l’algèbre de Boole est une théorisation de la logique introduisant les notions de variables booléennes ainsi que d’opérateurs booléens et de fonctions booléennes s’appliquant à ces variables

Valeur booléenne Une valeur booléenne (ou encore valeur logique ou valeur binaire ou valeur de vérité) est une valeur appartenant à un couple de valeurs possibles dont l’une est l’opposés (ou l’inverse ou la négation) de l’autre. On choisit souvent les couples de valeurs suivants : {0,1} ou {vrai, faux} ou {true, false} ou {V, F}. On utilisera essentiellement {0,1} par la suite. Les deux valeurs 1 et 0 sont dites opposées l’une de l’autre. Un couple de valeurs booléennes {1, 0} peut s’utiliser pour représenter n’importe quel couple de valeurs opposées. Par exemple : ouvert (valeur = 1) et fermé (valeur = 0). Ou encore : allumé (valeur = 1), éteint (valeur = 0).


Variable booléenne Une variable booléenne (ou booléen ou variable logique ou variable binaire) est une variable pouvant prendre des valeurs booléennes. Les variables booléennes sont notées habituellement en minuscule (comme en informatique), en commençant la série par « a » : a, b, c, … ou par « p » : p, q, r. a, en tant que variable booléenne, peut donc valoir 1 ou 0 (ou encore vrai ou faux, true ou false, V ou F). Les variables booléennes peuvent aussi avoir des noms plus longs et plus significatifs, comme on le fait usuellement en programmation : « etatRelai» est une variable (ou un attribut) qui correspond l’état d’un objet relai qui peut être ouvert (valeur = 1) ou fermé (valeur = 0). « etatLampe » est une variable (ou un attribut) qui correspond à un objet « lampe » qui peut être allumée (valeur = 1) ou fermée (valeur = 0). A noter qu’en informatique, on appelle parfois une variable booléenne un « drapeau » ou un « flag » en anglais. Un drapeau peut être levé (valeur = 1) ou baissé (valeur = 0).

Fonction logique

Présentation Une fonction logique (ou booléenne) est une fonction d'une ou plusieurs variables booléennes qui produit comme résultat une valeur booléenne. Les variables sur lesquelles porte la fonction sont appelées entrées. Le résultat de la fonction est appelé sortie. Une fonction logique a des entrées booléennes et une sortie booléenne.

Les 3 principales fonctions logiques non(a) : fonction unaire (avec une seule entrée) qui retourne l’opposé de a. La fonction non(a) correspond à la négation du langage naturel. et(a, b) : fonction binaire (avec 2 entrées) qui retourne 1uniquement si et et b valent 1.La fonction et(a, b) correspond à la conjonction de coordination « et » du langage naturel. ou(a,b) : fonction binaire (avec 2 entrées) qui retourne 0 uniquement si a et b valent 0. La fonction ou(a, b) correspond en partie à la conjonction de coordination « ou » du langage naturel. La fonction définit un « ou » dit inclusif : c’est a ou b ou les 2. Ce n’est pas le « ou » exclusif du langage naturel comme quand on propose « dessert ou café » mais pas les 2.


Opérateurs booléens

Présentation Aux 3 principales fonctions logiques correspondent respectivement les 3 principaux opérateurs logiques. Un opérateur unaire : « non » et 2 opérateurs binaires « et » et « ou ».

La négation : ¬p

Formalisme Fonctions : non(p), not(p) Opérateurs : -p, !p, ¬p,�p

Table de vérité – présentation Une table de vérité est un tableau lignes-colonnes qui permet de définir les valeurs de vérité possibles pour des variables et des expressions booléennes. Chaque colonne de la table correspond à une variable ou à une expression. Les variables sont présentées en premier et dans l’ordre alphabétique. La première ligne contient le nom des variables et les expressions. Les lignes suivantes contiennent les valeurs possibles pour les n-uplets de variables, puis les valeurs des expressions en colonne pour le n-uplets de variables. On commence traditionnellement en mettant un 0 en premier comme valeur possible pour les variables. De ce fait le premier n-uplet de valeurs pour les variables ne contient que des 0 et le dernier que des 1.

Table de vérité de la négation : -p La première colonne correspond à la variable p. La deuxième colonne correspond à l’expression –p. La première ligne commence par la valeur 0 pour p. Dans ce cas, -p vaut 1. La deuxième ligne contient 1 qui est l’autre valeur possible pour p. Dans ce cas –p vaut 0.

Exemples p : 1 -p : 0 q : « PI est un entier » -q : « PI n’est pas un entier » r : 3 > 4 -r : 3 <= 4 non(a) : fonction unaire (avec une seule entrée) qui retourne l’opposé de a. La fonction non(a) correspond à la négation du langage naturel.

Langage naturel Le langage naturel exprime la négation par un «ne pas » : PI est un entier, PI n’est pas un entier. Il exprime aussi la négation par un adjectif à signification contraire : la lampe est allumée, la lampe est éteinte. Toutefois, dans le langage naturel, cette négation peut être ambiguë. Il peut parfois y avoir un troisième terme.

variable expression p - p 0 1 1 0


La conjonction : p et q

Formalisme p et q, p and q, p∧q, p&q, p*q, pxq, p.q, pq, p ∩ q

Table de vérité de la conjonction : p et q La première colonne correspond à la variable p. La deuxième colonne correspond à la variable q. La troisième colonne correspond à l’expression p et q. Pour donner les valeurs aux variables, on commence par mettre une moitié de 0 pour la première variable, p en l’occurrence, puis une moitié de 1. Pour la deuxième variable, q, on met une moitié de 0 pour les cas où p vaut 0, puis une moitié de 1. En l’occurrence, on met un 0 et un 1. On fait de même pour les cas ou p vaut 1. On appliquerait le même principe si on avait plus de 2 variables. Ainsi, la première ligne contient un couple de 0 pour p et q et la dernière un couple de 1. Dans la colonne de l’expression, pour chaque couple de valeurs booléenne, on met le résultat correspondant. En l’occurrence, l’expression « p et q » n’est vrai (ne vaut 1) que si p et q valent chacun 1 individuellement.

Exemples p : les dauphins sont des poissons q : les thons sont des mammifères p et q : 0 p : 0 q : 1 p et q : 0 p : « un triangle rectangle a un angle droit» q : « PI est un entier » p et q : 0 p : 5 > 4 q : 3+3 = 4+2 p et q : 1

Langage naturel p et q veut dire les deux en même temps. C’est vrai uniquement si p et q sont vrais individuellement.

Approche ensembliste Si P et Q sont des ensembles (les animaux marins et les mammifères), les deux en même temps veut dire l’intersection des deux ensembles : les animaux marins qui sont aussi des mammifères, comme par exemple les dauphins et les baleines. A noter que dans ce cas, on écrit plutôt P et Q en majuscules car ce sont des ensembles.

Ø Définition avec des éléments P ∩ Q = { x / x ∈ P et x ∈ Q } P inter Q est égale à l’ensemble des x tels que x appartient à P et x appartient à Q P P ∩ Q Q

variables expression p q p et q 0 0 0 0 1 0 1 0 0 1 1 1

x1 x2 x3 x4 x5 x6 P ∩ Q = { x3, x4 }


La disjonction : p ou q

Formalisme p ou q, p or q, p∨q, p+q, p ∪ q

Table de vérité de la conjonction : p ou q La construction de la table est la même que pour p et q. Seules les valeurs de l’expression changent. Dans la colonne de l’expression, pour chaque couple de valeurs booléennes, on met le résultat correspondant. En l’occurrence, l’expression « p ou q » n’est faux (ne vaut 0) que si p et q valent chacun 0 individuellement.

Exemples p : les dauphins sont des poissons q : les thons sont des mammifères p ou q : 0 p : 0 q : 1 p ou q : 1 p : « un triangle rectangle a un angle droit» q : « PI est un entier » p ou q : 1 p : 5 > 4 q : 3+3 = 4+2 p ou q : 1

Langage naturel p ou q veut dire l’un ou l’autre ou les deux en même temps. C’est faux uniquement si p et q sont faux individuellement. Il s’agit là d’un « ou » dit inclusif : c’est p ou q ou les 2. Ce n’est pas le « ou » exclusif du langage naturel comme quand on propose « dessert ou café » mais pas les 2.

Approche ensembliste Si P ou Q sont des ensembles (les animaux marins et les mammifères), l’un ou l’autre veut dire l’union des deux ensembles : les animaux marins et les mammifères, comme par exemple les les lions, les thons et les dauphins. A noter que dans ce cas, on écrit plutôt P et Q en majuscules car ce sont des ensembles.

Ø Définition avec des éléments

P ∪ Q = { x / x ∈ P ou x ∈ Q ) E union F est égale à l’ensemble des x tel que x appartient à E ou x appartient à F P Q

variables expression p q p ou q 0 0 0 0 1 1 1 0 1 1 1 1

<---------------- P ∪ Q ----------------->

x1 x2 x3 x4 x5 x6 P ∪ Q = { x1, x2, x3, x4, x5, x6 }


Compléments

Priorité des opérateurs 1. Les parenthèses sont prioritaires sur les opérateurs. 2. L’opérateur unaire de négation est prioritaire sur les opérateurs binaires 3. L’opérateur « et » est prioritaire sur l’opérateur « ou » 4. Les opérateurs de comparaison arithmétique (==, >, >, etc) sont prioritaires sur les opérateurs

de logique propositionnelle (et, ou, implique, etc.).

Table de vérité et évaluation d’une expression complexe

Table de vérité avec 2 variables Soit l’expression : p ou (-p et r) On commence par mettre les propositions atomiques en colonnes. Ensuite met les négations qui interviennent dans la propositions complexes. Ensuite on met les opérations à faire dans l’ordre de l’évaluation. : ici d’abord le « et » puis le « ou »

variables expressions

p r -p -p et r p ou (-p et r)

0 0 1 0 0 0 1 1 1 1

1 0 0 0 1 1 1 0 0 1


Table de vérité avec 3 variables Soit l’expression : p ou (q et –r) On commence par mettre les propositions atomiques en colonnes. Ensuite met les négations qui interviennent dans la propositions complexes. Ensuite on met les opérations à faire dans l’ordre de l’évaluation : ici d’abord le « et » puis le « ou »

Donner une valeur à une variable On utilise le signe = qui permet de donner une valeur à la variable à gauche du signe =. La valeur correspond à celle de l’expression qui est à droite du signe =. p = 1 q = 0 a = p et q : dans ce cas, a vaut 0. p et q vaut 1 uniquement si p vaut 1 et q aussi. b = p ou q : dans ce cas, b vaut 1. p ou q vaut 0 uniquement si p vaut 0 et q aussi. c = -a et b : dans ce cas -a vaut 1 et b vaut 1. Et donc c vaut 1.

variables expressions

p q r -r q et –r p ou (q et –r)

0 0 0 1 0 0

0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1


Expression booléenne

Définition Une expression booléenne est une suite d’opérations dont le résultat est une valeur booléenne. Ces opérations utilisent des variables booléennes et des opérateurs booléens (et/ou des fonctions booléennes). On peut aussi y trouver des fonctions non booléennes mais retournant une valeur booléenne. On peut aussi y trouver des expressions mathématiques de comparaison. Par exemple : « x > y » est une expression mathématique. On peut la noter « p ». On écrira : p = « x > y ». Elle peut être vraie (valeur = 1) ou fausse (valeur = 0). De même pour « x = y ». On peut aussi y trouver des propositions en français. Une proposition est un énoncé ayant un sens et qui peut être vraie ou fausse. Par exemple : « il pleut » et une proposition. On peut la noter « p ». On écrira : p = « il pleut ». Elle peut être vraie (valeur = 1) ou fausse (valeur = 0).

Exemples d’expressions

Ø Expressions avec des variables, des opérateurs et des fonctions booléennes

Expression Explications 1 Expression la plus simple : uniquement une valeur booléenne. not(1) Négation du 1. Ca vaut 0. a Expression booléenne si a est une variable booléenne -a Négation de la précédente. C’est donc une expression booléenne. (-a ou b) et c Expression booléenne si a, b et c sont des variables booléennes.

Ø Expressions avec une fonction retournant un booléen

a et sortieAutorisée(température, hygrométrie)

Expression logique à condition que « a » soit une variable booléenne et que la fonction sortieAutorisée renvoie une valeur booléenne. A noter que les paramètres de cette fonction ne sont pas des booléens.

Ø Expressions avec des formules mathématiques de comparaison

1 > 2 Expression logique qui est fausse x > 0 Expression logique qui peut être vraie ou fausse en fonction de la valeur de

x. x == y Expression logique de comparaison d’égalité (opérateur ==) qui peut être

vraie ou fausse en fonction de la valeur de x et de y. -(x == y) et x>0

Expression logique utilisant un opérateur booléen et deux comparaisons mathématiques.

Ø Expressions avec des propositions

Il pleut Proposition qui peut être vraie ou fausse Il ne pleut pas Négation de la proposition précédente. Elle peut être vraie ou fausse. Il pleut et (x>0) ou a

Expression logique utilisant une proposition, un opérateur booléen, une comparaison mathématique et une variable booléenne.


Exercices (avec ou sans code Python – série 1

Préambule

Remarques syntaxiques Le symbole « = » est un symbole d’assignation (ou affectation) : il permet de donner une valeur à une variable. Ce n’est pas un symbole de comparaison d’égalité. Le symbole « == » est un symbole de comparaison d’égalité.

Utilisation de Python Python peut être installé nativement sur la machine. Tester la commande python dans un terminal (cmd sous Windows, terminal sous MacOS) Si python n’est pas installé, installer un anaconda. Syntaxe python : négation : fonction logique not() ou l’opérateur not. Mieux vaut éviter le « - ». et : opérateur « and » ou « & ». ou : opérateur « or » ou « | » (pipe, barre avec un espace au milieu). Dans l’interpréteur python, quand on tape une expression et qu’on tape sur « entrée », on obtient la valeur de l’expression. Donc, si on tape 4+3 on obtient 7. Si on tape 2>3 on obtient False. Si on tape a=2>3, on obtient aucun affichage. Mais la variable « a » a été créée. Si on tape « a », on obtient False.

Evaluation simple

Exercice 1 4>=2 # combien vaut cette expression 2==4-2 # combien vaut cette expression 2>3 # combien vaut cette expression p=2>3 # combien vaut p ? q=-p # combien vaut q ? 2==4-2 # combien vaut cette expression -(2==4-2) # combien vaut cette expression a=2==4-2 # combien vaut a ? b=2==2+2 # combien vaut b ? -a ou b # combien vaut cette expression

Exercice 2 p= 3 >2 et 6>5 # combien vaut p ? p= 2 >3 et 6>5 # combien vaut p ? p= 3 >2 ou 7 >6 # combien vaut p ?


p= 3 >2 ou 5 >6 # combien vaut p ? p= 3 >4 ou 5 >6 # combien vaut p ? x=0 p= x>0 et x<10 # combien vaut p ? x=5 p= x>0 et x<10 # combien vaut p ? p= x<0 ou x>10 # combien vaut p ? x=20 p= x<0 ou x>10 # combien vaut p ?

Exercice 3 Principe : si un réel intervient dans une proposition booléenne, s’il vaut 0, il vaut faux sinon il vaut vrai. En python : not(1) vaut faux, not(0.5) vaut faux. En python, bool(0) vaut faux. bool(réel) donne vrai si le réel est différent de 0.

x=5; y=10 p= x>0 et x<10 ou y <100 # combien vaut p ? p= x>0 et (x<10 ou y <100) # combien vaut p ? p= faux et faux or vrai # combien vaut p ? p= faux et (faux or vrai) # combien vaut p ? p= (4==4) et vrai # combien vaut p ? p= 4== (4 et vrai) # combien vaut p ? p= 4==4 et vrai # combien vaut p ?

Table de vérité

Exercice 1 Construire la table de vérité des propositions suivantes : • p et non(q) • p et non(q) ou r • non ((non p) ou q) et r


ALGEBRE DE BOOLE – 2 – PROPRIETE – TAUTOLOGIE

Propriétés importantes

Présentation De nombreuses propriétés sont remarquables et vont nous permettre de transformer les expressions pour les simplifier et les écrire comme bon nous semble. Une propriété s’exprime sous la forme d’une équivalence entre deux expressions booléennes. L’équivalence veut dire que chaque des deux expressions aura la même valeur booléenne quelle que soit la valeur des variables qui la composent.

Commutativité et associativité Ces propriétés sont assez intuitives. 1 Commutativité du « et » p et q <=> q et p 2 Commutativité du « ou » p ou q <=> q ou p

3 Associativité du « et » (p et q ) et r <=> p et (q et r) 4 Associativité du « ou » (p ou q ) ou r <=> p ou (q ou r)

Propriétés sur un seul élément – simplification d’expression avec une seule variable Ces propriétés sont plus ou moins intuitives intuitives. Elles sont particulièrement utiles pour simplifier les expressions booléennes. 5 Idempotence du et p et p <=> p 6 Idempotence du ou p ou p <=> p 7 Double négation non(non(p)) <=> p 8 Principe de non contradiction p et !p <=> faux 9 Principe du tiers exclu p ou !p <=> vrai 10 Vrai est l’élément neutre du et p et vrai <=> p 11 Faux est l’élément absorbant du et p et faux <=> faux 12 Faux est l’élément neutre du ou p ou faux <=> p 13 Vrai est l’élément absorbant du ou p ou vrai <=> vrai


Propriété du « ou » – simplification d’expression avec 2 variables 14 Simplification d’une disjonction factorisable -1 p ou pq <=> p 15 Simplification d’une disjonction factorisable -2 pq ou p!q <=> p

Ø La première propriété n’est pas évidente. On la démontre ainsi : Si p est Vrai, alors Vrai ou pq vaut Vrai car Vrai est l’élément absorbant du ou. Donc Vrai ou pq vaut p. Si p est Faux, alors pq est Faux d’après la table de vérité du « et ». Donc p ou pq vaut Faux d’après la table de vérité du « ou ». Donc les deux expressions sont fausses. Donc, quelle que soit la valeur de p, ce sera la même pour p ou pq. On peut aussi démontrer la propriété en utilisant une table de vérité (ce sera un exercice de ce chapitre).

Ø La deuxième propriété peut se démontrer en factorisant le p Cf. Exercices.

Distributivité On a une distributivité du « ou » sur le « et » et du « et » sur le « ou ». Les propriétés consistent à ajouter ou supprimer des parenthèses. 16 Distributivité du « ou » sur le « et »

ajout de parenthèses p ou (q et r) <=> (p ou q) et (p ou r) p ou qr <=> (p ou q) et (p ou r)

17 Distributivité du « et » sur le « ou » suppression de parenthèses

p et (q ou r) <=> (p et q) ou (p et r) p et (q ou r) <=> pq ou pr

On peut démontrer la propriété en utilisant une table de vérité (ce sera un exercice de ce chapitre).

Lois de Morgan

18 Loi de Morgan - 1 - (p et q) <=> -p ou -q 19 Loi de Morgan - 2 - (p ou q) <=> -p et -q

On peut démontrer la propriété en utilisant une table de vérité (ce sera un exercice de ce chapitre).


Tautologie

Propriétés = tautologies Les propriétés sont des expressions logiques qui sont toujours vraies. On les appelle des « tautologies » : toutes les propriétés sont des tautologies. On peut écrire : T = p et q <=> q et p (commutativité). ou T = p ou (q et r) <=> (p ou q) et (p ou r) (distributivité). Une tautologie correspond à une formulation du type a <=> b L’expression a <=> b est une expression booléenne : elle peut être vraie ou fausse. Le symbole d’équivalence, <=>, est un opérateur booléen.

L’équivalence : p <=> q

Formalisme p <=> q

Table de vérité de la conjonction : p <=> q La construction de la table est la même que pour les opérateurs « et » et « ou ». Dans la colonne de l’expression, pour chaque couple de valeurs booléenne, on met le résultat correspondant. En l’occurrence, l’expression « p <=> q » est vraie si les valeurs de p et q sont identique, fausse sinon.

Langage naturel L’équivalence consiste à dire la même chose mais autrement. C’est une transformation de la formulation qui permet éventuellement de découvrir, en mettant au jour, quelque chose qui était caché. En mathématique, une résolution d’équation fonctionne par équivalences : on part d’une équation dans laquelle la valeur d’une variable, un « x », est cachée, pour arriver à une valeur de « x » explicite. En algèbre de Boole, l’équivalence va permettre de transformer et simplifier les expressions.

variables expression p q p <=> q 0 0 1 0 1 0 1 0 0 1 1 1


Table de vérité et démonstration des propriétés

Tautologie et table de vérité La table de vérité d’une tautologie ne contient que des 1 (que des Vrai).

Démonstration d’une propriété avec une table de vérité Pour démontrer les propriétés, on utilise un tableau de vérité et on calcule la valeur de vérité de la propriété à démontrer. Dans tous les cas pour les propositions de départ, la tautologie doit être vraie.

Exemple de démonstration : la double négation Démontrer la tautologie T = p <=> - (-p)

Ø Démonstration :

p -p - (-p) T = p <=> - (-p) 0 1 0 1 1 0 1 1

On a que des 1 (vrai) pour la tautologie quelles que soient les valeurs de départ de p.

Exemple de démonstration : la distributivité du « ou » sur le « et » Démontrer la tautologie T = p ou (q et r) ⇔ (p ou q) et (p ou r)

Ø Démonstration :

p q r q et r A = p ou (q et r)

p ou q p ou r B= (p ou q) et (p ou r)

T = A<=>B

0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1

On a que des 1 (vrai) pour la tautologie T quelles que soient les valeurs de départ de chacune des propositions atomiques.


Exercices (avec ou sans code Python) – série 2

Evaluation simple

Exercice 1 : Quelle est la valeur de vérité des propositions suivantes En python, on peut utiliser l’opérateur « is » pour un opérateur d’équivalence. Mieux vaut parenthèser les termes autour du is. Logique en python : ici. 1. x=1 ; 4x - 8 == 0 <=> x == 2 2. x=2 ; 4x - 8 == 0 <=> x == 2 3. x=1 ; 4x – 8 == 0 <=> x == 1 4. x=2 ; 4x – 8 == 0 <=> x == 1 5. x=3 ; 4x – 8 == 0 <=> x == 1 6. 4 + 4 == 8 <=> 1 < 2 7. 4 + 4 == 9 <=> 1 < 2 8. 4 + 4 == 9 <=> 2 < 1 9. « La Terre est un cube <=> Les chats ont 6 pattes »

Calcul et développement

Exercice 1 : Développez jusqu’à retirer les parenthèses et simplifiez 1. non(a et b) ou a 2. non(a ou b) et a

Exercice 2 : Donner la négation des phrases suivantes : 1. x >= 3 1. 0 < x <=2 2. p et q et r 3. (p ou q) ou r 4. p ou (q et r) 5. (p ou q) et r

Exercice 3 : Développer et simplifier 1. (p ou –q) et (-p ou q)


Calcul et démonstration

Exercice 4 : Démontrer les propriétés suivantes 1. Démontrez avec une table de vérité la loi de Morgan-1

Exercice 5 : Démontrer les propriétés suivantes En utilisant les propriétés (il faut développer et simplifier) En utilisant une table de vérité 1. p ou pq <=> p 2. ab ou abc <=> ab 3. pq ou p!q <=> p


ALGEBRE DE BOOLE – 3 – FND – TABLEAU DE KARNAUGH

Forme Normale Disjonctive - FND

Présentation Pour simplifier les formulations booléennes, on va chercher à obtenir des formulations ressemblant à : « pqr ou !pq ou qr », c’est à dire des disjonctions (ou) de conjonctions (et). L’intérêt est de pouvoir simplifier les formules et de pouvoir les utiliser facilement en électronique et aussi en programmation. On va donc présenter plus précisément ces « disjonctions de conjonctions » : ce sont les FND. On verra ensuite les méthodes permettant de construire une FND et de la simplifier.

Eléments nécessaires : Forme Conjonctive et Forme Disjonctive

Forme Conjonctive : FC Une expression booléenne constitué de variables ou de leurs négations reliées entre elle uniquement par des conjonctions est une Forme Conjonctive : FC. Pour simplifier l’écriture, pour la négation, on utilise le « ! » ou la barre de négation :�p . Pour la conjonction, on utilise l’absence de symbole : pq, pqr, etc. Exemples de FC : « pq » « !pq » « p !q » « pq !r » « p » « !p » etc.

Forme Disjonctive : FD Une expression booléenne constitué de variables ou de leurs négations ou de FC, reliées entre elle uniquement par des disjonctions est une Forme Disjonctive : FC.

Exemples de FD : « pq ou !pq » «p ou pq !r ou !pr » « p ou !pq » etc.


Forme Normale Disjonctive : FND Une FND est une FD telle que on ne peut pas trouver une variable simple et sa négation dans une FC. Exemple de FND : « pqr ou !pqr ou r ». « r » est le seul atome. « !r » n’est pas présent dans une FC de la FND. Exemple de FD qui ne soit pas une FND : « p ou !pq ». En effet, « p » est un atome et « !p » se trouve dans une FC. La FND correspondante est : « p ou q ». Démonstration : p ou !pq <=> (p ou !p) et (p ou q) à distributivité <=> vrai et (p ou q) à principe du tiers exclu <=> p ou q à Vrai est l’élément neutre du et

Forme Normale Disjonctive Totalement Développée : FND-TD Une FND-TD est une FND dans laquelle chaque FC contient toutes les variables booléennes. Exemple de FND qui ne soit pas une FND-TD : « p!q!r ou pq ou qr ». On a 3 variables. La première FC contient 3 variables. Mais les 2 suivantes n’en contiennent que 2. Il faut donc les développer. pq <=> pqr ou pq !r qr <=> pqr ou !pqr Donc la FNT-TD = p!q!r ou pqr ou pq !r pqr ou !pqr Ce qu’on peut simplifier puisqu’on trouve plusieurs fois la même FC : FND-TD = pqr ou pq !r ou p!q!r ou !pqr

Propriétés

• Toute proposition peut s’écrire sous la forme d’une FND. • Une proposition peut avoir plusieurs FND. • Une proposition a une et une seule FND-TD.


Méthodes pour trouver une FND et la FND-TD

Méthode 1 pour construire une FND Traduire, si nécessaire, tous les connecteurs en « non », « et » et « ou ». Eliminer les doubles négations. Utiliser les lois de Morgan pour supprimer les parenthèses. Utiliser les lois de la distributivité du « et » sur le « ou » pour supprimer les parenthèses.

Méthode n°2 pour construire la FND-TD d’une proposition quelconque Faire la table de vérité de la proposition traitée. On regarde quelles sont les lignes sont vraies pour la proposition. Chaque ligne vraie va correspondre à une FC de la FND-TD. Chaque FC sera la conjonction des propositions atomique, vraies ou fausses.

Méthode n°3 pour construire une FND Construire la FND-TD à partir de la table de vérité. Il reste ensuite à transformer le résultat pour obtenir une FND simplifiée. On peut appliquer la loi de Simplification d’une disjonction factorisable. Ou utiliser les tableaux de Karnaugh.

Exercices de FND – série 3 1. Sachant que P, Q, R sont des propositions, écrire à la négation des propositions suivantes

sous la forme d’une FND • P et (Q et R) • P ou (Q et R)

2. Pour chaque expression :

2.1 Donnez la FND-TD à partir de la table de vérité 2.2 Trouvez une FND par la méthode 1. 2.3 Transformez la FND en FNT-TD • a (b ou !a) ou c • ab ou bc et ca • (a ou bc)( !a ou !b !c)


Tableaux de Karnaugh

Utilité Ces tableaux permettent de produire des formes normales disjonctives (FND) plus facilement. On distingue deux cas : les tableaux à 2 variables et ceux à 3 variables.

Tableau à 2 variables : a et b

Construction du tableau pour une expression à 2 variables booléennes Le tableau a 4 cases. On croise les valeurs de vérité de 2 variables : « a » et « b ». On obtient un tableau à 4 cases :

Chaque case correspond à une FC :

Utilisation du tableau Quand on a une expression, par exemple : ab +�b , on colorie la case du ab et la colonne du�b : A partir de là, on analyse le résultat graphique pour produire la FND la plus simple. Ici on voit que la ligne du « a » est pleine ainsi que la colonne du « b », donc on peut écrire : ab +�b <=> a +�b

Résultat obtenu par calcul On aurait pu trouver ce résultat par calcul, mais ça va plus vite avec le tableau. Par calcul : ab +�b <=> (a +�b) et (b +�b) à distribution du « ou » sur le « et <=> (a +�b) et Vrai à principe du tiers exclu <=> (a +�b) à Vrai élément neutre du « et»

b �b

a

�a

b �b

a a b a�b

�a �a b �a �b

b �b

a a b a�b

�a �a b �a �b


Tableau à 3 variables : a, b et c

Construction du tableau pour une expression à 3 variables booléennes Le tableau a 8 cases. On croise les valeurs de vérité de 3 variables : « a », « b » et « c ». Le tableau aura 8 cases : on croise les valeurs de vérité de a avec celles des couples possibles entre b et c : b c, b�c, �b�c, �b c dans cet ordre là par convention. On obtient un tableau à 8 cases :

La première ligne correspond à « a ». La suivante à �a Les deux premières colonnes correspondent à « b ». Les deux dernières à « c ». La première colonne correspond à « bc », la suivante à « b�c » , puis «�b�c » et enfin «�b c » Chaque case correspond à une FC :

Utilisation du tableau Soit P = -ab + abc + b-c + -a-b. C’est une FND On présente ci-dessous les cases correspondantes à chaque FC :

b �b

b c b�c �b�c �b c

a

�a

b �b b c b�c �b�c �b c

a a b c a b�c a�b�c a�b c

�a �a b c �a b�c b �a�b�c �a�b c


b-c : a a b c a b�c a�b�c a�b c



-a-b : a a b c a b�c a�b�c a�b c



-ab : a a b c a b�c a�b�c a�b c



abc : a a b c a b�c a�b�c a�b c



Dans un tableau unique, on grise toutes les cases : b c b�c �b�c �b c

a a b c a b�c a�b�c a�b c


Quelle FND peut-on produire à partir du tableau ? On a la ligne du -a et les colonnes du b, donc P = -a + b

Résultat obtenu par calcul On aurait pu trouver ce résultat par calcul, mais c’est compliqué ! Il faut appliquer le principe du tableau mais « à la main ». D’abord, on passe d’une FND à une FND-TD : P = -ab + abc + b-c + -a-b. P = (-abc + -ab-c) + (abc) + (ab-c + -ab-c) + (-a-bc + -a-b-c) De là on supprime les doublons (qui sont soulignés) P= -abc + -ab-c + abc + ab-c + -a-bc + -a-b-c Puis on va regarder si on a : 4 a, ou 4-a, idem avec b et c. On a 4 –a, donc tous les cas de –a sont présents. On peut réduire les 4 –a à « -a ». Il reste : abc + ab-c Avec ces 2 éléments là et ceux présents dans « -a », peut-on trouver 4 b, 4 –b, 4 c ou 4 -c ? Oui, on a 4 b. On peut donc réduire les deux éléments restants à « b ». Et la formule simplifiée devient : -a + b Il faut noter qu’un algorithme automatique traiterait facilement le problème.


Tableau à 4 variables : a, b, c et d

Construction du tableau pour une expression à 4 variables booléennes et plus Le tableau aura 16 cases : on croise les valeurs de vérité de du couple ab avec celles du couple cd. L’utilisation est la même que pour un tableau à 3 variables.

Résultat obtenu par calcul Même principe que pour une expression à 3 variables.

Tableau à plus de 4 variables La construction du tableau devient compliquée. Mieux vaut utiliser la méthode par calcul et avoir un algorithme qui traite le problème de façon général !

Exercices de tableaux de Karnaugh – Série 4 1. Reprendre les FND-TD des exercices de FND et simplifiez les FNT-TD à l’aide de tableau de

Karnaugh : vérifiez que vous retrouvez les mêmes résultats.

2. Soit A = ab + non(c) et B=non(a) + bc Déterminer la FND et non(A) et de non(B) en utilisant un tableau de Karnaugh, puis sans tableau.

3. Soit A=non(c)a+non(b)c+abd et B=non(a)b+non(b)c+non(c)a Déterminer la FND et non(A) et de non(B) en utilisant un tableau de Karnaugh, puis sans tableau.

c �c

c d c�d �c�d �c d

a a b

a�b

�a �a�b

�a b


ALGEBRE DE BOOLE – 4 – GENERALISATION – LES 16 OPERATEURS BINAIRES

Généralisations : les 16 opérateurs binaires

Généralisation : les 16 opérateurs binaires Quand on fait la table de vérité d’une opération binaire, on obtient un résultat qu’on peut lire comme un nombre binaire à 4 chiffres : P et Q = 0 0 0 1. Valeur de vérité p q p et q 0 0 0 0 1 0 1 0 0 1 1 1 Ilyadoncautantderésultatspossiblesquedecodagespossiblessur4chiffresbinaires=24=16Onpeutdoncfaireletableaudesrésultatspourles16caspossibles,qu’onnumérotede0à15etquicorrespondeauchiffrebinairedelacolonneluedebasenhaut.Ainsilacolonnen°7correspondauchiffrebinaire0111.

p q et ou ó

p q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Lecas2correspondau«et»: pop2q<=>petqLecas8correspondau«ou»: pop8q<=>pouqLecas10correspondau«<=>»: pop10q<=>(p<=>q)Cela nous montre qu’il y a 13 autres opérateurs que les 3 premiers que nous avonsprésentés.Certainsontunusagecourant,d’autressontplusanecdotiques.


Autres opérateurs courant : xor, nand, nor, =>

p q et xor ou nor ó => nand

p q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

La disjonction : p xor q

Formalisme p xor q, p ⊕ q

Table de vérité de la conjonction : p xor q L’un ou l’autre mais pas les deux. Opérateur n°6.

Langage naturel p ou q veut dire l’un ou l’autre mais pas les deux comme quand on propose « dessert ou café » mais pas les 2.

Approche ensembliste Si P ou Q sont des ensembles (les animaux marins et les mammifères), l’un ou l’autre mais pas les deux veut dire l’union des deux ensembles sans leur intersection : les animaux marins non mammifères et les mammifères non marins, comme par exemple les les lions et les thons mais pas les dauphins. A noter que dans ce cas, on écrit plutôt P et Q en majuscules car ce sont des ensembles.

Ø Définition avec des éléments

P ∪ Q = { x / x ∈ P ou x ∈ Q ) E union F est égale à l’ensemble des x tel que x appartient à E ou x appartient à F P Q

variables expression p q p xor q 0 0 0 0 1 1 1 0 1 1 1 0

<-------------> P xor Q <-------------->

x1 x2 x3 x4 x5 x6 P xor Q = { x1, x2, x5, x6 }


Le nand : p nand q : négation du et

Formalisme p nand q

Table de vérité de la conjonction : p xor q Opérateur n°14. p nand q <=> -(p et q)

Langage naturel C’est la négation du et. Pas de signification claire.

Utilité Le nand est opérateur qui peut être pratique pour certains circuits électroniques.

Le nor : p nor q : négation du or

Formalisme p nor q

Table de vérité de la conjonction : p xor q Opérateur n°8. p nor q <=> -(p ou q)

Langage naturel C’est la négation du ou. Pas de signification claire.

Utilité Le nor est opérateur qui peut être pratique pour certains circuits électroniques.

variables expression p q p nand q 0 0 1 0 1 1 1 0 1 1 1 0

variables expression

p q p nor q 0 0 1 0 1 0 1 0 0 1 1 0


L’implication : p => q

Formalisme p => q, p implique q, p donc q, si p alors q, p -> q

Antécédent et conséquent. « p » est l’antécédent, « q » est le conséquent.

Table de vérité de la conjonction : p => q Opérateur n°13. p nor q <=> -(p ou q)

Langage naturel - exemple Il pleut donc le sol est mouillé. p = il pleut q = le sol est mouillé p => q On peut aussi dire : si il pleut alors le sol est mouillé.

Condition suffisante et condition nécessaire Pour qu’il y ait implication, il faut : • que l’antécédent soit une condition suffisante du conséquent • que le conséquent soit une condition nécessaire de l’antécédent. C’est ce critère qui permet de savoir qui est l’antécédent et qui est le conséquent : pour que p il suffit que q.

Ø Exemple Il pleut donc le sol est mouillé. La pluie est une condition suffisante d’un sol mouillée. Il suffit qu’il pleuve pour que le sol soit mouillé. Le sol mouillé est une condition nécessaire de la pluie. Il faut (nécessité) que le sol soit mouillé pour dire qu’il pleuve. C’est nécessaire mais pas suffisant : si on a que cette information (le sol mouillé), il ne pleut pas forcément. A noter que le sol veut dire sol à l’air libre.

2 Propriétés fondamentales de l’implication 1 Transformation d’un => en « et » ou en « ou » p => q <=> - (p et –q)

<=> - p ou q 2 Contraposée p => q <=> - q => –p

variables expression

p q p nor q 0 0 1 0 1 1 1 0 0 1 1 1


Signification de la propriété 1 : P => Q <=> non (P et nonQ) P => Q <=> on ne peut pas avoir P sans Q : non (p et non q). P => Q <=> non (P et nonQ)

Ø Par exemple : Il pleut donc le sol est mouillé. p = il pleut. q = le sol est mouillé. p => q <=> non (p et non q) Ce qu’on peut traduire par : on ne peut pas avoir de la pluie sans que le sol soit mouillé.

Signification de la propriété 2 : la contraposée : P=>Q <=> nonQ => nonP

Ø Par exemple : Il pleut donc le sol est mouillé. p = il pleut. q = le sol est mouillé. p => q <=> non q => non p Le sol n’est pas mouillé donc il ne pleut pas.

Propriété secondaire : P => P P => P est toujours vrai. On peut le démontrer avec une table de vérité ou en utilisant la propriété 1.

Bizarrerie : du faux, on peut tout déduire A partir d’une proposition fausse, on peut tout déduire, du faux et du vrai. Autrement dit : « la lune est un gruyère implique que les poules ont des dents » est vrai ! C’est étrange, mais on le comprend aisément si on sait que : non (A et B) ó nonA ou nonB (lois de Morgan : cf suite du cours) Donc P=>Q ó non (P et nonQ) ó nonP ou Q Donc, si nonP est vrai alors nonP ou Q est vrai et donc P=>Q est vrai. Donc si P est faut, P => Q est vrai


Exercices sur l’implication

Implication et proposition 1. L’énonce « s’il pleut alors il ne pleut pas » est-il une proposition ? Si oui, quelle est sa valeur

de vérité ? 2. Doit-on dire : « Le temps est sec donc il ne pleut pas » ou « Il ne pleut pas donc le temps est

sec » ? Traduisez en propositions symbolique les énoncés et justifier votre réponse. Donnez aussi la contraposé.

3. Traduisez en propositions et implications les phrases suivantes. Dans chaque cas, donnez

aussi la contraposé • Le cours a lieu si le professeur est arrivé. • Je cours beaucoup donc je suis fatigué • Si l’accusé est coupable il n’a pas d’alibi. • Pour que les étudiants réussissent, il faut qu’ils étudient. 4. Dans les deux derniers cas, faites le tableau de vérité et interpréter tous les cas.

Traduire en langage symbolique les expressions suivantes Si on a une implication, donner la contraposée. Donner la formulation en français de la traduction symbolique. Donner la formulation en français de la contraposée, s’il y a lieu. 1. Le monde n’a ni commencement ni fin. 2. Un quadrilatère est un carré seulement si c’est un losange. 3. Pour que cette enveloppe soit ouverte il faut que Jean ait été informé à moins que Pierre ait

oublié de la coller. 4. On ne devient pas un musicien accompli sans apprendre à lire les notes et à jouer d’un

instrument. 5. Si le règlement est très strict mais est le même pour tout le monde alors les étudiants ont tort

de le contester.

Construire la table de vérité des expressions précédentes à partir de leur formule en langage symbolique

Implication et calcul logique 1. A l’aide d’une table de vérité, démontrer que P => Q ⇔ non(P et non(Q)) 2. A l’aide d’une table de vérité, démontrer que P => Q ⇔ nonQ => nonP 3. Sachant que P, Q, R, S sont des propositions, écrire à la négation de la proposition suivante

sous la forme d’une disjonction de propositions atomiques ou de conjonctions. • (P et Q) ⇒ (R ⇒S)


4. Démontrer avec une table de vérité l’équivalence entre implication et disjonction. 5. Faire la table de vérité des expressions suivantes

• !p => (p ou q) • p ou !q => !p ou r

6. Ecrire la négation de la proposition suivante • 1. P⇒Q

(Exercice 8 de exo7.emath.fr). 7. La proposition suivante est-elle vraie ?

• P ∧ Q ⇒ (¬P) ∨ Q (Exercice 19 de exo7.emath.fr)

Exercices de FND Pour chaque expression :

• Donnez la FND-TD à partir de la table de vérité • Trouvez une FND par la méthode 1. • Transformez la FND en FNT-TD

1. a =>b 2. !( (p=>q)=>r ) 3. (q ou r) => (r=> !q) 4. a xor b


Tous les autres opérateurs

Présentation

p q -T et -=> Ag -<= Ad xor ou nor ó -Ag <= -Ad => nand T

p q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Symbole numéro ExplicationspTq Op15 opérateurdeTautologie.Rendl’expressionvraiepourtousles

cas.p-Tq Op0 négation de l’opérateur de Tautologie. –(p T q). Rend

l’opérationfaussepourtouslescas.p<=q Op11 Implicationinverse:q=>pp-<=q Op4 Négationdel’implicationinverse:-(q=>p)p-=>q Op2 Négationdel’implication:-(p=>q)pAgq Op3 Opérateurabsorbantàgauche.Sonrésultatestl’opérandede

gauche.pApq<=>p

p-Agq Op12 Négationdel’opérateurabsorbant:-(pAgq)pAdq Op5 Opérateurabsorbantàdroite.Sonrésultatestl’opérandede

gauche.pAdq<=>q

p-Adq Op12 Négationdel’opérateurabsorbant:-(pAdq)

Usages

Cesopérateursontpeud’utilité!


ALGEBRE DE BOOLE – 5 – APPLICATIONS

Analyse d’un mot de passe D’après Mathématiques pour l’informatique – Dunod – Chanet et Vert.

On s’intéresse à la connexion à un site internet. La connexion exige un mot de passe entre 8 et 12 caractères qui peuvent être des majuscules, des chiffres ou des caractères spéciaux. Le mot de passe doit avoir au moins 3 chiffres et 3 caractères spéciaux, ou alors au moins 5 lettres, ou alors moins de 3 chiffres mais au moins 5 lettres et 3 caractères spéciaux. 1) Par les mots clés ci-dessous, lesquels sont valides ? Pourquoi ?

H32EXZ&K5= LUC230598** 123(M*K<4 2) On souhaite créer un mot de passe de 4 lettres, 4 chiffres et 4 caractères spéciaux. Est-ce

possible ? Pourquoi ? 3) On souhaite créer un mot de passe de 8 lettres. Est-ce possible ? Pourquoi ? 4) Définir 3 variables booléennes permettant de traduire les conditions de validité d’un mot de

passe. 5) Ecrire une expression logique utilisant les variables booléennes précédente et permettant de

définir si un mot de passe est valide ou pas. On appellera P cette expression. 6) Trouver une expression simplifiée de P avec un tableau de Karnaugh. 7) Trouver une expression simplifiée de P par le calcul en utilisant les propriétés. 8) Exprimer en français les conditions pour que le mot de passe soit valide. 9) Déterminer –P à partir du tableau de Karnaugh 10) Déterminer –P par le calcul 11) Exprimer en français les conditions pour que le mot de passe ne soit pas valide. L’intérêt de la FND et du tableau de Karnaugh est de réaliser plus facilement des circuits électroniques.


Circuit à relais L’intérêt de la FND et du tableau de Karnaugh est de réaliser plus facilement des circuits électroniques.

Notion de relais Les relais peuvent être ouverts ou fermés et ainsi laisser ou non passer le courant. Un relais ouvert vaut 1. Un relais fermé vaut 0.

Circuit ET Le courant circule de l’entrée E vers la sortie S en passant par 2 relais A et B. E ---------------------- A ------------------------ B -----------------------S Le courant passe si A et B sont ouverts. La fonction du circuit est f(A,B) = A et B

Circuit OU Le courant circule de l’entrée E vers la sortie S en passant par 2 relais A et B. |--------------A ------------| E --------------------- | |-----------------------S |--------------B ------------| Le courant passe si A ou B sont ouverts. La fonction du circuit est f(A,B) = A ou B

Circuit complexe en OU |-----A-------------non B----| E --------------------- |--A----------B---------C----|-----------------------S |-------A------------non C---| La fonction du circuit est f(A,B,C) = (A et non B) ou (A et B et C) ou (A et non C) C’est une FND

Circuit complexe en ET |--A--| |-----B----| |--non A--| E --------------------- | |-----| |------|--non B--|-----------------------S |--C--| |--non C--| |-----C-----|


La fonction du circuit est f(A,B,C) = (A ou C) et (B ou non C) et (non A ou non B ou C)

Simplification L’objectif est de fabriquer un circuit le plus simple possible. Dans nos 2 exemples complexes, on peut simplifier le circuit. Pour ça, il suffit de trouver la FND correspondant à la fonction du circuit. Pour cela, on peut passer par un tableau de Karnaugh. Ensuite, on peut reconstruire le circuit de façon simplifiée.

Exercices de circuits à relais Simplifier les deux circuits complexes présentés ci-dessus en FND.


Circuit électronique

Circuit de l’additionneur bit a bit On additionne x et y ainsi qu’un report d’addition : c (1 + 1 = 10, je pose 0 et je retiens 1. Le 1 que je retiens, c’est le report d’addition). Le résultat vaut Z, la retenue r L’objectif est de construire le circuit permettant de faire cette addition.

Table de vérité l’additionneur 1 bit Entrées Sorties

x y c Z r 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0

Z = (x y c) + (¬x ¬y c) + (x ¬y ¬c ) + (¬x y ¬c) r = (x y c) + (x ¬y c ) + (¬x y c) + (x y ¬c)

FND de Z et de r

r = (x y c) + (x ¬y c ) + (¬x y c) + (x y ¬c) x y x�y �x�y �x y

c c x y c x�y c�x�y c�x y

�c �c x y �c x�y b �c�x�y �c�x y

r= xy + xc + yc Z = (x y c) + (¬x ¬y c) + (x ¬y ¬c ) + (¬x y ¬c) x y x�y �x�y �x y

c c x y c x�y c�x�y c�x y

�c �c x y �c x�y b �c�x�y �c�x y


Cette configuration du tableau de Karnaugh correspond à une situation particulière qu’on n’a pas abordée : le ou exclusif Z = x ⊕ y ⊕ c

Exercice de vérification Prouver avec une table de vérité que : x ⊕ y ⊕ c ó (x y c) + (¬x ¬y c) + (x ¬y ¬c ) + (¬x y ¬c)

Transformation supplémentaire r= xy + xc + yc ó r = xy + c ( x + y ) ó r = xy + c ( x ⊕ y ) Cette dernière équivalence n’a rien d’évident ! L’intérêt de cette formulation est qu’on trouve une opération commune entre Z et r, ce qui facilitera la construction du circuit.

Exercice de vérification Prouver avec une table de vérité que : xy + c ( x + y ) ó xy + c ( x ⊕ y )

Conclusion

Z = x ⊕ y ⊕ c r = xy + c ( x ⊕ y ) = ( x ⊕ y ) c + xy

Circuit électronique de l’additionneur 1 bit

Les 4 portes logique de base des circuits électroniques A

-a

ab

a + b

a ⊕ b


Construction du circuit d’additionneur 1 bit On additionne A et B (qui correspondent à nos x et y précédent). Le report d’addition est Cin (qui correspond à notre c précédent). Le résultat de l’addition est S (qui correspond à notre Z précédent). La retenue est Cout (qui correspond à notre c précédent).

On avait pour notre additionneur : Z = x ⊕ y ⊕ c r = xy + c ( x ⊕ y ) On a donc dans ce schéma : S = A ⊕ B ⊕ Cin

Cout = AB + Cin ( A ⊕ B ) ó Cout = ( A ⊕ B ) Cin + AB

Ø On commence par A ⊕ B : premier XOR S = A ⊕ B ⊕ Cin Cout = ( A ⊕ B ) Cin + AB

Ø Ensuite on fait ⊕ Cin : deuxième XOR : on a S en sortie S = A ⊕ B ⊕ Cin

Ø Ensuite on fait ( A ⊕ B ) Cin : premier ET Cout = ( A ⊕ B ) Cin + AB

Ø Ensuite on fait AB : deuxième ET Cout = ( A ⊕ B ) Cin + AB


Ø Enfin on fait le OU restant : Cout = ( A ⊕ B ) Cin + AB

Exercice de vérification de l’additionneur 1 bit Faire la table de vérité du circuit

Documents

Algèbre de Boolebliaudet.free.fr/IMG/pdf/IPI-Mat-130-Algebre-de-Boole.pdf · Mathématiques appliquées à l’informatique – Logique - page 5/41 Variable booléenne Une variable