Neka bude neki set K, koji se sastoji od konačnog broja Booleovih funkcija. Superpozicija funkcija iz ovog skupa su nove funkcije dobivene primjenom konačnog broja dviju operacija;

možete preimenovati bilo koju varijablu uključenu u funkciju iz K;

umjesto bilo koje varijable možete staviti funkciju iz skupa K ili prethodno formirana superpozicija.

Superpozicija se također naziva složena funkcija.

Primjer 7. 1. Ako je dana jedna funkcija x|g(Schaefferov potez), tada će njegove superpozicije biti sljedeće funkcije x|x,x|(x|y),x|(y|z) itd.

Zatvaranjem skup funkcija iz K naziva se skup svih superpozicija. Klasa funkcije K nazvao zatvoreno, ako se njegovo zatvaranje poklapa sa samim sobom.

Skup funkcija se zove potpuna, ako se njegovo zatvaranje poklapa sa svim logičkim funkcijama. Drugim riječima, potpuni skup je skup takvih funkcija kroz koje se mogu izraziti sve druge Booleove funkcije.

Kompletan skup funkcija koji nije redundantan naziva se baza("neredundantno" znači da ako se neka funkcija ukloni iz skupa, taj skup više neće biti potpun).

Primjer 7.2. Konjunkcija, disjunkcija i negacija su potpuni skup (u to smo se uvjerili u 5. odjeljku), ali nisu osnova, jer je taj skup suvišan, jer pomoću De Morganovih pravila može se ukloniti konjunkcija ili disjunkcija. Bilo koja funkcija može se prikazati kao Zhegalkinov polinom (odjeljak 6). Jasno je da su funkcije konjunkcija, zbrajanje modulo 2 i konstante 0 i 1 potpuni skup, ali te četiri funkcije također nisu baza, jer je 1+1=0, pa se stoga konstanta 0 može isključiti iz cjelovitog skupa. skup (za konstruiranje polinoma potrebna je Zhegalkinova konstanta 0 jer izraz “1+1” nije Zhegalkinov polinom).

Lako je vidjeti da je jedan od načina provjere potpunosti nekog skupa DO je provjeriti mogu li se funkcije iz ovog skupa koristiti za izražavanje funkcija drugog kompletnog skupa (možete provjeriti da funkcije iz DO može se izraziti konjunkcija i negacija ili disjunkcija i negacija.

Postoje funkcije takve da je jedna takva funkcija i sama baza (ovdje je dovoljno provjeriti samo cjelovitost; očita je neredundancija). Takve funkcije se nazivaju Schefferove funkcije. Ovaj naziv je zbog činjenice da je Schaefferov udarac osnova. Prisjetimo se da je Schaefferov prost definiran sljedećom tablicom istine:

Budući da je očito, tj. negacija je superpozicija Schaefferovog poteza, a disjunkcija tada , Schaefferov udar je sam po sebi osnova. Isto tako, Peirceova strelica je Schefferova funkcija (učenici to mogu sami provjeriti). Za funkcije od 3 ili više varijabli postoji mnogo Shefferovih funkcija (naravno, izražavanje drugih Booleovih funkcija kroz Shefferovu funkciju velikog broja varijabli je teško, pa se rijetko koriste u tehnici).

Imajte na umu da se računalni uređaj najčešće temelji na punom skupu funkcija (često na bazama). Ako se uređaj temelji na konjunkciji, disjunkciji i negaciji, onda je za te uređaje važan problem minimiziranja DNF-a; Ako se uređaj temelji na drugim funkcijama, tada je korisno imati mogućnost algoritamskog minimiziranja izraza kroz te funkcije.

Prijeđimo sada na pojašnjavanje potpunosti specifičnih skupova funkcija. Da bismo to učinili, navodimo 5 najvažnijih klasa funkcija:

• T 0 je skup svih onih logičkih funkcija koje uzimaju vrijednost 0 na nultom skupu ( T 0 je klasa funkcije, očuvanje 0);
• T 1 je skup svih logičkih funkcija koje uzimaju vrijednost 1 na skupu jedinica ( T 1 je klasa funkcija, jedinica za očuvanje) (imajte na umu da je broj funkcija iz P varijable koje pripadaju klasama T 0 i T 1 jednake su 2 2n-1);
• L- Razred linearni funkcije, tj. funkcije za koje Zhegalkinov polinom sadrži samo prve stupnjeve varijabli;
• M- Razred monoton funkcije. Opišimo klasu ovih funkcija pobliže. Neka budu 2 kompleta P varijable: s1 = (x 1, x 2,..., x n)

s 1 = ( x 1 , x 2 , … , x n) i s 2 = (g 1 , g 2, … , y p). Reći ćemo da skup s 1 je manji od skupa s 2 (s 1 £ s 2 ), ako su svi x i £ y i .Očito, nisu svi setovi izPvarijable su međusobno usporedive (na primjer, kadan = 2 skupovi (0,1) i (1,0) nisu međusobno usporedivi). Funkcija odPvarijable se nazivajumonoton, ako na manjem skupu uzima manju ili jednaku vrijednost. Naravno, ove se nejednakosti trebaju testirati samo na usporedivim skupovima. Jasno je da su neusporedivi skupovi oni kod kojih u jednom skupu postoje neke koordinate tipa (0,1), au drugom (1,0) na odgovarajućim mjestima (u diskretnoj matematici monotone funkcije su kao “monotono rastuće”). funkcije”, “monotono opadajuće” funkcije ovdje nisu razmatrane).

