Teorema o proširenju funkcije u varijablu. Princip dualnosti

Razmotrite pitanje zastupanja n-lokalna Booleova funkcija f(x 1 ,x 2 ,…,x n) neka formula propozicione algebre.

Hajde da uvedemo notaciju gdje je parametar jednak 0 ili 1.

Očigledno je da

Teorema 1.1. Svaka funkcija logičke algebref(x 1 , x 2 ,…, x n ) za bilo kojem (1£ m £ n) može se predstaviti u sljedećem obliku:

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

Dokaz. Razmotrimo proizvoljan skup vrijednosti svih varijabli date funkcije. Pokažimo da na ovom skupu lijeva i desna strana formule (1) imaju istu vrijednost. Lijeva strana je , u redu

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

Komentar. Reprezentacija funkcije specificirane u teoremi naziva se proširenje funkcije u terminima m varijable

Zaključak 1(proširenje u jednoj varijabli).

U ovom slučaju funkcije I su pozvani komponente raspadanja.

Zaključak 2(proširivanje na sve varijable).

Očigledno, ako , To

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

Oblik formule (2) može se značajno pojednostaviti. Poznato je da se bilo koja formula u algebri logike može svesti ekvivalentnim transformacijama na formulu koja sadrži samo konjunkciju i negaciju ili disjunkciju i negaciju. Kao rezultat 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. Ni jedan logički termin ne sadrži i promenljivu i njenu negaciju.

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

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

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

Ako f(x 1 ,x 2 ,…,x n) je dat tablicom istinitosti, onda se odgovarajuća formula logičke algebre vrlo jednostavno obnavlja. Za sve vrijednosti argumenata x 1 ,x 2 ,…,x n, pri čemu f uzima vrijednost 1, potrebno je da zapišete konjunkciju elementarnih iskaza varijable, uzimajući kao član konjunkcije x i, Ako x i=1, i ako x i=0. Neophodna formula će biti disjunkcija svih napisanih veznika. O vrijednostima f 0 ne morate da brinete, jer... odgovarajući član u formuli će biti jednak 0 i može se odbaciti zbog ekvivalentnosti fÚ 0 ≡ f.

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

x	y	z	f(x, y, z)

Označimo sa . Onda

xs=

Konkretno, ako i samo ako .

Korištenje “power funkcije” bilo koje Boolean funkcije može se predstaviti kao:

pozvao proširenje Booleove funkcije po varijabli.

U stvari, ako , onda , i

Ako , onda , i

Primjer 4.

Proširimo funkciju po varijabli. Da biste to učinili, prvo napravite tablicu funkcija:

Iz tabele je jasno da i .

Koristeći formulu proširenja u smislu varijable, nalazimo

Primjer 5.

Proširimo funkciju iz primjera 4 za sve varijable. Pošto funkcija uzima vrijednost 1 na tri skupa: , tada, prema posljedicama teoreme o proširenju, imamo

Definicija 3.

Boolean funkcija proširenja za sve varijable u obrascu

pozvao savršena disjunktivna normalna forma(SDNF).

Primjer 6.

- SDNF za funkciju (vidi primjer 5).

Teorema 2.

Svaka Booleova funkcija (osim 0) ima jedinstveni SDNF.

Dokaz. Prema posledicama teoreme dekompozicije

Komentar. Ako pod disjunkciju jednog člana podrazumijevamo sam ovaj pojam, onda disjunkcija nultih članova ne postoji, stoga ne postoji SDNF za funkciju 0.

Prilikom konstruiranja SDNF-a, događa se sljedeće:

Pravilo jedinice. uzima vrijednost 1; Za svaki takav skup priprema se sabir u SDNF-u . Ako u ovaj set argumentima, onda se negacija objesi preko varijable u pripremljenom terminu: .

Teorema 3.

Svaka Booleova funkcija može se izraziti kroz disjunkciju, konjunkciju i negaciju:

Dokaz.

Ako , To . Ako , To

Teorema 4.

Svaka Booleova funkcija (osim 1) može se jedinstveno izraziti u savršenom konjunktivnom normalnom obliku (PCNF):

Dokaz.

Ako , To I

Primjenjujući princip dualnosti na posljednji identitet, nalazimo

Prilikom izgradnje SCNF-a dešava se sljedeće:

Pravilo nule. Razmatraju se samo oni skupovi argumenata na kojima je funkcija uzima vrijednost 0; Za svaki takav skup, faktor je pripremljen u SKNF-u. Ako je u datom skupu argumenata, negativ je obješen preko varijable u pripremljenom faktoru: .

Primjer 7.

Konstruirajmo funkciju za implikaciju: . Implikacija uzima vrijednost 0 na jednom skupu:

Budući da u ovom skupu i , Tada po pravilu nule dobivamo

dakle, - potrebna funkcija za implikaciju.

