Disjunktivni i konjunktivni normalni oblici propozicione algebre. Za svaku funkciju propozicijske logike može se sastaviti tabela istinitosti. Inverzni problem je također uvijek rješiv. Hajde da uvedemo nekoliko definicija.
Elementarni veznici (konjunkti) nazivaju se konjunkcije varijabli ili njihove negacije, u kojima se svaka varijabla javlja najviše
jednom.
Disjunktivni normalni oblik(DNF) je formula koja ima oblik disjunkcije elementarnih konjunkcija.
Elementarne disjunkcije (po klauzulama) nazivaju se disjunkcije varijabli sa ili bez negacija.
Konjunktivna normalna forma(CNF) je formula koja ima oblik konjunkcije elementarnih disjunkcija.
Za svaku funkciju propozicione algebre može se pronaći skup disjunktivnih i konjunktivnih normalnih oblika.
DNF konstrukcijski algoritam:
1. Idite na Bulove operacije koristeći ekvivalentne formule transformacije.
2. Idite na formule sa bliskim negativima, odnosno na formulu u kojoj se negativi nalaze ne više nego iznad varijabli - primijenite de Morganove zakone.
3. Otvorite zagrade - primijenite zakone distributivnosti.
4. Ponavljanje termina uzeti jedno vrijeme - zakon idempotencije.
5. Primijenite zakone apsorpcije i poluapsorpcije.
Primjer 6 Pronađite DNF formule: .
U Boole algebri, princip dualnosti. To je kako slijedi.
Funkcija se poziva dual na funkciju ako . One. da bismo pronašli funkciju dualnu datoj, potrebno je konstruisati negaciju funkcije iz negacija argumenata.
Primjer 7 Pronađite funkciju dualnu .
Među elementarne funkcije algebra logike 1 je dualna prema 0 i obrnuto, x je dualna prema x, dualna je prema , dualna je prema i obrnuto.
Ako se u formuli F 1 koja predstavlja funkciju zamjenjuju svi konjunkcije
na disjunkciju, disjunkciju na konjunkciju, 1 na 0, 0 na 1, tada dobijamo formulu F *, koja predstavlja funkciju *, dual.
Konjunktivni normalni oblik (CNF) je dvostruki koncept za DNF, tako da se može lako konstruirati prema shemi:
Primjer 8 Pronađite CNF formule: .
Koristeći rezultat primjera 6, imamo
Savršeni disjunktivni i savršeni konjunktivni normalni oblici. U svakom od tipova normalnih oblika (disjunktivni i konjunktivni) može se izdvojiti klasa savršenih oblika SDNF i SKNF.
Savršena elementarna konjunkcija je logički proizvod svih varijabli sa ili bez negacije, a svaka varijabla je uključena u proizvod samo jednom.
Bilo koji DNF se može svesti na SDNF cijepanjem konjukcija koje ne sadrže sve varijable, tj. sabirak za promenljivu koja nedostaje x i množi se korišćenjem zakona distributivnosti
Primjer 9 Pronađite SDNF za DNF primjer 6
Savršena elementarna disjunkcija poziva se logički zbir svih varijabli sa ili bez negacija, štoviše, svaka varijabla je uključena u zbir samo jednom.
Bilo koji CNF se može svesti na SKNF dodavanjem vezničkog termina koji ne sadrži nijednu varijablu X i konjunkcijom i primjenom distributivnog zakona
Primjer 10. Pretvorite CNF u SKNF:
Da biste konstruirali SKNF, možete koristiti shemu
Primjer 11. Pronađite SKNF za formulu primjera 6.
Svaka funkcija ima SDNF i, osim toga, jedinu. Svaka funkcija ima SKNF i, osim toga, jedan .
Jer SDNF i SKNF su jedinstveno definisani formulama, mogu se graditi prema tabeli istinitosti formule.
Za konstruiranje SDNF-a potrebno je odabrati redove u kojima F uzima vrijednost 1 i za njih zapisati savršene elementarne konjunkcije. Ako je vrijednost varijable u željenom redu tablice istinitosti jednaka jedan, tada se u savršenoj konjunkciji uzima bez negacije, ako je nula, onda s negacijom. Tada se savršeni konjunkti (njihov broj je jednak broju jedinica u tabeli) povezuju znakovima disjunkcije.
Za izgradnju SKNF-a prema tabeli istinitosti potrebno je u njoj odabrati redove, gdje je F=0, i zapisati savršene elementarne disjunkcije, a zatim ih povezati znakovima konjunkcije. Ako u traženom redu tablice istinitosti (F=0) vrijednost varijable odgovara nuli, onda se u savršenom disjunktu uzima bez negacije, ako je jednaka jedan, onda sa negacijom.
Primjer 12. Pronađite SDNF i SKNF prema tabeli istinitosti za formulu primjera 6.
Tabela 14 prikazuje samo konačnu vrijednost F=10101101. Valjanost ove izjave treba provjeriti nezavisno konstruiranjem proširene tablice istinitosti.
Tabela 14
| x | y | z | ||
Primjer. Pronađite CNF formule 
~ 
~
Savršeni disjunktivni normalni oblik SDNF-a može se konstruirati korištenjem sljedećeg algoritma:
1. = 1. DNF algoritam
2. = 2. DNF algoritam
3. = 3. DNF algoritam
4. = 4. DNF algoritam
5. Izostavite identično lažne termine, tj. termine obrasca
6. Popunite preostale pojmove varijablama koje nedostaju
7. Ponovite tačku 4.
Primjer. Pronađite sdnf formule.
~
Sljedeća shema se može koristiti za konstruiranje SKNF-a:
Primjer. Pronađite sdnf formule.
~
Poznato je (teoreme 2.11, 2.12) da su SDNF i SKNF jednoznačno definisani formulom i stoga se mogu izgraditi prema tabeli istinitosti formule .
Šema za konstruisanje SDNF i SKNF prema tabeli istinitosti data je u nastavku, za formulu ~ :
 ~