Primjer. U sljedećoj tablici funkcije f 1 ,f 2 su monotone funkcije, a funkcije f 3 ,f 4 - Ne.

Prirodni poredak varijabli je osiguran činjenicom da ako je neki skup manji od drugog skupa, onda se nužno nalazi u tablici istinitosti viši“veći” set. Zato ako je u tablici istine()na vrhu su nule,a zatim jedinice,onda je ova funkcija definitivno monotona.Međutim, moguće su inverzije, tj. jedan dolazi ispred nekih nula, ali funkcija je još uvijek monotona(u ovom slučaju skupovi koji odgovaraju "gornjoj" i "donjoj" nuli trebaju biti neusporediv; može se provjeriti da funkcija dana tablicom istine s prirodnim redoslijedom skupa varijabli(00010101), je monoton);

Teorema .T funkcijske klase 0 ,T 1 ,L,M,S zatvoreno.

Ova tvrdnja izravno proizlazi iz definicije samih ovih klasa, kao i iz definicije zatvorenosti.

U teoriji Booleovih funkcija vrlo je važan sljedeći Postov teorem.

Postov teorem .Da bi neki skup funkcija K bio potpun, potrebno je i dovoljno da sadrži funkcije koje ne pripadaju ni jednoj od klasa T 0 ,T 1 ,L,M,S.

Imajte na umu da Što nužnost ovaj izjave očito Tako Kako Ako to je sve funkcije iz novačenje DO uključeno V jedan iz navedeni razredi, Da I svi superpozicije, A Sredstva, I kratki spoj novačenje uključeno bi V ovaj Klasa I Klasa DO Ne mogao biti puna.

Adekvatnost ovaj izjave je dokazano dovoljno teško, Zato nije prikazano ovdje.

Iz ovog teorema slijedi prilično jednostavan način određivanja potpunosti određenog skupa funkcija. Za svaku od ovih funkcija utvrđuje se pripadnost gore navedenim klasama. Rezultati se unose u tzv Post stol(u našem primjeru ova tablica je sastavljena za 4 funkcije, a znak "+" označava da funkcija pripada odgovarajućoj klasi, znak "-" znači da funkcija nije uključena u nju).

Prema Postovom teoremu, skup funkcija bit će potpun ako i samo ako u svakom stupcu Postove tablice postoji barem jedan minus. Dakle, iz gornje tablice proizlazi da ove 4 funkcije čine cjelovit skup, ali te funkcije nisu osnova. Od ovih funkcija možete formirati 2 baze: f 3 ,f 1 I f 3 ,f 2. Potpuni skupovi su svi skupovi koji sadrže neku bazu.

Iz Postove tablice izravno proizlazi da broj baznih funkcija ne može biti veći od 5. Nije teško dokazati da je zapravo taj broj manji ili jednak 4.

Neka postoje 2 funkcije:

: A→B i g: D→F

Neka je područje definicije D funkcije g uključeno u područje vrijednosti funkcije f (DB). Zatim možete definirati novu funkciju - superpozicija (sastav, složena funkcija) funkcije f i g: z= g( (x)).

