Rastavite funkciju f zadanu stupcem vrijednosti. Dekompozicija Booleovih funkcija u varijablama

Razmotrimo pitanje reprezentacije n-lokalna Booleova funkcija f(x 1 ,x 2 ,…,x n) nekom formulom propozicijske algebre.

Uvedimo oznaku, gdje je parametar jednak 0 ili 1.

Očito je da

Teorem 1.1. Svaka funkcija algebre logikef(x 1 , x 2 ,…, x n ) za bilo kojim(1£ m £ n) može se predstaviti u sljedećem obliku:

gdje se disjunkcija preuzima na sve moguće skupove vrijednosti varijabli.

Dokaz. Razmotrite proizvoljan skup vrijednosti svih varijabli dane funkcije. Pokažimo da na tom skupu lijevi i desni dio formule (1) imaju istu vrijednost. Lijeva strana je , točno

jer , ako samo , ako , tada se odgovarajući logički termin može odbaciti.

Komentar. Prikaz funkcije navedene u teoremu naziva se proširenje funkcije u smislu m varijable .

Korolar 1(proširenje u jednoj varijabli).

U ovom slučaju funkcije i nazvao komponente razgradnje.

Posljedica 2(proširenje u svim varijablama).

Očito je da ako , onda

Dakle, ako funkcija f(x 1 ,x 2 ,…,x n) nije identično lažna funkcija, tada se može izraziti ekvivalentnom formulom, koja je logički zbroj različitih proizvoda oblika , a takav prikaz je jedinstven.

Oblik formule (2) može se znatno pojednostaviti. Poznato je da se bilo koja formula logičke algebre može reducirati pomoću ekvivalentnih transformacija na formulu koja sadrži samo konjunkciju i negaciju ili disjunkciju i negaciju. Kao rezultat provođenja ekvivalentnih transformacija može se dobiti nekoliko formula, ali samo jedna od njih će imati sljedeća svojstva:

1. Svaki logički termin sadrži sve varijable uključene u formulu f(x 1 ,x 2 ,…,x n).

2. Nijedan logički termin ne sadrži i varijablu i njezinu negaciju.

3. Svi logički pojmovi u formuli su različiti.

4. Nijedan logički termin ne sadrži istu varijablu dva puta.

Ova četiri svojstva nazivaju se svojstva savršenstva(ili svojstva C).

Ako a f(x 1 ,x 2 ,…,x n) dana tablicom istine, tada se odgovarajuća formula logičke algebre može vrlo jednostavno obnoviti. Za sve vrijednosti argumenata x 1 ,x 2 ,…,x n, na kojem f ima vrijednost 1, potrebno je zapisati konjunkciju elementarnih varijabli iskaza, uzimajući za termin konjunkcije x i, ako x i=1, a ako x i=0. Disjunkcija svih zabilježenih veznika bit će potrebna formula. O vrijednostima f 0 ne morate brinuti, jer odgovarajući član u formuli bit će jednak 0 i može se odbaciti zbog ekvivalencije fÚ 0 ≡ f.

Na primjer, neka funkcija f(x, g, z) ima sljedeću tablicu istinitosti:

x	g	z	f(x, g, z)

Ovaj je teorem konstruktivan jer nam omogućuje da za svaku funkciju konstruiramo formulu koja je realizira u obliku savršenog d.s. f. Da bismo to učinili, u tablici istine za svaku funkciju označimo sve retke u kojima

Podijelite rad na društvenim mrežama

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

Aranov Viktor Pavlovič Diskretna matematika.

Sekcija 4. Funkcionalni sustavi s operacijama. Algebra logike.

Predavanje 21. Načelo dualnosti. Dekompozicija funkcija u varijablama. Savršeni DNF i CNF

Predavanje 21 NAČELO DUALNOSTI. BOOLEANSKA DEKOMPOZICIJA

FUNKCIJE NAD VARIJABLAMA. PERFEKT DISJUNKTIV I

VEZNIK NORMALNI OBLICI

Plan predavanja:

1. Načelo dualnosti.
2. Dekompozicija Booleovih funkcija u varijablama. Perfektni disjunktivni i konjunktivni normalni oblici.