| ||||
| 1 0 1 0 1 1 0 1 | SDNF; SKNF. |
2.2. Vježbajte.
2.2.1 Ispod su logički izrazi. Pojednostavite izraze svoje opcije što je više moguće koristeći Booleove zakone logike. Zatim, koristeći tablice istinitosti, uporedite svoj pojednostavljeni izraz sa originalnim.
2.2.2. Otkrijte pitanje ekvivalentnosti f 1 i f 2 tako što ćete ih svesti na SDNF (tabela 1).
2.2.3. Naći dualnu funkciju za f 3 prema generaliziranom i Bulovom principu (Tablica 1). Uporedite rezultate.
| № | f1 | f2 | f 3 |
 | |||
 |
|||
 | |||
 | |||
 | |||
 |  |
||
 |  |
||
 |
|||
 | |||
 | |||
 |
|||
 | |||
 |  |
||
 | |||
 |
2.3. Kontrolna pitanja.
2.3.1. Definirajte izjavu.
2.3.2. Navedite osnovne operacije na iskazu.
2.3.3. Šta je tabela istine?
2.3.4. Napravite tablice istinitosti za sljedeće formule:
~ ~ 
~ ;
2.3.5. Uzimajući u obzir konvencije o redoslijedu operacija, izostavite "dodatne" zagrade i znak "" u formulama:
;
2.3.6. Primjenjujući ekvivalentne transformacije, dokazati identičnu istinitost formula:
2.3.7. Pronađite dvojne formule:
)
2.3.8. Smanjite sljedeće formule na savršeni DNF (SDNF) oblik:
~
2.3.9. Pretvorite sljedeće formule u savršeni CNF (SKNF) oblik:
~
Predmet:“Minimizacija Booleovih funkcija. Logika"
Cilj: Stjecanje praktičnih vještina u radu sa metodama za minimiziranje Bulovih funkcija.
3.1. Teorijske informacije.
Minimalni oblici
Kao što je prikazano u , bilo koja Booleova funkcija može biti predstavljena u savršenom normalnom obliku (disjunktivna ili konjunktivna). Štaviše, takva reprezentacija je prvi korak u tranziciji od tabelarne definicije funkcije ka njenom analitičkom izrazu. U nastavku ćemo poći od disjunktivnog oblika i odgovarajućih rezultata za konjunktivni oblik dobijena na osnovu principa dualnosti.
Kanonski problem sinteze logičkih kola u Booleovoj bazi svodi se na minimiziranje Bulovih funkcija, tj. da ih predstavimo u disjunktivnom normalnom obliku, koji sadrži najmanji broj slova (varijable i njihove negacije). Takvi oblici se nazivaju minimalnim. U kanonskoj sintezi, pretpostavlja se da se oba signala i njihove inverzije unose na ulaze kola.
Formula predstavljena u disjunktivnom normalnom obliku je pojednostavljena ponovljenom primjenom operacije lijepljenja i operacije apsorpcije i (dvostruki identiteti za konjunktivni normalni oblik su: i ). Ovdje se može razumjeti bilo koja formula Bulove algebre. Kao rezultat, dolazimo do takvog analitičkog izraza kada dalje transformacije više nisu moguće, tj. dobijamo ćorsokak.
Među oblicima ćorsokaka postoji i minimalni disjunktivni oblik, koji možda nije jedinstven. Da biste bili sigurni da je ovaj oblik slijepe ulice minimalan, morate pronaći sve oblike slijepe ulice i uporediti ih prema broju slova koje sadrže.
Neka je, na primjer, funkcija data u savršeno normalnom disjunktivnom obliku:
Grupiranjem članova i primjenom operacije lijepljenja imamo .
Sa drugom metodom grupisanja dobijamo:
Oba oblika slijepe ulice nisu minimalna. Da biste dobili minimalni oblik, morate pogoditi da ponovite jedan pojam u originalnoj formuli (ovo se uvijek može učiniti, budući da). U prvom slučaju, takav član može biti . Onda . Dodavanjem pojma dobijamo: . Nakon što prođemo kroz sve moguće opcije, možemo se uvjeriti da su posljednja dva oblika minimalna.
Rad sa formulama na ovom nivou je kao lutanje u mraku. Proces traženja minimalnih formi postaje vizualniji i svrsishodniji ako se koriste neki grafički i analitički prikazi i simboli posebno dizajnirani za tu svrhu.
Višedimenzionalna kocka
Svakom vrhu -dimenzionalne kocke može se dodijeliti jedinični konstituent. Prema tome, podskup označenih vrhova je preslikavanje na -dimenzionalnu kocku Bulove funkcije varijabli u savršenom disjunktivnom normalnom obliku. Na sl. 3.1 prikazuje takvo preslikavanje za funkciju iz odjeljka 3.7.
Slika 3.1 Prikaz na trodimenzionalnoj kocki funkcije predstavljene u SDNF-u
Da bi se prikazala funkcija varijabli predstavljenih u bilo kojem disjunktivnom normalnom obliku, potrebno je uspostaviti korespondenciju između njenih miniterma i elemenata -dimenzionalne kocke.
Miniterm (-1) ranga može se smatrati rezultatom lijepljenja dva miniterma -tog ranga (jediničnog konstituenta), tj. 
, Na -dimenzionalnoj kocki, to odgovara zamjeni dva vrha, koji se razlikuju samo po vrijednostima koordinata koje povezuju ove vrhove, s ivicom (rečeno je da rub pokriva vrhove koji su mu incidentni). Dakle, minitermmi reda (-1) odgovaraju ivicama -dimenzionalne kocke. Slično, minitermmi (-2)-tog reda odgovaraju plohama -dimenzionalne kocke, od kojih svaka pokriva četiri vrha (i četiri ivice).
Elementi -dimenzionalne kocke karakterizirani dimenzijama nazivaju se -kocke. Dakle, vrhovi su 0-kocke, ivice su 1-kocke, lica su 2-kocke, itd. Generalizirajući gornje rezonovanje, možemo pretpostaviti da je miniterm ()-tog ranga u disjunktivnom normalnom obliku za funkciju varijabli preslikan pomoću -kocke, a svaka -kocka pokriva sve one -kocke najniže dimenzije koje su povezana sa njegovim vrhovima. Kao primjer, na sl. 3.2 prikazuje mapiranje funkcije tri varijable. Ovdje minitermi i odgovaraju 1-kockama (), a minitermi su predstavljeni sa 2-kockama ().
Sl.3.2 Pokrivenost funkcija 
Dakle, bilo koja disjunktivna normalna forma je prikazana na -dimenzionalnoj kocki skupom -kocki koje pokrivaju sve vrhove koji odgovaraju jediničnim konstituentima (0-kocka). Obrnuta tvrdnja je također istinita: ako određena kolekcija -kocki pokriva skup svih vrhova koji odgovaraju jediničnim vrijednostima funkcije, tada je disjunkcija miniterma koji odgovaraju tim -kockama izraz ove funkcije u disjunktivnom normalnom obliku . Kaže se da takva kolekcija -kocki (ili njima odgovarajućih miniterma) čini pokrivanje funkcije.
Želja za minimalnom formom intuitivno je shvaćena kao potraga za takvim poklopcem čiji bi broj -kocki bio manji, a dimenzije veće. Poklopac koji odgovara minimalnom obliku naziva se minimalni poklopac. Na primjer, za funkciju pokrivenosti na sl. 3.3 odgovara minimalnim obrascima 
I 
.
Rice. 3.3 Pokrivenosti funkcija.
lijevo – ; desno –
Prikaz funkcije na -dimenzionalnoj kocki je jasan i jednostavan kada . Četvorodimenzionalna kocka se može nacrtati kao što je prikazano na sl. 3.4, koji prikazuje funkciju od četiri varijable i njenu minimalnu pokrivenost koja odgovara izrazu 
. Upotreba ove metode zahtijeva tako složene konstrukcije da se gube sve njene prednosti.
Rice. 3.4 Prikaz funkcija na četvorodimenzionalnoj kocki
Karnot karte
Koristi se još jedna metoda za crtanje logičkih funkcija Carnot karte, koje su posebno organizirane tabele pretraživanja. Stupci i redovi tabele odgovaraju svim mogućim skupovima vrijednosti ne više od dvije varijable, a ti skupovi su raspoređeni tako da se svaki sljedeći skup razlikuje od prethodnog po vrijednosti samo jedne od varijabli . Zbog toga se susjedne ćelije tabele i horizontalno i vertikalno razlikuju u vrijednosti samo jedne varijable. Ćelije koje se nalaze na rubovima stola također se smatraju susjednim i imaju ovo svojstvo. Na sl. 3.5 prikazuje Karnaughove karte za dvije, tri, četiri varijable.
 |