Primjeri. f(x)=x 2 , g(x)=e x. f:R→R, g:R→R .

(g(x))=e 2x , g((x))=.

Definicija

Neka postoje dvije funkcije. Tada je njihov sastav funkcija definirana jednakošću:

Svojstva sastava

Kompozicija je asocijativna:

Ako F= id x- identično preslikavanje na x, to je

.

Ako G= id Y- identično preslikavanje na Y, to je

.

Dodatna svojstva

Prebrojivi i neprebrojivi skupovi.

Dva konačna skupa sastoje se od jednakog broja elemenata ako se među tim skupovima može uspostaviti korespondencija jedan prema jedan. Broj elemenata konačnog skupa je kardinalnost skupa.

Za beskonačan skup može se uspostaviti korespondencija jedan na jedan između cijelog skupa i njegovog dijela.

Najjednostavniji od beskonačnih skupova je skup N.

Definicija. Skupovi A i B nazivaju se ekvivalent(AB), ako se između njih može uspostaviti korespondencija jedan na jedan.

Ako su dva konačna skupa ekvivalentna, tada se sastoje od istog broja elemenata.

Ako su skupovi A i B koji su međusobno ekvivalentni proizvoljni, onda kažu da A i B imaju isto vlast. (snaga = ekvivalencija).

Za konačne skupove pojam kardinalnosti podudara se s pojmom broja elemenata skupa.

Definicija. Skup se zove prebrojiv, ako je moguće uspostaviti korespondenciju jedan na jedan između njega i skupa prirodnih brojeva. (To jest, prebrojiv skup je beskonačan, ekvivalentan skupu N).

(To jest, svi elementi prebrojivog skupa mogu biti numerirani).

Svojstva jednakosti odnosa snaga.

1) AA - refleksivnost.

2) AB, zatim BA – simetrija.

3) AB i BC, tada je AC tranzitivnost.

Primjeri.

1) n→2n, 2,4,6,… - parni prirodni

2) n→2n-1, 1,3,5,… - neparni prirodni.

Svojstva prebrojivih skupova.

1. Beskonačni podskupovi prebrojivog skupa su prebrojivi.

Dokaz. Jer A je prebrojiv, tada je A: x 1, x 2,... - preslikao A u N.

VA, V: →1,→2,… - dodijelio svaki element od B prirodnom broju, tj. preslikao B u N. Stoga je B prebrojiv. itd.

2. Unija konačnog (prebrojivog) sustava prebrojivih skupova je prebrojiva.

Primjeri.

1. Skup cijelih brojeva Z je prebrojiv, jer skup Z može se predstaviti kao unija prebrojivih skupova A i B, gdje A: 0,1,2,.. i B: -1,-2,-3,...

2. Puno naredio parovi ((m,n): m,nZ) (tj. (1,3)≠(3,1)).

3 (!) . Skup racionalnih brojeva je prebrojiv.

Q=. Može se uspostaviti korespondencija jedan na jedan između skupa nesvodivih razlomaka Q i skupa uređenih parova:

Da. skup Q je ekvivalentan skupu ((p,q))((m,n)).

Skup ((m,n)) – skup svih uređenih parova – je prebrojiv. Prema tome, skup ((p,q)) je prebrojiv, pa je stoga Q prebrojiv.

Definicija. Iracionalan broj je proizvoljna beskonačna decimala neperiodični razlomak, tj.  0 , 1  2 …

Skup svih decimalnih razlomaka čini skup pravi (stvarni) brojevi.

Skup iracionalnih brojeva je neprebrojiv.

Teorem 1. Skup realnih brojeva iz intervala (0,1) je neprebrojiv skup.

Dokaz. Pretpostavimo suprotno, tj. da se svi brojevi u intervalu (0,1) mogu numerirati. Zatim, zapisujući te brojeve u obliku beskonačnih decimalnih razlomaka, dobivamo niz:

x 1 =0,a 11 a 12 ...a 1n ...

x 2 =0,a 21 a 22 …a 2n …

…………………..

x n =0,a n 1 a n 2 …a nn …

……………………

Razmotrimo sada realni broj x=0,b 1 b 2 …b n…, gdje je b 1 bilo koji broj različit od a 11, (0 i 9), b 2 je bilo koji broj različit od a 22, (0 i 9 ) ,…, b n - bilo koji broj različit od a nn, (0 i 9).

