Logička funkcija naziva se konjunktivna normalna forma. Konjunktivni oblici prikazivanja logičkih funkcija

Normalne forme logičkih funkcija Prikaz Booleove funkcije u obliku disjunkcije konjunktivnih članova sastavnica jedinice Ki 2.7 naziva se disjunktivna normalna forma DNF-a te funkcije. sadrže točno jednu od svih logičkih varijabli uzetih sa ili bez negacija, tada se ovaj oblik reprezentacije funkcije naziva savršena disjunktivna normalna forma SDNF te funkcije. Kao što vidite, kada sastavljate SDNF funkciju, trebate stvoriti disjunkciju svih minterma za koje funkcija ima vrijednost 1.

Ako vam ovaj rad ne odgovara, 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

Predstavljanje Booleove funkcije u obliku disjunkcije konjunktivnih članova (konstituent jedinice) K i

, (2.7)

nazvao disjunktivni normalni oblik(DNF) ove funkcije.

Ako su svi konjunktivni pojmovi u DNF minterms , tj. sadrže točno jednu od svih logičkih varijabli, uzete s negacijama ili bez njih, tada se ovaj oblik reprezentacije funkcije nazivasavršeni disjunktivni normalni oblik(SDNF ) ovu funkciju. Zove se SDNF savršen , jer svaki član u disjunkciji uključuje sve varijable; disjunktivan , jer je glavna operacija u formuli disjunkcija. Koncept “normalnog oblika” znači nedvosmislen način pisanja formule koja implementira zadanu funkciju.

Uzimajući u obzir navedeno, iz teorema 2.1 proizlazi sljedeći teorem.

Teorem 2. Bilo koja Booleova funkcija(nije identično 0) mogu se prezentirati u SDNF, .

Primjer 3. Neka nam je tablica zadana funkcija f (x 1 , x 2 , x 3 ) (tablica 10).

Tablica 10

Na temelju formule (2.6) dobivamo:

Kao što vidite, kada sastavljate SDNF funkciju, trebate stvoriti disjunkciju svih minterma za koje funkcija ima vrijednost 1.

Predstavljanje Booleove funkcije u obliku konjunkcije disjunktivnih članova (nulti konstituent) D i

, (2.8)

nazvao konjunktivni normalni oblik(CNF) ove funkcije.

Ako su svi disjunktivni pojmovi CNF maxterms , tj. sadrže točno jednu od svih logičkih varijabli funkcije, uzete s negacijama ili bez njih, tada se takva CNF nazivaperfektni konjunktiv normalni oblik(SKNF) ove funkcije.

Teorem 3. Bilo koja Booleova funkcija(nije identičan 1) može se predati SKNF-u, a takav prikaz je jedini.

Dokaz teorema može se izvesti slično dokazu teorema 2.1 na temelju sljedeće Shannonove leme o konjunktivnoj dekompoziciji.

Shannonova lema . Bilo koja Booleova funkcija f (x 1, x 2, …, x m) od m varijable se mogu prikazati ovako:

. (2.9)

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

U praksi se najčešće koristi DNF, jer je ovaj oblik osobi poznatiji: od djetinjstva je više navikao na zbrajanje proizvoda nego na množenje iznosa (u potonjem slučaju intuitivno ima želju otvoriti zagrade i time prijeći na DNF).

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

Za razliku od SDNF-a, kada sastavljate SCNF u tablici istinitosti logičke funkcije, trebate pogledati kombinacije varijabli pri kojima funkcija poprima vrijednost 0 i stvoriti konjunkciju odgovarajućih maxtermova,ali varijable se moraju uzeti s obrnutom inverzijom:

Treba napomenuti da je nemoguće izravno prijeći iz SDNF funkcije u njen SCNF ili obrnuto. Pri pokušaju takvih transformacija rezultati su funkcije koje su suprotne od željenih. Izrazi za funkcije SDNF i SCNF mogu se izravno dobiti samo iz njihove tablice istinitosti.

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

Koristeći rezultat primjera 2.3 dobivamo:

Kao što vidite, pod općom inverzijom dobili smo SCNF logičke funkcije, koja je inverzna funkciji dobivenoj u primjeru 2.4:

jer sadrži sve maxtermove koji nisu u izrazu za SCNF funkcije koja se razmatra.

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

