On trouvera ci-après un rappel substanciel d'une terminologie spécifique à la logique dite combinatoire par opposition à la logique séquentielle S'ensuivra la méthode de simplification algébrique par la méthode des consensus. Celle-ci, que nous devons à TISON (Grenoble), fait de la table de Karnaugh une méthode de simplification obsolète. Par ailleurs, le principe algébrique fait que la méthode s'applique quel que soit l'ordre de la fonction considérée. On est aussi prié de ne pas confondre la méthode de Tison et celle de Quine Mc Cluskey.
Il est regrettable de constater qu'on peut encore voir écrire:     Y  =  a/b + bc + ac sans que l'on mette d'emblée le doigt sur l'économie d'un terme dans la fonction. ( a/b, lire: a ET b barre)

Terminologie
Formes canoniques
Les bases
Simplifications d'une expression booléenne
Table de recouvrement

Les écritures algébriques d'une mème fonction booléenne Y  peuvent prendre de multiples formes nettement différentes les unes des autres.

                        Y  = a./b  + c

S'écrit aussi:      Y = (a + c).(/b + c)
ou encore   :      Y =  /a. /b.c  +  b.c + a./b                (a)
voire mème:      Y =  /a. /b.c +  a.b.c + a./b.c  + /a.b.c +  a./b./c
etc .....
 

Cette diversité des représentations algébriques d'une mème fonction booléenne demande à ce que soit adoptée une terminologie suffisamment rigoureuse et non ambigue permettant l'identification précise du type d'écriture de la fonction à laquelle on a affaire. Nous  nous attachons ici à la classification et à l'identification des éléments et formes des fonctions booléennes. La seule connaissance de cette terminologie suffit déja pour une bonne part à la maitrise de la logique dite combinatoire.
 

Forme  DISJONCTIVE

C'est une fonction se présentant strictement sous la forme d'une SOMME de MONOMES.

EX :       y = a ./b  +  b.c./d  +  /a.c              (b)

Le premier monome se lit :    a   ET   PAS   b      (intersection logique)

On dit aussi d'une forme disjonctive que c'est une forme  P.L.A  (Programmable Logic Array). Nous savons qu'un PLA est en effet essentiellement constitué de deux couches logiques: Une couche de ET suivie d'une couche de OU.
 

Forme  CONJONCTIVE

C'est une fonction exclusivement constituée d'un PRODUIT de SOMMES.

EX :     y = (a  +  /c) . ( /b  +  c  +  /d ) . ( /c  +  d )               (c)

Intersection de trois sommes ou additions logiques.
 

Fonction ELEMENTAIRE

Une fonction Y  est une fonction élémentaire si elle ne se présente que selon l'une ou l'autre des deux formes précédentes (disjonctive ou conjonctive).

La fonction :               y  =   a . /b  +  c . ( /a.b  +  d . (a + /b))

n'est pas une fonction élémentaire. Elle n'est exclusivement ni une somme de produits ni un produit de sommes. Ce ne serait qu'en développant les mises en facteur que l'on obtiendrait une fonction élémentaire qui serait une somme de produits .

Chacun des termes d'une fonction élémentaire est un terme élémentaire [/ac  dans  (a),  /b+c+/d  dans  (c)].
 

Terme FONDAMENTAL

Un terme élémentaire dans lequel on retrouve toutes les variables de la fonction est un terme fondamental . Il n'y a pas de termes fondamentaux dans  (b) autant que dans (c).

Monome fondamental

Lorsqu'un terme fondamental est un produit, c'est un monome fondamental. Dans la fonction (a), le terme  /a/bc est un monome fondamental, bc  ne l'est pas .

On peut retenir qu'un monome fondamental est un monome qui rend compte d'un  '1'  et d'un seul parmi les '1' d'une table de Karnaugh.

Minterme / Maxterme

Dans une forme disjonctive un terme fondamental est un MINTERME. Dans une forme conjonctive c'est un  maxterme.
 

Formes  CANONIQUES :

Pour une mème fonction nous distinguerons deux formes canoniques:

 - La forme canonique disjonctive
 - La forme canonique conjonctive

A - Forme canonique  DISJONCTIVE :