1. Načelo dvojnosti

Poziva se funkcija jednaka dual funkcija do funkcije.

Očito je da se tablica istinitosti za dualnu funkciju dobiva iz tablice istinitosti za funkciju invertiranjem (tj. zamjenom 0 s 1 i 1 s 0) vrijednosti varijabli i funkcije. Na primjer, .

Za funkcije 0, 1 lako je ustanoviti da

1. funkcija 0 je dualna na 1;
2. funkcija 1 je dualna na 0;
3. funkcija je dvostruka;
4. funkcija je dvostruka;
5. funkcija je dvostruka;
6. funkcija je dvostruka.

Iz definicije dualiteta proizlazi da

tj. Funkcija je dualna prema (svojstvo reciprociteta).

Načelo dualnosti.Ako formula implementira funkciju, tada formula, odnosno formula dobivena zamjenom funkcija sa, odnosno, implementira funkciju.

Formula će se zvati formula dualna na k.

Da bismo dokazali ovu tvrdnju, potrebno je provjeriti njezinu valjanost za elementarne korake superpozicije i.

Neka je, na primjer, funkcija dobivena iz funkcije kao rezultat sljedeće zamjene varijabli:

Zatim

tj. funkcija je dobivena kao rezultat iste zamjene varijable.

Dokažimo valjanost principa dualnosti za korak pomoću primjera. Neka

Zatim

tj. Funkcija se dobiva iz i na isti način kao funkcija iz i.

Načelo dualnosti omogućuje pojednostavljenje izvođenja osnovnih tautologija i ima niz korisnih primjena, o kojima će biti riječi kasnije.

Primjer 1 Identitet proizlazi iz identiteta.

Stvarno,

;; .

Primjer 2 Konstrukcija formule za negaciju funkcije.

Iz definicije dualne funkcije slijedi

Dobijamo sljedeće pravilo: neka formula implementira funkciju. Da biste dobili formulu za funkciju, trebate zamijeniti sve varijable u formuli njihovim negacijama.

Pronađite negaciju funkcije.

Od tad.

1. Dekompozicija Booleovih funkcija u varijablama. Savršen

Disjunktivni i konjunktivni normalni oblici

Uvodimo notaciju

gdje je parametar jednak ili 0 ili 1. Očito,

Lako je vidjeti da 1 ako i samo ako.

Teorem o proširenju funkcija po varijablama. Svaka funkcija logičke algebre za bilo koji () može se prikazati u sljedećem obliku:

, (1)

gdje se disjunkcija preuzima na sve moguće skupove vrijednosti varijable.

Ova prezentacija se zoveproširenje funkcije u varijablama.

Dokaz. Promotrimo proizvoljan skup vrijednosti varijabli i pokažimo da lijevi i desni dio relacije (1) na njemu imaju istu vrijednost. Lijeva strana daje. Pravo

Kao korolacije teorema, razmatramo dva posebna slučaja dekompozicije.

1. Proširenje varijable:

Funkcije i nazivaju sekomponente razgradnje.Ova dekompozicija je korisna kada se neka svojstva utvrđuju indukcijom.

1. Ekspanzija u svim varijablama:

Kada identično nije jednako 0, može se transformirati:

Kao rezultat toga, konačno dobivamo

. (2)

Takva se dekompozicija nazivasavršeni disjunktivni normalni oblik(Savršeni doktor znanosti).

Izravno na koncept savršenog d.s. f. nadovezuje se na sljedeći teorem.

Teorema. Svaka funkcija algebre logike može se prikazati formulom u bazi.

Dokaz. 1) Neka. Onda očito

1. Neka nije identički jednak 0. Tada se može prikazati formulom (2).

Ovaj je teorem konstruktivan jer nam omogućuje da za svaku funkciju konstruiramo formulu koja je realizira u obliku savršenog d.s. f. Da bismo to učinili, u tablici istine za svaku funkciju označimo sve retke u kojima. Za svaki takav red formiramo logički umnožak, a zatim sve dobivene veznike povezujemo disjunkcijskim znakom.

Primjer 3 Pronađite savršene d.s. f. za funkciju.

