Konjunktivni normalni oblik logičke funkcije. "Udžbenik diskretne matematike dnf, sdnf, knf, sknf

Za bilo koju logičku formulu, uz pomoć identičnih transformacija, moguće je konstruirati beskonačno mnogo njoj ekvivalentnih formula. U algebri logike, jedan od glavnih zadataka je potraga za kanonskim oblicima (odnosno formulama izgrađenim prema jednom pravilu, kanonu).

Ako je logička funkcija izražena kroz disjunkciju, konjunkciju i negaciju varijabli, tada se ovaj oblik reprezentacije naziva normalnim.

Među normalnim oblicima razlikuju se savršeni normalni oblici (takvi oblici u kojima su funkcije zapisane na jedinstven način).

Savršeni disjunktivni normalni oblik (SDNF)

Definicija. Formula se naziva elementarnom konjunkcijom ako je nastala konjunkcijom niza varijabli ili njihovim negacijama.

Primjeri: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definicija. Formula se naziva disjunktivnim normalnim oblikom (DNF) ako je disjunkcija elementarnih veznika koji se ne ponavljaju.

DNF se zapisuje u sljedećem obliku: F 1 ∨ F 2 ∨ ... ∨ F n, gdje je F i elementarna konjunkcija

Primjeri: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definicija. Logička formula u k varijabli naziva se savršena disjunktivna normalna forma (SDNF) ako:
1) formula je DNF, u kojoj je svaka elementarna konjunkcija konjunkcija k varijabli x 1, x 2, ..., x k i na i-to mjesto ova konjunkcija je ili varijabla x i, ili njena negacija;
2) sve elementarne konjukcije u takvom DNF-u su parno različite.

Primjer: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Savršena konjunktivna normalna forma (SKNF)

Definicija. Formula se naziva elementarna disjunkcija ako je nastala disjunkcijama određenog broja varijabli ili njihovim negacijama.

Primjeri: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definicija. Formula se naziva konjunktivni normalni oblik (CNF) ako je konjunkcija neponovljivih elementarnih disjunkcija.

CNF se zapisuje u sljedećem obliku: F 1 ∧ F 2 ∧ ... ∧ F n, gdje je F i elementarna disjunkcija

Primjeri: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definicija. Logička formula u k varijabli naziva se savršeni konjunktivni normalni oblik (CDNF) ako:
1) formula je CNF, u kojoj je svaka elementarna disjunkcija disjunkcija k varijabli x 1, x 2, ..., x k, a na i-tom mjestu ove disjunkcije je ili varijabla x i ili njena negacija;
2) sve elementarne disjunkcije u takvoj CNF su parno različite.

Primjer: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

primijeti da bilo koja logička funkcija koja nije identično jednaka 0 ili 1 može se predstaviti kao SDNF ili SKNF.

Algoritam za konstruiranje SDNF-a prema tablici istinitosti

1. Odaberite sve retke tablice u kojima je vrijednost funkcije jednaka jedan.
2. Za svaki takav redak napišite konjunkciju svih varijabli na sljedeći način: ako je vrijednost neke varijable u ovom skupu jednaka 1, tada u konjukciju uključujemo i samu varijablu, inače - njezinu negaciju.
3. Sve nastale veznike povezujemo operacijama disjunkcije.

Algoritam za konstruiranje SKNF-a prema tablici istinitosti

1. Odaberite sve retke tablice u kojima je vrijednost funkcije jednaka nuli.
2. Za svaki takav redak napišite disjunkciju svih varijabli na sljedeći način: ako je vrijednost neke varijable u ovom skupu jednaka 0, tada uključujemo samu varijablu u konjukciju, inače - njezinu negaciju.
3. Sve nastale disjunkcije povezujemo konjunkcijskim operacijama.

Analiza algoritama pokazuje da ako je na većini redaka tablice istinitosti vrijednost funkcije jednaka 0, tada je za dobivanje njene logičke formule bolje konstruirati SDNF, inače - SKNF.

Primjer: Zadana je tablica istinitosti logičke funkcije tri varijable. Izgraditi logična formula provedbu ove funkcije.