Kompletnost sistema

Definicija 4. Sistem funkcija ( f 1 , f 2 , ..., f s , ...)M P 2 se zove kompletan in R 2 ako postoji funkcija f(x 1 , ..., x n) Î P 2 se može napisati kao formula kroz funkcije ovog sistema.

Kompletni sistemi

1. P 2 – kompletan sistem.

2. Sistem M={x 1 &x 2 , x 1 Ú x 2 , ) – kompletan sistem, jer bilo koja funkcija logičke algebre može se napisati kao formula kroz ove funkcije.

Primjer 8. Nepotpuni sistemi: ( }, {0,1}.

Lemma(dovoljan uslov za kompletnost)

Pustite sistem U = {f 1 , f 2 , ..., fs, ...) je puna R 2. Neka B = {g 1 , g 2 , ..., g k, ...) – neki sistem od R 2 i bilo koju funkciju f i Î U može se izraziti formulom preko B, zatim sistem B pun in R 2 .

7. Sistem ( x 1 &x 2 , x 1 Å x 2 , 0, 1) je završeno R 2 , U = {x 1 &x 2 , }, = x 1 Å1.

Zhegalkin polinom

f(x 1 , ..., x n) Î P 2, predstavljamo ga kao formulu kroz konjunkciju i zbir po modulu dva, koristeći brojeve 0 i 1. To se može učiniti pošto ( x 1 &x 2 , x 1 Å x 2 , 0, 1) je završeno R 2. Zbog imovine x & (yÅ z) = xy Å xz možete otvoriti sve zagrade, dodati slične pojmove i dobiti polinom iz n varijable koje se sastoje od članova forme X X ...X, povezanih znakom Å. Takav polinom naziva se Zhegalkin polinom.

Opšti pogled na Zhegalkin polinom:

Gdje , s = 0, 1, ..., n, i at s= 0 dobijamo slobodni termin A 0 .

Predstavljanje funkcije kao Zhegalkin polinom

1. Predstavimo bilo koju funkciju formulom preko ( x 1 &x 2 , ) i izvršite zamjenu = xÅ1. Ova metoda je pogodna ako je funkcija data formulom.

Primjer 9. (x 1 (x 2 x 3))(x 1 Ú x 2) x 3 = (x 1 Ú x 2 Ú x 3)(x 1 Ú x 2) x 3 = (`x 1 x 2 Ú x 1 x 3 Ú x 1 x 2 Ú x 2 Ú x 2 x 3)x 3 = (`x 1 x 3 Ú x 2)x 3 = x 1 x 3 x 2 x 3 = ((x 1 x 3 Å1) x 2 Å1) x 3 = x 1 x 2 x 3 Å x 2 x 3 Å x 3 .

Moramo zapamtiti da je paran broj identičnih članova u zbiru mod 2 daje 0.

2. Metoda neodređenih koeficijenata. Zgodno je ako je funkcija specificirana u tabeli.

Primjer 10.

Zapišimo Zhegalkin polinom sa neodređenim koeficijentima za funkciju od tri varijable f(x 1 , x 2 , x 3) = (01101001) = A 0 Å A 1 X 1 Å A 2 X 2 Å A 3 X 3 Å b 1 x 1 x 2 Å b 2 x 2 x 3 Å b 3 x 1 x 3 Å cx 1 x 2 x 3. Zatim pronalazimo koeficijente koristeći vrijednosti funkcije na svim skupovima. Na setu (0, 0, 0) f(0, 0, 0) = 0, s druge strane, zamjenom ovog skupa u polinom, dobijamo f(0, 0, 0) = A 0 , odavde A 0 = 0. f(0, 0, 1) = 1, zamjenom skupa (0, 0, 1) u polinom, dobijamo: f(0, 0, 1) = A 0 Å A 3, jer A 0 = 0, dakle A 3 = 1. Slično, f(0, 1, 0) = 1 = A 2 , f(0, 1, 1) = 0 = A 2 Å A 3 Å b 2 b 2 = 0; A 1 = 1; 0 = A 1 Å A 3 Å b 3 , b 3 = 0; 0 = A 1 Å A 2 Å b 1 , b 1 = 0; 1 = 1 Å 1 Å 1 Å c; c= 0; tada Zhegalkin polinom za ovu funkciju ima oblik: f(x 1 , x 2 , x 3) = x 1 Å x 2 Å x 3 .

Žegalkinov polinom se također može dobiti pomoću Pascalovog trokuta koristeći jedinice njegove lijeve strane prema tablici kako slijedi. Konstruirajmo Zhegalkin polinom za funkciju f= (10011110). Gornja strana trokuta je funkcija f. Bilo koji drugi element trougla je modulo zbir dva susjedna elementa prethodnog reda. Lijeva strana trokuta za funkciju f sadrži šest jedinica. Žegalkinov polinom će sadržati šest članova. Prva jedinica trougla odgovara skupu (000). Prvi član polinoma je 1. Treći 1 odozdo na lijevoj strani trougla odgovara skupu (101). Kao pojam polinoma uzimamo x 1 x 3. Slično za ostale jedinice trougla. Lijevo od skupova prikazani su članovi Zhegalkinovog polinoma.