|||||
 |
|||||
 |
|||||
Rice. 3.5 Karnot karte za dvije, tri i četiri varijable
Kao iu običnim tablicama istinitosti, ćelije skupova na kojima funkcija poprima vrijednost 1 ispunjene su jedinicama (nule obično se ne uklapaju, one odgovaraju praznim ćelijama). Na primjer, na sl. 3.6, A prikazuje Karnaughovu kartu za funkciju, čiji je prikaz na četverodimenzionalnoj kocki dat na sl. 3.4. Radi pojednostavljenja, redovi i stupci koji odgovaraju vrijednostima 1 za neku varijablu istaknuti su vitičastom zagradom s oznakom ove varijable.
 |
|||
 |
|||
Rice. 3.6 Karnotov grafikon prikaz funkcije četiri varijable
(a) i njegovu minimalnu pokrivenost (b)
Između mapiranja funkcija uključeno n-dimenzionalna kocka i na Karnaugh mapi postoji korespondencija jedan-na-jedan. Na karti Carnota s-kocka odgovara skupu od 2 susjedne ćelije postavljene u red, stupac, kvadrat ili pravougaonik (uzimajući u obzir blizinu suprotnih rubova karte). Dakle, sve odredbe navedene u prethodnom tekstu (vidi stav višedimenzionalna kocka) vrijede za Carnot karte. Dakle, na sl. 3.6, b pokrivenost jedinica karte je prikazana u skladu sa minimalnom disjunktivnom formom 
dotičnu funkciju.
Očitavanje miniterma sa Karnoove kartice vrši jednostavno pravilo. Ćelije koje se formiraju s-kocka, daj miniter (n–s) rang, koji uključuje one (n–s) varijable koje zadržavaju iste vrijednosti na ovome s-cube, pri čemu vrijednost 1 odgovara samim varijablama, a vrijednost 0 odgovara njihovim negacijama. Varijable koje ne zadržavaju svoje vrijednosti na s-kocka, nema u minitermu. Različiti načini čitanja dovode do različitih prikaza funkcije u disjunktivnom normalnom obliku (najdesniji je minimalan) (slika 3.7).
 |  |
