Les fonctions booléennes

Résumé du document

Cours de Mathématiques sur les fonctions booléennes.

Extraits

[...] (nous avons la somme de produits littéraux ) On peut toutefois trouver directement la forme canonique conjonctive d'une fonction booléenne f. On utilise alors les maxtermes, Qui sont dans ce cas, les fonctions qui prennent une seule fois la valeur et on les représente aussi par une formule. Exemple : Toujours dans l'exemple d est majoré par 3 maxtermes m m m3 qui correspondent aux mots binaires Pour écrire m1 comme somme de littéraux = Il faut donc que chaque variable soit égale à 0 On a pour m2 : z=1 donc m2 = y On obtient alors la forme canonique conjonctive de d : (comme vu plus haut . [...]

[...] Par contre, on écrira xy au lieu de pour simplifier l'écriture des formules ; est appelé produit booléen, on l'assimile à la multiplication (avec priorité du produit sur la somme booléenne). Ainsi nous écrirons fg h au lieu de h fg fh au lieu de LA FORME CANONIQUE DISJONCTIVE Méthode pratique pour obtenir la forme canonique disjonctive d'une fonction booléenne de f : 1 Déterminer sa table de vérité Chaque fois qu'elle prend la valeur écrire le minterme correspondant sous forme de produits littéraux Ecrire f comme somme booléenne de ces mintermes. Dans Fn, on appelle mintermes, les fonctions booléennes qui ne prennent la valeur 1 qu'une fois. [...]

[...] Une fonction booléenne de n variables est donc une application qui associe une valeur 0 ou à chaque mot binaire de longueur n. Elle peut être définie au moyen d'un tableau appelé table de vérité de la fonction, qui possède alors 2n lignes et colonnes. La dernière colonne détermine entièrement la fonction ; C'est la liste des valeurs de la fonction qui permet d'identifier chaque fonction booléenne de n variables à 1 mot binaire de longueur 2n. Une fonction booléenne peut aussi être interprétée comme une fonction caractéristique d'une partie n de B ; Les éléments de cette partie sont les mots binaires auxquels la fonction associe le bit 1. [...]

[...] Pour cela, il faut chercher un ensemble de cellules noircies, aussi grosses, et aussi peu nombreuses que possible, dont la réunion est égale au diagramme de Karnaugh de la fonction. Il faut les comparer. Celle qui demande le moins d'opérations est la meilleure. [...]

[...] On a pour m1 : x = y = et z=1 donc m1 = x = x y z (puisqu'on n'utilise plus le signe ) Ainsi d=xyz xyz x y z x y z xyz (ou ) = forme canonique disjonctive Exercice : Ecrire la forme canonique disjonctive des fonctions booléennes f1, et f2 suivantes : x y z f f1 = x y z x y z x y z xyz f2 = x y z x y z x y z x y z Page 5 f DIXIEME PARTIE - FONCTIONS BOOLEENNES LA FORME CANONIQUE CONJONCTIVE Méthode pratique pour obtenir la forme canonique conjonctive d'une fonction booléenne de f : 1 Déterminer la table de vérité de f Chaque fois que f prend la valeur écrire le maxterme correspondant comme somme booléenne de littéraux Ecrire f comme produit de ces maxtermes. La symétrie des rôles joués par les opérateurs (ou & et) & fait qu'il existe aussi une formule dans laquelle f est une fonction booléenne, apparaît comme un produit de somme de littéraux. On l'appelle la forme canonique conjonctive de f. [...]