Žegalkinova teorema

Svaka funkcija može biti predstavljena kao Zhegalkin polinom na jedinstven način.

Ovdje se jedinstvenost razumije do reda članova u zbiru i redoslijeda faktora u konjunkcijama:

, s = 0, 1, ..., n.

Dokaz.

Bilo koja funkcija iz R 2 se može predstaviti formulom preko ( x 1 & x 2 , x 1 Å x 2, 0, 1), a ova formula, nakon otvaranja svih zagrada i donošenja sličnih pojmova, daje Žegalkinov polinom. Dokažimo jedinstvenost reprezentacije. Pogledajmo funkcije f(x 1 , ..., x n) od n varijable. Znamo da ukupno takve funkcije, tj. njihove tabele istine, 2 n. Hajde da izbrojimo broj različitih Zhegalkin polinoma iz n varijable, tj. broj varijacija forme: . Broj skupova je jednak broju svih podskupova skupa ( x 1 , ..., x n), ovo uključuje prazan skup (if s= 0). Broj podskupova skupa od n elemenata je 2 n, a pošto je svaki skup uključen s koeficijentom koji ima dvije vrijednosti: 0 ili 1, tada će broj svih mogućih polinoma biti . Budući da svaki polinom odgovara jednoj funkciji, broj funkcija iz n varijabli je jednak broju polinoma, tada će svaka funkcija odgovarati jednom polinomu.

Definicija.

Funkcija f(x 1 , ..., x n), polinom Žegalkina za koji ima sljedeći linearni oblik u odnosu na varijable: f = A 0 Å A 1 X 1 Å A 2 X 2 Å ... Å a n x n, naziva se linearnim.

Lemma o nelinearnoj funkciji .

Superpozicijom nelinearne funkcije, negacije i konstante 1, može se dobiti konjunkcija.

Dokaz.

Neka f(x 1 , ..., x n) je nelinearna funkcija. Tada Zhegalkin polinom sadrži izraz za njega, koji sadrži proizvod x i x j. Radi jednostavnosti to ćemo pretpostaviti x 1 x 2 u Zhegalkin polinomu je ovaj proizvod. Nakon grupiranja pojmova, funkcija f predstavimo ga u obliku

Funkcija h 0 nije identično nula, inače Žegalkinovom polinomu nedostaje termin s proizvodom x 1 x 2. Zatim postoji set ( a 3 , …, a n) od 0 i 1, za koje h 0 (a 3 , …, a n) = 1. Neka h 1 (a 3 , …, a n) = a, h 2 (a 3 , …, a n) = b, h 3 (a 3 , …, a n) = c. Onda

Napravimo funkciju:

Gdje d = ab Å c. Ako d= 0, onda h(x 1 , x 2) = x 1 x 2. Ako d= 1, onda h(x 1 , x 2) = x 1 x 2 Å 1 i zatim Lema je dokazana.

Funkcija f(x 1 , ..., x n) održava se konstantnim a O (0, 1), ako f(a, …, a) = a.

Primjer 11.

Funkcija xy pohranjuje 0, pohranjuje 1. Funkcija x® y pohranjuje 1 i ne pohranjuje 0.

Minimiziranje Booleovih funkcija

Minimiziranje normalnih oblika

Minimalni DNF (MDNF) funkcije f(x 1 , ... ,x n) se naziva DNF koji implementira funkciju f i koji sadrži minimalni broj varijabilnih simbola u poređenju sa svim drugim tipovima DNF-a koji implementiraju funkciju f.

Ako je za svaki skup = ( a 1 , ..., a n) vrijednosti stanja varijabli g()=1 implicira , a zatim funkciju g naziva se dijelom funkcije f(ili funkcija f pokriva funkciju g). Ako je za neki skup = ( c 1 , ..., c n) funkcija g()=1, onda kažu da je funkcija g pokriva jedinicu funkcije f na setu (ili šta g pokriva sastavnu jedinicu funkcije f). Imajte na umu da je sastavni dio jedinice funkcije f postoji dio funkcije f, pokrivajući jedinu jedinicu funkcije f.

Elementarna konjunkcija K nazvana funkcija implikantna f, ako za svaki skup =( a 1 , ..., a n) od 0 i 1 stanja K()=1 implicira f()=1.

Implikantno K funkcije f naziva se jednostavnim ako izraz dobijen iz njega eliminacijom bilo kojeg faktora više nije implikacija funkcije f.

Jasno je da svaka implikacija funkcije f postoji dio funkcije f.

