Les formes, les énoncés et les opérateurs booléens

Les formes, les énoncés et les opérateurs booléens.......................................................................................2Les formes booléennes...............................................................................................................................2Les énoncés booléens.................................................................................................................................2Les opérateurs booléens.............................................................................................................................2

La négation............................................................................................................................................2La conjonction.......................................................................................................................................2La disjonction........................................................................................................................................3

La tautologie et la contradiction................................................................................................................3La précédence des opérateurs logiques......................................................................................................3Les équivalences logiques.........................................................................................................................3La simplification des énoncés booléens.....................................................................................................4

Les propriétés des opérateurs booléens.........................................................................................................4Simplification d'un énoncé booléen...............................................................................................................4

Les circuits logiques..................................................................................................................................5Le circuit série.......................................................................................................................................5Le circuit parallèle.................................................................................................................................5

- 1 -

Les formes, les énoncés et les opérateurs booléens

Socrate ‘’ Ce que dit Platon est faux’’Platon ‘’Socrate dit la vérité’’

L'énoncé précédant est un paradoxe car si Socrate dit la vérité alors l'énoncé de Platon doit être faux mais si l'énoncé de Platon est faux alors Socrate ne dit pas la vérité et l'énoncé de Platon doit être vrai ! Ce n'est que vers 1910 que de tels paradoxes de la logique formelle furent résolus par Russell et Whitehead. Cependant vers 1854 Boole (1815-1864) présenta une étude systématique de la logique mathématique. Il construisit les lois mathématiques des énoncés qui permettent d'obtenir une conclusion valide. Le raisonnement fut alors transformé en une algèbre qui s'avéra un outil essentiel vers 1937 quand Claude E. Shannon, alors étudiant en génie électrique au MIT utilisa l'algèbre de Boole pour simplifier les circuits électriques. La voie s'ouvrait vers les microprocesseurs d'aujourd'hui.

Les formes, les énoncés et les opérateurs booléens

Les formes booléennesUne forme booléenne ou forme propositionnelle est une expression qui ne peut devenir vraie ou fausse que lorsque la valeur de la variable est connue. Par exemple on ne peut décider de la valeur logique VRAI ou FAUX de l'énoncé x < 5 qu'en connaissant la valeur de x. Cette expression est une forme booléenne.

Les énoncés booléensUn énoncé booléen ou une proposition est un énoncé dont on peut décider de la valeur logique VRAI ou FAUX. Par exemple 2 < 5 est un énoncé vrai dans le cadre de référence des entiers.

Les opérateurs booléensLes opérateurs booléens ou les connectifs sont des mots ou des symboles utilisés pour relier des énoncés booléens simples. Les énoncés ainsi reliés s'appellent énoncés composés. Les connectifs de base sont la négation (NON), la disjonction (OU) et la conjonction (ET). Les énoncés booléens sont souvent représentés par les lettres p, q, r ou A, B, C...

La négation

La négation d'un énoncé booléen p se note ¬p, ou ~p. L'énoncé << non p >> est vrai si p est faux et est faux si p est vrai. On utilise habituellement les symboles 0 et 1 pour représenter les valeurs logiques <<FAUX>> et <<VRAI>>. Ceci est représenté par un tableau appelé table de vérité.

p ¬p

0 1

1 0

La conjonction

Si p et q sont deux énoncés booléens, la conjonction de p et q, << p ET q >>, est un énoncé qui est vrai si et seulement si les deux énoncés sont vrais, autrement la conjonction est fausse. Voici la table de vérité de la conjonction:

- 2 -

Les formes, les énoncés et les opérateurs booléens

p q0 0 0

0 1 0

1 0 0

1 1 1

La disjonction

Si p et q sont des énoncés booléens, la disjonction de p et q, << p OU q >>, est un énoncé qui est vrai lorsqu’au moins un des énoncés simples est vrai. Voici la table de vérité de la disjonction:

p q0 0 0

0 1 1

1 0 1

1 1 1

Les opérateurs servent à composer des énoncés plus complexes. Les valeurs de vérité de ces énoncés sont affichées dans des tables de vérité. Voici par exemple la table de vérité de l'énoncé << non p ou q >>:

0 0 1 1 0

0 1 1 1 1