C'est une somme de monomes FONDAMENTAUX    (mintermes) .

Exemples :
      y  =  a./b.c   + /a./b.c   +  a.b.c
      z  =  ab/c/de  +   abcd/e   +   /abc/d/e   +   ab/cde

Dans une forme canonique disjonctive fonction de  n  variables, chacun des  monomes est d'ordre  n.

La fonction ci-dessous ne se présente pas sous sa forme canonique disjonctive,

      v  =  abc + /ac + a/bc

Si les monomes abc et a/bc sont des monomes fondamentaux, le monome /ac  n'est pas fondamental.
 

B - Forme canonique CONJONCTIVE  :

C'est un produit de "maxtermes" exclusivement

exemple :              y  = (a + b + /c).(/a + /b + c).(a + /b + /c)

NOTA-BENE :

Pour une fonction F donnée, l'écriture d'une forme canonique, qu'elle soit disjonctive ou conjonctive, est unique. Elle identifie parfaitementla fonction.
 

Ecriture d'une fonction sous sa forme canonique disjonctive.

Il s'agit de faire apparaitre dans les monomes non fondamentaux les variables manquantes. Si  x  est une variable manquante pour le monome  m, on écrira :
   m  =     m(x  +  /x)   =     mx  +  m/x         (puisque:   x + /x = 1)

Exemple :

    Y =   a./b  +  /a./b.c  +  a./c    fonction des trois variables  (a, b, c)

Puisque seule c n'apparait pas dans le 1° monome on développe celui-ci sous la forme  a./b.(c + /c). De mème il ne manque que b  dans le dernier monome. Nous obtenons des monomes fondamentaux en écrivant  a./c.(b+/b)  et en développant. Soit :

    Y =   a./b.(c  +  /c)  + /a./b.c  +  a./c.(b  +  /b)

 Le développement amène la forme canonique disjonctive

    Y = a./b.c  +  a./b./c  +  /a./b.c  +  a.b./c  +  a./b./c

    On élimine les éventuels monomes qui se  répètent. Ce sont des inclusions de première espèce.
 

Ecriture d'une fonction sous sa forme canonique conjonctive.

On utilise cette fois la relation     x . /x  =  0.

Pour toute expression booléenne  E  on pourra toujours écrire:

       E = E  +  x. /x

Par distributivité de l'addition par rapport à la multiplication il vient :

       E  =  (E + x) . (E + /x)

exemple :
Soit:    Y = (a + c + /d) . (/a + /b +c + d)

Il manque dans le premier terme la variable  b  pour en faire un maxterme. Ajoutons '0' à ce terme, soit:

    Y = (a + c + /d + b./b) . (/a + /b + c+ d)

Et par distributivité de l'addition par rapport à la multiplication:

    Y = (a + b + c+ /d) . (a + /b + c + /d) . (/a + /b + c + d)

Cette expression est une forme canonique conjonctive.
 

Monome COMPATIBLE

 Pour une fonction  F, un monome est dit  compatible  si on vérifie qu'en le rajoutant à  l'expression de  F on ne modifie pas  F.

Exemple:

si:    F  =    a./b  + b.c

 On peut écrire aussi:

 F  =    a/b  +  bc  +  ac                 (ac est un monome compatible)

Le rajout du monome  ac  ne modifie pas  F  puisque:

                   a./b + b.c   =   a./b + b.c + a.c

la table de Karnaugh de F, ou sa table de vérité, ne se trouvent pas modifiées par le rajout du monome  ac  à la fonction.
 

Inclusion de première espèce

Un monome qui est divisé par un autre monome dans la mème expression est un monome redondant pour cette expression. On peut le supprimer. On dit aussi de ce monome qu'il est inclus dans le monome qui le divise. C'est une inclusion de première espèce. Dans une table de Karnaugh ce serait une intersection logique entièrementrecouverte par le domaine du monome diviseur.

Y  =   /abc/de  +  b/c  + c/de      =    b/c  +  c/de

Le monome  /abc/de  que l'on peut diviser par  c/de  est un monome inclus de première espèce.
 

Monome  PREMIER  (prime implicant)