Jer u većini redaka tablice istinitosti, vrijednost funkcije je 1, tada konstruiramo SKNF. Kao rezultat, dobivamo sljedeću logičnu formulu:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Provjerimo dobivenu formulu. Da bismo to učinili, napravimo tablicu istinitosti funkcije.

Uspoređujući izvornu tablicu istinitosti i onu izgrađenu za logičku formulu, primjećujemo da su stupci vrijednosti funkcije isti. To znači da je logička funkcija ispravno izgrađena.

Normalan oblik logička formula ne sadrži znakove implikacije, ekvivalencije i negacije neelementarnih formula.

Normalni oblik dolazi u dva oblika:

konjunktivni normalni oblik (CNF)- spoj nekoliko disjunkcija, na primjer, $ \ lijevo (A \ vee \ overline (B) \ vee C \ desno) \ klin \ lijevo (A \ vee C \ desno) $;

disjunktivni normalni oblik (DNF)- disjunkcija nekoliko veznika, na primjer, $ \ lijevo (A \ klin \ precrtaj (B) \ klin C \ desno) \ vee \ lijevo (B \ klin C \ desno) $.

SKNF

Savršena konjunktivna normalna forma (SKNF) je CNF koji zadovoljava tri uvjeta:

ne sadrži identične elementarne disjunkcije;

niti jedna klauzula ne sadrži iste varijable;

svaka elementarna disjunkcija sadrži svaku varijablu iz zadane CNF.

Bilo koja Booleova formula koja nije identično istinita može biti predstavljena u SKNF-u.

Pravila za konstruiranje SKNF-a prema tablici istinitosti

Za svaki skup varijabli za koji je funkcija 0, upisuje se zbroj, a varijable koje imaju vrijednost 1 uzimaju se s negacijom.

SDNF

Savršeni disjunktivni normalni oblik (SDNF) je DNF koji zadovoljava tri uvjeta:

ne sadrži identične elementarne veznike;

niti jedan od veznika ne sadrži iste varijable;

svaka elementarna konjunkcija sadrži svaku varijablu iz danog DNF-a, štoviše, istim redoslijedom.

Bilo koja Booleova formula koja nije identično lažna može biti predstavljena u SDNF-u, štoviše, na jedinstven način.

Pravila za konstruiranje SDNF-a prema tablici istinitosti

Za svaki skup varijabli za koji je funkcija jednaka 1 zapisuje se umnožak, a varijable koje imaju vrijednost 0 uzimaju se s negacijom.

Primjeri pronalaženja SKNF i SDNF

Primjer 1

Napišite logičku funkciju prema njezinoj tablici istinitosti:

Slika 1.

Riješenje:

Koristimo pravilo za konstruiranje SDNF-a:

Slika 2.

Dobijamo SDNF:

Koristimo se pravilom za konstruiranje SKNF-a.

Jednostavan konjunkcija pozvao konjunkcija jedan ili nekoliko varijable, na ovaj svaki varijabla susreće ne više jedan puta (ili sebe, ili nju negacija).

Na primjer, jednostavan je veznik,

Disjunktivni normalan oblik(DNF) pozvao disjunkcija jednostavan veznici.

Na primjer, izraz je DNF.

Savršen disjunktivni normalan oblik(SDNF) pozvao tako disjunktivni normalan oblik, na koji v svaki konjunkcija su uključeni svi varijable dano popis (ili se, ili njihov poricanja), štoviše v jedan i volumen istou redu.

Na primjer, izraz je DNF, ali ne i SDNF. Izraz je SDNF.

Slične definicije (sa zamjenom konjunkcije disjunkcijom i obrnuto) vrijede za CNF i SKNF. Ovdje su točne formulacije.

Jednostavan disjunkcija pozvao disjunkcija jedan ili nekoliko varijable, na ovaj svaki varijabla ulazi ne više jedan puta (ili sebe, ili nju negacija) Na primjer, izraz je jednostavna disjunkcija,

Vezivni normalan oblik(CNF) pozvao konjunkcija jednostavan disjunkcije(na primjer, izraz je CNF).

Savršena konjunktivna normalna forma (SCNF) je CNF u kojoj svaka jednostavna disjunkcija sadrži sve varijable danog popisa (bilo same ili njihove negacije), i to istim redoslijedom.