Savršeni d.s. f. je izraz tipa P. Pokažimo da, kada 1 nije identično jednak 1, može se prikazati u obliku Zapišimo za dualnu funkciju (očito ne identično jednaku 0) proširenje u obliku savršenog d.s. f.:

Iz principa dualnosti slijedi

Tako dobivamo dekompoziciju tzvperfektni konjunktiv normalni oblik(savršen doktorat):

. (3)

Primjer 4 Izgradite savršen doktorat. f. za funkciju.

Imamo.

Ostali srodni radovi koji bi vas mogli zanimati.vshm>
200.		Normalni oblici Booleovih funkcija	63,53 KB
	Normalne forme Booleovih funkcija Prikaz Booleove funkcije u obliku disjunkcije konjunktivnih članova jediničnih konstituenata Ki 2.7 naziva se disjunktivna normalna forma DNF-a te funkcije. sadrže točno jednu po jednu sve logičke varijable uzete s negacijama ili bez njih, tada se ovaj oblik reprezentacije funkcije naziva savršeni disjunktivni normalni oblik SDNF-a ove funkcije. Kao što vidite, prilikom kompajliranja SDNF funkcije morate napraviti disjunkciju svih minterma za koje funkcija ima vrijednost 1.
9015.		METODE ZA MINIMIZIRANJE BOOLEANSKIH FUNKCIJA	81,74 KB
	DNF i sheme iz FE. Minimizacija Booleovih funkcija na temelju konstrukcije slijepih DNF-ova. Minimizacija Booleovih funkcija temeljena na konstrukciji slijepih DNF-ova Reducirani slijepi i minimalni DNF-ovi su u sljedećem odnosu. Slijepi DNF dobiva se iz smanjenog DNF-a uklanjanjem nekih članova.
9017.		PROBLEM MINIMIZACIJE BOOLEANSKIH FUNKCIJA. GEOMETRIJSKA INTERPRETACIJA	109,86 KB
	DNF i sheme iz FE. GEOMETRIJSKA INTERPRETACIJA Plan predavanja: Pojam disjunktivne normalne forme DNF. Koncept DNF. Izraz za gdje je elementarna konjunkcija ranga naziva se disjunktivni normalni oblik DNF-a.
14731.		Proširenje signala u generalizirani Fourierov red u smislu sustava ortogonalnih funkcija. Walshove funkcije	38,95 KB
	Proširenje signala u generalizirani Fourierov red u smislu sustava ortogonalnih funkcija. Upoznati se s osnovnim karakteristikama signala i smetnji. Proučiti reprezentaciju signala u obliku generaliziranog Fourierovog niza u terminima sustava ortogonalnih funkcija. Proširenje signala u generalizirani Fourierov red u smislu sustava ortogonalnih funkcija.
6707.		Projektiranje relacijskih baza podataka. Problemi dizajna u klasičnom pristupu. Principi normalizacije, normalni oblici	70,48 KB
	Što je dizajn relacijske baze podataka?To je skup međusobno povezanih odnosa u kojima su definirani svi atributi, postavljeni primarni ključevi odnosa i postavljena neka dodatna svojstva odnosa koja se odnose na principe održavanja cjelovitosti. Stoga dizajn baze podataka mora biti vrlo precizan i provjeren. Zapravo, projekt baze podataka temelj je budućeg programskog paketa koji će dugo i dugo koristiti veliki broj korisnika.
4849.		Oblici i načini provedbe funkcija države	197,3 KB
	Pojam "funkcija" ima različito značenje u domaćoj i stranoj znanstvenoj literaturi. U filozofskom i općesociološkom smislu, smatra se "vanjskom manifestacijom svojstava objekta u danom sustavu odnosa"; kao skup običnih ili specifičnih radnji pojedinaca ili tijela
1790.		Proširenje u pojmove	180.15KB
	Sama riječ algoritam podsjeća na algorithmi - latinski oblik napisan u ime velikog matematičara IX stoljeća. al-Khwarizmi, koji je formulirao pravila za vikonnannyju aritmetiku diy. Nasumično se temelji na algoritmima i razumije samo pravila za vikonnanny chotirioh aritmetičke diy preko bogatih digitalnih brojeva.