Da. x(0,1), ali xx i (i=1,…,n) jer inače, b i =a ii . Došli smo do kontradikcije. itd.

Teorem 2. Svaki interval realne osi je neprebrojiv skup.

Teorem 3. Skup realnih brojeva je neprebrojiv.

O svakom skupu koji je jednak skupu realnih brojeva kaže se da jest kontinualna snaga(latinski continuum - neprekidan, kontinuiran).

Primjer. Pokažimo da interval ima snagu kontinuuma.

Funkcija y=tg x: →R prikazuje interval na cijelom brojevnom pravcu (graf).

Superpozicija funkcija

Superpozicija funkcija f1, ..., fm je funkcija f dobivena supstitucijom ovih funkcija jedne u drugu i preimenovanjem varijabli.

Neka postoje dva preslikavanja i, štoviše, neprazan skup. Tada je superpozicija ili kompozicija funkcija funkcija definirana jednakošću za svaki.

Područje definiranja superpozicije je skup.

Funkcija se naziva vanjska i unutarnja funkcija za superpoziciju.

Funkcije predstavljene kao sastav "jednostavnijih" nazivamo složenim funkcijama.

Primjeri korištenja superpozicije su: rješavanje sustava jednadžbi supstitucijom; nalaženje izvoda funkcije; pronalaženje vrijednosti algebarskog izraza zamjenom vrijednosti navedenih varijabli u njega.

Rekurzivne funkcije

Rekurzija je metoda definiranja funkcije u kojoj se vrijednosti definirane funkcije za proizvoljne vrijednosti argumenata izražavaju na poznati način kroz vrijednosti definirane funkcije za manje vrijednosti argumenata.

Primitivno rekurzivna funkcija

Definicija pojma primitivne rekurzivne funkcije je induktivna. Sastoji se od specificiranja klase osnovnih primitivnih rekurzivnih funkcija i dva operatora (superpozicija i primitivna rekurzija) koji vam omogućuju konstruiranje novih primitivnih rekurzivnih funkcija na temelju postojećih.

Osnovne primitivne rekurzivne funkcije uključuju sljedeće tri vrste funkcija:

Null funkcija je funkcija bez argumenata koja uvijek vraća 0 .

Sukcesivna funkcija jedne varijable koja povezuje bilo koji prirodni broj sa sljedećim prirodnim brojem.

Funkcije, gdje, od n varijabli, preslikavanje bilo kojeg uređenog skupa prirodnih brojeva u broj iz tog skupa.

Operatori supstitucije i primitivne rekurzije definirani su na sljedeći način:

Operator superpozicije (ponekad operator supstitucije). Neka je funkcija od m varijabli i neka je uređen skup funkcija, svaka s varijablama. Tada je rezultat superpozicije funkcija u funkciju funkcija varijabli koja pridružuje broj bilo kojem uređenom skupu prirodnih brojeva.

Operator primitivne rekurzije. Neka je funkcija n varijabli i neka je funkcija varijabli. Tada se rezultat primjene operatora primitivne rekurzije na par funkcija naziva funkcija varijable oblika;

U ovoj definiciji, varijabla se može shvatiti kao brojač iteracija, -- kao početna funkcija na početku iterativnog procesa koji proizvodi određeni slijed funkcija varijable počevši s, i -- kao operator koji kao ulaz varijable uzima broj koraka iteracije, funkcija u danom koraku iteracije i vraća funkciju u sljedećem koraku iteracije.

Skup primitivnih rekurzivnih funkcija je minimalni skup koji sadrži sve osnovne funkcije i zatvoren je prema navedenim operatorima supstitucije i primitivne rekurzije.

U terminima imperativnog programiranja, primitivne rekurzivne funkcije odgovaraju programskim blokovima koji koriste samo aritmetičke operacije, kao i uvjetni operator i operator aritmetičke petlje (operator petlje u kojem je broj ponavljanja poznat na početku petlje). Ako programer počne koristiti operator petlje while, u kojem je broj ponavljanja unaprijed nepoznat i, u načelu, može biti beskonačan, tada prelazi u klasu djelomično rekurzivnih funkcija.

Istaknimo niz dobro poznatih aritmetičkih funkcija koje su primitivno rekurzivne.

Funkcija zbrajanja dvaju prirodnih brojeva () može se smatrati primitivno rekurzivnom funkcijom dviju varijabli, dobivenom primjenom operatora primitivne rekurzije na funkcije i, od kojih je druga dobivena zamjenom glavne funkcije u glavnu funkciju:

Množenje dvaju prirodnih brojeva može se smatrati primitivno rekurzivnom funkcijom dviju varijabli, dobivenom primjenom operatora primitivne rekurzije na funkcije i, od kojih je druga dobivena supstitucijom osnovnih funkcija u funkciju zbrajanja:

Simetrična razlika (apsolutna vrijednost razlike) dvaju prirodnih brojeva () može se smatrati primitivno rekurzivnom funkcijom dviju varijabli, dobivenom primjenom sljedećih supstitucija i primitivnih rekurzija:

Funkcija izgradnje

Nudimo vam uslugu za izradu grafova funkcija na mreži, čija sva prava pripadaju tvrtki Desmos. Koristite lijevi stupac za unos funkcija. Možete unijeti ručno ili pomoću virtualne tipkovnice na dnu prozora. Da biste povećali prozor s grafikonom, možete sakriti lijevi stupac i virtualnu tipkovnicu.

Prednosti online crtanja grafikona

• Vizualni prikaz unesenih funkcija
• Izgradnja vrlo složenih grafikona
• Konstrukcija grafova navedenih implicitno (na primjer, elipsa x^2/9+y^2/16=1)
• Mogućnost spremanja grafikona i primanja veze na njih, koja postaje dostupna svima na Internetu
• Upravljanje ljestvicom i bojom linija
• Mogućnost iscrtavanja grafova po točkama, korištenjem konstanti
• Iscrtavanje nekoliko grafova funkcija istovremeno
• Crtanje u polarnim koordinatama (koristite r i θ(\theta))

S nama je jednostavno izgraditi grafikone različite složenosti online. Izgradnja se vrši trenutno. Usluga je tražena za pronalaženje točaka presjeka funkcija, za prikazivanje grafova za njihovo daljnje premještanje u Word dokument kao ilustracije pri rješavanju problema, te za analizu karakteristika ponašanja grafova funkcija. Optimalan preglednik za rad s grafikonima na ovoj web stranici je Google Chrome. Ispravan rad nije zajamčen kada koristite druge preglednike.