Na primjer, izraz je SKNF.

Ovdje su algoritmi za prijelaze iz jednog oblika u drugi. Naravno, u određenim slučajevima (uz određeni kreativni pristup) korištenje algoritama je mukotrpnije od jednostavnih transformacija pomoću određene vrste ovog oblika:

a) prijelaz s DNF na CNF

Algoritam za ovaj prijelaz je sljedeći: stavljamo dvije negacije iznad DNF-a i, koristeći de Morganova pravila (bez dodirivanja gornje negacije), vraćamo negaciju DNF-a natrag u DNF. U tom slučaju morate otvoriti zagrade pomoću pravila apsorpcije (ili Blakeovog pravila). Negacija (gornja) dobivenog DNF-a (opet prema de Morganovom pravilu) odmah nam daje CNF:

Imajte na umu da se CNF može dobiti i iz početnog izraza, ako izvadimo na izvan zagrada;

b) prijelaz s CNF na DNF

Ovaj prijelaz se provodi jednostavnim otvaranjem zagrada (u ovom slučaju, opet se koristi pravilo apsorpcije)

Tako smo dobili DNF.

Obrnuti prijelaz (sa SDNF na DNF) povezan je s problemom minimiziranja DNF-a. O tome će se detaljnije govoriti u Pog. 5, ovdje ćemo pokazati kako pojednostaviti DNF (ili SDNF) prema Blakeovom pravilu. Ovaj DNF se zove skraćeno DNF;

c) skraćenica od DNF (ili SDNF) po Pravilo Blake

Primjena ovog pravila ima dva dijela:

Ako među disjunktnim članovima u DNF-u postoje pojmovi , zatim cijeloj disjunkciji dodajemo pojam DO 1 DO 2. Ovu operaciju radimo nekoliko puta (može biti uzastopno, može biti istovremeno) za sve moguće parove pojmova, a zatim primjenjujemo uobičajenu apsorpciju;

Ako je dodani izraz već bio sadržan u DNF-u, tada se može potpuno odbaciti, na primjer,

ili

Naravno, skraćeni DNF nije jednoznačno definiran, ali svi sadrže isti broj slova (npr. postoji DNF , nakon što na njega primijenite Blakeovo pravilo, možete doći do DNF ekvivalenta ovom):

c) prijelaz s DNF na SDNF

Ako nekom jednostavnom vezniku nedostaje varijabla, npr. z, umetnite izraz u njega, a zatim proširite zagrade (u ovom slučaju ne pišemo ponovljene disjunktne pojmove). Na primjer:

d) prijelaz s CNF na SKNF

Ovaj prijelaz se provodi na način sličan prethodnom: ako jednostavnoj disjunkciju nedostaje neka varijabla (npr. z, zatim mu dodamo izraz (ovo ne mijenja samu disjunkciju), nakon čega proširujemo zagrade koristeći zakon distribucije):

Dakle, SKNF se dobiva iz CNF-a.

Imajte na umu da se minimalni ili skraćeni CNF obično dobiva iz odgovarajućeg DNF-a.

Uvedimo pojam elementarne disjunkcije.

Elementarna disjunkcija je izraz oblika

Konjunktivni normalni oblik (CNF) logičke funkcije je konjunkcija bilo kojeg konačnog skupa po paru različitih elementarnih disjunkcija. Na primjer, logičke funkcije

su konjunkcije elementarnih disjunkcija. Stoga se pišu u konjunktivnom normalnom obliku.

Proizvoljna logička funkcija data analitičkim izrazom može se svesti na CNF izvođenjem sljedećih operacija:

Korištenje pravila inverzije ako se operacija negacije primjenjuje na booleov izraz;

Koristeći aksiom distributivnosti s obzirom na množenje:

Korištenje operacije apsorpcije:

Iznimke u disjunkcijama ponovljenih varijabli ili njihovih negacija;

Uklanjanje svih istih elementarnih disjunkcija, osim jedne;

Uklanjanje svih klauzula koje istovremeno uključuju varijablu i njezinu negaciju.

Valjanost navedenih operacija proizlazi iz osnovnih aksioma i identičnih odnosa algebre logike.