2690.		Proučavanje performansi bušilica s promjenjivim korakom zavojnice	18,85 KB
	Modeli procesa rezanja mogu se prikazati sustavom matematičkih jednadžbi koje u svakom slučaju određuju funkciju procjene ili kriterije za izvedbu reznih alata, kao i tehnička ograničenja kinematike alatnog stroja, krutost reznih alata i cijeli tehnološki sustav.
17088.		KAZNENA ODGOVORNOST ZA DJELA POČINJENA U SASTAVU ORGANIZIRANE ZLOČINAČKE SKUPINE	50,97 KB
	Lomtev OPĆI OPIS RADA Relevantnost teme istraživanja određena je potrebom daljnjeg razvoja i usavršavanja teorije i prakse provedbe kaznene odgovornosti za kaznena djela počinjena u sastavu organizirane kriminalne skupine. Istraživanja u području suzbijanja organiziranog kriminala pokazuju da se najopasnija i najteže rješiva ​​kaznena djela čine unutar organiziranih kriminalnih skupina. U sklopu rješavanja problema povećanja učinkovitosti kaznenog zakona u smislu suzbijanja...
11576.		Pojam, vrste i oblici transakcija. Posljedice nepoštivanja traženog oblika transakcija	49,82 KB
	Prepoznavanje transakcije kao nevaljane vrste nevaljane transakcije. Primijenjena vrijednost kolegija je pojednostavljenje pojma transakcije, odnosno njezina javna prezentacija u pristupačnijem obliku.

Postavljanje Booleovih funkcija varijabli pomoću tablice istinitosti, definiranje formule, vrste najvažnijih ekvivalencija (zakona) algebre logike. Ekvivalentne formule, zakoni ekvivalencije, logičke jednadžbe. Dekompozicija Booleovih funkcija u varijablama.

Klikom na gumb "Preuzmi arhivu" besplatno preuzimate potrebnu datoteku.
Prije preuzimanja ove datoteke sjetite se onih dobrih eseja, kontrolnih, seminarskih radova, diplomskih radova, članaka i drugih dokumenata koji nisu zatraženi na vašem računalu. Ovo je vaš rad, treba sudjelovati u razvoju društva i koristiti ljudima. Pronađite ove radove i pošaljite ih u bazu znanja.
Mi i svi studenti, diplomanti, mladi znanstvenici koji koriste bazu znanja u svom studiranju i radu bit ćemo vam jako zahvalni.

Za preuzimanje arhive s dokumentom unesite peteroznamenkasti broj u polje ispod i kliknite gumb "Preuzmi arhivu"

Slični dokumenti

Osnovni aksiomi i identiteti algebre logike. Analitički oblik prikaza Booleovih funkcija. Elementarne funkcije logičke algebre. Funkcije algebre logike jednog argumenta i oblici njegove realizacije. Svojstva, značajke i vrste logičkih operacija.

sažetak, dodan 06.12.2010


Pojam logičke algebre, njezina bit i obilježja, osnovni pojmovi i definicije, predmet i metodologija proučavanja. Zakoni logike algebre i posljedice iz njih, metode za konstruiranje formula prema zadanoj tablici istinitosti. Oblici prikaza Booleovih funkcija.

tutorijal, dodan 29.04.2009


Booleove algebre su rešetke posebnog tipa koje se koriste u proučavanju logike (i logike ljudskog mišljenja i logike digitalnog računala), kao i sklopnih sklopova. Minimalni oblici Booleovih polinoma. Teoremi apstraktne Booleove algebre.

seminarski rad, dodan 12.05.2009


Operacije na logičkim iskazima: Booleove funkcije i izražavanje nekih od ovih ovisnosti kroz druge. Iskazne formule i neki zakoni iskazne logike. Prijevod izraza prirodnog jezika u simbolički govor algebre logike.

test, dodan 26.04.2011


Logika je znanost o zakonima i oblicima mišljenja, a osnovni pojam algebre logike je iskaz. Osnovni pojmovi i identiteti Booleove algebre. Proučavanje metoda za minimiziranje Booleovih funkcija. Quineova metoda koja se temelji na primjeni dva osnovna odnosa.

test, dodan 20.01.2011