2. Korištenjem svojstava negacije i De Morganovih zakona (vidi tablicu 9), osiguravamo da se operacije negacije primjenjuju samo na pojedinačne varijable, a ne na cijele izraze.

3. Korištenjem svojstava logičkih operacija I i ILI (vidi tablicu 9) dobivamo normalni oblik (DNF ili CNF).

4. Po potrebi prelazimo na svršene oblike (SDNF ili SKNF). Na primjer, da biste dobili SCNF često morate koristiti svojstvo: .

Primjer 6. Pretvorite logičku funkciju u SKNF

Provodeći redom korake gornjeg algoritma, dobivamo:

Koristeći svojstvo apsorpcije, dobivamo:

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

2.2.6. Minimiziranje logičkih funkcija

Budući da se ista logička funkcija može prikazati kao h osobne formule, zatim pronalaženje najjednostavnijeg oblika R mule koji definira Booleovu funkciju, pojednostavljuje logički sklop koji implementira Booleovu funkciju za ciju. Minimalni oblik l O logička funkcijau nekoj osnovi možemo smatrati onu koja sadrži minimalan broj superpozicija zabave Do cije osnove, dopuštajući zagrade. Međutim, teško je izgraditi učinkovit l algoritam za takvu minimizaciju za dobivanje minimalne zagrade r mi.

Razmotrimo jednostavniji problem minimizacije u sintezi kombinacijskih sklopova, u kojemu ne tražimo minimalni zagradni oblik 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 nepotpune operacije lijepljenja

, (2.10)

a zatim apsorpcija

, (2.11)

i ovaj se par koraka primjenjuje opetovano. Dakle, moguće je smanjiti rang pojmova. Ovaj se postupak ponavlja sve dok ne ostane niti jedan pojam koji se može povezati s bilo kojim drugim pojmom.

Imajte na umu da se lijeva strana jednadžbe (2.10) može odmah minimizirati na jednostavniji i očitiji način:

Ova metoda je loša jer takvom izravnom minimizacijom konjunktivni termini ili nestaju, iako još uvijek postoje mogući slučajevi njihove upotrebe za lijepljenje i apsorpciju s preostalim terminima.

Valja napomenuti da je Quineova metoda prilično radno intenzivna, tako da je vjerojatnost pogrešaka tijekom transformacija prilično velika. Ali njegova prednost je što se teoretski može koristiti za bilo koji broj argumenata i kako se broj varijabli povećava, transformacije postaju manje komplicirane.

Karnaughova metoda karte

Metoda Carnotovih mapa (tablica) je vizualniji, manje radno intenzivan i pouzdan način minimiziranja logičkih funkcija, ali je njezina upotreba praktički ograničena na funkcije 3-4 varijable, maksimalno 5-6 varijabli.

Carnotova karta ovo je dvodimenzionalni tablični oblik predstavljanja tablice istinitosti Booleove funkcije, koji vam omogućuje jednostavno pronalaženje minimalnih DNF-ova logičkih funkcija u grafičkom vizualnom obliku. Svakoj ćeliji tablice pridružuje se SDNF minterm funkcije koja se minimizira, i to na način da bilo koje osi simetrije tablice odgovaraju zonama koje su međusobno inverzne u odnosu na neku varijablu. Ovakav raspored ćelija u tablici olakšava određivanje uvjeta prianjanja SDNF-a (različitih u znaku inverzije samo jedne varijable): oni se nalaze simetrično u tablici.

Tablice istinitosti i Carnaughove karte za funkcije I i ILI dviju staza e Varijable su prikazane na sl. 8. Vrijednost je zapisana u svakoj ćeliji kartice A Vrijednost funkcije na skupu vrijednosti argumenata koji odgovaraju ovoj ćeliji N druže

A) I b) ILI

Riža. 8. Primjer Karnaughovih mapa za funkcije dviju varijabli

U Karnaughovoj mapi postoji samo jedan 1 za And funkciju, tako da se ne može zalijepiti ni za što. Izraz za minimalnu funkciju sadržavat će samo član koji odgovara ovom 1:

f = x y .

U Carnotovoj mapi za funkciju OR već postoje tri 1 i možete napraviti dva nepovezana para, pri čemu 1 odgovara izrazu xy , koristi se dva puta. U izrazu za minimalnu funkciju potrebno je zapisati članove za parove koji se lijepe, ostavljajući u njima sve varijable koje se ne mijenjaju za taj par, a uklanjati varijable koje mijenjaju svoju vrijednost. Za horizontalno lijepljenje dobivamo x , i za okomite g , kao rezultat dobivamo izraz