Diskretni logički uređaji s jednim ciklusom (ne sadrže memorijske elemente) implementiraju na izlazu određeni skup funkcija logičke algebre `F m =(F 1 ,F 2 ,…,F m), koji u svakom trenutku vremena ovise samo o stanju ulaza uređaja `x n =(x 1 ,x 2 ,…,x n): `F m = `F m(`x n). U praksi se takvi uređaji projektiraju i proizvode od zasebnih nedjeljivih elemenata koji ostvaruju određeni skup (sustav) ( f) elementarne funkcije algebre povezivanjem izlaza jednih elemenata s ulazima drugih.

Pri projektiranju logičkih uređaja relevantna su sljedeća pitanja.

1. Zadan je sustav elementarnih funkcija ( f). Što su izlazne funkcije F i može se dobiti pomoću funkcija iz ( f}?

2. Skup izlaznih Booleovih funkcija ( F) (konkretno, jednako cijelom skupu funkcija algebre logike R 2). Kakav bi trebao biti početni sustav elementarnih funkcija ( f), pružajući mogućnost dobivanja na izlazu bilo koje funkcije skupa ( F}?

Za razuman odgovor na ova pitanja koriste se pojmovi superpozicije, zatvorenosti i potpunosti sustava funkcija.

Definicija. Razmotrimo skup logičkih konektora ( F), koji odgovara nekom sustavu funkcija ( f} . Superpozicija završena{f) je svaka funkcija j koja se može realizirati formulom nad ( F}.

U praksi se superpozicija može prikazati kao rezultat zamjene funkcija iz ( f) kao argumenti funkciji iz istog skupa.

Primjer 1. Razmotrimo sustav funkcija ( f} = {f 1 (x) =`x, f 2 (x,y)= x&y, f 3 (x,y)=xÚ y). Zamjena u funkciju f 3 (x,y) umjesto prvog argumenta x funkcija f 1 (x), umjesto drugog - f 2 (x,y), dobivamo superpoziciju h(x,y)=f 3 (f 1 (x),f 2 (x,y))=`xÚ x& na. Fizička izvedba zamjene prikazana je na slici 1.18.

Definicija. Neka M-određeni skup funkcija logičke algebre( P 2). Skup svih superpozicija preko M nazvao kratki spoj postavlja M i označava se sa [ M]. Primanje [ M] prema izvornom skupu M nazvao operacija zatvaranja. Gomila M nazvao funkcionalno zatvorena klasa, Ako [ M] = M. Podskup mÍ M nazvao funkcionalno cjelovit sustav u M, Ako [ m] = M.

Zatvaranje [ M] predstavlja cijeli skup funkcija koje se mogu dobiti iz M primjenom operacije superpozicije, tj. sve moguće zamjene.

Bilješke. 1. Očito, svaki sustav funkcija ( f) sam po sebi funkcionalno potpun.

2 . Bez gubitka općenitosti, možemo pretpostaviti da funkcija identiteta f(x)=x, koji ne mijenja istinite vrijednosti varijabli, u početku je dio bilo kojeg sustava funkcija.

Primjer 2. Za sustave funkcija o kojima se raspravlja u nastavku ( f) učinite sljedeće:

1) pronađite zatvaranje [ f],

2) saznati je li sustav ( f) zatvoreni razred,

3) pronaći funkcionalno potpune sustave u ( f}.

Riješenje.

ja. ( f}={0} . Prilikom zamjene funkcije ( fº 0) primamo ga u sebe, tj. ne stvaraju se nove funkcije. Iz čega slijedi: [ f] = {f). Razmatrani sustav je funkcionalno zatvorena klasa. Funkcionalno cjelovit sustav u njemu je jedan i jednak cjelini ( f}.

II. ( f} = {0,Ø } . Zamjena Ø (Ø x) daje identičnu funkciju koja formalno ne proširuje izvorni sustav. Međutim, zamjenom Ø (0) dobivamo identičnu jedinicu - novu funkciju koje nije bilo u izvornom sustavu: Ø (0)=1 . Primjena svih ostalih zamjena ne dovodi do pojave novih funkcija, na primjer: ØØ 0 = 0, 0 (Ø x)=0.

Stoga je korištenje operacije superpozicije omogućilo dobivanje šireg skupa funkcija od izvornog [ f]=(0,Ø ,1). Ovo podrazumijeva striktan unos: ( f} Ì [ f]. Izvorni sustav ( f) nije funkcionalno zatvorena klasa. Osim samog sustava ( f) u njemu nema drugih funkcionalno cjelovitih sustava, jer u slučaju njegovog sužavanja s jedne funkcije f= 0 se ne može negirati supstitucijom, a identična nula ne može se dobiti samo iz funkcije negacije.

III. ( f) = (& ,Ú ,Ø ). Zatvaranje ovog sustava je cijeli skup funkcija algebre logike P 2, budući da se formula bilo koje od njih može prikazati kao DNF ili CNF, koja koristi elementarne funkcije ( f) = (& ,Ú ,Ø). Ova činjenica je konstruktivan dokaz cjelovitosti razmatranog sustava funkcija u P 2: [f]=P 2 .

Budući da je u P 2 sadrži beskonačan broj drugih funkcija osim ( f) = (& ,Ú ,Ø ), onda ovo implicira striktno pojavljivanje: ( f}Ì[ f]. Razmatrani sustav nije funkcionalno zatvorena klasa.

Osim samog sustava, funkcionalno će biti dovršeni i podsustavi ( f) 1 = (& ,Ø ) i ( f) 2 = (Ú ,Ø ). To proizlazi iz činjenice da se pomoću De Morganovih pravila funkcija logičkog zbrajanja Ú može izraziti kroz (& , Ø), a funkcija logičkog množenja & kroz (Ú, Ø):

(x & na) = Ø (` xÚ` na), (x Ú na) = Ø ( x &`na).

Ostali funkcionalno cjeloviti podsustavi u ( f) Ne

Provjera potpunosti funkcionalnog podsustava ( f) 1 M ( f)u cijelom sustavu ( f) može se proizvesti kombiniranjem ( f) 1 drugom, očito završeno u ( f)sustav.

Nepotpunost podsustava ( f) 1 u ( f) može se provjeriti dokazivanjem striktne pojave [ f 1 ] M [ f].