Osnovni pojmovi algebre logike. Disjunktivni i konjunktivni normalni oblici. Bit Shannonovog teorema. Booleove funkcije dviju varijabli. Serijski i paralelni spoj dviju sklopki. Svojstva elementarnih funkcija logičke algebre.

test, dodan 29.11.2010


Booleova varijabla u logičkoj algebri. Logičke operacije: negacija, konjunkcija, disjunkcija, implikacija, ekvivalencija. Osnovni zakoni logičke algebre. Pravila za minimiziranje logičke funkcije (oslobađanje od operacija implikacije i ekvivalencije).

seminarski rad, dodan 16.01.2012

Skup B na kojem su definirane dvije binarne operacije (konjunkcija i disjunkcija) i jedna unarna operacija (negacija) i odabrana dva elementa 0 i 1 naziva se Booleova algebra.

Štoviše, za ove operacije moraju biti zadovoljena sljedeća svojstva:

Asocijativnost

komutativnost

Distributivnost konjunkcije u odnosu na disjunkciju

Distributivnost disjunkcije u odnosu na konjunkciju

Idempotencija

Dvaput ne

Konstantna svojstva

De Morgan vlada

Zakon kontradikcije

Zakon isključene sredine

U logičkoj algebri ti se zakoni nazivaju ekvivalencije.

Savršene normalne forme

Savršeni disjunktivni normalni oblik

Uvedimo oznaku:

; A A = 1; X A =1 ako je X=A, X A =0 ako je XA.

Formula X A 1…… X A n, gdje je A=- bilo koji binarni skup, a među varijablama Xi može biti ista, naziva se elementarna konjunkcija.

Svaka disjunkcija elementarnih konjunkcija naziva se disjunktivna normalna forma (DNF).

Elementarna se konjunkcija naziva ispravnom ako se svaka varijabla u njoj pojavljuje najviše jednom (uključujući i pojavljivanje pod znakom negacije).

Na primjer: 1) (ikona veznika je u ovom slučaju izostavljena).

1),4) pravilni su elementarni veznici;

2) - varijabla x jednom ulazi sama, a drugi put pod predznakom negacije;

Varijabla y pojavljuje se tri puta: jednom sama i dva puta pod znakom negacije.

Ispravna elementarna konjunkcija naziva se potpunom s obzirom na varijable x 1 ... .. x n ako uključuje svaku od tih varijabli i samo jednom (može postojati i znak negacije).

Na primjer: od veznika navedenih u prethodnom primjeru samo su 4) potpune u odnosu na varijable x, y, z, t; a u odnosu na varijable x,y,z samo je 1 potpuna).

Savršena disjunktivna normalna forma (PDNF) s obzirom na varijable x 1 .....x n je disjunktivna normalna forma u kojoj nema identičnih elementarnih konjunkcija i sve su elementarne konjunkcije točne i potpune s obzirom na varijable x 1 . ....x n

Varijabilna ekspanzija

Teorem 1. Bilo koja logička funkcija može se predstaviti u SDNF:

gdje je m, a disjunkcija se preuzima preko svih 2 m skupova vrijednosti varijabli x 1 ,…x m . Funkcija f je proširena u prvih n-varijabli. Ova jednakost se naziva proširenje u varijablama. x 1 ,… x m . Na primjer, za n=4, m=2, dekompozicija izgleda ovako:

teorem se dokazuje zamjenom proizvoljnog skupa (b 1 ,…,b m , b m+1 ,…,b n) svih n-varijabli u obje strane jednakosti (1).

Za m = 1, iz (1) dobivamo proširenje funkcije u jednoj varijabli:

Očito, slično proširenje vrijedi za bilo koju od n-varijabli.

Drugi važan slučaj je kada je n=m. U ovom slučaju sve varijable s desne strane (1) dobivaju fiksne vrijednosti i funkcije u konjunkciji s desne strane postaju jednake 0 ili 1, što daje:

gdje se disjunkcija preuzima na sve skupove (b 1 …b n) na kojima je f=1. Za f=0, skup konjunkcija na desnoj strani je prazan. Takva se dekompozicija naziva savršena disjunktivna normalna forma. SDNF funkcije f sadrži točno onoliko konjunkcija koliko ih ima u tablici istinitosti funkcije f. Svaki skup jedinica (b 1 ,…, b n) odgovara konjunkciji svih varijabli, u kojoj se x i uzima s negacijom ako je b i =0 b , a bez negacije ako je b i =1. Dakle, postoji korespondencija jedan-na-jedan između tablice istinitosti funkcije f i njezinog SDNF-a, te je, prema tome, SDNF za bilo koju logičku funkciju jedinstven. Jedina funkcija koja nema SDNF je konstanta 0.

Teorem 2. Bilo koja logička funkcija može se prikazati kao Booleova formula.

Doista, za bilo koju funkciju, osim za konstantu 0, njezin SDNF može poslužiti kao takav prikaz. Konstanta 0 može se prikazati Booleovom formulom.

3.1 Dekompozicija Booleovih funkcija u varijablama

3.2 Zhegalkinova algebra

Gore smo pokazali da se bilo koja Booleova funkcija može definirati pomoću tablice istinitosti. Ovaj odjeljak opisuje prijelaz s tabličnog prijelaza specifikacije funkcije na analitički.

3.1 Proširenje Booleovih funkcija u varijablama.

Neka je G parametar jednak 0 ili 1. Uvedimo oznaku:

To je lako provjeriti provjerom toga x G = 1 ako i samo ako x =G. Iz ovoga proizlazi da veznik
je 1 (ovdje je G 0 ili 1) ako i samo ako
. Na primjer, konjunkcija
(u kojem je G 2 \u003d G 1 \u003d 0, G 3 \u003d G 4 \u003d 1) jednako 1 samo ako x 1 =x 2 = 0,x 3 =x 4 = 1.

Teorem 1Bilo koja Booleova funkcijaf(x 1 , x 2 ,…, x n ) može se predstaviti u sljedećem obliku:

gdje je 1 ≤k ≤ n, u disjunkciji se preuzimaju svi skupovi vrijednosti varijable.

Taj se prikaz naziva proširenje funkcije u smislu varijabli.
. Na primjer, za n= 4,k= 2, proširenje (3.1) ima oblik:

.

Dokažimo proširenje (3.1). Da biste to učinili, uzmite proizvoljan skup vrijednosti varijabli
. Pokažimo da lijeva i desna strana relacije (3.1) imaju istu vrijednost. Doista, budući da x G = 1 ako i samo ako x = G, zatim među 2 K veznika
na desnoj strani (3.1), samo onaj u kojem
. Svi ostali veznici
jednaki su nuli.

Zato . Kao korolar proširenja (3.1), dobivamo sljedeća dva posebna proširenja.

Varijabilna ekspanzijax n :

Ako Booleova funkcija nije konstanta 0, tada je dekompozicija

Ekspanzija u svim varijablama:

,
(3.3)

gdje se disjunkcija preuzima na sve skupove
, za koju je vrijednost funkcije
jednako 1.

Dekompozicija (3.3) se naziva savršeni disjunktivni normalni oblik (skraćeni zapis SDNF) funkcije.

Dekompozicija (3.3) daje način za konstrukciju SDNF-a. Da biste to učinili, označite sve retke u tablici istine
, u kojem
. Za svaki takav red formiramo veznik
a zatim sve nastale veznike povezujemo disjunkcijskim znakom.

Dakle, postoji korespondencija jedan na jedan između tablice istinitosti funkcije
i njezin SDNF. A to znači da je SDNF za Booleovu funkciju jedinstven.

Jedna booleova funkcija koja nema sdnf je konstanta 0.

Primjer 1 Pronađite savršeni disjunktivni oblik za funkciju
.

Napravimo tablicu istine za ovu funkciju:

Odavde dobivamo:
==.

Važnu ulogu u algebri logike igra sljedeća dekompozicija Booleovih funkcija.

Teorem 2Bilo koja Booleova funkcija
može se predstaviti u sljedećem obliku:

gdje je 1≤k≤n, a konjunkcija je uzeta za sve 2 k skupovi varijabilnih vrijednosti.