1 0 0 0 0

1 1 0 1 1

La tautologie et la contradictionUn énoncé qui est toujours vrai est appelé une tautologie et est noté << t >>, tandis qu'un énoncé qui est toujours faux est appelé une contradiction et est noté << c >>.

La précédence des opérateurs logiquesUn ordre de priorité des opérateurs existe dans l'écriture et l'évaluation des énoncés booléens. Par ordre de priorité de 1 à 5 nous retrouvons:Les parenthèses La négation La conjonction (ET) La disjonction (OU) L'égalité, l'inégalité, la supériorité, l'infériorité...

Les équivalences logiquesDes énoncés qui ont la même valeur logique pour chaque ligne de leur table de vérité sont dit équivalents. On dit que ces énoncés ont la même table de vérité.Considérons par exemple les énoncés suivants: non( p et q ), non p ou non q et calculons la table de vérité de chacun de ces énoncés:

- 3 -

Les formes, les énoncés et les opérateurs booléens

0 0 1 0

0 1 1 0

1 0 1 0

1 1 0 1

0 0 1 1 1

0 1 1 1 0

1 0 0 1 1

1 1 0 0 0

Les résultats sont les mêmes dans la table de vérité nous concluons que ces énoncés sont équivalents et nous notons ce fait ainsi:

La simplification des énoncés booléensLes équivalences logiques qui décrivent les propriétés des opérateurs logiques, sont utilisées pour simplifier les énoncés booléens et les circuits logiques.

Les propriétés des opérateurs booléens

Le tableau suivant donne les propriétés des opérateurs booléens qui peuvent être utilisées pour la simplification d'énoncés plus complexes:

IdempotenceAssociativitécommutativitéDistributivitéIdentité

Complémentarité

Involution

Lois de De Morgan

Simplification d'un énoncé booléen

Les propriétés des opérateurs booléens sont utiles pour simplifier des énoncés plus complexes. Examinons par exemple la simplification suivante:

distributivité

complémentarité

- 4 -

Les formes, les énoncés et les opérateurs booléensidentité

Les circuits logiques

La logique des énoncés booléens trouve une application naturelle dans les circuits électriques et électroniques qui sont au coeur même des ordinateurs.

Le circuit série

L'image suivante illustre deux contacts A et B, une tension à l'entrée et une charge. Le circuit est en série car les deux contacts doivent être fermés pour que le courant circule vers la charge.

Nous pouvons associer une table de vérité à ce circuit de la façon suivante:

contact A

contact B

courant

0 0 0

0 1 0

1 0 0

1 1 1

Cette table de vérité établit tous les états possibles des contacts et les résultats sur le courant. Ici << 0 >> indique que le contact n'est pas fermé et << 1 >> indique que le contact est fermé. Nous reconnaissons facilement la table de vérité de la conjonction << ET >>. Il est habituel dans l'étude des circuits d'utiliser le point << . >> pour représenter la conjonction. Ainsi les contacts A et B en série sont représentés par A.B.

Le circuit parallèle

L'image suivante illustre deux contacts A et B, une tension à l'entrée et une charge. Le circuit est en parallèle car au moins un des contacts doit être fermé pour que le courant circule vers la charge. L'image suivante illustre un tel circuit.

- 5 -

Les formes, les énoncés et les opérateurs booléens

 Nous pouvons associer une table de vérité à ce circuit de la façon suivante:

Contact

Contact

Courant

0 0 0

0 1 1

1 0 1

1 1 1

Cette table de vérité établit tous les états possibles des contacts et les résultats sur le courant. Ici << 0 >> indique que le contact n'est pas fermé et << 1 >> indique que le contact est fermé. Nous reconnaissons facilement la table de vérité de la disjonction << OU >>. Il est habituel dans l'étude des circuits d'utiliser le symbole << + >> pour représenter la disjonction. Ainsi les contacts A et B en parallèle sont représentés par A+B.La négation est représentée habituellement par une barre sur la lettre pour les circuits logiques.Pour simplifier les représentations graphiques nous pouvons laisser tomber la description de la tension et de la charge qui n'ont pas d'intérêt pour notre propos. Nous obtenons les illustrations suivantes où E indique l'entrée et S la sortie.

- 6 -