Konjunktivni normalni oblik naziva se savršenim ako svaka elementarna disjunkcija uključena u njega sadrži, u izravnom ili inverznom obliku, sve varijable o kojima ovisi funkcija.

Pretvorba CNF-a u savršeni CNF provodi se izvođenjem sljedećih operacija:

Dodaci na svaku elementarnu disjunkciju konjunkcija varijabli i njihove negacije, ako nisu uključeni u ovu elementarnu disjunkciju;

Korištenje aksioma distributivnosti;

Uklanjanje svih identičnih elementarnih disjunkcija, osim jedne.

Bilo koja logička funkcija može biti predstavljena u savršenom CNF, osim

identično jednako jednom(). Posebnost savršenog CNF-a je da je prikaz logičke funkcije u njemu jedinstven.

Elementarne disjunkcije uključene u savršenu CNF funkciju nazivaju se nultim sastojcima. Svaki konstituent nule uključen u savršeni CNF nestaje na jednom skupu vrijednosti varijabli, a to je nulti skup funkcije. Posljedično, broj nulti skupova logičke funkcije poklapa se s brojem nultih konstituenata uključenih u njezin savršeni CNF.

Konstanta logičke funkcije nula u savršenom CNF-u predstavljena je konjunkcionom 2n konstantom nule. Formulirajmo pravilo za sastavljanje SCNF-a logičke funkcije prema tablici korespondencije.

Za svaki red tablice pretraživanja, u kojem je funkcija jednaka nuli, sastavlja se elementarna disjunkcija svih varijabli. U ovom slučaju, sama varijabla je uključena u disjunkciju ako je njezina vrijednost jednaka nuli, ili negacija ako je njezina vrijednost jednaka jedan. Rezultirajuće elementarne disjunkcije objedinjuju se znakom veznika.

Primjer 3.4. Za logičku funkciju z (x), danu korespondentnom tablicom 2.2, definiramo savršeni konjunktivni oblik.

Za prvi red tablice, koji odgovara nultom skupu funkcije 000, nalazimo konstituent nule. Nakon što smo izvršili slične operacije za drugu, treću i petu liniju, definiramo željenu savršenu CNF funkciju:

Treba napomenuti da je za funkcije čiji je broj jediničnih skupova veći od broja nula skupova kompaktnije napisati ih u obliku SKNF-a i obrnuto.

Normalni oblici logičkih funkcija Predstavljanje Booleove funkcije u obliku disjunkcije konjunktivnih članova konstituenata jedinice Ki 2.7 naziva se disjunktivnim normalnim oblikom DNF-a ove funkcije. sadrže točno jednu po jednu sve logičke varijable uzete s negacijama ili bez njih, tada se ovaj oblik prikaza funkcije naziva savršenim disjunktivnim normalnim oblikom SDNF-a ove funkcije. Kao što vidite, prilikom kompajliranja SDNF funkcije morate napraviti disjunkciju svih minterma za koje funkcija poprima vrijednost 1.

Ako vam ovaj rad nije odgovarao na dnu stranice nalazi se popis sličnih radova. Također možete koristiti gumb za pretraživanje

Predavanje 1.xx

Normalni oblici logičkih funkcija

Reprezentacija Booleove funkcije u obliku disjunkcije konjunktivnih pojmova (sastavna jedinica) K i

, (2.7)

pozvao disjunktivni normalni oblik(DNF) ove funkcije.

Ako su svi konjunktivni pojmovi u DNF-u minterms , odnosno sadrže točno jednu po jednu sve logičke varijable, uzete s negativima ili bez njih, tada se ovaj oblik prikaza funkcije nazivasavršena disjunktivna normalna forma(SDNF ) ove funkcije. SDNF se zove savršen jer svaki pojam u disjunkciji uključuje sve varijable; disjunktivni jer je glavna operacija u formuli disjunkcija. Koncept "normalan oblik”Znači nedvosmislen način pisanja formule koja implementira zadanu funkciju.

S obzirom na gore navedeno, teorem 2.1 implicira sljedeći teorem.

Teorem 2. Bilo koja logička funkcija(nije identično jednako 0) može se dostaviti SDNF-u, .