f = x + y.

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

Pri određivanju minimalne DNF funkcije koriste se sljedeća pravila. Sve ćelije koje sadrže 1 spojene su u zatvorena pravokutna područja tzv k-kocke, gdje je k = log 2 K, K količina 1 u pravokutnom području. U ovom slučaju, svako područje treba biti pravokutnik s brojem ćelija 2 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 zove se tri kocke ; itd. Jedinice koje se ne mogu spojiti u pravokutnike mogu se zvati nula-kocke , koji sadrže samo jednu jedinicu (2 0 = 1). Kao što se vidi, za čak k područja mogu imati kvadratni oblik (ali ne nužno), a ako nepar k samo pravokutnici.

Riža. 9. Primjer Karnaughovih mapa za funkcije triju varijabli

Te se regije mogu preklapati, odnosno iste ćelije mogu ući u različite regije. Tada se minimalna DNF funkcija piše kao disjunkcija svih konjunktivnih članova koji odgovaraju k - kocke.

Svako od naznačenih područja na Karnaughovoj karti predstavljeno je u minimalnom DNF-u konjunkcijom, broj argumenata u kojoj je k manji od ukupnog broja argumenata funkcije m , tj. ovaj broj je jednak mk . Svaka konjunkcija minimalnog DNF-a sastoji se samo od onih argumenata koji za odgovarajuće područje mape imaju vrijednosti ili bez inverzija ili samo s inverzijama, tj. ne mijenjaju svoje značenje.

Dakle, kada se ćelije karte pokrivaju zatvorenim područjima, treba težiti tome da broj područja bude minimalan, a da svako područje sadrži što više ćelija, jer će u tom slučaju broj članova u minimalnom DNF-u biti minimalan, a broj argumenata u odgovarajućoj konjunkciji bit će minimalan.

Za funkciju prema Karnaughovoj mapi na Sl. 9, b nalazimo

budući da za gornju zatvorenu regiju varijable x 1 i x 2 imaju vrijednosti bez inverzija, za niže x 1 stvari s inverzijom, i x 3 bez inverzije.

Nedefinirane vrijednosti u karti na sl. 9, V može se dalje definirati zamjenom s nulom ili jedinicom. Za ovu funkciju je jasno da je isplativije zamijeniti obje nedefinirane vrijednosti s 1. U ovom slučaju formiraju se dva područja, koja su različite vrste 2-kocke. Tada će izraz za minimalnu DNF funkciju biti sljedeći:

Prilikom konstruiranja zatvorenih područja dopušteno je presavijati Carnotovu kartu u cilindar vodoravno i okomito. R tikalne sjekire sa spojem suprotnih lica R vi, tj. jedinice smještene uz rubove Carnotove karte simetrije h ali se mogu i kombinirati.

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

a b

Riža. 10. Različiti načini prikazivanja Carnaughovih karata
za funkciju 3 varijable

Ali najprikladnije opcije za Karnaughove mape za funkcije od 2-4 varijable su one prikazane na sl. 11 tablica, jer se prikazuju za svaku ćeliju A Imamo sve varijable u izravnom ili obrnutom obliku.

a b

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

Za funkcije od 5 i 6 varijabli, metoda prikazana na Sl. 10, V .

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

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

Standardna osnova. Elementarne formule su literali. Elementarna konjunkcija (disjunkcija). Disjunktivni (konjunktivni) normalni oblik i svršeni oblik. Teorem: svaka Booleova funkcija različita od 0 (od 1) može se prikazati u obliku SDNF (SCNF). Cjelovitost standardne osnove. Primjeri potpunih baza: Zhegalkinova baza, Schaefferov potez, Peirceova strelica.

Standardna osnova je skup od tri osnovne operacije Booleove algebre: zbrajanje (unija), množenje (presjek) i negacija.

