Funcții booleene
Metoda diagramei Weich.
„Metoda face posibilă obținerea rapidă a DNF minimă a unei funcții booleene f a unui număr mic de variabile. Metoda se bazează pe o diagrame funcție booleană unei forme speciale, numite diagrame Veitch. Pentru o funcție booleană de două variabile Veitch diagramă are forma (tab. 4.4.1).
Fiecare celulă din diagramă corespunde unui set de variabile ale funcției Boolean în tabelul său de adevăr. În tabelul 4.4.1, această corespondență este prezentată în celula diagramei Weich, una este pusă dacă funcția Boolean ia o valoare unitară pe setul corespunzător. Valorile zero ale funcției Boolean din diagrama Weich nu sunt introduse. Pentru o funcție booleană a trei variabile, diagrama Weich are următoarea formă (Tabelul 4.4.2).
Adăugând la el același tabel oferă o diagramă pentru funcția a 4 variabile (Tabelul 4.4.3).
În același mod, adică. E. Atribuire o altă diagramă 3 variabile doar la considerate pot fi obținute pentru graficul funcției 5 variabile și t. D. Diagrama Totuși pentru funcțiile multor variabile, cu mai mult de 4 sunt rar utilizate. Diagramele date sunt caracterizate de următoarele:- Fiecare celulă a diagramei corespunde setului propriu;
- seturile adiacente sunt situate una lângă alta într-un rând sau într-o coloană.
constituțiile corespunzătoare unei perechi de unități din partea stângă a mesei sunt lipite împreună și generează un produs elementar cu 2 litere:
Despre perechea de unități din partea dreaptă a diagramei, puteți spune același lucru:
Rețineți că produsul elementar rezultat este ușor de determinat imediat din diagramă: este un produs al variabilelor care au aceeași valoare în ambele celule.
O altă observație importantă: coloanele situate la marginile diagramei sunt, de asemenea, considerate a fi adiacente. De exemplul nostru, acest lucru înseamnă că există o altă lipire, în care, în urma unei reguli specificate, obținem un produs elementar de x2 / x3 Dintre metodele discutate mai sus, noi știm că este posibil să continue lipirea obținute produse elementare. Pe diagramele Weich, ele sunt de asemenea situate una lângă alta. Regula generală pentru lipirea diagramelor Veitch poate afirma, după cum urmează: supusă lipirea configurație dreptunghiulară și care cuprinde unități de număr de celule umplute fiind o putere de 2. Produsul rezultat nou elementar este definit ca produsul dintre variabilele nu schimbă valorile pentru toate seturile lipite. Numărul m al variabilelor rămase dintr-un produs elementar este ușor de determinat:
unde n este numărul de variabile ale funcției, M este numărul de seturi lipite. Metoda este folosită pe scară largă în practică, datorită simplității și confortului acesteia. După un antrenament mic, se obține o aptitudine elementară pentru a determina DNF minim pe diagrama "la prima vedere". Minimalizarea funcției booleene este de a găsi acoperirea minimă toate unitățile diagramei Veitch de blocuri de unități (de configurare specificate) situate în diagrama vecine celule. În acest caz, se presupune că întotdeauna marginea din stânga a diagramei Beycha 4 variabile adiacente la marginea sa dreaptă, iar graficul okray superior adiacent la marginea inferioară. După obținerea minimă care acoperă toate unitățile diagrama Veitch, cea mai mică funcție DNF Boolean este scris ca o disjuncție de conjuncții elementare unități bloc alocate în diagrama corespunzătoare. Să luăm în considerare câteva exemple.
Un exemplu. Funcția booleană f are următoarea valoare SDNF:
Găsiți DNF minimă cu ajutorul diagramei Weich. Diagrama Weich care corespunde funcției f este prezentată în Tabelul. 4.4.5. Acoperirea minimă a tuturor unităților din diagramă este posibilă numai în blocuri de câte două unități. Fiecare astfel de bloc are o conjuncție proprie, așa cum se arată în Tabelul. 4.4.5.
În consecință, DNF minimă a unei funcții are forma:
Articole similare
Trimiteți-le prietenilor: