Définition 1.Monôme conjonctif (conjonction élémentaire) des variables est appelée la conjonction de ces variables ou de leurs négations.
par exemple, est une conjonction élémentaire.
Définition 2.Monôme disjonctif (disjonction élémentaire) des variables s'appelle la disjonction de ces variables ou de leurs négations.
par exemple, - disjonction élémentaire.
Définition 3. Une formule équivalente à une formule d'algèbre propositionnelle donnée et étant une disjonction de monômes conjonctifs élémentaires est appelée forme normale disjonctive(DNF) de cette formule.
Par exemple,- DNF.
Définition 4. Une formule équivalente à une formule d'algèbre propositionnelle donnée et étant la conjonction de monômes disjonctifs élémentaires est appelée forme normale conjonctive(CNF) de cette formule.
par exemple, - CNF.
Pour chaque formule de l'algèbre propositionnelle, on peut trouver un ensemble de formes normales disjonctives et conjonctives.
Algorithme de construction de formes normales
En utilisant les équivalences de l'algèbre de la logique, remplacez toutes les opérations de la formule par celles de base : conjonction, disjonction, négation :
Débarrassez-vous des signes de double négation.
Appliquer, si nécessaire, aux opérations de conjonction et de disjonction les propriétés de distributivité et la formule d'absorption.
2.6. Formes normales parfaites disjonctives et parfaites conjonctives
Toute fonction booléenne peut avoir plusieurs représentations sous forme de DNF et CNF. Parmi ces représentations, une place particulière est occupée par le DNF parfait (SDNF) et le CNF parfait (SKNF).
Définition 1. Forme normale disjonctive parfaite(SDNF) est un DNF dans lequel, dans chaque monôme conjonctif, chaque variable de l'ensemble apparaît exactement une fois, et soit elle-même, soit sa négation apparaît.
De manière constructive, le SDNF pour chaque formule de l'algèbre propositionnelle réduite au DNF peut être défini comme suit :
Définition 2. Forme normale disjonctive parfaite(SDNF) d'une formule d'algèbre propositionnelle est appelée son DNF, qui a les propriétés suivantes :
Définition 3. Forme normale conjonctive parfaite(SKNF) est un CNF dans lequel, dans chaque monôme disjonctif, chaque variable de l'ensemble apparaît exactement une fois, et soit elle-même, soit sa négation apparaît.
Structurellement, le SKNF pour chaque formule de l'algèbre propositionnelle réduite au CNF peut être défini comme suit.
Définition 4. Forme normale conjonctive parfaite(SKNF) d'une formule d'algèbre propositionnelle donnée est appelée son CNF qui satisfait les propriétés suivantes.
Théorème 1. Chaque fonction booléenne de variables qui n'est pas identiquement fausse peut être représentée dans le SDNF, et de plus de manière unique.
Façons de trouver SDNF
1ère voie
2ème voie
sélectionnez les lignes où la formule prend la valeur 1 ;
on compose une disjonction de conjonctions, à condition que si une variable est incluse dans une conjonction avec une valeur de 1, alors on écrit cette variable, si avec une valeur de 0, alors sa négation. Nous obtenons SDNF.
Théorème 2. Chaque fonction booléenne de variables qui n'est pas identiquement vraie peut être représentée dans SKNF et, de plus, de manière unique.
Façons de trouver SKNF
1ère voie- en utilisant des transformations équivalentes :
2ème voie- en utilisant les tables de vérité :
sélectionnez les lignes où la formule prend la valeur 0 ;
on compose une conjonction de disjonctions, à condition que si une variable est incluse dans une disjonction avec une valeur de 0, alors on écrit cette variable, si avec une valeur de 1, alors sa négation. Nous obtenons SKNF.
Exemple 1. Tracer les fonctions CNF.
Solution
Excluons le bundle "" en utilisant les lois de transformation des variables :
= / de Morgan et les lois de la double négation / =
/ lois distributives / =
Exemple 2. Apportez la formule à DNF.
Solution
Exprimons les opérations logiques en termes de, et :
= / nous rapporterons la négation aux variables et réduirons les doubles négatifs / =
= / loi de distribution /.
Exemple 3. Notez la formule dans DNF et SDNF.
Solution
En utilisant les lois de la logique, nous amènerons cette formule à une forme ne contenant que des disjonctions de conjonctions élémentaires. La formule résultante sera le DNF souhaité :
Pour construire SDNF, nous allons composer une table de vérité pour cette formule :
Nous marquons les lignes du tableau dans lesquelles la formule (la dernière colonne) prend la valeur 1. Pour chaque ligne, nous écrivons la formule qui est vraie sur l'ensemble de variables, de la ligne donnée :
ligne 1:;
ligne 3 : ;
ligne 5 :.
La disjonction de ces trois formules prendra la valeur 1 uniquement sur les ensembles de variables des lignes 1, 3, 5, et sera donc la forme normale disjonctive parfaite (SDNF) requise :
Exemple 4. Apportez la formule à SKNF de deux manières :
a) en utilisant des transformations équivalentes ;
b) en utilisant la table de vérité.
Solution:
On transforme la deuxième disjonction élémentaire :
La formule est :
b) compiler une table de vérité pour cette formule :
Nous marquons les lignes du tableau dans lesquelles la formule (la dernière colonne) prend la valeur 0. Pour chaque ligne, nous écrivons la formule qui est vraie sur l'ensemble des variables, de la ligne donnée :
ligne 2:;
ligne 6 :.
La conjonction de ces deux formules prendra la valeur 0 uniquement sur les ensembles de variables des lignes 2 et 6, et sera donc la forme normale conjonctive parfaite (SCNF) souhaitée :
Questions et tâches pour une solution indépendante
1.En utilisant des transformations équivalentes, amenez les formules à DNF :
2.En utilisant des transformations équivalentes, apportez les formules à CNF :
3.Utilisez la deuxième loi distributive pour convertir DNF en CNF :
une) 
;
4. Convertissez les DNF donnés en SDNF :
5. Convertissez le CNF donné en SKNF :
6. Pour les formules logiques données, construisez SDNF et SKNF de deux manières : en utilisant des transformations équivalentes et en utilisant la table de vérité.
b) 
;
La forme normale conjonctive est pratique pour la démonstration automatique de théorèmes. Toute formule booléenne peut être convertie en CNF. Pour ce faire, vous pouvez utiliser : la loi de la double négation, la loi de de Morgan, la distributivité.
YouTube collégial
-
1 / 5
Formules au KNF:
¬ A ∧ (B ∨ C), (\ displaystyle \ neg A \ wedge (B \ vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\ displaystyle (A \ vee B) \ wedge (\ neg B \ vee C \ vee \ neg D) \ wedge ( D \ vee \ neg E),) A B. (\ displaystyle A \ coin B.)Formules pas dans KNF:
¬ (B ∨ C), (\ displaystyle \ neg (B \ vee C),) (A ∧ B) C, (\ displaystyle (A \ wedge B) \ vee C,) A (B (D ∧ E)). (\ displaystyle A \ wedge (B \ vee (D \ wedge E)).)Mais ces 3 formules hors CNF sont équivalentes aux formules suivantes en CNF :
¬ B ∧ ¬ C, (\ displaystyle \ neg B \ wedge \ neg C,) (A ∨ C) ∧ (B ∨ C), (\ displaystyle (A \ vee C) \ wedge (B \ vee C),) A (B ∨ D) ∧ (B ∨ E). (\ displaystyle A \ cale (B \ vee D) \ cale (B \ vee E).)Construire le CNF
Algorithme de construction de CNF
1) Se débarrasser de toutes les opérations logiques contenues dans la formule en les remplaçant par les principales : conjonction, disjonction, négation. Cela peut être fait en utilisant des formules équivalentes :
A → B = ¬ A ∨ B, (\ displaystyle A \ rightarrow B = \ neg A \ vee B,) A B = (¬ A ∨ B) ∧ (A ∨ ¬ B). (\ displaystyle A \ leftrightarrow B = (\ neg A \ vee B) \ coin (A \ vee \ neg B).)2) Remplacer le signe de négation, se référant à l'expression entière, par les signes de négation, se référant à des déclarations de variables individuelles basées sur les formules :
¬ (A ∨ B) = ¬ A ∧ ¬ B, (\ displaystyle \ neg (A \ vee B) = \ neg A \ wedge \ neg B,) (A B) = ¬ A ∨ ¬ B. (\ displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B.)3) Débarrassez-vous des signes de double négation.
4) Appliquer, si nécessaire, aux opérations de conjonction et de disjonction les propriétés de distributivité et la formule d'absorption.
Un exemple de construction d'un CNF
Apportons au CNF la formule
F = (X → Y) ((¬ Y → Z) → ¬ X). (\ displaystyle F = (X \ rightarrow Y) \ wedge ((\ neg Y \ rightarrow Z) \ rightarrow \ neg X).)Transformons la formule F (\ style d'affichage F)à une formule qui ne contient pas → (\ displaystyle \ rightarrow):
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ wedge (\ neg (\ neg Y \ rightarrow Z) \ vee \ neg X) = (\ neg X \ vee Y) \ wedge (\ neg (\ neg \ neg Y \ vee Z) \ vee \ neg X).)Dans la formule résultante, nous transférons la négation aux variables et réduisons les doubles négatifs :
F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ wedge ((\ neg Y \ wedge \ neg Z) \ vee \ neg X).)Par exemple, la formule suivante s'écrit en 2-CNF :
(A B) (¬ B ∨ C) ∧ (B ∨ ¬ C). (\ displaystyle (A \ lor B) \ land (\ neg B \ lor C) \ land (B \ lor \ neg C).)Disjonction simple(disjonction incluse) ou disjoint(Disjunct anglais) est une disjonction d'une ou plusieurs variables ou de leurs négations, et chaque variable n'apparaît pas plus d'une fois.
Disjonction simple
- Achevée si chaque variable (ou sa négation) y apparaît exactement une fois ;
- monotone s'il ne contient pas de variables négatives.
Forme normale conjonctive, CNF(eng. conjonctive normal form, CNF) forme normale, dans laquelle la fonction booléenne a la forme de la conjonction de plusieurs propositions simples.
Exemple CNF :$ f (x, y) = (x \ lor y) \ land (y \ lor \ neg (z)) $
SKNF
Forme normale conjonctive parfaite, SKNF(forme normale conjonctive parfaite, PCNF) est un CNF qui remplit les conditions suivantes :
- il n'a pas les mêmes disjonctions simples
- chaque disjonction simple est complète
Exemple SKNF :$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $
Théorème: Pour toute fonction booléenne $ f (\ vec (x)) $, qui n'est pas égale à l'identité, il existe un SKNF qui la définit.
Preuve: Puisque l'inverse de la fonction $ \ neg (f) (\ vec x) $ est égal à un sur les tuples sur lesquels $ f (\ vec x) $ est égal à zéro, alors le SDNF pour $ \ neg (f) (\ vec x) $ peut s'écrire comme suit :
$ \ neg (f) (\ vec x) = \ bigvee \limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ coin x_ (2) ^ (\ sigma_ (2)) \ coin ... \ coin x_ (n) ^ (\ sigma_ (n ))) $, où $ \ sigma_ (i) $ désigne la présence ou l'absence de négation pour $ x_ (i) $
Trouvez l'inverse des côtés gauche et droit de l'expression :
$ f (\ vec x) = \ neg ((\ bigvee \limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ coin x_ (2) ^ (\ sigma_ (2)) \ coin ... \ coin x_ (n) ^ (\ sigma_ (n ))))) $
En appliquant deux fois la règle de de Morgan à l'expression obtenue du membre de droite, on obtient : $ f (\ vec x) = \ bigwedge \limits_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2), \ dots , x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ dots \ vee \ neg (x_n ^ (\ sigma_n) ))) $
La dernière expression est SKNF. Puisque le SKNF est obtenu à partir du SDNF, qui peut être construit pour toute fonction qui n'est pas identiquement nulle, le théorème est prouvé.
Algorithme pour construire SKNF selon la table de vérité
- Dans la table de vérité, nous marquons les ensembles de variables sur lesquels la valeur de la fonction est égale à $ 0 $.
- Pour chaque ensemble marqué, nous écrivons la disjonction de toutes les variables selon la règle suivante : si la valeur d'une variable est $ 0 $, alors la variable elle-même est incluse dans la disjonction, sinon sa négation.
- On relie toutes les disjonctions résultantes par des opérations de conjonction.
Un exemple de construction de SKNF pour la médiane
un). Dans la table de vérité, nous marquons les ensembles de variables sur lesquels la valeur de la fonction est égale à $ 0 $.
X oui z $ \ langle x, y, z \ rang $ 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 2). Pour chaque ensemble marqué, nous écrivons la conjonction de toutes les variables selon la règle suivante : si la valeur d'une variable est $ 0 $, alors nous incluons la variable elle-même dans la disjonction, sinon sa négation.
X oui z $ \ langle x, y, z \ rang $ 0 0 0 0 $ (x \ lor y \ lor z) $ 0 0 1 0 $ (x \ lor y \ lor \ neg (z)) $ 0 1 0 0 $ (x \ lor \ neg (y) \ lor z) $ 0 1 1 1 1 0 0 0 $ (\ neg (x) \ lor y \ lor z) $ 1 0 1 1 1 1 0 1 1 1 1 1 3). On relie toutes les disjonctions résultantes par des opérations de conjonction.
$ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ land (\ neg (x) \ lor y \ lor z) \ land (x \ lor \ neg (y) \ lor z) \ terre (x \ lor y \ lor \ neg (z)) $
Exemples SKNF pour certaines fonctions
Flèche de Pierce : $ x \ downarrow y = (\ neg (x) \ lor (y)) \ land ((x) \ lor \ neg (y)) \ land (\ neg (x) \ lor \ neg (y) ) $
Exclusif ou : $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ land (\ neg (x) \ lor y \ lor \ neg (z)) \ land (x \ lor \ neg (y) \ lor \ neg (z)) \ land (x \ lor y \ lor z) $
Exemple. Trouver des formules CNF
~
~ 
Une forme normale disjonctive parfaite de SDNF peut être construite en utilisant l'algorithme suivant :
1. = 1. de l'algorithme DNF
2. = 2. de l'algorithme DNF
3. = 3. algorithme DNF
4. = 4. de l'algorithme DNF
5. Supprimer les termes identiquement faux, c'est-à-dire les termes de la forme
6. Reconstituer les termes restants avec les variables manquantes
7. Répétez l'étape 4.
Exemple. Trouvez des formules SDNF.
~ 
Pour construire le SKNF, vous pouvez utiliser le schéma suivant :
Exemple. Trouvez des formules SDNF.
~ 
Il est connu (théorèmes 2.11, 2.12) que SDNF et SKNF sont uniquement déterminés par la formule et, par conséquent, ils peuvent être construits à partir de la table de vérité de la formule.
Le schéma pour construire SDNF et SKNF selon la table de vérité est donné ci-dessous, pour la formule
~ :
~
1 0 1 0 1 1 0 1 SDNF ; SKNF. 2.2. Exercer.
2.2.1 Vous trouverez ci-dessous les expressions logiques. Simplifiez au maximum les expressions de votre variante en utilisant les lois logiques de Boole. Utilisez ensuite des tables de vérité pour comparer votre expression simplifiée avec l'originale.
2.2.2. Trouver la question de l'équivalence de f 1 et f 2 en les réduisant à SDNF (tableau 1).
2.2.3. Trouver la fonction duale pour f 3 selon le principe généralisé et booléen (tableau 1). Comparez les résultats.
№ f 1 f 2 f 3 
2.3. Questions de contrôle.
2.3.1. Donnez la définition de l'énoncé.
2.3.2. Lister les opérations de base sur l'énoncé.
2.3.3. Qu'est-ce qu'une table de vérité ?
2.3.4. Créez des tables de vérité pour les formules suivantes :
~ ~
~ ;2.3.5. Compte tenu des conventions sur l'ordre d'exécution des opérations, omettez les parenthèses "extra" et le signe "" dans les formules :
;2.3.6. En utilisant des transformations équivalentes, prouver la vérité identique des formules :
2.3.7. Trouver des formules doubles :
)
2.3.8. Apportez les formules suivantes à la forme DNF parfaite (SDNF) :
~ 2.3.9. Apportez les formules suivantes à la forme CNF parfaite (SKNF) :
~ 
Travaux de laboratoire n°3
Sujet:"Minimisation des fonctions booléennes. Logique"
Cibler: Acquisition de compétences pratiques pour travailler avec des méthodes de minimisation des fonctions booléennes.
3.1. Informations théoriques.
Formes minimales
Comme indiqué dans, toute fonction booléenne est représentable sous une forme normale parfaite (disjonctive ou conjonctive). De plus, une telle présentation est la première étape du passage de la définition tabulaire d'une fonction à son expression analytique. Dans ce qui suit, nous partirons de la forme disjonctive, et les résultats correspondants pour la forme conjonctive sont obtenus sur la base du principe de dualité.
Le problème canonique de la synthèse des circuits logiques dans une base booléenne se réduit à minimiser les fonctions booléennes, c'est-à-dire pour les représenter sous forme normale disjonctive, qui contient le plus petit nombre de lettres (variables et leurs négations). De telles formes sont appelées minimales. Dans la synthèse canonique, on suppose que les deux signaux et leurs inversions sont appliqués aux entrées du circuit.
La formule, présentée sous forme normale disjonctive, est simplifiée par de multiples applications de l'opération de collage et de l'opération d'absorption et (les identités duales pour la forme normale conjonctive ont la forme : et). Ici, et peut être compris comme n'importe quelle formule de l'algèbre booléenne. En conséquence, nous arrivons à une expression analytique lorsque d'autres transformations sont déjà impossibles, c'est-à-dire nous obtenons une forme sans issue.
Parmi les formes sans issue se trouve la forme disjonctive minimale, et elle peut ne pas être unique. Pour s'assurer qu'une forme sans issue donnée est minimale, il est nécessaire de trouver toutes les formes sans issue et de les comparer par le nombre de lettres qu'elles contiennent.
Par exemple, soit la fonction donnée sous la forme disjonctive normale parfaite :
En regroupant les membres et en appliquant l'opération de collage, nous avons.
Avec une autre méthode de regroupement, on obtient :
Les deux formes sans issue ne sont pas minimes. Pour obtenir la forme minimale, vous devez deviner répéter un terme dans la formule d'origine (cela peut toujours être fait, depuis). Dans le premier cas, un tel membre peut l'être. Puis . En ajoutant un membre, on obtient :. Après avoir parcouru toutes les options possibles, vous pouvez vous assurer que les deux dernières formes sont minimales.
Travailler avec des formules à ce niveau, c'est comme errer dans le noir. Le processus de recherche de formes minimales devient plus visuel et utile si vous utilisez des représentations graphiques et analytiques et des symboles spécialement conçus à cet effet.
Cube multidimensionnel
Chaque sommet du cube -dimensionnel peut être associé au constituant de l'unité. Par conséquent, le sous-ensemble des sommets marqués est une application sur le cube -dimensionnel d'une fonction booléenne de variables sous forme normale disjonctive parfaite. En figue. 3.1 montre un tel mappage pour la fonction de la section 3.7.
Fig. 3.1 Représentation sur un cube tridimensionnel de la fonction présentée dans SDNF
Pour afficher une fonction de variables présentées sous n'importe quelle forme normale disjonctive, il est nécessaire d'établir une correspondance entre ses minitermes et les éléments du cube -dimensionnel.
Le minitherm de (-1) -ième rang peut être considéré comme le résultat du collage de deux minitermes de -ième rang (constituant de l'unité), c'est-à-dire
Sur un cube -dimensionnel, cela correspond à remplacer deux sommets qui ne diffèrent que par les valeurs de la coordonnée reliant ces sommets par une arête (on dit que l'arête recouvre les sommets incidents). Ainsi, les minitermes du (-1) ème ordre correspondent aux arêtes du cube -dimensionnel. De même, la correspondance des minitermes du (-2) ème ordre est établie avec les faces du cube -dimensionnel, dont chacune couvre quatre sommets (et quatre arêtes).Les éléments d'un cube -dimensionnel, caractérisés par des dimensions, sont appelés -cubes. Ainsi, les sommets sont des 0-cubes, les arêtes sont des 1-cubes, les faces sont des 2-cubes, etc. En résumant le raisonnement ci-dessus, nous pouvons supposer que le miniterme du () -ième rang dans la forme normale disjonctive pour la fonction des variables est affiché par un -cube, et chaque -cube couvre tous ces -cubes de dimension la plus basse qui sont associé à ses sommets. A titre d'exemple, la fig. 3.2 le mappage de la fonction de trois variables est donné. Ici, les minitherms et correspondent à 1-cubes (), et les miniterms sont affichés sous forme de 2-cubes ().
Figure 3.2 Couverture fonctionnelle
Ainsi, toute forme normale disjonctive est affichée sur le cube -dimensionnel par une collection de -cubes qui couvrent tous les sommets correspondant aux constituants de l'unité (0-cubes). L'inverse est également vrai : si une collection de -cubes couvre l'ensemble de tous les sommets correspondant aux valeurs unitaires de la fonction, alors la disjonction des minitermes correspondant à ces -cubes est l'expression de cette fonction sous forme normale disjonctive . On dit qu'un tel ensemble de -cubes (ou les minitermes correspondants) forme la couverture d'une fonction.
La recherche de la forme minimale est intuitivement comprise comme la recherche d'une telle couverture, dont le nombre de -cubes serait plus petit, et leur dimension serait plus grande. La couverture correspondant à la forme minimale est appelée couverture minimale. Par exemple, pour la couverture de fonction de la Fig. 3.3 correspond aux formes minimales
et 
.
Riz. 3.3 Couvertures de fonction.
à gauche –
; sur la droite – 
L'affichage d'une fonction sur un cube -dimensionnel est clair et simple. Un cube à quatre dimensions peut être dessiné comme le montre la fig. 3.4, où la fonction de quatre variables et sa couverture minimale correspondant à l'expression 
... L'utilisation de cette méthode nécessite des constructions si complexes que tous ses avantages sont perdus.Riz. 3.4 Affichage des fonctions
sur un cube à quatre dimensionsCartes de Karnaugh
Une autre méthode de représentation graphique des fonctions booléennes utilise Cartes de Karnot, qui sont des tables de consultation spécialement organisées. Les colonnes et les lignes du tableau correspondent à tous les ensembles de valeurs possibles de deux variables au maximum, et ces ensembles sont disposés dans un ordre tel que chacun des suivants diffère du précédent par la valeur d'une seule des variables . Pour cette raison, les cellules adjacentes horizontalement et verticalement du tableau diffèrent par la valeur d'une seule variable. Les cellules situées sur les bords du tableau sont également considérées comme adjacentes et ont cette propriété. En figue. 3.5 montre des graphiques de Karnaugh pour deux, trois, quatre variables.
Riz. 3.5 Cartes de Karnot pour deux, trois et quatre variables
Comme dans les tables de vérité ordinaires, les cellules des ensembles dans lesquels la fonction prend la valeur 1 sont remplies de uns (les zéros ne rentrent généralement pas, ils correspondent à des cellules vides). Par exemple, dans la Fig. 3.6, une montre la carte de Karnot pour la fonction, dont le mappage sur le cube à quatre dimensions est donné dans la Fig. 3.4. Pour plus de simplicité, les lignes et les colonnes correspondant aux valeurs de 1 pour une variable sont entourées d'accolades avec la désignation de cette variable.
Riz. 3.6 Affichage d'une fonction de quatre variables sur un graphe de Karnot
(a) et sa couverture minimale (b)
Entre les mappages de fonction sur m-cube de dimension et sur la carte de Karnot il y a une correspondance un à un. Sur la carte de Karnot s-cube correspond à un ensemble de 2 cellules voisines situées dans une ligne, une colonne, un carré ou un rectangle (en tenant compte de la proximité des bords opposés de la carte). Par conséquent, toutes les dispositions énoncées ci-dessus (voir p. cube multidimensionnel) sont valables pour les cartes de Karnot. Ainsi, dans la fig. 3.6, b la couverture des unités cartographiques correspondant à la forme disjonctive minimale est montrée
la fonction considérée.La lecture des minitermes de la carte Karnot s'effectue selon une règle simple. Les cellules qui se forment s-cube, donne ministre (n – s)-ème rang, qui comprend ceux (n – s) variables qui stockent les mêmes valeurs sur ce s-cube, où la valeur 1 correspond aux variables elles-mêmes, et les valeurs 0 correspondent à leurs négations. Variables qui ne stockent pas leurs valeurs pour s-cube, dans le miniterm sont absents. Différentes manières de lire conduisent à différentes représentations de la fonction sous forme normale disjonctive (celle la plus à droite est minimale) (Fig. 3.7).
L'utilisation des cartes de Karnaugh nécessite des constructions plus simples que la cartographie sur m-cube dimensionnel, en particulier dans le cas de quatre variables. Pour afficher les fonctions de cinq variables, deux cartes de Karnot pour quatre variables sont utilisées, et pour une fonction de six variables, quatre de ces cartes sont utilisées. Avec une nouvelle augmentation du nombre de variables, les cartes de Karnot deviennent pratiquement inutilisables.
Connu dans la littérature Cartes de Weich ne diffèrent que par un ordre différent des ensembles de valeurs de variables et ont les mêmes propriétés que les cartes de Karnot.
Complexe de cubes
L'incohérence des méthodes graphiques avec un grand nombre de variables est compensée par diverses méthodes analytiques de représentation des fonctions booléennes. L'une de ces représentations est complexe de cubes en utilisant la terminologie de l'espace logique multidimensionnel en combinaison avec une symbologie spécialement conçue.
). Les 0-cubes correspondant aux constituants de un sont représentés par des ensembles de valeurs de variables sur lesquelles la fonction est égale à un. Evidemment dans le dossier
Riz. 3.8 Complexe de cubes d'une fonction de trois variables ( une) et sa représentation symbolique ( b)
Un complexe de formes de cubes couverture fonctionnelle maximale... En excluant tous ceux s-des cubes, qui sont recouverts de cubes de la plus haute dimension, on obtient des revêtements correspondant à des formes sans issue. Ainsi, pour l'exemple considéré (Fig. 3.8) nous avons un couvercle sans issue
,qui correspond à la fonction
... Dans ce cas, cette couverture est également minime.Pour deux fonctions booléennes, l'opération de disjonction correspond à l'union de leurs complexes de cubes, et l'opération de conjonction correspond à l'intersection de complexes de cubes. La négation d'une fonction correspond au complément d'un complexe de cubes, c'est-à-dire qu'elle est déterminée par tous les sommets auxquels la fonction prend la valeur 0. Ainsi, il existe une correspondance bijective (isomorphisme) entre l'algèbre de Fonctions booléennes et ensembles booléens représentant des complexes de cubes.
La représentation d'une fonction sous forme de complexes de cubes est moins claire, mais ses avantages les plus importants sont qu'elle supprime les restrictions sur le nombre de variables et facilite l'encodage des informations lors de l'utilisation d'ordinateurs.
Minimiser les fonctions booléennes
Formulation du problème. Minimiser un circuit dans une base booléenne se réduit à trouver la forme disjonctive minimale, qui correspond à la couverture minimale. Le nombre total de lettres dans la forme normale est exprimé par le prix de la couverture
, où est le nombre de - cubes formant une couverture de la fonction donnée en n variables. La couverture minimale se caractérise par la valeur la plus basse de son prix.Habituellement, le problème de minimisation est résolu en deux étapes. Tout d'abord, recherchez une couverture abrégée qui inclut tous les cubes de dimension maximale, mais ne contient aucun cube couvert par un cube de cette couverture. La forme normale disjonctive correspondante est appelée abrégée, et ses minitermes sont appelés implicants simples. Pour cette fonction, la couverture coupée est la seule, mais elle peut être redondante du fait que certains des cubes sont couverts par des collections d'autres cubes.
À la deuxième étape, le passage des formes normales disjonctives réduites aux formes sans issue est effectuée, parmi lesquelles les formes minimales sont sélectionnées. Les formes sans issue sont formées en excluant de la couverture abrégée de tous les cubes redondants, sans lesquels l'ensemble de cubes restant forme toujours une couverture de la fonction donnée, mais après exclusion supplémentaire de l'un des cubes, il ne couvre plus les ensembles de tous les sommets correspondant aux valeurs unitaires de la fonction, c'est-à-dire qu'elle cesse d'être une couverture...
Un cube à couverture réduite qui couvre les sommets d'une fonction donnée qui ne sont couverts par aucun autre cube ne peut pas être redondant et sera toujours inclus dans la couverture minimale. Un tel cube, comme l'implicant correspondant, est appelé un extrémal (implicant essentiel), et les sommets qu'il couvre sont appelés sommets annulés. L'ensemble des extrémaux constitue le noyau de la couverture ; il est clair que lorsqu'on passe d'une couverture réduite au minimum, il faut tout d'abord distinguer tous les extrémaux. Si l'ensemble des extrémaux ne forme pas une couverture, alors il est complété pour être recouvert de cubes de la couverture réduite.
Ces définitions sont illustrées à la Fig. 3.9, où la couverture réduite (voir fig. 3.9a, ) et la couverture minimale (Fig. 3.9b) et (voir Fig. 3.9, b) sont exprimées comme suit.
Formes normales disjonctives et conjonctives de l'algèbre propositionnelle. Pour chaque fonction de la logique des énoncés, vous pouvez créer une table de vérité. Le problème inverse est également toujours soluble. Introduisons plusieurs définitions.
Conjonctions élémentaires (conjoints) sont appelées conjonctions de variables ou leurs négations, dans lesquelles chaque variable apparaît au plus
une fois.
Forme normale disjonctive(DNF) est une formule qui a la forme d'une disjonction de conjonctions élémentaires.
Clauses élémentaires (clauses) sont appelées disjonctions de variables avec ou sans négations.
Forme normale conjonctive(CNF) est une formule qui a la forme d'une conjonction de disjonctions élémentaires.
Pour chaque fonction de l'algèbre des propositions, on peut trouver un ensemble de formes normales disjonctives et conjonctives.
Algorithme de construction du DNF :
1. Accédez aux opérations booléennes à l'aide de formules de transformation équivalentes.
2. Aller aux formules avec des négations proches, c'est-à-dire à une formule dans laquelle les négations ne sont pas situées plus haut qu'au-dessus des variables - pour appliquer les lois de de Morgan.
3. Développez les parenthèses - appliquez les lois de la distribution.
4. Prenez les termes répétés une fois - la loi de l'idempotence.
5. Appliquer les lois de l'absorption et de la semi-absorption.
Exemple 6. Trouver des formules DNF :.
L'algèbre de Boole tient principe de dualité... C'est comme suit.
La fonction s'appelle doubleà la fonction si. Celles. pour trouver une fonction duelle à une fonction donnée, il faut construire la négation de la fonction à partir des négations des arguments.
Exemple 7. Trouvez la fonction dual to.
Parmi les fonctions élémentaires de l'algèbre de Boole, 1 est dual à 0 et vice versa, x est dual à x, dual, dual et vice versa.
Si dans la formule F 1 représentant la fonction toutes les conjonctions sont remplacées
sur disjonction, disjonction sur conjonction, 1 à 0, 0 à 1, alors on obtient la formule F * représentant la fonction * dual.
La forme normale conjonctive (CNF) est un concept dual pour la DNF, il est donc facile de la construire selon le schéma :
Exemple 8. Trouvez le CNF de la formule :.
En utilisant le résultat de l'exemple 6, on a
Formes normales parfaites disjonctives et parfaites conjonctives. Dans chacun des types de formes normales (disjonctive et conjonctive), une classe de formes parfaites SDNF et SKNF peut être distinguée.
Une conjonction élémentaire parfaite est le produit logique de toutes les variables avec ou sans négation, et chaque variable n'apparaît dans le produit qu'une seule fois.
Tout DNF peut être réduit à SDNF en divisant les conjonctions qui ne contiennent pas toutes les variables, c'est-à-dire l'addition pour la variable manquante x i est multipliée en utilisant la loi de distribution
Exemple 9. Trouver SDNF pour DNF exemple 6
Disjonction élémentaire parfaite est la somme logique de toutes les variables avec ou sans négations, et chaque variable n'est incluse dans la somme qu'une seule fois.
Tout CNF peut être réduit à SKNF en ajoutant un terme de conjonction qui ne contient aucune conjonction variable X i et en appliquant la loi de distribution
Exemple 10. Apportez CNF à SKNF :
Pour construire le SKNF, vous pouvez utiliser le schéma
Exemple 11. Trouvez le SKNF pour la formule de l'exemple 6.
Chaque fonction a SDNF et, de plus, est unique. Chaque fonction a un SKNF et, de plus, le seul.
Parce que SDNF et SKNF sont définis par des formules uniquement, ils peuvent être construits selon la table de vérité de la formule.
Pour construire le SDNF, il faut sélectionner les lignes dans lesquelles F prend la valeur 1 et noter pour elles les conjonctions élémentaires parfaites. Si la valeur d'une variable dans la ligne requise de la table de vérité est égale à un, alors dans une conjonction parfaite, elle est prise sans négation, si zéro, alors avec négation. Ensuite, les conjonctions parfaites (leur nombre est égal au nombre de uns dans le tableau) sont reliées par des signes de disjonction.
Pour construire le SKNF selon la table de vérité, il est nécessaire de sélectionner les lignes qu'il contient, où F = 0, et d'écrire les disjonctions élémentaires parfaites, puis de les connecter avec des signes de conjonction. Si dans la ligne requise de la table de vérité (F = 0) la valeur de la variable correspond à zéro, alors dans une clause parfaite elle est prise sans négation, si c'est un - alors avec négation.
Exemple 12. Trouvez SDNF et SKNF en utilisant la table de vérité pour la formule de l'exemple 6.
Le tableau 14 ne montre que la valeur finale de F = 10101101. Vous devriez vous-même être convaincu de la validité de cette affirmation en construisant une table de vérité élargie.
Tableau 14
X oui z