Doista, neka
je proizvoljan skup vrijednosti varijable. Pokažimo da lijevi i desni dio relacije (3.4) imaju istu vrijednost. Jer
samo kada
, zatim između 2 k disjunkcija
na desnoj strani (3.4) nestaje samo jedan, u kojem
. Sve ostale disjunkcije jednake su 1.

Zato
==
.

Proširenja Booleovih funkcija slijede izravno iz proširenja (3.4):

Posljednja dekompozicija naziva se savršena konjunktivna normalna forma (CKNF). Dekompozicija (3.6) daje način da se konstruira SKNF. Da biste to učinili, označite sve retke u tablici istine
, u kojem. Za svaki takav red formiramo disjunkciju
a zatim sve nastale veznike povezujemo vezničkim znakom. Dakle, postoji korespondencija jedan na jedan između tablice istinitosti funkcije
i njezin SKNF. A to znači da je SKNF za Booleovu funkciju jedinstven.

Jedina Booleova funkcija koja nema SKNF je konstanta 1.

Primjer 2 Pronađite savršeni konjunktivni normalni oblik za funkciju
.

Napravimo tablicu istine za ovu funkciju.

Odavde dobivamo SKNF

Formula obrasca (kratka notacija
), gdje
- veznici
nazvao disjunktivni normalni oblik (DNF).

Na temelju gornje definicije DNF-a postojat će, na primjer, izrazi:
,
.

Kao što je navedeno u paragrafu 2.2, sve logičke operacije mogu se svesti na tri: konjunkcija, disjunkcija i negacija. Štoviše, s obzirom na de Morganov zakon, može se pretpostaviti da se znak negacije primjenjuje samo na varijable.

Sada, koristeći zakon distribucije, otvaramo zagrade i dobivamo disjunktivnu normalnu formu. Dakle, sljedeća teorema je istinita.

Teorema3 Za svaku formulu logičke algebre postoji disjunktivna normalna forma koja joj je ekvivalentna.

Dokaz ovog teorema daje način da se konstruira disjunktivni normalni oblik za bilo koju formulu u logičkoj algebri.

Primjer 3 Pronađite disjunktivni normalni oblik za sljedeću formulu:
.

Isključujući znak
u pravu
i primjenom de Morganovih zakona i dvostruke negacije, dobivamo:

Zatim, primjenom zakona distributivnosti, raširimo zagrade

Posljednji izraz je disjunktivni normalni oblik.

Prikaži obrazac
(kratak unos ), gdje
- disjunkcije
nazvao konjunktivni normalni oblik (CNF).

To su, na primjer, izrazi:

,
.

Kao što je gore pokazano, za bilo koju formulu logičke algebre postoji disjunktivni oblik koji joj je ekvivalentan. Koristeći zakon distribucije, lako je dobiti CNF iz zadane DNF.

Dakle, sljedeća teorema je istinita.

Teorem 4Za svaku formulu algebre logike postoji konjunktivna normalna forma koja joj je ekvivalentna.

Dokaz ovog teorema daje način da se konstruira konjunktivni normalni oblik za bilo koju formulu u logičkoj algebri.

Primjer4 Pronađite disjunktivni i konjunktivni normalni oblik za sljedeću formulu:
.

Korištenje zakona
, isključujemo znak
. Dobili smo formulu
.

Koristeći de Morganov zakon dobivamo formulu
. Proširivanjem zagrada dobivamo disjunktivnu normalnu formu

.

Da biste dobili konjunktivni normalni oblik, primijenite na formulu
zakon distribucije, dobivamo:

Posljednji izraz je konjunktivni normalni oblik. Jer
i
, tada je rezultirajuća CNF ekvivalentna sljedećoj CNF:

Među svim normalnim formulama ove formule izdvajamo savršeni normalni oblik, disjunktivni i konjunktivni. Uzimajući u obzir ekspanziju (3), lako je vidjeti da je savršeni disjunktivni normalni oblik formule algebre logike koja sadrži točno n različitih varijabli njezin disjunktivni normalni oblik, u kojem:

1) svi su veznici parno različiti;

2) svaka konjunkcija sadrži točno n varijabli;

3) u svakoj konjunkciji ima svih n varijabli.