Teorema 5.

Svaka funkcija se ostvaruje disjunkcijom svih njenih jednostavnih ilikantnih (PI).

dakle, f = A. Teorema je dokazana.

Skraćeno DNF funkcije f je disjunkcija svih primarnih implikantnih funkcija f. Svaka funkcija f implementiran je svojim skraćenim DNF-om. Za svaku funkciju koja nije identično nula, postoji jedinstveni skraćeni DNF.

Neka A I B– proizvoljne formule. Sljedeća invertibilna pravila DNF transformacije slijede iz svojstava Booleovih operacija:

1) – kompletno lijepljenje (rasklapanje);

2) – nepotpuno lepljenje;

3) – generalizovano lepljenje;

4) – apsorpcija;

5) – idempotencija (uklanjanje duplikata članova).

Quineova teorema. Ako su u SDNF funkcije f izvršiti sve operacije nepotpunog lijepljenja, a zatim sve operacije apsorpcije i uklanjanja duplih članova, tada će rezultat biti smanjenje DNF funkcije f.

Dokaz.

Hajde da imamo skraćenu DNF funkciju f. Izvodimo sve operacije proširenja za svaku osnovnu implikaciju da bismo dobili varijable koje nedostaju u svakom disjunktivnom članu reduciranog DNF-a. U rezultirajućem izrazu, od nekoliko identičnih disjunktivnih pojmova, ostavićemo svaki samo po jednu instancu. Kao rezultat, dobijamo SDNF funkcije f. Sada, na osnovu dobijenog SDNF-a, u obrnutim redosledom Provedimo operacije sabiranja identičnih disjunktivnih pojmova (koristeći pravila idempotencije), nepotpunog lijepljenja i apsorpcije. Kao rezultat, dobijamo originalni redukovani DNF.

Odaberimo varijablu x 1 i razmotrimo funkciju f u odnosu na nju.

Sve mnogo kompleta tabela istinitosti je podijeljena na dva podskupa, od kojih svaki ima četiri skupa<0, a 2 , a 3 >I<1, a 2 , a 3 >.

Tada se funkcija f(x 1 ,x 2 ,x 3) može predstaviti kao disjunkcija dvije funkcije dvije varijable i ova formula će izgledati ovako:

Razmotrite sljedeće formule:

Lijeva strana prve formule je ekvivalentna desnoj, jer je za x 1 =0 iu skladu sa operacijom konjunkcije. Slično, možemo pokazati valjanost druge formule. Dakle, stavljajući ove formule u prethodnu disjunkciju, dobijamo:

Ovaj izraz se naziva proširenjem funkcije f(x 1, x 2, x 3) u varijablu x 1.

Sada, na sličan način, možemo proširiti funkcije f(0,x 2,x 3) i f(1,x 2,x 3) u varijablu x 2. Dobijamo

Zamjenom ovih formula u prethodne dobijamo

U skladu sa distributivnošću operacije &, uvodimo varijablu x 1 i njenu inverziju u zagrade, dobijamo

Općenito, za funkciju f(x 1 ,x 2 ,..,x n) od n varijabli, proširenje u m varijabli (m£n) ima oblik

gdje se disjunkcija preuzima na sve 2 m skupove varijabli x 1 ,x 2 ,..,x m .

Razmotrimo ekspanziju (*4) u ekstremnom slučaju kada je m=n. (vidi primjer (*3)).

Tada u svim konjunkcijama vrijednost funkcije f na svakom fiksnom skupu ima vrijednosti jednake nuli ili jedan. Uklonivši sve nulte konjunkcije, dobijamo novu ekspanziju iu ovom novom proširenju uklanjamo faktore funkcija u konjunkcijama, jer jednaki su 1. Preostali izraz se naziva SDNF (savršena disjunktivna normalna forma).

Uradimo sve ovo za primjer (*3).

Nakon uklanjanja iz (*3) konjunkcija sa nultim vrijednostima funkcije f na datim skupovima, dobijamo:

Pošto, prema tabeli istine

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

tada iz konjunkcija uklanjamo faktore funkcija, nakon čega dobijamo:

Ovo je savršena disjunktivna normalna forma Booleove funkcije f.

Lemma. Svaka Booleova funkcija (osim konstante "0") ima SDNF, i to samo jedan.

Slično, možete uvesti konjunktivni oblik,

Konstrukcija SDNF-a za funkciju datu tablicom

Ova posljedica je konstruktivne prirode, jer koristeći tablicu funkcija, omogućava vam da konstruirate formulu koja je SDNF (ako ).
SDNF funkcije f sadrži tačno onoliko veznika koliko ima jedinica u tabeli f; svaki set „jedinica“. (d 1 ,…,d n), one. skup na kojem je vrijednost funkcije jednaka 1 odgovara konjunkciji svih varijabli u kojoj x i uzeti sa negacijom ako d i=0, i bez negacije, ako d i =1.

Podijelite svoj rad na društvenim mrežama

Ako vam ovaj rad ne odgovara, na dnu stranice nalazi se lista sličnih radova. Možete koristiti i dugme za pretragu

Aranov Viktor Pavlovič. Discrete Math.

Odjeljak 4. Funkcionalni sistemi sa operacijama. Algebra logike.

Predavanje 21. Princip dualnosti. Proširenje funkcija u varijable. Savršen DNF i CNF

Predavanje 21. PRINCIP DUALNOSTI. BOOLEAN DEKOMPOZICIJA

FUNKCIJE PO Varijablama. SAVRŠENI DISJUNKTIV I

KONJUNKTIVNI NORMALNI OBLICI

Pregled predavanja:

Princip dualnosti.
Proširenje Booleovih funkcija u varijable. Savršeni disjunktivni i konjunktivni normalni oblici.

Princip dualnosti

Poziva se funkcija jednaka dual funkcija do funkcije.

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

Lako je postaviti za funkcije 0, 1 to

funkcija 0 je dvojna prema 1;
funkcija 1 je dvojna prema 0;
funkcija je dvostruka;
funkcija je dvostruka;
funkcija je dvostruka;
funkcija je dvostruka.

Iz definicije dualnosti proizilazi da

to jest, funkcija je dualna (svojstvo reciprociteta).

Princip dualnosti.Ako formula implementira funkciju, onda formula, odnosno formula dobijena zamjenom funkcija s respektivno, implementira funkciju.

Formulu ćemo nazvati dualnom formulom.

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

Neka se, na primjer, funkcija dobije iz funkcije kao rezultat sljedeće zamjene varijabli:

Onda

tj. funkcija se dobija kao rezultat iste zamjene varijabli.

Na primjeru ćemo dokazati valjanost principa dualnosti za korak. Neka

Onda

odnosno funkcija se dobija iz i na isti način kao što se funkcija dobija iz i.

Princip dualnosti nam omogućava da pojednostavimo izvođenje osnovnih tautologija i ima niz korisnih primjena, o kojima će biti riječi u nastavku.

Primjer 1. Iz identiteta slijedi identitet.

stvarno,

;; .

Primjer 2. Izrada 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.

Nađimo negaciju funkcije.

Od tada.

Proširenje Booleovih funkcija u varijable. Savršeno

Disjunktivni i konjunktivni normalni oblici

Hajde da uvedemo notaciju

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

Lako je vidjeti da je 1 ako i samo ako.

Teorema o proširenju funkcija u varijablama. Svaka funkcija algebre logike za bilo koji () može se predstaviti u sljedećem obliku:

, (1)

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

Ovaj pogled se zoveproširenje funkcije u varijablama.

Dokaz. Razmotrimo proizvoljan skup varijabilnih vrijednosti i pokažemo da lijeva i desna strana relacije (1) poprimaju istu vrijednost. Lijeva strana daje. U redu

Kao posledice teoreme, razmatramo dva posebna slučaja ekspanzije.

Promjenjiva ekspanzija:

Funkcije se pozivajukomponente raspadanja.Ova dekompozicija je korisna kada se neka svojstva utvrde indukcijom.

Proširenje za sve varijable:

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

Kao rezultat, konačno dobijamo

. (2)

Ova dekompozicija se zovesavršena disjunktivna normalna forma(savršen d.n.f.).

Direktno na koncept savršenog d.n. f. sljedeća teorema je susjedna.

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

Dokaz.1) Neka. Onda očigledno

Neka nije identično jednako 0. Tada se može predstaviti formulom (2).

Ova teorema je konstruktivne prirode, jer omogućava svakoj funkciji da konstruiše formulu koja je implementira u obliku savršenog d.n. f. Da bismo to učinili, u tabeli istinitosti za svaku funkciju označavamo sve redove u kojima. Za svaku takvu liniju formiramo logički proizvod, a zatim povezujemo sve nastale konjunkcije znakom disjunkcije.

Primjer 3. Pronađite savršen d.n. f. za funkciju.

Savršen doktor nauka f. je izraz tipa P. Pokažimo da kada nije identično jednak 1, može se predstaviti u obliku. Zapišimo za dualnu funkciju (očito nije identično jednaku 0) ekspanziju u obliku savršenog d.n. f.:

Iz principa dualnosti to slijedi

Tako dobijamo dekompoziciju tzvsavršeni konjunktivni normalni oblik(savršen doktorat):

. (3)

Primjer 4. Izgradite savršenu Ph.D. f. za funkciju.

Imamo.

