# Fonctions booléennes à n variables

- tableaux de Karnaugh
- passage ET/OU en NAND

                     _     _         _ _
    ex: f(a,b,c,d)=abcd + abc + ab + abc

On peut essayer de simplifier son équation à l'aide des relations de l'algèbre de Boole. Mais on peut aussi représenter graphiquement cette fonction par son tableau de vérité :

Ce tableau nous donne l'état de f (0 ou 1) dans tous les cas (ceci permet de ne pas oublier certains cas particuliers).Dans la pratique on remplit dans le tableau tous les cas où f vaut 1, on complète les zéros dans les cases restantes. On peut remarquer que la fonction f ' est représentée par le même tableau. f ' et f sont donc égales, puisqu'ayant la même valeur dans tous les cas.

## tableaux de Karnaugh

Un tableau de Karnaugh est un tableau de vérité dans lequel les différentes possibilités des entrées sont classées en code GRAY (binaire réfléchi) qui sera détaillé plus loin. Ceci correspond à 0 puis 1 dans le cas d'une variable, 00, 01, 11, 10 pour 2 variables. On peut remarquer qu'en passant d'une case à une case adjacente, une seule variable a changé. Regrouper ces deux cases adjacentes correspond donc à la simplification par cette variable (du fait de l'axiome de complémentation). On simplifie l'équation d'une fonction en faisant des regroupements sous forme d'une, deux ou quatre lignes ou colonnes. Le passage de la dernière ligne à la première est également un cas adjacent (idem pour les colonnes).

En représentant graphiquement une fonction booléenne à n variables, on peut en déterminer une expression simplifiée. Cette simplification est évidente jusqu'à 4 variables, possible avec 5 ou 6 variables (en traitant deux ou quatre tableaux différents supposés superposés). Dans les autres cas, un tableau de Karnaugh permettra toujours de simplifier l'équation, mais jamais au maximum. Par exemple :

          _       _   _   _ _ _
        f=a.b.c + a.b.c + a.b.c + b.c + a.c

                   _ _   _                _ _
    donc : f=a.c + a.c + a.b  ou  f=a.c + a.c + b.c

Remarque : Dans la pratique, si certains cas sont indifférents (par exemple combinaison de capteurs impossible), on place un X dans le tableau, que l'on mettra à 0 ou 1 pour simplifier l'expression finale.

On pouvait également regrouper les 0 (s'il y en a moins ou plus groupés) :

     _  _ _       _               _  _        _    _ _
     f=(a b c)+(a c) d'où  f=(a+b+c)(a+c)=ac+ba+bc+a c

On peut également développer la fonction en somme de MINTERMES (forme canonique disjonctive).

                       _ _ _ _   _ _       _
    Dans notre cas : f=a.b.c+a.b.c+a.b.c+a.b.c+a.b.c

Propriétés : Il y a 2n mintermes d'ordre n (n étant le nombre de variables de la fonction). Deux mintermes de même ordre ont un produit nul. La somme de tous les mintermes d'ordre n est 1.

L'intérêt de ces décompositions est leur unicité, donc en particulier une programmation facilitée.

exercices : trouver la forme réduite et les formes canoniques des fonctions :

a) |
b) |

question : où cliquer pour la solution ?

## passage ET/OU en NAND

              ___
    on notera abc par NAND[a,b,c]

On décompose la fonction sous forme canonique : (comme vous pouvez le voir, je trouve que j'ai assez travaillé, je garde mes équations en mode texte bien que ce soit moins beau)

on peut alors écrire :

donc :

Dans la pratique, les schémas de fonctions définies par ET / OU se transforment facilement en réseaux composés uniquement de NAND. Il suffit d'inverser toutes les extrémités des liaisons internes :

La symbolisation est détaillée dans le transparent 5