Ovdje ćemo nazvati doslovan varijablu x ili njezinu negaciju x i označiti xˆ. Booleov presjek nekoliko literala definiranih različitim varijablama, tj. izraz oblika X = xˆ 1 xˆ 2 . . . xˆ l, tzv elementarna konjunkcija . Zahtjev da sve varijable budu različite određen je sljedećim. Ako konjunkcija uključuje nekoliko identičnih literala, tada je zbog komutativnosti, asocijativnosti i idempotencije konjunkcije moguće, prelazeći na ekvivalentnu formulu, ostaviti samo jedan literal (npr. x 1 x 1 = x 1). Ako konjunkcija uključuje varijablu i njezinu negaciju, tada je formula ekvivalentna konstanti 0, budući da je x x = 0 i za svaku formulu Y imamo Y x x = 0.

Disjunkcija nekoliko elementarnih konjunkcija naziva se disjunktivni normalni oblik , ili DNF . Na primjer,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

Ako je sastav varijabli u svakoj elementarnoj konjunkciji danog DNF-a isti, tada se DNF naziva savršen . Navedeni primjer je DNF koji nije savršen. Naprotiv, formula

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

postoji savršeni oblik.

Budući da su u Booleovoj algebri zbrajanje i množenje simetrične operacije i zbrajanje uvijek možete interpretirati kao množenje, a množenje kao zbrajanje, postoji dvojni koncept - konjunktivni normalni oblik (KNF ), koja je konjunkcija elementarnih disjunkcija, i svršeni konjunktivni oblik (SKNF ). Iz principa dualnosti za simetrične poluprstenove slijedi da se na svaku tvrdnju o DNF odgovara dualnom tvrdnjom o CNF, koja se dobiva zamjenom zbrajanja (disjunkcije) množenjem, množenja (konjunkcije) zbrajanjem, konstante 0 s konstantom 1, konstante 1 s konstantom 0, odnos reda s dualnim (inverznim) redom. Stoga ćemo se dalje fokusirati na proučavanje samo DNF-a.

Teorem 1.4. Bilo koja Booleova funkcija osim konstante 0 može se predstaviti kao SDNF.

◀Dogovorimo se da pod x σ podrazumijevamo formulu x ako je σ = 1, a formulu x ako je σ = 0. Neka funkcija f(y 1 , . . . , y n) poprimi vrijednost 1 na vektoru (t 1 , . . . , t n ) (takav se vektor naziva sastavna jedinica ). Tada elementarna konjunkcija također poprima vrijednost 1 na ovom skupu, ali nestaje na svim ostalim n-dimenzionalnim Booleovim vektorima. Razmotrite formulu

u kojem se zbroj (unija) proteže na sve one skupove (t 1, . . . , t n) vrijednosti argumenata na kojima dana funkcija ima vrijednost 1. Imajte na umu da skup takvih skupova nije prazan, pa je zbroj sadrži barem jedan član.

Lako je vidjeti da formula Φ postaje 1 za one i samo one vrijednosti varijabli za koje dotična funkcija postaje 1. To znači da formula Ψ predstavlja funkciju f.

Korolar 1.1. Standardna osnova je gotova.

◀ Doista, ako funkcija nije konstanta 0, tada se može prikazati ili u obliku SDNF-a, što je formula preko standardne baze. Konstanta 0 može se prikazati, na primjer, formulom f(x 1, x 2, . . . , x n) = x 1 x 1.

Primjer 1.2. Promotrimo funkciju triju varijabli m(x 1, x 2, x 3) (tablica 1.4), tzv. većinska funkcija ̆. Ova funkcija daje vrijednost 1 ako više od polovice njezinih argumenata ima vrijednost 1. Stoga se često naziva funkcija glasanja. Izgradimo SDNF za to.

Cjelovitost standardne osnove omogućuje odabir drugih cjelovitih sustava funkcija. Potpunost skupa F može se utvrditi iz sljedećih razmatranja. Pretpostavimo da se svaka od tri standardne poslovne funkcije može predstaviti formulom nad F . Tada će prema teoremu 1.3 identitet F biti potpun.

Primjer 1.3. Poziva se skup operacija modula 2 zbrajanja, množenja i konstante 1 Zhegalkinova osnova . Zbrajanje po modulu 2 i množenje osnovne su operacije Z2 prstena, a izrazi sastavljeni pomoću njih su polinomi nad Z2 prstenom. Konstanta 1 u ovom slučaju je neophodna za pisanje slobodnog člana. Budući da je xx = x, tada svi faktori u polinomu imaju stupanj 1. Stoga, kada pišete polinom, možete bez pojma stupnja. Primjeri formula nad Zhegalkinovom osnovom:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Svaka takva formula naziva se Zhegalkin polinom. Zapravo, Zhegalkinov polinom je polinom nad prstenom Z2.