||||||||
 |
|||||||||
Upotreba Karnaughovih karata zahtijeva jednostavnije konstrukcije u odnosu na prikaz na n-dimenzionalna kocka, posebno u slučaju četiri varijable. Za prikaz funkcija pet varijabli koriste se dvije Karnotove karte za četiri varijable, a za funkciju od šest varijabli koriste se četiri takve karte. Daljnjim povećanjem broja varijabli, Karnot karte postaju praktički neupotrebljive.
Poznat u književnosti Veitchove karte razlikuju se samo u drugačijem redoslijedu skupova vrijednosti varijabli i imaju ista svojstva kao Karnaughove karte.
Kompleks kocki
Neuspjeh grafičkih metoda kod veliki brojevi varijable se kompenzira različitim analitičkim metodama za predstavljanje Bulovih funkcija. Jedna od ovih reprezentacija je kompleks kocki, koji koristi terminologiju višedimenzionalnog logičkog prostora u kombinaciji sa posebno dizajniranom simbolikom.
). 0-kocke koje odgovaraju konstituentima jedinice su predstavljene skupovima varijabilnih vrijednosti na kojima je funkcija jednaka jedinici. Očigledno u zapisniku
Rice. 3.8 Kompleks kocki funkcija tri varijable ( A) i njegov simbolički prikaz ( b)
Formira se kompleks kocki maksimalna pokrivenost funkcijama. Isključujući sve to s-kocke koje su prekrivene kockama veće dimenzije, dobijamo obloge koje odgovaraju ćorsokacima. Dakle, za primjer koji se razmatra (slika 3.8), imamo poklopac slijepe ulice
,
što odgovara funkciji 
. U ovom slučaju i ovo pokriće je minimalno.
Za dvije Booleove funkcije, operacija disjunkcije odgovara uniji njihovih kompleksa kocke, a operacija konjukcije presjeku njihovih kompleksa kocke. Negacija funkcije odgovara sabiranju kompleksa kocki, tj. i određena je svim vrhovima na kojima funkcija poprima vrijednost 0. Dakle, postoji korespondencija jedan prema jedan (izomorfizam) između algebre Bulove funkcije i Boolean skupovi koji predstavljaju komplekse kocki.
Reprezentacija funkcije u obliku kompleksa kocki je manje vizualna, ali njene najvažnije prednosti su što su uklonjena ograničenja broja varijabli i olakšano kodiranje informacija pri korištenju računala.
Minimiziranje logičkih funkcija
Formulacija problema. Minimizacija šeme u Booleovoj bazi svodi se na pronalaženje minimalnog disjunktivnog oblika, koji odgovara minimalnom pokrivanju. Ukupan broj pisama uključenih u normalnu formu izražen je troškom pokrivenosti 
, gdje je broj - kocki koje čine pokrivenost date funkcije u n varijabli. Minimalno pokriće karakteriše najniža vrijednost njegove cijene.
Obično se problem minimizacije rješava u dva koraka. Prvo se traži smanjeni poklopac koji uključuje sve -kocke maksimalne dimenzije, ali ne sadrži nijednu kocku pokrivenu nijednom kockom ovog poklopca. Odgovarajući disjunktivni normalni oblik naziva se reduciran, a njegovi minitermmi se nazivaju jednostavnim implikantima. Za ovu funkciju, smanjena pokrivenost je jedina, ali može biti suvišna zbog činjenice da su neke kocke pokrivene kolekcijama drugih kocki.
U drugom koraku vrši se prijelaz sa reduciranih na ćorsokak disjunktivne normalne forme, od kojih se biraju minimalni oblici. Slijepi oblici se formiraju isključivanjem svih redundantnih kocki iz smanjene pokrivenosti, bez čega preostali skup kocki i dalje čini pokrivenost date funkcije, ali uz daljnje isključivanje bilo koje od kocki, više ne pokriva skup svih vrhova koji odgovaraju jediničnim vrijednostima funkcije, tj. prestaje biti pokrivenost .
Smanjena pokrovna kocka koja pokriva vrhove date funkcije koji nisu pokriveni nijednom drugom kockom ne može biti redundantna i uvijek će biti uključena u minimalno pokrivanje. Takva kocka, kao i implikant koji joj odgovara, naziva se ekstremal (esencijalni implikant), a vrhovi pokriveni njom nazivaju se poništeni vrhovi. Skup ekstremala čini srž pokrivenosti, jasno je da pri prelasku sa smanjene pokrivenosti na minimalnu, prije svega, treba odabrati sve ekstreme. Ako skup ekstremala ne tvori poklopac, onda se on dopunjuje kockama iz reduciranog omotača.
Date definicije su ilustrovane na sl. 3.9, gdje je smanjena pokrivenost (vidi sliku 3.9a, ) a minimalne pokrivenosti (slika 3.9b) i (vidi sliku 3.9b) su izražene na sljedeći način.
Definicija 1.Konjunktivni monom (elementarna konjunkcija) iz varijabli naziva se konjunkcija ovih varijabli ili njihove negacije.
Na primjer, je elementarna konjunkcija.
Definicija 2.Disjunktivni monom (elementarna disjunkcija) od varijabli naziva se disjunkcija ovih varijabli ili njihove negacije.
Na primjer, je elementarna disjunkcija.
Definicija 3. Formula koja je ekvivalentna datoj formuli propozicionalne algebre i koja je disjunkcija elementarnih konjunktivnih monoma naziva se disjunktivni normalni oblik(DNF) ove formule.
Na primjer,- DNF.
Definicija 4. Formula koja je ekvivalentna datoj formuli propozicionalne algebre i koja je konjunkcija elementarnih disjunktivnih monoma naziva se konjunktivni normalni oblik(CNF) ove formule.
Na primjer, – KNF.
Za svaku formulu propozicione algebre može se pronaći skup disjunktivnih i konjunktivnih normalnih oblika.
Algoritam za konstruisanje normalnih oblika
Koristeći ekvivalencije algebre logike, zamijenite sve operacije u formuli glavnim: konjunkcija, disjunkcija, negacija:
Riješite se dvostrukih negativa.
Primijenite, ako je potrebno, na operacije konjunkcije i disjunkcije svojstva distributivnosti i formule apsorpcije.
2.6. Savršeni disjunktivni i savršeni konjunktivni normalni oblici
Bilo koja Booleova funkcija može imati mnogo DNF i CNF reprezentacija. Posebno mjesto među ovim prikazima zauzimaju savršeni DNF (SDNF) i savršeni CNF (SKNF).
Definicija 1. Savršena disjunktivna normalna forma(SDNF) je DNF u kojem svaki konjunktivni monom sadrži svaku promjenljivu iz skupa točno jednom, a ulazi ili sam ili njegova negacija.
Strukturno, SDNF za svaku formulu propozicionalne algebre svedene na DNF može se definirati na sljedeći način:
Definicija 2. Savršena disjunktivna normalna forma(SDNF) formule propozicionalne algebre naziva se njen DNF, koja ima sljedeća svojstva:
Definicija 3. Savršena konjunktivna normalna forma(SKNF) je CNF u kojem svaki disjunktivni monom sadrži svaku varijablu iz skupa tačno jednom, i ulazi ili sam ili njegova negacija.
Strukturno, SKNF za svaku formulu propozicionalne algebre redukovane na CNF može se definirati na sljedeći način.
Definicija 4. Savršena konjunktivna normalna forma(SKNF) date formule propozicione algebre je njen CNF, koji zadovoljava sljedeća svojstva.
Teorema 1. Svaka Booleova funkcija varijabli koja nije identično lažna može biti predstavljena u SDNF, i štaviše, na jedinstven način.
Načini pronalaženja SDNF-a
1. način
2nd way
odaberite linije u kojima formula uzima vrijednost 1;
pravimo disjunkciju konjunkcija, pod uslovom da ako je varijabla uključena u konjunkciju sa vrijednošću 1, onda pišemo ovu varijablu, ako je sa vrijednošću 0, onda njenu negaciju. Dobijamo SDNF.
Teorema 2. Svaka Booleova funkcija varijabli koja nije identično istinita može biti predstavljena u SKNF-u, i štaviše, na jedinstven način.
Načini za pronalaženje SKNF-a
1. način– uz pomoć ekvivalentnih transformacija:
2nd way- korištenjem tablica istinitosti:
odaberite linije u kojima formula uzima vrijednost 0;
sastavljamo konjunkciju disjunkcija, pod uslovom da ako je promenljiva uključena u disjunkciju sa vrednošću 0, onda pišemo ovu promenljivu, ako je vrednost 1, onda njenu negaciju. Dobijamo SKNF.
Primjer 1 Iscrtajte CNF funkcije.
Rješenje
Uklonite vezu "" koristeći zakone transformacije varijabli:
= /de Morganovi zakoni i dvostruka negacija/ =
/distributivni zakoni/ =
Primjer 2 Pretvorite formulu u DNF.
Rješenje
Logičke operacije izražavamo u terminima i:
= /Povežite negaciju sa varijablama i smanjite dvostruke negacije/ =
= /zakon distribucije/ .
Primjer 3 Napišite formulu u DNF i SDNF.
Rješenje
Koristeći zakone logike, ovu formulu svodimo na oblik koji sadrži samo disjunkcije elementarnih konjunkcija. Rezultirajuća formula će biti željeni DNF:
Da bismo napravili SDNF, sastavit ćemo tabelu istinitosti za ovu formulu:
Označavamo one redove tabele u kojima formula (posljednja kolona) uzima vrijednost 1. Za svaki takav red ispisujemo formulu koja je istinita na skupu varijabli ,, ovog reda:
red 1: ;
red 3: ;
red 5: .
Disjunkcija ove tri formule će poprimiti vrijednost 1 samo na skupovima varijabli u redovima 1, 3, 5, i stoga će biti traženi savršeni disjunktivni normalni oblik (PDNF):
Primjer 4 Donesite formulu u SKNF na dva načina:
a) uz pomoć ekvivalentnih transformacija;
b) korištenjem tablice istinitosti.
Rješenje:
Transformiramo drugu elementarnu disjunkciju:
Formula izgleda ovako:
b) sastavite tabelu istinitosti za ovu formulu:
Označavamo one redove tabele u kojima formula (posljednja kolona) uzima vrijednost 0. Za svaki takav red ispisujemo formulu koja je istinita na skupu varijabli ,, ovog reda:
red 2: ;
red 6: .
Konjunkcija ove dvije formule poprimiće vrijednost 0 samo na skupovima varijabli u redovima 2 i 6, te će stoga biti željeni savršeni konjunktivni normalni oblik (CKNF):
Pitanja i zadaci za samostalno rješavanje
1. Koristeći ekvivalentne transformacije, donesite formule u DNF:
2. Koristeći ekvivalentne transformacije, donesite formule u CNF:
3. Koristeći drugi distributivni zakon, pretvorite DNF u CNF:
A) 
;
4. Pretvorite date DNF-ove u SDNF-ove:
5. Pretvorite dati CNF u SKNF:
6. Za date logičke formule, konstruirajte SDNF i SKNF na dva načina: korištenjem ekvivalentnih transformacija i korištenjem tablice istinitosti.
b) 
;
Jednostavna disjunkcija(eng. inclusive disjunction) ili disjunctome(engleski disjunct) se naziva disjunkcija jedne ili više varijabli ili njihovih negacija, a svaka varijabla se ne pojavljuje više od jednom.
Jednostavna disjunkcija
- kompletan, ako svaka varijabla (ili njena negacija) uđe u nju tačno jednom;
- monotono, ako ne sadrži negacije varijabli.
Konjunktivna normalna forma, CNF(Engleski konjunktivni normalni oblik, CNF) je normalan oblik u kojem Booleova funkcija ima oblik spoja nekoliko jednostavnih klauzula.
CNF primjer:$f(x,y) = (x \lor y) \land (y \lor \neg (z))$
SKNF
Savršena konjunktivna normalna forma, SKNF(engleski savršeni konjunktivni normalni oblik, PCNF) je CNF koji zadovoljava uslove:
- nema identične jednostavne disjunkcije
- svaka jednostavna disjunkcija je potpuna
SKNF primjer:$f(x,y,z) = (x \lor \neg (y) \lor z) \land (x\lor y \lor \neg (z))$
Teorema: Za bilo koju Booleovu funkciju $f(\vec ( x ))$ koja nije jednaka identičnoj jedinici, postoji SKNF koji je definira.
dokaz: Budući da je inverz funkcije $\neg ( f ) (\vec x)$ jednak jedinici na onim torkama na kojima je $f(\vec x)$ jednako nuli, onda je SDNF za $\neg ( f ) (\vec x)$ se može napisati ovako:
$\neg ( f ) (\vec x) = \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n ) )) = 0 ) (x_ ( 1 ) ^ ( \sigma_ ( 1 ) ) \wedge x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \wedge ... \wedge x_ ( n ) ^ ( \sigma_ ( n ) ) )) $, gdje $ \sigma_ ( i ) $ označava prisustvo ili odsustvo negacije na $ x_ ( i ) $
Pronađite 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 ) ) \wedge x_ ( 2 ) ^ ( \sigma_ ( 2 ) ) \wedge ... \wedge x_ ( n ) ^ ( \sigma_ ( n ) ) ))) )) $
Primjenjujući de Morganovo pravilo dvaput na izraz dobijen na desnoj strani, dobijamo: $ 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 ) )) $
Poslednji izraz je SKNF. Pošto se SKNF dobija iz SDNF-a, koji se može konstruisati za bilo koju funkciju koja nije identično nula, teorema je dokazana.
Algoritam za konstruisanje SKNF-a prema tabeli istinitosti
- U tabeli istinitosti označavamo one skupove varijabli na kojima je vrijednost funkcije jednaka $0$.
- Za svaki označeni skup pišemo disjunkciju svih varijabli prema sljedećem pravilu: ako je vrijednost neke varijable $0$, tada u disjunkciju uključujemo i samu varijablu, inače njenu negaciju.
- Sve dobijene disjunkcije povezujemo konjunkcijskim operacijama.
Primjer konstruiranja SKNF-a za medijanu
1). U tabeli istinitosti označavamo one skupove varijabli na kojima je vrijednost funkcije jednaka $0$.
| x | y | 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 pišemo konjunkciju svih varijabli prema sljedećem pravilu: ako je vrijednost neke varijable $0$, tada u disjunkciju uključujemo i samu varijablu, inače njenu negaciju.
| x | y | 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) \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). Sve dobijene disjunkcije povezujemo konjunkcijskim operacijama.
$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg ( x ) \lor y \lor z) \land (x \lor \neg (y) \lor z) \land (x \lor y \lor \neg (z))$
SKNF primjeri za neke funkcije
Probodna 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) \lor z) \land (\neg (x) \lor y \lor \neg (z)) \land (x \lor \neg ( y ) \lor \neg ( z )) \land (x \lor y \lor z)$
Konjunktivna normalna forma je pogodna za automatske dokaze teorema. Bilo koja Booleova formula se može svesti na CNF. Da biste to učinili, možete koristiti: zakon dvostruke negacije, de Morganov zakon, distributivnost.
Enciklopedijski YouTube
-
1 / 5
Formule u 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\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\wedge E)).)Ali ove 3 formule nisu u CNF-u ekvivalentne 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-a
Algoritam za konstruisanje CNF
1) Riješite se svih logičkih operacija sadržanih u formuli, zamjenjujući ih glavnim: konjunkcija, disjunkcija, negacija. To se može učiniti korištenjem 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)\klin (A\vee \neg B).)2) Zamijenite znak negacije, koji se odnosi na cijeli izraz, znakovima negacije, koji se odnosi na pojedinačne iskaze varijable, na osnovu formula:
¬ (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) Oslobodite se dvostrukih negativnih znakova.
4) Primijeniti, ako je potrebno, na operacije konjunkcije i disjunkcije svojstva distributivnosti i formule apsorpcije.
Primjer izgradnje CNF-a
Hajde da svedemo formulu na CNF
F = (X → Y) ∧ ((¬Y → Z) → ¬X) . (\displaystyle F=(X\desno Y)\klin ((\neg Y\desno Z)\strelica desno \neg X).)Hajde da transformišemo 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 rezultirajućoj formuli prenosimo negaciju na varijable i smanjujemo dvostruke negacije:
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) . (\displaystyle (A\ili B)\zemlje (\neg B\ili C)\zemlje (B\ili \neg C).)