Drugi slični radovi koji bi vas mogli zanimati.vshm>
200.		Normalni oblici logičkih funkcija	63,53 KB
	Normalni oblici logičke funkcije Reprezentacija Bulove funkcije u obliku disjunkcije konjunktivnih članova konstituenata jedinice Ki 2.7 naziva se disjunktivnim normalnim oblikom DNF ove funkcije. sadrže tačno jednu od svih logičkih varijabli uzetih sa ili bez negacija, onda se ovaj oblik reprezentacije funkcije naziva savršena disjunktivna normalna forma SDNF ove funkcije. Kao što možete vidjeti, kada sastavljate SDNF funkciju, morate kreirati disjunkciju svih minterma za koje funkcija uzima vrijednost 1.
9015.		METODE ZA MINIMIZUJU BOOLOVA FUNKCIJA	81,74 KB
	DNF i FE kola. Minimizacija Booleovih funkcija zasnovana na konstrukciji DNF-ova slijepe ulice. Minimizacija Booleovih funkcija zasnovana na konstrukciji DNF-ova slijepe ulice. Redukovana slijepa ulica i minimalni DNF su u sljedećem odnosu. DNF u slijepoj ulici se dobija iz reduciranog uklanjanjem nekih pojmova.
9017.		PROBLEM MINIMIZACIJE BOOLOVA FUNKCIJA. GEOMETRIJSKA INTERPRETACIJA	109,86 KB
	DNF i FE kola. GEOMETRIJSKA INTERPRETACIJA Kratak sadržaj predavanja: Koncept disjunktivnog normalnog oblika DNF. Koncept DNF-a. Izraz za gdje je elementarna konjunkcija ranga naziva se disjunktivni normalni oblik DNF-a.
14731.		Dekompozicija signala u generalizovani Fourierov red u sistemima ortogonalnih funkcija. Walshove funkcije	38,95 KB
	Dekompozicija signala u generalizovani Fourierov red u sistemima ortogonalnih funkcija. Upoznajte se sa osnovnim karakteristikama signala i smetnji. Proučavati prikaz signala u obliku generaliziranog Fourierovog reda u sistemima ortogonalnih funkcija. Dekompozicija signala u generalizovani Fourierov red u sistemima ortogonalnih funkcija.
6707.		Dizajn relacionih baza podataka. Problemi dizajna u klasičnom pristupu. Principi normalizacije, normalni oblici	70,48 KB
	Šta je projekat relacione baze podataka Ovo je skup međusobno povezanih odnosa u kojima su definisani svi atributi, specificirani su primarni ključevi relacija i određena dodatna svojstva relacija koja se odnose na principe održavanja integriteta? Stoga dizajn baze podataka mora biti vrlo precizan i verifikovan. U stvari, projekat baze podataka je temelj budućnosti softverski paket koji će se koristiti dugo vremena i od strane mnogih korisnika.
4849.		Oblici i metode realizacije državnih funkcija	197,3 KB
	Pojam „funkcija“ ima daleko od istog značenja u domaćoj i stranoj naučnoj literaturi. U filozofskom i opštesociološkom smislu, on se smatra „spoljnom manifestacijom svojstava objekta u datom sistemu odnosa“; kao skup uobičajenih ili specifičnih radnji pojedinaca ili tijela
1790.		Raspadanje	180,15 KB
	Sama reč algoritam podseća na algoritmi – latinski oblik pisanja imena velikog matematičara 9. veka. al-Khwarizma, koji je formulirao pravila aritmetičkih operacija. U početku su se pod algoritmima razumjela samo pravila za odgonetanje nekoliko aritmetičkih operacija nad bogatim digitalnim brojevima.
2690.		Proučavanje performansi bušilica s promjenjivim nagibom spirale	18,85 KB
	Modeli procesa rezanja mogu se predstaviti sistemom matematičkih jednačina koje u svakom konkretnom slučaju određuju funkciju evaluacije ili kriterijume za performanse reznog alata, kao i tehnička ograničenja na kinematiku mašine, krutost reznog alata. i tehnološki sistem u cjelini
17088.		KRIVIČNA ODGOVORNOST ZA ZLOČINA POČINJENA KAO PRIPADNIK ORGANIZOVANE KRIMINALNE GRUPE	50,97 KB
	Lomtev OPŠTE KARAKTERISTIKE RADA Relevantnost teme istraživanja određena je potrebom daljeg razvoja i unapređenja teorije i prakse sprovođenja krivične odgovornosti za krivična djela počinjena u sastavu organizovane kriminalne grupe. Istraživanja u oblasti borbe protiv organizovanog kriminala pokazuju da se upravo u okviru organizovanih kriminalnih grupa vrše najopasniji i najteže rasvetljivi zločini. U sklopu rješavanja problema povećanja djelotvornosti krivičnog zakona u pogledu suzbijanja...
