SYSTEMES LOGIQUES COMBINATOIRES

Un système logique est dit combinatoire si sa sortie à un instant donné t dépend uniquement des entrées à ce même instant t.

1 Algèbre de Boole
L’algèbre de Boole a pour objet de valider des propositions logiques, ie. des combinaisons de variables logiques obtenues à l’aide
d’opérateurs logiques.

1.1. Opérateurs logiques de base

Une variable logique ou une expression (proposition) logique peut prendre 2 valeurs seulement:
1 si elle est vraie ou 0 si elle est fausse.
L’ensemble des valeurs d’une proposition logique en fonction de toutes les combinaisons possibles des variables d’entrée est
représenté par une table de vérité:

Fonctions d’une variable:

OUI (égalité) NON (négation) (ou complémentation)

S=a S= a
a S a S
0 0 0 1
1 1 1 0

Fonctions de 2 variables:

ET OU (inclusif) OU (exclusif)
S=a.b S=a+b S=a⊕b
Remarque:
a b S a b S a b S
0 0 0 0 0 0 0 0 0 a ⊕ b = (a + b).( a . b )
0 1 0 0 1 1 0 1 1
1 0 0 1 0 1 1 0 1
1 1 1 1 1 1 1 1 0

NON ET (NAND) NON OU (NOR)

Remarque:
S= a. b S= a + b
a b S a b S Toute expression logique peut être obtenue par une
0 0 1 0 0 1 combinaison d’opérateurs ET, OU et NON (cf. exercice)
0 1 1 0 1 0
1 0 1 1 0 0
1 1 0 1 1 0

Les opérateurs fondamentaux + et . possèdent un certain nombre de propriétés, résumées dans le formulaire page suivante.
Il est aisé de démontrer ces propriétés en comparant la table de vérité du membre de gauche et celle du membre de droite.
Par exemple, pour le 1er théorème de De Morgan:

a b a + b a b a.b
0 0 1 1 1 1
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 0

Cours MPSI M.Chapuis 2014 SYSTEMES A EVENEMENTS DISCRETS 1

 1.2. Principales propriétés des opérateurs logiques fondamentaux - Formulaire

Opérateur « ou » Opérateur « et »

1 Complémentation a+a =1 a.a = 0

2 Elément neutre a+0= a a.1 = a

3 Elément absorbant a +1 = 1 a.0 = 0

4 Idempotence a+a = a a.a = a

5 Commutativité a+b = b+a a.b = b.a

6 Associativité (a + b) + c = a + (b + c) (a.b).c = a.(b.c)

7 Distributivité a + b. c = (a + b). (a + c) a.(b + c) = a.b + a.c

d’où: a + b.a = a + b a.(b + a) = a.b
et: a + b.a = a a.(b + a) = a
8 Théorèmes de a + b = a.b a.b = a + b
De Morgan

Remarque 1: Par convention (comme en algèbre ordinaire), l’opérateur . est prioritaire sur l’opérateur +.
Ainsi, on écrit: a + b.c , au lieu de: a + (b.c)

Remarque 2: Les propriétés indiquées dans chacune des colonnes sont duales de celles de l’autre colonne
(application des théorèmes de De Morgan, puis complémentation).

2 Représentations des expressions booléennes

Les expressions logiques peuvent être représentées de différentes façons, selon la technologie utilisée pour les réaliser.

2.1. Représentation par logigramme

Une telle représentation est utilisée notamment lorsque la fonction logique doit être réalisée à l’aide de circuits électroniques (ou
pneumatiques, pour certaines applications).

Symboles des portes logiques de base (norme EN 60617-12:1999 ):

OUI ET NAND OU exclusif

a a a
a 1 S=a & S = a.b & S = a.b =1 S=a⊕b
b b b

NON OU NOR Identité logique *

a a a
a 1 S= a ≥1 S=a+b ≥1 S= a+b = S= a⊕b
b b b

(*): La sortie est à 1 lorsque les 2 entrées sont au même état.

Identité logique
Inhibition: S= a⊕b
a a b S
& S = a .b 0 0 1
b
0 1 0
1 0 0
1 1 1

Cours MPSI M.Chapuis 2014 SYSTEMES A EVENEMENTS DISCRETS 2

Exemple de logigramme:

a 1

b
≥1 & S = a.(b + c).d.e
c
d
&
e

Utilisation de portes NAND et NOR

Il est possible de réaliser le logigramme d’une expression booléenne quelconque en utilisant uniquement des portes NAND, ou bien
uniquement des portes NOR. Cette propriété est utilisée pour la réalisation de circuits électroniques.

NAND NOR

NON
1 & ≥1

NAND NOR

≥1
ET
& & ≥1
&
≥1

&
OU ≥1 & ≥1
≥1
&

Le logigramme en NAND ou en NOR d’une expression booléenne s’obtient par double complémentation et application des
théorèmes de De Morgan:

Exemple: Ecriture de S = a.b.(c + d)

En NOR: S = a + b + (c + d) En NAND: S = a.b.(c.d)

a
a a
≥1 a
c
c &
c c+d S c. d a.b.(c. d )
≥1 ≥1 & & & S
d d
d &
b b
≥1 a b

Cours MPSI M.Chapuis 2014 SYSTEMES A EVENEMENTS DISCRETS 3

 2.2. Représentation par schéma à contacts

Une telle représentation est utilisée lorsque la fonction logique doit être réalisée à l’aide de circuits électriques à contacts.

OUI NON ET OU
a
a a a b
b

Exemple: Ecriture de L = a.b.(c + d)

L (lampe)
a b c

2.3. Représentation par algorigramme

Un algorithme est une règle qui s’exprime par une suite de directives ordonnées selon un processus aboutissant à une solution.
L’algorigramme décrit ce processus dans un langage graphique normalisé. Cette représentation est utilisée principalement en logique
programmée, préalablement à la programmation.

Exemple: Ecriture de L = a.b + c

Début

non
a=1

oui
non
b=1
non
oui c=1

oui

L=1 L=0

Fin

Principaux symboles:

Symbole général
Début, fin, interruption Entrée-sortie Embranchement « traitement », lorsqu’aucun
symbole normalisé n’existe.

Cours MPSI M.Chapuis 2014 SYSTEMES A EVENEMENTS DISCRETS 4