Definicija 1.Konjunktivni monom (elementarna konjunkcija) varijabli je konjunkcija tih varijabli ili njihovih negacija.
Na primjer, je elementarna konjunkcija.
Definicija 2.Disjunktivni monom (elementarna disjunkcija) od varijabli je disjunkcija tih varijabli ili njihovih negacija.
Na primjer, je elementarna disjunkcija.
Definicija 3. Formula koja je ekvivalentna zadanoj formuli propozicione algebre i disjunkcija je elementarnih konjunktivnih monoma naziva se disjunktivni normalni oblik(DNF) ove formule.
Na primjer,– DNF.
Definicija 4. Formula koja je ekvivalentna zadanoj formuli propozicione algebre i konjunkcija je elementarnih disjunktivnih monoma naziva se konjunktivni normalni oblik(CNF) ove formule.
Na primjer, – KNF.
Za svaku formulu propozicionalne algebre može se pronaći skup disjunktivnih i konjunktivnih normalnih formi.
Algoritam za konstruiranje normalnih formi
Koristeći ekvivalente logičke algebre, zamijenite sve osnovne operacije u formuli: konjunkcija, disjunkcija, negacija:
Riješite se dvostrukih negativa.
Primijenite, ako je potrebno, svojstva distributivnosti i formule apsorpcije na operacije konjunkcije i disjunkcije.
2.6. Perfektni disjunktivni i perfektni konjunktivni normalni oblici
Bilo koja Booleova funkcija može imati mnoge reprezentacije u obliku DNF i CNF. Među tim prikazima posebno mjesto zauzimaju savršeni DNF (SDNF) i savršeni CNF (SCNF).
Definicija 1. Savršeni disjunktivni normalni oblik(SDNF) je DNF u kojem svaki konjunktivni monom sadrži svaku varijablu iz skupa točno jednom, bilo samu sebe ili svoju negaciju.
Strukturno, SDNF za svaku formulu propozicijske algebre svedenu na DNF može se definirati na sljedeći način:
Definicija 2. Savršeni disjunktivni normalni oblik(SDNF) formule iskazne algebre naziva se njezin DNF, koji ima sljedeća svojstva:
Definicija 3. Perfektni konjunktivni normalni oblik(SCNF) je CNF u kojem svaki disjunktivni monom sadrži svaku varijablu iz skupa točno jednom, a pojavljuje se ili sam ili njegova negacija.
Strukturno, SCNF za svaku formulu propozicijske algebre svedenu na CNF može se definirati na sljedeći način.
Definicija 4. Perfektni konjunktivni normalni oblik(SCNF) dane formule propozicionalne algebre naziva se CNF koja zadovoljava sljedeća svojstva.
Teorem 1. Svaka Booleova funkcija varijabli koja nije identično lažna može se predstaviti u SDNF-u, i to na jedinstven način.
Metode za pronalaženje SDNF
1. metoda
2. metoda
odaberite retke u kojima formula ima vrijednost 1;
sastavljamo disjunkciju konjunkcija pod uvjetom da ako je varijabla uključena u konjunkciju s vrijednošću 1, tada zapisujemo tu varijablu, ako s vrijednošću 0, onda njenu negaciju. Dobivamo SDNF.
Teorem 2. Svaka Booleova funkcija varijabli koja nije identično istinita može se predstaviti u SCNF-u, i to na jedinstven način.
Metode za pronalaženje SCNF
1. metoda– koristeći ekvivalentne transformacije:
2. metoda– korištenje tablica istinitosti:
odaberite retke u kojima formula ima vrijednost 0;
sastavljamo konjunkciju disjunkcija pod uvjetom da ako je varijabla uključena u disjunkciju s vrijednošću 0, tada zapisujemo tu varijablu; ako s vrijednošću 1, onda njezinu negaciju. Dobivamo SKNF.
Primjer 1. Konstruirajte CNF funkcije.
Riješenje
Eliminirajmo veznik "" koristeći zakone transformacije varijabli:
= /de Morganovi zakoni i dvostruka negacija/ =
/distribucijski zakoni/ =
Primjer 2. Daj formulu DNF-u.
Riješenje
Izrazimo logičke operacije pomoću i:
= /klasificirajmo negaciju kao varijable i smanjimo dvostruke negative/ =
= /zakon distributivnosti/ .
Primjer 3. Napišite formulu u DNF i SDNF.
Riješenje
Koristeći se zakonima logike, ovu formulu svodimo na oblik koji sadrži samo disjunkcije elementarnih konjunkcija. Rezultirajuća formula bit će željeni DNF:
Da bismo konstruirali SDNF, napravimo tablicu istine za ovu formulu:
Označavamo one retke tablice u kojima formula (posljednji stupac) ima vrijednost 1. Za svaki takav redak ispisujemo formulu koja je istinita na skupu varijabli ovog retka:
linija 1: ;
redak 3: ;
redak 5: .
Disjunkcija ove tri formule poprimit će vrijednost 1 samo na skupovima varijabli u redovima 1, 3, 5, i stoga će biti željena savršena disjunktivna normalna forma (PDNF):
Primjer 4. Donesite formulu u SKNF na dva načina:
a) pomoću ekvivalentnih transformacija;
b) pomoću tablice istinitosti.
Riješenje:
Transformirajmo drugu elementarnu disjunkciju:
Formula izgleda ovako:
b) sastavite tablicu istinitosti za ovu formulu:
Označavamo one retke tablice u kojima formula (posljednji stupac) ima vrijednost 0. Za svaki takav redak ispisujemo formulu koja je istinita na skupu varijabli ovog retka:
redak 2: ;
redak 6: .
Konjunkcija ovih dviju formula poprimit će vrijednost 0 samo na skupovima varijabli u recima 2 i 6, te će stoga biti željena savršena konjunktivna normalna forma (PCNF):
Pitanja i zadaci za samostalno rješavanje
1. Pomoću ekvivalentnih transformacija svedite formule na DNF:
2. Pomoću ekvivalentnih transformacija dovedite formule u CNF:
3. Koristeći drugi zakon distribucije, pretvorite DNF u CNF:
A) 
;
4. Pretvorite dane DNF-ove u SDNF-ove:
5. Pretvorite dani CNF u SCNF:
6. Za zadane logičke formule konstruirajte SDNF i SCNF na dva načina: korištenjem ekvivalentnih transformacija i korištenjem tablice istinitosti.
b) 
;
Konjunktivni normalni oblik je pogodan za automatsko dokazivanje teorema. Bilo koja Booleova formula može se svesti na CNF. Za to možete koristiti: zakon dvostruke negacije, de Morganov zakon, distributivnost.
Enciklopedijski YouTube
-
1 / 5
Formule u KNF-u:
¬ A ∧ (B ∨ C), (\displaystyle \neg A\klin (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\klin B.)Formule ne u KNF:
¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\displaystyle A\klin (B\vee (D\klin E)).)Ali ove 3 formule koje nisu u CNF-u ekvivalentne su sljedećim formulama u CNF-u:
¬ B ∧ ¬ C , (\displaystyle \neg B\klin \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\klin (B\vee D)\klin (B\vee E).)Izgradnja CNF
Algoritam za konstruiranje CNF
1) Riješite se svih logičkih operacija sadržanih u formuli, zamjenjujući ih osnovnima: konjunkcija, disjunkcija, negacija. To se može učiniti pomoću ekvivalentnih formula:
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)\wedge (A\vee \neg B).)2) Zamijenite znak negacije koji se odnosi na cijeli izraz s predznakom negacije koji se odnosi na pojedinačne iskaze varijable na temelju formula:
¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\klin \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\klin B)=\neg A\vee \neg B.)3) Riješite se dvostrukih negativa.
4) Primijeniti, ako je potrebno, svojstva distributivnosti i formule apsorpcije na operacije konjunkcije i disjunkcije.
Primjer konstrukcije CNF
Prenesimo formulu na CNF
F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\desna strelica Y)\klin ((\neg Y\desna strelica Z)\desna strelica \neg X).)Transformirajmo formulu F (\displaystyle F) na formulu koja ne sadrži → (\displaystyle \rightarrow ):
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\klin (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\klin (\neg (\neg \ neg Y\vee Z)\vee \neg X).)U dobivenoj formuli prenosimo negaciju na varijable i smanjujemo dvostruke negative:
F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)Na primjer, sljedeća formula je napisana u 2-CNF:
(A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\stil prikaza (A\ili B)\zemlja (\neg B\ili C)\zemlja (B\ili \neg C).)Jednostavna disjunkcija(eng. inclusive disjunction) ili disjunkcija(engleski disjunct) je disjunkcija jedne ili više varijabli ili njihovih negacija, pri čemu se svaka varijabla ne pojavljuje više od jednom.
Jednostavna disjunkcija
- puna, ako se svaka varijabla (ili njezina negacija) pojavljuje točno jednom;
- monoton, ako ne sadrži negacije varijabli.
Konjunktivni normalni oblik, CNF(eng. conjunctive normal form, CNF) normalni oblik u kojem Booleova funkcija ima oblik konjunkcije nekoliko jednostavnih rečenica.
KNF primjer:$f(x,y) = (x \lor y) \land (y \lor \neg ( z ))$
SKNF
Savršena konjunktivna normalna forma, SCNF(engleski perfect conjunctive normal form, PCNF) je CNF koji zadovoljava uvjete:
- ne sadrži identične jednostavne disjunkcije
- svaka jednostavna disjunkcija je potpuna
SKNF primjer:$f(x,y,z) = (x \lor \neg ( y ) \or z) \land (x\lor y \lor \neg ( z ))$
Teorema: Za bilo koju Booleovu funkciju $f(\vec ( x ))$ koja nije jednaka identičnoj jedinici, postoji SCNF koji je definira.
Dokaz: Budući da je inverz funkcije $\neg ( f ) (\vec x)$ jednak jedan na onim skupovima na kojima je $f(\vec x)$ jednak nuli, tada je SDNF za $\neg ( f ) (\vec x)$ može se napisati na sljedeći način:
$\neg ( f ) (\vec x) = \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \klin x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \klin ... \klin x_ ( n ) ^ ( \sigma_ ( n ) )) $, gdje $ \sigma_ ( i ) $ označava prisutnost ili odsutnost negacije na $ x_ ( i ) $
Nađimo inverziju lijeve i desne strane izraza:
$ f(\vec x) = \neg (( \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \klin x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \klin ... \klin x_ ( n ) ^ ( \sigma_ ( n )))) )) $
Primjenom de Morganovog pravila dva puta na izraz dobiven na desnoj strani, dobivamo: $ 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 ) ) ) $
Zadnji izraz je SKNF. Budući da se SCNF dobiva iz SDNF, koji se može konstruirati za bilo koju funkciju koja nije identična nula, teorem je dokazan.
Algoritam za konstruiranje SCNF pomoću tablice istine
- U tablici istinitosti označavamo one skupove varijabli za koje je vrijednost funkcije jednaka $0$.
- Za svaki označeni skup ispisujemo disjunkciju svih varijabli prema sljedećem pravilu: ako je vrijednost neke varijable $0$, tada u disjunkciju uključujemo samu varijablu, inače njezinu negaciju.
- Sve nastale disjunkcije povezujemo operacijama konjunkcije.
Primjer konstruiranja SCNF za medijan
1). U tablici istinitosti označavamo one skupove varijabli za koje je vrijednost funkcije jednaka $0$.
x g z $ \langle x,y,z \rangle $ 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). Za svaki označeni skup ispisujemo konjunkciju svih varijabli prema sljedećem pravilu: ako je vrijednost neke varijable $0$, tada u disjunkciju uključujemo samu varijablu, inače njezinu negaciju.
x g z $ \langle x,y,z \rangle $ 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 ) \or 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). Sve nastale disjunkcije povezujemo operacijama konjunkcije.
$ \langle x,y,z \rangle = (x \lor y \or z) \zemlja (\neg ( x ) \lor y \or z) \zemlja (x \lor \neg ( y ) \or z) \zemlja (x \lor y \lor \neg ( z ))$
Primjeri SKNF-a za neke funkcije
Peirceova strelica: $ x \downarrow y = (\neg ( x ) \lor ( y )) \land (( x ) \lor \neg ( y )) \land (\neg ( x ) \lor \neg ( y ) )$
Isključivo ili: $ x \oplus y \oplus z = (\neg ( x ) \lor \neg ( y ) \or z) \land (\neg ( x ) \lor y \lor \neg ( z )) \land (x \lor \neg ( y ) \lor \neg ( z )) \land (x \lor y \or z)$
Primjer. Pronađite CNF formule
~
~ 
Savršeni disjunktivni normalni oblik SDNF-a može se konstruirati pomoću sljedećeg algoritma:
1. = 1. DNF algoritam
2. = 2. DNF algoritam
3. = 3. DNF algoritam
4. = 4. DNF algoritam
5. Izostaviti istovjetno netočne pojmove, tj. pojmove obrasca
6. Dopunite preostale izraze varijablama koje nedostaju
7. Ponovite točku 4.
Primjer. Pronađite SDNF formule.
~ 
Za konstrukciju SCNF-a možete koristiti sljedeću shemu:
Primjer. Pronađite SDNF formule.
~ 
Poznato je (teoremi 2.11, 2.12) da su SDNF i SCNF jedinstveno definirani formulom i stoga se mogu konstruirati pomoću tablice istinitosti formule.
Shema za konstruiranje SDNF-a i SCNF-a prema tablici istinitosti dana je u nastavku, za formulu
~ :
~
1 0 1 0 1 1 0 1 SDNF; SKNF. 2.2. Vježbajte.
2.2.1 Ispod su Booleovi izrazi. Pojednostavite izraze svoje varijante što je više moguće koristeći Booleove zakone logike. Zatim upotrijebite tablice istine da usporedite svoj pojednostavljeni izraz s izvornim.
2.2.2. Razjasnite pitanje ekvivalentnosti f 1 i f 2 reducirajući ih na SDNF (Tablica 1).
2.2.3. Nađite dualnu funkciju za f 3 koristeći generalizirani i Booleov princip (Tablica 1). Usporedite rezultate.
№ f 1 f 2 f 3 
2.3. Kontrolna pitanja.
2.3.1. Definirajte izjavu.
2.3.2. Navedite glavne operacije na izvodu.
2.3.3. Što je tablica istinitosti?
2.3.4. Napravite tablice istinitosti za sljedeće formule:
~ ~
~ ;2.3.5. Uzimajući u obzir konvencije o redoslijedu operacija, izostavite "ekstra" zagrade i znak " " u formulama:
;2.3.6. Ekvivalentnim transformacijama dokažite identičnu istinitost formula:
2.3.7. Pronađite dualne formule:
)
2.3.8. Smanjite sljedeće formule u savršeni DNF (SDNF) oblik:
~ 2.3.9. Reducirajte sljedeće formule u savršeni CNF (SCNF) oblik:
~ 
Predmet:“Minimizacija Booleovih funkcija. Logika"
Cilj: Stjecanje praktičnih vještina rada s metodama minimiziranja Booleovih funkcija.
3.1. Teorijske informacije.
Minimalni oblici
Kao što je pokazano u, bilo koja Booleova funkcija može se prikazati u savršeno normalnom obliku (disjunktivno ili konjunktivno). Štoviše, takav je prikaz prvi korak u prijelazu s tablične specifikacije funkcije na njezin analitički izraz. U nastavku ćemo polaziti od disjunktivnog oblika, a odgovarajući rezultati za konjunktivni oblik dobivaju se na temelju načela dualnosti.
Kanonski problem sintetiziranja logičkih sklopova u Booleovoj bazi svodi se na minimiziranje Booleovih funkcija, tj. da ih predstavimo u disjunktivnom normalnom obliku, koji sadrži najmanji broj slova (varijabli i njihovih negacija). Takvi se oblici nazivaju minimalnim. U kanonskoj sintezi pretpostavlja se da se oba signala i njihove inverzije dovode na ulaze sklopa.
Formula prikazana u disjunktivnom normalnom obliku pojednostavljena je opetovanom upotrebom operacije lijepljenja i operacije apsorpcije i (dualni identiteti za konjunktivni normalni oblik imaju oblik: i ). Ovdje se može razumjeti kao bilo koja formula Booleove algebre. Kao rezultat dolazimo do analitičkog izraza u kojem daljnje transformacije više nisu moguće, tj. dobivamo slijepu formu.
Među slijepim oblicima postoji i minimalni disjunktivni oblik, a on ne mora biti jedinstven. Kako biste bili sigurni da je određeni slijepi obrazac minimalan, morate pronaći sve slijepe oblike i usporediti ih prema broju slova koja sadrže.
Neka je, na primjer, funkcija dana u savršenom normalnom disjunktivnom obliku:
Grupiranjem pojmova i primjenom operacije lijepljenja imamo .
S drugom metodom grupiranja dobivamo:
Oba slijepa oblika nisu minimalna. Da biste dobili minimalni oblik, morate pogoditi da ponovite jedan član u izvornoj formuli (ovo se uvijek može učiniti, jer ). U prvom slučaju takav član može biti . Zatim . Dodavanjem člana dobivamo: . Prošavši sve moguće opcije, možemo potvrditi da su posljednja dva oblika minimalna.
Rad s formulama na ovoj razini je poput lutanja u mraku. Proces traženja minimalnih oblika postaje vizualniji i svrhovitiji ako koristite neke grafičke i analitičke prikaze i simbole posebno razvijene za tu svrhu.
Višedimenzionalna kocka
Svaki vrh -dimenzionalne kocke može se pridružiti sastavnom dijelu jedinice. Posljedično, podskup označenih vrhova je preslikavanje na -dimenzionalnu kocku Booleove funkcije varijabli u savršenom disjunktivnom normalnom obliku. Na sl. 3.1 prikazuje takvo preslikavanje za funkciju iz klauzule 3.7.
Slika 3.1 Prikaz funkcije predstavljene u SDNF na trodimenzionalnoj kocki
Da bi se prikazala funkcija varijabli predstavljena u bilo kojem disjunktivnom normalnom obliku, potrebno je uspostaviti korespondenciju između njezinih minitermova i elemenata -dimenzionalne kocke.
Miniterm ranga (-1) može se smatrati rezultatom spajanja dvaju miniterma ranga (sastav jedinstva), tj.
, Na -dimenzionalnoj kocki, to odgovara zamjeni dvaju vrhova koji se razlikuju samo u vrijednostima koordinate koja povezuje ove vrhove s rubom (za rub se kaže da pokriva vrhove koji mu incidentiraju). Dakle, minitermovi (-1) reda odgovaraju bridovima -dimenzionalne kocke. Slično, uspostavljena je korespondencija minitermova (-2) reda sa plohama -dimenzionalne kocke, od kojih svaka pokriva četiri vrha (i četiri brida).Elementi -dimenzionalne kocke karakterizirani dimenzijama nazivaju se -kocke. Dakle, vrhovi su 0-kocke, bridovi su 1-kocke, lica su 2-kocke, itd. Generalizirajući gornje razmišljanje, možemo pretpostaviti da je miniterm ()th ranga u disjunktivnom normalnom obliku za funkciju varijabli predstavljen -kockom, a svaka -kocka pokriva sve one -kocke niže dimenzije koje su pridružene njezinim vrhovima . Kao primjer na Sl. 3.2 prikazuje funkciju triju varijabli. Ovdje miniterm odgovara 1-kocki (), a miniterm je predstavljen 2-kockom ().
Slika 3.2 Pokrivenost funkcije
Dakle, svaka disjunktivna normalna forma se preslikava na -dimenzionalnu kocku skupom -kocki koje pokrivaju sve vrhove koji odgovaraju konstituentima jedinice (0-kocke). Obratna izjava je također istinita: ako određeni skup -kocki pokriva skup svih vrhova koji odgovaraju jediničnim vrijednostima funkcije, tada je disjunkcija minitermova koji odgovaraju tim -kockama izraz ove funkcije u disjunktivnoj normali oblik. Za takvu kolekciju -kocki (ili njihovih odgovarajućih minitermova) kaže se da tvori pokrivanje funkcije.
Želja za minimalnom formom intuitivno se shvaća kao potraga za takvim pokrovom čiji bi broj kockica bio manji, a njihova dimenzija veća. Pokriće koje odgovara minimalnom obliku naziva se minimalnim pokrićem. Na primjer, za funkciju pokrivanja na Sl. 3.3 zadovoljava minimalne obrasce
I 
.
Riža. 3.3 Pokrivanja funkcija.
lijevo –
; desno – 
Prikaz funkcije na -dimenzionalnoj kocki je jasan i jednostavan kada . Četverodimenzionalna kocka može se prikazati kao što je prikazano na sl. 3.4, koja prikazuje funkciju četiriju varijabli i njenu minimalnu pokrivenost koja odgovara izrazu 
. Korištenje ove metode zahtijeva tako složene konstrukcije da se gube sve njene prednosti.Riža. 3.4 Prikaz funkcija
na četverodimenzionalnoj kockiCarnotove karte
Druga metoda za grafički prikaz Booleovih funkcija koristi se Carnotove karte, koji su posebno organizirane tablice korespondencije. Stupci i redovi tablice odgovaraju svim mogućim skupovima vrijednosti ne više od dvije varijable, a ti skupovi su raspoređeni takvim redoslijedom da se svaki sljedeći razlikuje od prethodnog u vrijednosti samo jedne od varijabli. . Zahvaljujući tome, susjedne ćelije tablice vodoravno i okomito razlikuju se u vrijednosti samo jedne varijable. Ćelije koje se nalaze na rubovima tablice također se smatraju susjednim i imaju ovo svojstvo. Na sl. Slika 3.5 prikazuje Karnaughove mape za dvije, tri, četiri varijable.
Riža. 3.5 Carnaughove karte za dvije, tri i četiri varijable
Kao iu običnim tablicama istine, ćelije skupova u kojima funkcija ima vrijednost 1 popunjene su jedinicama (nule obično ne stanu, one odgovaraju praznim ćelijama). Na primjer, na sl. 3.6, A prikazuje Karnaughovu mapu za funkciju, čiji je prikaz na četverodimenzionalnoj kocki dan na sl. 3.4. Kako bismo pojednostavili stvari, retci i stupci koji odgovaraju vrijednostima 1 za varijablu istaknuti su vitičastom zagradom koja označava tu varijablu.
Riža. 3.6 Prikaz funkcije četiriju varijabli na Carnaughovoj karti
(a) i njegovo minimalno pokriće (b)
Između preslikavanja funkcija u n-dimenzionalna kocka i Carnotova karta postoji korespondencija jedan na jedan. Na Carnotovoj karti s- kocka odgovara skupu od 2 susjedne ćelije postavljene u red, stupac, kvadrat ili pravokutnik (uzimajući u obzir blizinu suprotnih rubova karte). Stoga, sve gore navedene odredbe (vidi stavak. višedimenzionalna kocka), vrijede za Karnaughove karte. Dakle, na Sl. 3.6, b prikazuje pokrivenost jedinica karte koje odgovaraju minimalnom disjunktivnom obliku
dotičnu funkciju.Čitanje miniterma s Karnaughove karte provodi se pomoću jednostavno pravilo. Formiranje stanica s-kocka, daj miniter (n–s)-th rang, koji uključuje one (n–s) varijable koje zadržavaju iste vrijednosti na ovome s-kocka, gdje vrijednost 1 odgovara samim varijablama, a vrijednost 0 odgovara njihovim negacijama. Varijable koje ne zadržavaju svoje vrijednosti za s-kocka, nema ih u minitermu. Razni načini očitanja rezultiraju različitim prikazima funkcije u disjunktivnom normalnom obliku (onaj krajnje desno je minimalan) (Slika 3.7).
Korištenje Karnaughovih mapa zahtijeva jednostavnije konstrukcije u usporedbi s mapiranjem na n-dimenzionalna kocka, posebno u slučaju četiri varijable. Za prikaz funkcija pet varijabli koriste se dvije Karnaughove karte za četiri varijable, a za funkciju šest varijabli četiri takve mape. Daljnjim povećanjem broja varijabli Karnaughove karte postaju praktički neupotrebljive.
Poznat u književnosti Veitch karte Razlikuju se samo u različitom redoslijedu skupova vrijednosti varijabli i imaju ista svojstva kao Karnaughove karte.
Kompleks kocki
Nedosljednost grafičkih metoda s velikim brojem varijabli kompenzira se različitim analitičkim metodama za prikaz Booleovih funkcija. Jedan takav prikaz je kompleks kocaka, koristeći terminologiju višedimenzionalnog logičkog prostora u kombinaciji s posebno razvijenom simbolikom.
). 0-kocke koje odgovaraju konstituentima jedinice predstavljene su skupovima varijabilnih vrijednosti na kojima je funkcija jednaka jedinici. Očito na snimci
Riža. 3.8 Kompleks kubova funkcije triju varijabli ( A) i njegov simbolički prikaz ( b)
Kompleks kocki se formira maksimalno pokrivanje funkcija. Isključujući iz toga sve one s-kocke koje su prekrivene kockama veće dimenzije, dobivamo navlake koje odgovaraju slijepim oblicima. Dakle, za primjer koji razmatramo (slika 3.8) imamo slijepi kraj
,što odgovara funkciji
. U ovom slučaju, ova pokrivenost je minimalna.Za dvije Booleove funkcije operacija disjunkcije odgovara uniji njihovih kubnih kompleksa, a konjunkcija odgovara presjeku njihovih kubnih kompleksa. Negacija funkcije odgovara komplementu kompleksa kocki, tj. i određena je svim vrhovima u kojima funkcija ima vrijednost 0. Dakle, postoji korespondencija jedan na jedan (izomorfizam) između algebre Booleove funkcije i Booleovi skupovi koji predstavljaju komplekse kocki.
Predstavljanje funkcije u obliku kompleksa kocaka manje je vizualno, ali jest najvažnije prednosti su da su ograničenja broja varijabli uklonjena i da je kodiranje informacija olakšano pri korištenju računala.
Minimiziranje Booleovih funkcija
Formulacija problema. Minimizacija sklopa u Booleovoj bazi svodi se na pronalaženje minimalne disjunktivne forme koja odgovara minimalnoj pokrivenosti. Ukupan broj slova uključenih u normalan obrazac izražen je cijenom pokrića
, gdje je broj kocki koje tvore pokrivanje zadane funkcije od n varijabli. Karakterizirana je minimalna pokrivenost najniža vrijednost njegove cijene.Obično se problem minimizacije rješava u dva koraka. Prvo, tražimo smanjeni pokrov koji uključuje sve kocke maksimalnih dimenzija, ali ne sadrži niti jednu kocku pokrivenu nijednom kockom ovog pokrova. Odgovarajuća disjunktivna normalna forma naziva se reducirana, a njezini minitermovi nazivaju se jednostavnim implikacijama. Za određenu funkciju, smanjena pokrivenost je jedinstvena, ali može biti suvišna zbog činjenice da su neke od kocki pokrivene zbirkama drugih kocki.
U drugom koraku se vrši prijelaz sa reduciranih na slijepe disjunktivne normalne forme, iz kojih se biraju minimalne forme. Bezizlazne forme nastaju tako da se iz reducirane navlake isključe sve suvišne kocke, bez kojih preostali skup kocki i dalje čini navlaku zadane funkcije, ali daljnjim isključivanjem bilo koje od kocki više ne pokriva skup svih vrhova koji odgovaraju pojedinačnim vrijednostima funkcije, tj. prestaje biti pokrivanje.
Kocka smanjene pokrivenosti koja pokriva vrhove dane funkcije koji nisu pokriveni nijednom drugom kockom ne može biti suvišna i uvijek će biti uključena u minimalnu pokrivenost. Takva kocka, kao i njezin odgovarajući implikant, naziva se ekstremal (esencijalni implikant), a vrhovi koje pokriva nazivaju se poništeni vrhovi. Skup ekstremala čini jezgru pokrivanja; jasno je da pri prelasku sa reduciranog pokrivanja na minimalno, prije svega treba izolirati sve ekstremale. Ako skup ekstrema ne tvori pokrov, tada se nadopunjuje za pokrivanje kockama iz smanjenog pokrova.
Date definicije ilustrirane su na sl. 3.9, gdje je smanjena pokrivenost (vidi sl. 3.9a, ) i minimalne pokrivenosti (Sl. 3.9b) i (vidi Sl. 3.9, b) izražene su kako slijedi.
Disjunktivni i konjunktivni normalni oblici iskazne algebre. Za svaku funkciju propozicijske logike može se konstruirati tablica istinitosti. Inverzni problem je također uvijek rješiv. Uvedimo nekoliko definicija.
Elementarni veznici (konjunkti) nazivaju se konjunkcije varijabli ili njihove negacije u kojima se svaka varijabla pojavljuje najviše
jednom.
Disjunktivni normalni oblik(DNF) je formula koja ima oblik disjunkcije elementarnih konjunkcija.
Elementarne disjunkcije (disjunkcije) nazivaju se disjunkcije varijabli sa ili bez negacija.
Konjunktivni normalni oblik(CNF) je formula koja ima oblik konjunkcije elementarnih disjunkcija.
Za svaku funkciju propozicionalne algebre može se pronaći skup disjunktivnih i konjunktivnih normalnih formi.
Algoritam za konstrukciju DNF-a:
1. Idite na Booleove operacije koristeći ekvivalentne transformacijske formule.
2. Idite na formule s bliskim negacijama, odnosno na formule u kojima se negacije ne nalaze iznad varijabli - primijenite De Morganove zakone.
3. Otvorite zagrade - primijenite zakone distributivnosti.
4. Uzimajte termine koji se ponavljaju jedan po jedan - zakon idempotencije.
5. Primijeniti zakone apsorpcije i poluapsorpcije.
Primjer 6. Pronađite DNF formule: .
U Booleovoj algebri to je točno načelo dvojnosti. To je kako slijedi.
Funkcija se zove dual na funkciju if . Oni. Da bismo pronašli funkciju dualnu na zadanu, potrebno je konstruirati negaciju funkcije iz negacija argumenata.
Primjer 7. Pronađite funkciju dualnu na .
Među elementarne funkcije algebra logike 1 je dualna na 0 i obrnuto, x je dualna na x, dualna na , dualna i obrnuto.
Ako u formuli F 1 koja predstavlja funkciju zamijenimo sve veznike
na disjunkciji, disjunkciji na konjunkciji, 1 na 0, 0 na 1, tada dobivamo formulu F * koja predstavlja funkciju * dualnu na .
Konjunktivna normalna forma (CNF) je dualni koncept za DNF, tako da se lako može konstruirati prema sljedećoj shemi:
Primjer 8. Pronađite formulu CNF: .
Koristeći rezultat primjera 6, imamo
Perfektni disjunktivni i perfektni konjunktivni normalni oblici. U svakom od tipova normalnih oblika (disjunktivnih i konjunktivnih) razlikuje se klasa perfektnih oblika SDNF i SCNF.
Savršena elementarna konjunkcija logički je umnožak svih varijabli sa ili bez negacije, a svaka se varijabla u umnošku pojavljuje samo jednom.
Svaki DNF može se svesti na SDNF razdvajanjem konjunkcija koje ne sadrže sve varijable, tj. dodavanjem varijable koja nedostaje x i se množi prema zakonu distribucije
Primjer 9. Pronađite SDNF za DNF primjera 6
Savršena elementarna disjunkcija je logički zbroj svih varijabli sa ili bez negacija, a svaka varijabla je uključena u zbroj samo jednom.
Svaki CNF može se reducirati na SCNF dodavanjem konjunkcijskog člana koji ne sadrži nikakvu varijablu X i pomoću konjunkcije i primjenom zakona distribucije
Primjer 10. Donesite KNF u SKNF:
Da biste konstruirali SCNF, možete koristiti dijagram
Primjer 11. Pronađite SCNF za formulu primjera 6.
Svaka funkcija ima SDNF i, štoviše, jedinstven. Svaka funkcija ima SCNF i, štoviše, jedinstven.
Jer SDNF i SKNF jedinstveno su definirani formulama; mogu se konstruirati pomoću tablice istinitosti formule.
Za konstruiranje SDNF-a potrebno je odabrati retke u kojima F ima vrijednost 1 i za njih napisati savršene elementarne konjunkcije. Ako je vrijednost varijable u željenom retku tablice istine jednaka jedinici, tada se u savršenoj konjunkciji uzima bez negacije, ako je nula, onda s negacijom. Tada se savršeni veznici (njihov broj je jednak broju jedinica u tablici) povezuju disjunkcijskim znakovima.
Za konstrukciju SCNF pomoću tablice istinitosti potrebno je u njoj odabrati retke u kojima je F = 0, te zapisati savršene elementarne disjunkcije, a zatim ih povezati konjunkcijskim znakovima. Ako u traženom retku tablice istinitosti (F=0) vrijednost varijable odgovara nuli, tada se u savršenoj klauzuli uzima bez negacije, ako je jedinica, onda s negacijom.
Primjer 12. Pronađite SDNF i SCNF pomoću tablice istine za formulu primjera 6.
Tablica 14 prikazuje samo konačnu vrijednost F=10101101. Trebali biste sami provjeriti valjanost ove izjave izradom detaljne tablice istinitosti.
Tablica 14
x g z