11576.		Pojam, vrste i oblici transakcija. Posljedice nepridržavanja traženog oblika transakcija	49,82 KB
	Priznavanje transakcije kao nevažeće vrste nevažećih transakcija. Vrijednost aplikacije rad na kursu je pojednostaviti koncept transakcije, odnosno javno je predstaviti u pristupačnijem obliku.

Proširenje Booleovih funkcija u varijable.

Neka je G parametar jednak 0 ili 1. Uvedemo notaciju:

To je lako provjeriti x G = 1, ako i samo ako x= G. Iz toga slijedi da je konjunkcija jednaka 1 (ovdje je G jednako 0 ili 1) ako i samo ako . Na primjer, konjunkcija (u kojoj je G 2 = G 1 = 0, G 3 = G 4 = 1) jednaka je 1 samo ako x 1 = x 2 = 0, x 3 = x 4 = 1.

Teorema 1Bilo koja Booleova funkcija f(x 1 ,x 2 ,…,x n) mora biti predstavljena u sljedećem obliku:

gdje je 1 ≤ k ≤ n, u disjunkciji se preuzima preko svih skupova vrijednosti varijabli.

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

Dokažimo valjanost ekspanzije (3.1). Da biste to učinili, uzmite proizvoljan skup vrijednosti varijabli . Pokažimo da lijeva i desna strana relacije (3.1) poprimaju istu vrijednost. Zaista, pošto x G = 1 ako i samo ako x= G, tada se među 2 Do konjunkcije desne strane (3.1) samo jedan pretvara u jedan, u kojem . Sve ostale konjunkcije su jednake nuli.

Iz ovog razloga. Kao posljedica proširenja (3.1) dobijamo sljedeća dva specijalna proširenja.

Promjenjiva ekspanzija x n:

Ako Boolean funkcija nije konstanta 0, tada je proširenje istinito

Proširenje za sve varijable:

, (3.3)

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

Ekspanzija (3.3) se obično naziva savršenim disjunktivnim normalnim oblikom (kratki oblik SDNF) funkcije.

Proširenje (3.3) pruža način za konstrukciju SDNF-a. Da bismo to učinili, označavamo sve redove u tabeli istinitosti , u kojem . Za svaku takvu liniju formiramo konjunkciju, a zatim povezujemo sve nastale konjunkcije znakom disjunkcije.

Međutim, postoji korespondencija jedan-na-jedan između tablice istinitosti funkcije i njen SDNF. To znači da je SDNF za Booleovu funkciju jedinstven.

Jedna Booleova funkcija koja nema SDNF je konstanta 0.

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

Kreirajmo tabelu istinitosti za ovu funkciju:

Odavde dobijamo: = = .

Sljedeće proširenje Booleovih funkcija igra važnu ulogu u algebri logike.

Teorema 2Bilo koja Booleova funkcija moraju biti predstavljeni u sljedećem obliku:

gdje je 1≤k≤n, i uzeta je konjunkcija preko svih 2 k skupova varijabilnih vrijednosti.

Zaista, neka – proizvoljan skup varijabilnih vrijednosti. Pokažimo da lijeva i desna strana relacije (3.4) poprimaju istu vrijednost. Budući da samo kada , Tada među 2 k disjunkcija na desnoj strani (3.4) samo jedan ide na 0, u kojem . Sve ostale disjunkcije su jednake 1.

Iz tog razloga = = .

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

Posljednja dekompozicija se naziva savršena konjunktivna normalna forma (PCNF). Ekspanzija (3.6) daje metodu za konstruisanje SCNF-a. Da bismo to učinili, u tabeli istine označavamo sve redove u kojima . Za svaku takvu liniju formiramo disjunkciju a zatim sve nastale veznike povezujemo znakom veznika. Međutim, postoji korespondencija jedan-na-jedan između tablice istinitosti funkcije i njegov SKNF. To znači da je SCNF za Booleovu funkciju jedinstven.

Jedina Booleova funkcija koja nema SCNF je konstanta 1.

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

Kreirajmo tabelu istinitosti za ovu funkciju.

Odavde dobijamo SKNF

Formula oblika (kratka notacija), gdje – veznici obično se zove disjunktivni normalni oblik (DNF).

Na osnovu gornje definicije DNF-a postojaće, na primjer, izrazi: , .

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

Sada, koristeći distributivni zakon, otvaramo zagrade i dobijamo disjunktivni normalni oblik. Dakle, tačna je sljedeća teorema.

Teorema 3 Za bilo koju formulu u algebri logike postoji disjunktivni normalni oblik koji joj je ekvivalentan.

Dokaz ove teoreme pruža način da se konstruiše disjunktivni normalni oblik za bilo koju formulu u algebri logike.

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

Isključujući potpis po zakonu i primjenom De Morganovih zakona i dvostruke negacije, dobivamo:

Zatim, primjenom zakona distributivnosti, otvaramo zagrade

Posljednji izraz je disjunktivni normalni oblik.