Pour une fonction  F,  un monome  m  est  premier si, appartenant à  F  ou au moins compatible, il n'est pas possible de diminuer l'ordre de  m  sans entrainer la modification de  F  (table de vérité).

Exemple :

 F  =   a./b  +  b.c     (1)

bc  est un monome premier, a/b aussi. le monome a/bc qui est un monome compatible pour F car on peut aussi écrire:

 F  =   a./b  +   b.c   +   a./b.c    (2)

n'est pas premier. on peut encore retirer une variable à ce monome sans modifier  F  (ici ce serait la variable  b). Par contre,  ac  qui est aussi un monome compatible pour  F  est premier.

 F  = a/b  +  bc  +  ac     (3)
 

BASE :

 On appelle BASE  toute fonction  F  dont tous les monomes sans exception sont  premiers. La fonction ( 2 ) n'est pas une base, la fonction (3 ) en est une ainsi que (1).
 

BASE COMPLETE :

Pour une fonction  F donnée, une base est dite  COMPLETE  si elle est constituée de l'ensemble de tous les monomes premiers possibles. Cette écriture identifie parfaitement la fonction. La fonction (3) est une base complète  (présence de tous les monomes premiers  de  F).
 

BASE  IRREDONDANTE

Pour une fonction F donnée, une base qui ne contient que le minimum de monomes premiers nécessaires à la couverture de cette fonction est une base irredondante. C'est une forme minimale d'écriture de la fonction  (minimum de termes et minimum de variables dans ces termes). Les travaux de simplification de fonctions booléennes consistent souvent à amener l'écriture de bases irredondantes.
 

Variable  BIFORME

Considérant deux monomes  mi, mj  dans  F, une variable  x  est biforme pour  ces  deux monomes si elle apparait VRAIE  dans l'un et  COMPLEMENTEE  dans l'autre.

Ex :

 Pour les couples de monomes ci-après , la variable  c  est  biforme :

 ( a/b/cd/e  ,  bc/g  )
 ( cd/e  ,  a/c/efg/i )

 Cette notion s'étend évidemment à l'ensemble des monomes d'une  fonction.
 

RESIDU

Pour un monome donné  m, le résidu par rapport à une variable  x  de  m   est ce qui reste du monome après élimination de  x  dans ce monome.
 

 Lorsque deux monomes  mi  et  mj  contiennent au moins une variable biforme  x, le CONSENSUS  de  ces deux monomes par rapport  à  x,  noté C(x) , s'obtient  en  écrivant  l'intersection logique des résidus par rapport à  x.

Ex :
 C(e)       [ a/bcd/e/f  , ce/h ]      =    a/bcd/f/h
 C(b)       [ ab/g   ,  a/bcd/e ]      =    acd/e/g

Consensus de valeur nulle

Si dans mi et mj il y a plus d'une variable biforme, le consensus par rapport à l'une de ces variables existe mais vaut  "0".

Ex :          mi =  a/bc/d ,       mj =  b/ce/fg

      C(b)     =  (ac/d) . (/ce/fg)  = 0

Le consensus par rapport à  c  vaut aussi  0.
 

Inclusion de DEUXIEME ESPECE

Dans une fonction  F, le consensus de deux monomes  mi et  mj  est un  monome compatible pour F. Il est inclus partiellement dans l'un et l'autre de ces deux monomes (réunion logique).

Preuve:

considérons dans  F  les monomes  m1 et m2 de formes respectives  x . @  et  /x . $  pour lesquelles x est donc biforme. @ et $ sont deux produits logiques de longueurs quelconques. Ecrivons la réunion logique:

       z =     m1  +  m2     =      x . @   +   /x . $

ajoutons à  z  le consensus des deux monomes, qui est un monome compatible, soit  @ . $

       z =     x . @   +   /x . $   +   @ . $

multiplions  @ . $   par  '1', soit   (x  +  /x)

       z =     x . @   +  /x . $   +   @ . $ . (x  +  /x)

développons :
       z =     x . @   +   /x . $   +   x . @ . $   +   /x . @ . $

simplifions par inclusions de première espèce ou inclusions directes:

       z =     x . @   +   /x . $

Le rajout du consensus n'a pas modifié  z. Ce consensus est en fait un monome inclus dans la somme  mi + mj. Il est dit monome inclus de  deuxième espèce.
 

Cas particulier de simplification par consensus:

Simplification par adjacence.

La simplification par adjacence n'est qu'un cas particulier de simplification par consensus. Alors que les monomes considérés jusqu'ici étaient d'ordre quelconque, on considère ici pour écriture d'un consensus deux monomes du mème ordre et fonctions des mèmes variables dont une seule est biforme.
 

exemple:    F  =  /a.b.c  +  b.c./d./e  +  b.c.d./e       (Consensus par rapport à d des monomes  b.c./d./e et b.c.d./e)
rajout du consensus  bc/e:

                   F  =  /abc + bc/d/e +  bcd/e +  bc/e

Disparition des deux monomes bc/d/e et bcd/e par inclusions de première espèce dans bc/e.  soit:

                   F  =  /abc + bc/e
 

Simplifier une somme de monomes, c'est aboutir à une écriture telle qu'aucun des monomes n'est de trop et  qu'aucune des variables dans chacun de ces monomes n'est de trop (monomes premiers). On dit disposer alors d'une  base irredondante de l'expression booléenne.

On peut simplifier une fonction booléenne de deux façons:

- Recherche directe d'une base irredondante (voie algébrique intuitive).
- Recherche systématique.

1) recherche directe.

On commence par traquer les inclusions de première espèce (trivial).
On rajoute les consensus possibles en examinant chaque fois si cela n'entraine pas de simplifications par inclusions de première espèce. En réitérant ces essais on parvient à l'écriture d'une des bases irredondantes.

2) Recherche systématique.

Consiste à travailler en deux temps:

    1) Ecriture de la base complète.
    2) Ecritures des bases irredondantes par exploitation d'un  tableau de recouvrement.
 

1)  Base complète

On amène la base complète d'une fonction booléenne en rajoutant à l'expression, de façon systématique, tous les consensus possibles. On élimine, à chaque tour de consensus, toutes les inclusions de première espèce. La somme de monomes qui reste constitue la liste exhaustive de tous les monomes premiers de la fonction.

2)  Tableau de recouvrement

Disposant de la base complète d'une fonction F, amenée par autant de tours de consensus que nécessaires, on peut procéder à la sélection d'un minimum de monomes (forcément premiers) qui suffisent à recouvrir la fonction  F à l'aide d'un tableau de recouvrement.

Exemple:

F  = /a/b/c/d  + /ab/c  + a/b/c  + a/cd  + bd  + /b/c/d  + /ab/c  + a/b/c  + a/cd  +  /a/c/d

Base complète:

F  =  b/c/d  + /ab/c  + a/b/c  + a/cd  + bd  + /a/c/d

qui s'écrit aussi par profils binaires:

         -100  +  010-  +  100-  +  1-01  +  -1-1  +  0-00
 

Tableau de recouvrement

On dresse une table à deux entrées. En  x, les profils binaires de la base complète. En y les profils des monomes fondamentaux.
 

             b  a  s  e         c  o  m  p  l  e  t  e

	-100	010-	100-	1-01	-1-1	0-00
0100	x	x				x
1100	<x>
0101		x			x
1000			<x>
1001			x	x
1101				x	x
0111					<x>
1111					<x>
0000						<x>

<x>  :  repère les monomes essentiels

Dans une table de recouvrement un monome est essentiel si il est le seul à recouvrir certains monomes fondamentaux.  Ici les  <x>  gras

Monomes essentiels:      -100,  100-,    -1-1,    0-00

soit:                                 b/c/d,  a/b/c,   bd,     /a/c/d

Ces monomes feront forcément partie de toute écriture simplifiée de  F.

F1  =     b/c/d  + a/b/c +  bd +  /a/c/d  +  ........      ;
F2  =     b/c/d  + a/b/c +  bd +  /a/c/d  +  ........      ;
F3  =    ............                                                     ;

Pour chaque forme simplifiée ou irredondante, on rajoute les monomes premiers qui servent à terminer le recouvrement de  F.   (/ab/c,    a/cd)

Le concept P.L.A
 
 

cd \ ab	00	01	11	10
00	X	0	1	1
01	1	0	1	1
11	1	1	0	0
10	X	1	1	X