Definicija. Podskup mÍ M nazvao funkcionalna osnova(osnova)M sustavi, Ako [ m] = M, a nakon eliminiranja bilo koje funkcije iz njega, skup preostalih nije potpun u M .

Komentar. Osnove sustava funkcija (f) su svi njegovi funkcionalno cjeloviti podsustavi (f) 1, koji se ne može reducirati bez gubitka cjelovitosti (f).

Primjer 3. Za sve sustave razmatrane u primjeru 2 pronađite baze.

Riješenje.U slučajevima 1 i 2 samo su sami sustavi funkcionalno cjeloviti i nemoguće ih je suziti. Prema tome, oni su i baze.

U slučaju 3 postoje dva funkcionalno potpuna u ( f)podsustavi ( f) 1 = (&,Ø ) i ( f) 2 =(Ú,Ø ), koji se ne može reducirati bez gubitka potpunosti. Oni će biti osnova sustava ( f} = {&,Ú,Ø}.

Definicija. Neka sustav ( f) je zatvorena klasa. Njegov podskup ( f) 1 M ( f) se zovu razred juniora u{f), ako ( f) 1 nije potpun u ( f} ([f 1 ] M [ f]), a za bilo koju funkciju j iz sustava ( f), nije uključeno u ( f) 1 (jO( f} \ {f) 1) točno: [ jÈ { f} 1 ] = [f], tj. dodavanje jk ( f) 1 čini ga potpunim u ( f} .

Zadaci

1. Provjerite zatvorenost skupova funkcija:

a) (Ø); b) (1, Ø); c) ((0111); (10));d) ((11101110); (0110));d) ((0001); (00000001); (00000000000000001); … ).

2. Provjerite cjelovitost funkcionalnih sustava u P 2:

a) (0,Ø); b) ((0101) , (1010) ); V ); d) ((0001) , (1010) ).

3. Pronađite zatvorenost sustava funkcija i njegovu osnovu:

a) (0, 1, Ø); b) ((1000) , (1010), (0101) ); c) ((0001) , (1110), (10) ); d) ((1010) , (0001), (0111) ).

1.10.2 Funkcije koje čuvaju konstante. Klase T 0 i T 1

Definicija. Funkcija f(`x n) sprema 0 ako f(0,..., 0) = 0. Funkcija f(`x n) sprema 1 ako f(1, ... , 1) = 1.

Puno značajki n varijable koje pohranjuju 0 i 1 označene su redom, T 0 n I T 1 n. Svi skupovi funkcija logičke algebre koji čuvaju 0 i 1 , označiti T 0 I T 1 . Svaki od skupova T 0 i T 1 je zatvoreni predkompletni razred u R 2 .

Od elementarnih funkcija do T 0 i T 1 su istovremeno uključeni, na primjer, & i Ú. Pripadnost bilo koje funkcije klasama T 0 , T 1 može se provjeriti prvom i posljednjom vrijednošću njegovog vektora vrijednosti u tablici istine ili izravnom zamjenom nula i jedinica u formulu prilikom analitičkog određivanja funkcije.

Definicija.Duplikat je supstitucija u kojoj se ista varijabla supstituira u funkciju umjesto nekoliko neovisnih varijabli. U ovom slučaju, vrijednosti varijabli u skupovima koji su prethodno uzimali vrijednosti neovisno jedna o drugoj uvijek će biti iste.

ZADACI

1. Provjerite članstvo u razredu T 0 I T 1 funkcije:

a) generalizirano zbrajanje, b) generalizirano množenje, c) konstante, d) xyÚ yz, d) x® na® xy e) xÅ na, i)( x 1 Å … Å x n) ® ( g 1 Å … Å g m) na n,mÎ N.

2. Dokažite zatvorenost svake klase T 0 I T 1 .

3. Dokažite da ako f(`x n) Ï T 0, onda iz njega dupliciranjem zamjene možete dobiti konstantu 1 ili negaciju.

4. Dokažite da ako f(`x n) Ï T 1 , onda iz njega, dupliciranjem zamjene, možete dobiti konstantu 0 ili negaciju.

5. Dokažite predpotpunost svake od klasa T 0 I T 1 (na primjer, smanjenjem proširenog sustava na ( f} = {& ,Ú ,Ø }).

6. Pronađite snagu klasa T 0 n I T 1 n.