Primjer 3. Neka imamo tablično definiranu funkciju f (x 1, x 2, x 3) (tablica 10).

Tablica 10

Na temelju formule (2.6) dobivamo:

Kao što vidite, prilikom kompajliranja SDNF funkcije morate sastaviti disjunkciju svih minterma za koje funkcija poprima vrijednost 1.

Predstavljanje Booleove funkcije u obliku konjunkcije disjunktivnih pojmova (konstituent nule) D i

, (2.8)

pozvao konjunktivni normalni oblik(CNF) ovu funkciju.

Ako su svi disjunktivni pojmovi CNF makstermas , tj. sadržavati točno jednu sve logičnu funkcijske varijable uzeti sa ili bez negacija, onda se takav CNF nazivasavršeni konjunktiv normalni oblik(SKNF) ovu funkciju.

Teorem 3. Bilo koja logička funkcija(nije jednako identično 1) mogu biti zastupljeni u SKNF-u, štoviše, takav prikaz je jedini.

Dokaz teorema može se provesti slično kao i dokaz teorema 2.1 na temelju sljedeće Shannon leme o konjunktivnoj dekompoziciji.

Shannon-ova lema ... Bilo koja logička funkcija f (x 1, x 2, ..., x m) iz m varijable se mogu predstaviti na sljedeći način:

. (2.9)

Treba napomenuti da su oba oblika predstavljanja logičke funkcije (DNF i CNF) teoretski jednaka u svojim mogućnostima: bilo koja logička formula može biti predstavljena i u DNF (osim identične nule) i u CNF (osim identične jedinice ). Ovisno o situaciji, prikaz funkcije u ovom ili onom obliku može biti kraći.

U praksi se najčešće koristi DNF, budući da je ovaj oblik osobi poznatiji: od djetinjstva je više naviknut na zbrajanje djela nego na množenje zbroja (u potonji slučaj on intuitivno ima želju otvoriti zagrade i tako otići na DNF).

Primjer 4. Za funkciju f (x 1, x 2, x 3 ) dano tablicom. 10, napišite to u SKNF.

Za razliku od SDNF-a, prilikom sastavljanja SCNF-a u tablici istinitosti logičke funkcije, morate pogledati kombinacije varijabli za koje funkcija uzima vrijednost 0 i sastaviti konjukciju odgovarajućih maksimalnih pojmova,ali se varijable moraju uzeti s obrnutom inverzijom:

Treba napomenuti da je nemoguće prijeći izravno s funkcije SDNF na njen SKNF ili obrnuto. Pokušaj takvih transformacija rezultira inverznim funkcijama od željenih. Izrazi za SDNF i SKNF funkcije mogu se izravno dobiti samo iz njegove tablice istinitosti.

Primjer 5. Za funkciju f (x 1, x 2, x 3 ) dano tablicom. 10, pokušajte prijeći sa SDNF na SKNF.

Koristeći rezultat primjera 2.3, dobivamo:

Kao što možete vidjeti, pod općom inverzijom, dobiva se SKNF logičke funkcije, koja je inverzna u odnosu na funkciju dobivenu u primjeru 2.4:

budući da sadrži sve maxterme koji nisu u izrazu za SKNF funkcije koja se razmatra.

1. Koristeći svojstva operacija (vidi tablicu 9) identitet (), zbroj po modulu 2 (), implikacija (), prelazimo na operacije I, ILI, NOT (u Booleovoj bazi).

2. Koristeći svojstva negacije i de Morganove zakone (vidi tablicu 9), postižemo da se operacije negacije odnose samo na pojedinačne varijable, a ne na cijele izraze.

3. Koristeći svojstva logičkih operacija AND i OR (vidi tablicu 9), dobivamo normalni oblik (DNF ili CNF).

4. Ako je potrebno, prijeđite na savršene oblike (SDNF ili SKNF). Na primjer, da biste dobili SKNF, često morate koristiti svojstvo:.

Primjer 6. Pretvori Booleovu funkciju u SKNF

Provodeći redom korake gornjeg algoritma, dobivamo:

Koristeći svojstvo apsorpcije, dobivamo:

Tako smo dobili CNF funkcije f (x 1, x 2, x 3 ). Da biste dobili njegov SKNF, trebate ponoviti svaku disjunkciju, kojoj nedostaje bilo koja varijabla, dvaput - s ovom varijablom i s njenom negacijom:

2.2.6. Minimiziranje Booleovih funkcija

Budući da se ista logička funkcija može predstaviti kao s osobne formule, zatim pronalaženje najjednostavnijeg fo R mule, koji definira Booleovu funkciju, pojednostavljuje logički sklop koji implementira Booleovu funkciju. do cije. Minimalni oblik l O geološka funkcijau nekoj bazi, možemo pretpostaviti da sadrži minimalni broj superpozicija funkcije Do osnovu, uključujući zagrade. Međutim, teško je izgraditi učinkovit a l algoritam za takvu minimizaciju s dobivanjem minimalne zagrade r mi.

Razmotrimo jednostavniji problem minimizacije u sintezi kombinacijskih sklopova, u kojem se ne traži oblik minimalne zagrade funkcije, već njezin minimalni DNF. Za ovaj zadatak postoje jednostavni, učinkoviti algoritmi.

Quineova metoda

Funkcija koju treba minimizirati predstavljena je u SDNF-u i na nju se primjenjuju sve moguće operacije nepotpunog lijepljenja

, (2.10)

a zatim apsorpcija

, (2.11)

a ovaj se par koraka primjenjuje više puta. Tako je moguće sniziti rang pojmova. Ovaj postupak se ponavlja sve dok ne ostane termin koji se može zalijepiti za bilo koji drugi pojam.

primijeti da lijeva strana Jednadžbe (2.10) mogu se odmah minimizirati na jednostavniji i očitiji način:

Ova metoda je loša po tome što s takvom izravnom minimiziranjem konjunktivni pojmovi ili nestaju, iako još uvijek postoje slučajevi njihove upotrebe za lijepljenje i upijanje s preostalim pojmovima.

Valja napomenuti da je Quineova metoda dosta dugotrajna, pa je vjerojatnost pogreške tijekom transformacija prilično velika. Ali njegova je prednost u tome što se u teoriji može koristiti za bilo koji broj argumenata, a kako se broj varijabli povećava, pretvorbe postaju manje komplicirane.

Karnaughova metoda karte

Metoda Karnaughovih karata (tablica) je vizualniji, manje dugotrajan i pouzdan način minimiziranja logičkih funkcija, ali je njezina uporaba praktički ograničena na funkcije od 3-4 varijable, maksimalno - 5-6 varijabli.

Carnotova karta Je dvodimenzionalni tablični oblik predstavljanja tablice istinitosti Booleove funkcije, koji vam omogućuje da lako pronađete minimalni DNF logičkih funkcija u grafičkom vizualnom obliku. Svaka ćelija tablice povezana je s mintermom SDNF funkcije koju treba minimizirati, tako da bilo koja os simetrije tablice odgovara zonama koje su međusobno inverzne u bilo kojoj varijabli. Ovakav raspored ćelija u tablici olakšava određivanje SDNF pojmova lijepljenja (koji se razlikuju po predznaku inverzije samo jedne varijable): oni su raspoređeni simetrično u tablici.

Tablice istine i Karnotove karte za AND i OR funkcije za dvije trake e varijable su prikazane na sl. 8. U svakoj ćeliji kartice upisan je znak a funkcija na argumentu koji odgovara ovoj ćeliji n Druže

A) I b) ILI

Riža. osam. Primjer Karnotovih mapa za funkcije dviju varijabli

U Karnotovoj karti postoji samo jedna 1 za funkciju I, tako da se ne može zalijepiti ni na što. Izraz za minimalnu funkciju sadržavat će samo izraz koji odgovara ovoj 1:

f = x y.

U Karnot karti za funkciju OR već postoje tri 1 i moguće je napraviti dva para lijepljenja, pri čemu 1 odgovara pojmu xy , koristi se dva puta. U izraz za minimalnu funkciju potrebno je napisati pojmove za parove koji se lijepe, ostavljajući u njima sve varijable koje se ne mijenjaju za ovaj par, a uklanjajući varijable koje mijenjaju svoju vrijednost. Za horizontalno lijepljenje dobivamo x , a za okomite - y , kao rezultat dobivamo izraz