Nije teško konstruirati formule preko Zhegalkinove baze, koje predstavljaju operacije zbrajanja i negacije standardne baze (množenje dviju baza je uobičajeno):

x+y=x⊕y⊕xy, x =x⊕1.

Stoga je Zhegalkinova osnova kompletan set.
Može se pokazati da je za bilo koju Booleovu funkciju Zhegalkinov polinom jedinstveno definiran

(točnije do reda pojmova). Koeficijenti Zhegalkinovog polinoma s malim brojem varijabli mogu se pronaći metodom neodređenih koeficijenata.

Primjer 1.4. Razmotrimo skup jedne funkcije - Schaefferov udar*. Ovaj skup je potpun, kao što slijedi iz sljedećih lako provjerljivih identiteta:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

Primjer 1.5. Osnova koja se sastoji od jedne funkcije, Peirceove strelice, također je dovršena. Test za ovo sličan je slučaju Schaefferovog moždanog udara. Međutim, ovaj se zaključak može izvesti i na temelju načela dualnosti za simetrične poluprstenove.

*Schaefferov potez je binarna, ali ne asocijativna operacija. Stoga, kada koristite infiks formu, trebate biti oprezni: rezultat ovisi o redoslijedu operacija. U tom slučaju preporuča se eksplicitno naznačiti redoslijed operacija pomoću zagrada, na primjer, napisati (x | y) | z, a ne x | y | z, iako su oba oblika ekvivalentna.

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) ;

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 elementarnim funkcijama logičke algebre, 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

Za bilo koju logičku formulu, korištenjem transformacija identiteta, može se konstruirati beskonačno mnogo njoj ekvivalentnih formula. U algebri logike jedan od glavnih zadataka je potraga za kanonskim oblicima (tj. formulama konstruiranim prema jednom pravilu, kanonu).

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

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

Savršeni disjunktivni normalni oblik (PDNF)

Definicija. Formula se naziva elementarnom konjunkcijom ako je nastala konjunkcijom određenog broja varijabli ili njihovih negacija.

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

Definicija. Formula se naziva disjunktivna normalna forma (DNF) ako je disjunkcija neponavljajućih elementarnih konjunkcija.

DNF se piše 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 (PDNF) ako:
1) formula je DNF, u kojoj je svaka elementarna konjunkcija konjunkcija k varijabli x 1, x 2, ..., x k, a na i-tom mjestu te konjunkcije nalazi se ili varijabla x i ili njezina negacija ;
2) sve elementarne konjunkcije u takvoj DNF 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 (PCNF)

Definicija. Formula se naziva elementarna disjunkcija ako je nastala disjunkcijom određenog broja varijabli ili njihovih negacija.

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

Definicija. Formula se naziva konjunktivna normalna forma (CNF) ako je konjunkcija neponavljajućih elementarnih disjunkcija.

CNF se piše 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šena konjunktivna normalna forma (CPNF) 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 te disjunkcije nalazi se ili varijabla x i ili njezina 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 svaka logička funkcija koja nije identično jednaka 0 ili 1 može se predstaviti kao SDNF ili SKNF.

Algoritam za konstruiranje SDNF-a pomoću tablice istinitosti

1. Odaberite sve retke tablice u kojima je vrijednost funkcije jednaka jedinici.
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 konjunkciju uključujemo samu varijablu, inače njezinu negaciju.
3. Sve nastale konjunkcije povezujemo operacijama disjunkcije.

Algoritam za konstruiranje SCNF pomoću tablice istine

1. Odaberite sve retke tablice u kojima je vrijednost funkcije nula.
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 u konjunkciju uključujemo samu varijablu, u suprotnom, njezinu negaciju.
3. Sve nastale disjunkcije povezujemo operacijama konjunkcije.

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

Primjer: Dana je tablica istinitosti logičke funkcije tri varijable. Konstruirajte logičku formulu koja implementira ovu funkciju.

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

Provjerimo dobivenu formulu. Da bismo to učinili, napravit ćemo tablicu istine za funkciju.

Uspoređujući izvornu tablicu istine i onu konstruiranu za logičku formulu, primjećujemo da se stupci vrijednosti funkcije podudaraju. To znači da je logička funkcija ispravno konstruirana.