Pogledaj obrazac (kratka notacija), gdje su disjunkcije obično se zove konjunktivni normalni oblik (CNF).

Takvi izrazi su, na primjer:

, .

Kao što je gore prikazano, za bilo koju formulu u algebri logike postoji ekvivalentan disjunktivni oblik. Koristeći distributivni zakon, lako je dobiti CNF iz datog DNF-a.

Dakle, tačna je sljedeća teorema.

Teorema 4 Za bilo koju formulu u algebri logike postoji konjunktivni normalni oblik koji joj je ekvivalentan.

Dokaz ove teoreme pruža način da se konstruiše konjunktivni normalni oblik za bilo koju formulu u algebri logike.

Primjer 4 Pronađite disjunktivnu i konjunktivnu normalnu formu za sljedeću formulu: .

Koristeći zakon , isključiti znak. Dobijamo formulu.

Koristeći De Morganov zakon, dobijamo formulu . Otvaranjem zagrada dobijamo disjunktivni normalni oblik

Da biste dobili konjunktivni normalni oblik, primijenite formulu distributivni zakon, dobijamo:

Posljednji izraz je konjunktivni normalni oblik. Budući da i , rezultirajući CNF je ekvivalentan sljedećem CNF:

Među svim normalnim formulama ove formule, ističemo savršeni normalni oblik, i disjunktivni i konjunktivni. Uzimajući u obzir dekompoziciju (3), lako je vidjeti da je savršena disjunktivna normalna forma formule logičke algebre koja sadrži tačno n različitih varijabli njen disjunktivni normalni oblik u kojem:

1) svi veznici su parno različiti;

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

3) u svakoj konjunkciji ima svih n varijabli.

Koristeći primjer 1, pogledali smo jedan od načina za konstruiranje SDNF-a, zasnovan na sastavljanju tablice istinitosti. Sljedeća metoda konstrukcije SDNF-a zasniva se na primjeni zakona logičke algebre.

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

Koristeći to , dobijamo . S obzirom na De Morganove zakone i dvostruku negaciju, dobili smo disjunktivni normalni oblik. Ovaj DNF je ekvivalentan formuli.

Proširujući zagrade, dobijamo: .

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

Uzimajući u obzir dekompoziciju (3.6), lako je vidjeti da je savršena konjunktivna normalna forma formule logičke algebre koja sadrži tačno n različitih varijabli, postoji njegov konjunktivni normalni oblik, u kojem:

1) sve disjunkcije su po paru različite;

2) svaka disjunkcija sadrži tačno n pojmova identično je istinita ako za sve vrijednosti varijabli koje su u njoj uključene poprima vrijednost istinito.

Primjeri identično istinitih formula su formule:

identično lažno, ako za sve vrijednosti varijabli uključenih u njega, uzima vrijednost laž.

Primjeri identično lažnih formula su formule:

Algebarska formula logike se obično naziva izvodljivo, ako za neke vrijednosti varijabli uključenih u njega uzima vrijednost istinito.

Primjeri izvršnih formula su sljedeće formule:

U algebri logike možete postaviti sljedeći zadatak: označite metodu (algoritam) koja vam omogućava da za svaku formulu u algebri logike saznate da li je identično istinita ili ne. Zadatak se zove rješavanje problema.

Razmotrimo sljedeća dva načina rješavanja ovog problema.

Metoda 1 (tabela) Da bi se utvrdilo da li je data formula identično istinita ili ne, dovoljno je sastaviti njenu tabelu istinitosti.

Štaviše, ova metoda, iako pruža osnovno rješenje problema rješivosti, prilično je glomazna.

Metoda 2 zasniva se na svođenju formula na normalni oblik.

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

Doista, ako svaka disjunkcija u konjunktivnom normalnom obliku sadrži varijablu zajedno sa svojom negacijom, tada su sve disjunkcije jednake 1, jer , . Iz toga slijedi da je CNF identično istinit.

Neka sada ova formula bude identično tačna, i neka postoji određena disjunkcija u CNF-u ove formule. Pretpostavimo da ova disjunkcija ne sadrži varijablu zajedno sa svojom negacijom. U ovom slučaju možemo dati vrijednost 0 svakoj varijabli koja nije pod predznakom negacije, a vrijednost 1 svakoj varijabli koja je pod predznakom negacije, nakon naznačene zamjene, sve disjunkcije će postati jednake 0, dakle, formula nije identično tačna. Imamo kontradikciju.

Primjer 7 Saznajte da li je formula identično istinita

Koristeći to , dobijamo .

Primjenom zakona distributivnosti dobijamo CNF:

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

Slično prethodnoj teoremi, dokazana je teorema:

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

Proširenje Booleovih funkcija u varijable. - koncept i vrste. Klasifikacija i karakteristike kategorije "Proširenje Booleovih funkcija u varijable." 2017, 2018.