f = x + y.

Na sl. 9 prikazuje tablice istinitosti dviju funkcija tri varijable ( a ) i njihove Karnot karte ( b i c). Funkcija f 2 razlikuje se od prvog po tome što nije definiran na tri skupa varijabli (to je označeno crticom u tablici).

Prilikom određivanja minimalnog DNF-a funkcije koriste se sljedeća pravila. Sve stanice koje sadrže 1 kombiniraju se u zatvorena pravokutna područja koja se nazivaju k -kocke, gdje je k = log 2 K, K - količina 1 u pravokutnom području. Štoviše, svako područje treba biti pravokutnik s 2 ćelije k, gdje je k = 0, 1, 2, 3,…. Za k = 1 pravokutnik se zove jedan je kocka i sadrži 2 1 = 2 jedinice; za k = 2 pravokutnik sadrži 2 2 = 4 jedinice i zove se dvije kocke; za k = 3 područje od 2 3 = 8 jedinica se zove trokockasti ; i tako dalje.Mogu se pozvati jedinice koje se ne mogu kombinirati u pravokutnike nula kocke koji sadrže samo jednu jedinicu (2 0 = 1). Kao što vidite, s čak k područja mogu biti kvadratna (ali nije neophodna) i za neparna k - samo pravokutnici.

Riža. devet. Primjer Karnotovih mapa za funkcije tri varijable

Ta se područja mogu preklapati, odnosno mogu ući iste stanice različitim područjima... Tada se minimalni DNF funkcije zapisuje kao disjunkcija svih konjunktivnih članova koji odgovaraju k - kocke.

Svaka od navedenih regija na Karnot karti je u minimalnom DNF-u predstavljena konjunkcijom, broj argumenata u kojoj je k manji od ukupnog broja argumenata funkcije m , odnosno ovaj broj je jednak m - k ... Svaka konjunkcija minimalnog DNF-a sastoji se samo od onih argumenata koji za odgovarajuće područje karte imaju vrijednosti ili bez inverzija, ili samo s inverzijama, odnosno ne mijenjaju svoje vrijednosti.

Dakle, kada se ćelije karte prekrivaju zatvorenim područjima, treba nastojati osigurati da broj područja bude minimalan, a da svako područje sadrži najveći mogući broj ćelija, jer će u tom slučaju broj članova u minimalnom DNF-u biti minimalan i broj argumenata u odgovarajućoj konjunkciji bit će minimalan.

Za funkciju Karnot karte na sl. devet, pronašli smo

budući da za gornje zatvoreno područje varijable x 1 i x 2 materija bez inverzija, za niže x 1 stvari s inverzijom, i x 3 - nema inverzije.

Nedefinirane vrijednosti na karti na Sl. devet, v može se proširiti zamjenom s nulom ili jedinicom. Za ovu funkciju se može vidjeti da je povoljnije obje nedefinirane vrijednosti zamijeniti s 1. U tom slučaju se formiraju dvije regije koje su različite vrste 2 kocke. Tada će izraz za minimalnu DNF funkciju biti sljedeći:

Prilikom konstruiranja zatvorenih područja, dopušteno je sažimanje Karnaughove karte u cilindar i horizontalno i okomito. R tičke osi sa spojem suprotnih bridova R vi, odnosno jedinice koje se nalaze na rubovima Carnotove karte simetrije h ali, mogu se i kombinirati.

Karnaughove karte mogu se crtati na različite načine (slika 10).

a b

Riža. deset. Različiti načini crtanja Karnaughovih karata
za funkciju od 3 varijable

Ali najprikladnije varijante Karnotovih karata za funkcije 2-4 varijable prikazane su na Sl. 11 tablica, jer se za svaku ćeliju prikazuju a sve varijable su u izravnom ili inverznom obliku.

a b

Riža. jedanaest. Najprikladnija slika Karnot karata
za funkcije 3 ( a) i 4 (b) varijable

Za funkcije od 5 i 6 varijabli, metoda prikazana na Sl. deset, v.

Riža. 12. Slika Karnotove karte za funkciju od 5 varijabli

Riža. 13. Slika Karnotove karte za funkciju od 6 varijabli