U primjeru 1 razmotrili smo jedan od načina konstruiranja SDNF-a na temelju kompilacije tablice istinitosti. Sljedeći način konstruiranja SDNF-a temelji se na primjeni zakona algebre logike.

Primjer 5 Pronađite savršeni disjunktivni oblik formule
.

Koristeći se time
, dobivamo
. S obzirom na de Morganove zakone i dvostruku negaciju, dobili smo disjunktivni normalni oblik
. Ovaj DNF je ekvivalentan formuli.

Proširivanjem zagrada dobivamo: .

Koristeći zakon idempotencije, dobivamo traženi SDNF:

Uzimajući u obzir dekompoziciju (3.6), lako je vidjeti da savršeni konjunktivni normalni oblik formule algebre logike sadrži točno n različitih varijabli, postoji njegov konjunktivni normalni oblik, u kojem:

1) sve su disjunkcije parno različite;

2) svaka disjunkcija sadrži točno n članova;

3) svaka disjunkcija sadrži svih n varijabli.

Koristeći primjer 2, razmotrili smo jedan od načina konstruiranja SKNF-a, koji se temelji na sastavljanju tablice istinitosti. Sljedeći način konstruiranja SKNF-a temelji se na primjeni zakona algebre logike.

Primjer 6 Pronađite savršeni konjunktivni normalni oblik formule
.

korištenje,
, dobivamo
.

Ova je formula u konjunktivnom normalnom obliku. Ekvivalent je formuli.

Koristeći zakon distributivnosti, dobivamo:

Primjenom zakona idempotencije dobivamo traženu savršenu konjunktivnu normalnu formu

identično istinito ako, za sve vrijednosti varijabli koje su u njemu uključene, uzima vrijednost pravi.

Primjeri identično istinitih formula su formule:

Algebarska formula logike zove se identično lažna ako za sve vrijednosti varijabli koje su u njemu uključene, uzima vrijednost lažno.

Primjeri identično lažnih formula su formule:

,

Algebarska formula logike zove se izvodljiv ako, za neke vrijednosti varijabli koje su u njemu uključene, uzima vrijednost pravi.

Primjeri izvedivih formula su sljedeće formule:

,
.

U algebri logike može se postaviti sljedeći problem: naznačiti metodu (algoritam) koja omogućuje da se za svaku formulu algebre logike otkrije je li identično istinita ili ne. Zadatak se zove rješavanje problema.

Razmotrite sljedeća dva načina za rješavanje ovog problema.

Metoda 1 (tablica) Da bismo utvrdili je li određena formula identično istinita ili ne, dovoljno je sastaviti njezinu tablicu istinitosti.

Međutim, ova je metoda, iako daje temeljno rješenje problema rješivosti, prilično glomazna.

Metoda 2 na temelju svođenja formula na normalan oblik.

Teorem 4Formula algebre logike identično je istinita ako i samo ako svaka disjunkcija u svom konjunktivnom normalnom obliku sadrži neku varijablu zajedno sa svojom negacijom.

Doista, ako svaka rečenica u konjunktivnom normalnom obliku sadrži varijablu zajedno sa svojom negacijom, tada su sve rečenice jednake 1, jer
,
. Slijedi da je CNF identično istinit.

Neka je sada dana formula identično istinita i neka
postoji neka disjunkcija u CNF ove formule. Pretpostavimo da dana disjunkcija ne sadrži varijablu zajedno s njezinom negacijom. U tom slučaju svakoj varijabli koja nije negativna možemo dati vrijednost 0, a svakoj varijabli koja je negativna vrijednost 1. Nakon ove zamjene sve će disjunkcije postati 0, dakle formula nije identično istinita. Imamo kontradikciju.

Primjer 7 Utvrdite je li formula identično istinita

.

Koristeći se time
, dobivamo
.

Primjenom zakona distributivnosti dobivamo CNF:

Budući da svaka disjunkcija sadrži neku varijablu zajedno sa svojom negacijom, formula je identično istinita.

Slično prethodnom teoremu, dokazuje se i sljedeći teorem:

Teorem 5 Formula algebre logike je identično lažna ako i samo ako svaka konjunkcija u svom disjunktivnom obliku sadrži neku varijablu zajedno sa svojom negacijom.