Susipažinkime su funkcijų superpozicijos (arba primetimo) sąvoka, kurią sudaro funkcijos pakeitimas kitu argumentu, o ne duotosios funkcijos argumentu. Pavyzdžiui, funkcijų superpozicija suteikia funkciją, o funkcijos gaunamos panašiai

Apskritai, tarkime, kad funkcija yra apibrėžta tam tikrame domene, o funkcija yra apibrėžta domene ir visos jos reikšmės yra domene, tada kintamasis z, kaip sakoma, per y, pats yra funkcija

Duodami tam tikrą reikšmę, jie pirmiausia suranda ją atitinkančią reikšmę y (pagal taisyklę, apibūdinamą ženklu), o tada nustato atitinkamą reikšmę y (pagal taisyklę

apibūdinamas ženklu, jo reikšmė laikoma atitinkančia pasirinktą x. Iš funkcijos arba sudėtingos funkcijos gaunama funkcija yra funkcijų superpozicijos rezultatas

Prielaida, kad funkcijos reikšmės neperžengia Y srities, kurioje funkcija apibrėžta, ribų, yra labai reikšminga: jei jos praleisite, gali kilti absurdas. Pavyzdžiui, darant prielaidą, kad galime atsižvelgti tik į tas x reikšmes, kurioms kitaip išraiška nebūtų prasminga.

Manome, kad čia naudinga pabrėžti, kad funkcijos, kaip kompleksinės, apibūdinimas nėra susijęs su z funkcinės priklausomybės nuo x pobūdžiu, o tik su šios priklausomybės patikslinimo būdu. Pavyzdžiui, tegul y yra Tada

Čia funkcija buvo nurodyta kaip sudėtinga funkcija.

Dabar, kai funkcijų superpozicijos sąvoka yra visiškai suprantama, galime tiksliai apibūdinti paprasčiausias iš tų funkcijų klasių, kurios yra tiriamos analizėje: tai pirmiausia yra pirmiau išvardytos elementarios funkcijos, o tada visos tos, kurios gaunamos iš jų. naudojant keturias aritmetines operacijas ir superpozicijas , paeiliui taikomas baigtinis skaičius kartų. Sakoma, kad jie išreiškiami per elementarumą galutiniu pavidalu; kartais jie dar vadinami elementariais.

Vėliau, įvaldę sudėtingesnį analitinį aparatą (begalinės eilutės, integralai), susipažinsime su kitomis funkcijomis, kurios taip pat atlieka svarbų vaidmenį analizėje, bet jau peržengia elementariųjų funkcijų klasę.

Tebūnie funkcija f(x 1 , x 2 , ... , x n) ir funkcijos

tada iškviesime funkciją funkcijos superpozicija f(x 1 , x 2 , ... , x n) ir funkcijas .

Kitaip tariant: tegul F = ( f j ) - loginės algebros funkcijų rinkinys, nebūtinai baigtinis. Funkcija f vadinama funkcijų iš aibės F superpozicija arba funkcija virš F, jei ji gaunama iš funkcijos pakeitus vieną ar kelis jos kintamuosius funkcijomis iš aibės F.

Pavyzdys.

Tegu pateikiamas funkcijų rinkinys

F = (f 1 (x 1), f 2 (x 1, x 2, x 3), f 3 (x 1, x 2)).

Tada funkcijų superpozicijos iš F bus, pavyzdžiui, funkcijos:

j 1 (x 2 , x 3) = f 3 (f 1 (x 2), f 1 (x 3));

j 2 (x 1 , x 2) = f 2 (x 1 , f 1 (x 1), f 3 (x 1, x 2)).

Perfect DNF – funkcijų superpozicija iš rinkinio

. ð

Apibrėžimas.

Funkcijų sistema vadinama pilnas, jei naudojant superpozicijos ir kintamųjų keitimo operacijas, iš šios sistemos funkcijų galima gauti bet kurią logikos algebros funkciją. ð

Mes jau turime tam tikrą pilnų sistemų rinkinį:

;

Nes ;

Nes ;

(x+y, xy, 1). ð

Kaip galime nustatyti sąlygas, kuriomis sistema yra baigta? Su užbaigtumo samprata glaudžiai susijusi uždaros klasės samprata.

Uždaros klasės.

Vadinama logikos algebros funkcijų aibė (klasė) K uždara klasė, jei jame yra visos funkcijos, gautos iš K superpozicijos ir kintamųjų kaitos operacijomis, ir nėra jokių kitų funkcijų.

Tegu K yra tam tikras funkcijų poaibis iš P 2 . K uždarymas yra aibė visų Būlio funkcijų, kurias galima pavaizduoti naudojant superpozicijos ir funkcijų kintamųjų kaitos operacijas iš aibės K. Aibės K uždarymas žymimas [K].

Kalbant apie uždarymą, galime pateikti kitus uždarumo ir užbaigtumo apibrėžimus (atitinkančius originalius):

K yra uždara klasė, jei K = [K];

K yra visa sistema, jei [K] = P 2 .

Pavyzdžiai.

* (0), (1) - uždaros klasės.

* Vieno kintamojo funkcijų rinkinys yra uždara klasė.

* - uždara klasė.

* Klasė (1, x+y) nėra uždara klasė.

Pažvelkime į kai kurias svarbiausias uždaras klases.

1. T 0- funkcijų klasė, kuri išsaugo 0.

T 0 pažymėkime visų logikos f(x 1 , x 2 , ... , x n) algebros funkcijų, išsaugančių konstantą 0, klasę, tai yra funkcijas, kurioms f(0, ... , 0 ) = 0.

Nesunku pastebėti, kad yra funkcijų, priklausančių T 0, ir funkcijų, kurios nepriklauso šiai klasei:

0, x, xy, xÚy, x+y О T 0 ;

Iš to, kad Ï T 0, pavyzdžiui, išplaukia, kad jis negali būti išreikštas disjunkcija ir konjunkcija.

Kadangi funkcijos f iš klasės T 0 lentelėje pirmoje eilutėje yra reikšmė 0, tada funkcijoms iš T 0 galite nustatyti savavališkas reikšmes tik 2 n - 1 kintamųjų reikšmių rinkiniui, tai yra

,

kur yra funkcijų, kurios išsaugo 0 ir priklauso nuo n kintamųjų, rinkinys.

Parodykime, kad T 0 yra uždara klasė. Kadangi xÎT 0 , tai uždarumui pagrįsti pakanka parodyti uždarumą superpozicijos operacijos atžvilgiu, kadangi kintamųjų veikimas yra ypatingas superpozicijos su funkcija x atvejis.

Leisti . Tada užtenka tai parodyti. Pastaroji išplaukia iš lygybių grandinės

2. T 1- funkcijų išsaugojimo klasė 1.

T 1 pažymėkime visų logikos f(x 1, x 2, ... , x n) algebros funkcijų, išsaugančių konstantą 1, klasę, tai yra funkcijas, kurioms f(1, ... , 1 ) = 1.

Nesunku pastebėti, kad yra funkcijų, priklausančių T 1, ir funkcijų, kurios nepriklauso šiai klasei:

1, x, xy, xÚy, xºy О T 1 ;

0, , x+y Ï T 1 .

Iš to, kad x + y Ï T 0, pavyzdžiui, išplaukia, kad x + y negalima išreikšti disjunkcijos ir konjunkcijos terminais.

Rezultatai apie klasę T 0 trivialiai perkeliami į klasę T 1 . Taigi mes turime:

T 1 - uždara klasė;

.

3. L- tiesinių funkcijų klasė.

L pažymėkime visų loginės algebros f(x 1 , x 2 , ... , x n) funkcijų, kurios yra tiesinės, klasę:

Nesunku pastebėti, kad yra funkcijų, priklausančių L, ir funkcijų, kurios nepriklauso šiai klasei:

0, 1, x, x+y, x 1 º x 2 = x 1 + x 2 + 1, = x+1 О L;

Pavyzdžiui, įrodykime, kad xÚy Ï L .

Tarkime, priešingai. Ieškosime xÚy išraiškos tiesinės funkcijos su neapibrėžtais koeficientais forma:

Jei x = y = 0, turime a = 0,

jei x = 1, y = 0, turime b = 1,

jei x = 0, y = 1, turime g = 1,

bet tada, kai x = 1, y = 1, turime 1v 1 ¹ 1 + 1, o tai įrodo funkcijos xy netiesiškumą.

Tiesinių funkcijų klasės uždarumo įrodymas yra gana akivaizdus.

Kadangi tiesinė funkcija vienareikšmiškai nustatoma nurodant koeficiento a 0, ... , a n reikšmes n+1, tai linijinių funkcijų skaičius L (n) funkcijų klasėje, priklausomai nuo n kintamųjų, yra lygus 2 n+1 .

.

4.S- savarankiškų dvigubų funkcijų klasė.

Savaiminių dvigubų funkcijų klasės apibrėžimas grindžiamas vadinamojo dualumo ir dvigubų funkcijų principo vartojimu.

Iškviečiama lygybe apibrėžta funkcija dviguba funkcija .

Akivaizdu, kad dvigubos funkcijos lentelė (su standartine kintamųjų reikšmių rinkinių tvarka) gaunama iš pradinės funkcijos lentelės apverčiant (ty pakeičiant 0 į 1 ir 1 pakeičiant 0) funkcijų reikšmių stulpelį. ir apversdamas.

Tai nesunku pastebėti

(x 1 Ú x 2)* = x 1 Ù x 2,

(x 1 Ù x 2)* = x 1 Ú x 2 .

Iš apibrėžimo matyti, kad (f*)* = f, tai yra, funkcija f yra dviguba f*.

Tegul funkcija išreiškiama naudojant superpoziciją per kitas funkcijas. Kyla klausimas, kaip sukurti formulę, kuri įgyvendina ? Pažymėkime = (x 1, ..., x n) visus skirtingus kintamųjų simbolius, esančius aibėse.

2.6 teorema. Jei funkcija j gaunama kaip funkcijų f, f 1, f 2, ..., f m superpozicija, tai yra

funkcija dviguba superpozicijai yra dvigubų funkcijų superpozicija.

Įrodymas.

j*(x 1,...,x n) = ` f(`x 1 ,...,`x n) =

Teorema įrodyta. ð

Iš teoremos išplaukia dualumo principas: jei formulė A realizuoja funkciją f(x 1 , ... , x n), tai formulė, gauta iš A, pakeitus joje esančias funkcijas jų dvigubosiomis, realizuoja dvigubą funkciją f *(x 1 , ... , xn).

Pažymėkime S visų savaiminių dvigubų funkcijų klasę iš P 2:

S = (f | f* = f )

Nesunku pastebėti, kad yra funkcijų, priklausančių S, ir funkcijų, kurios nepriklauso šiai klasei:

0, 1, xy, xÚy Ï S .

Mažiau trivialus savarankiškos dvigubos funkcijos pavyzdys yra funkcija

h(x, y, z) = xy Ú xz Ú ​​yz;

Naudodami teoremą apie funkciją dvigubą superpoziciją, turime

h*(x, y, z)= (x Ú y)Ù(x Ú z) Ù (y Ù z) = x y Ú x z Ú y z; h = h* ; h О S.

Atliekant dvigubą funkciją, tapatybė galioja

taip ir rinkiniuose ir , kurią vadinsime priešinga, savidualinė funkcija įgauna priešingas reikšmes. Iš to išplaukia, kad dvigubą funkciją visiškai lemia jos reikšmės pirmoje standartinės lentelės eilučių pusėje. Todėl savarankiškų dvigubų funkcijų skaičius funkcijų klasėje S (n), priklausomai nuo n kintamųjų, yra lygus:

.

Dabar įrodykime, kad S klasė uždara. Kadangi xÎS , tai uždarumui pagrįsti pakanka parodyti uždarumą superpozicijos operacijos atžvilgiu, kadangi kintamųjų operacija yra ypatingas superpozicijos su funkcija x atvejis. Leisti . Tada užtenka tai parodyti. Pastarasis montuojamas tiesiogiai:

5. M- monotoninių funkcijų klasė.

Prieš apibrėžiant monotoninės funkcijos sąvoką logikos algebroje, būtina įvesti eilės santykį jos kintamųjų aibėje.

Jie sako, kad rinkinys ateina prieš rinkinį (arba „ne daugiau nei“, arba „mažiau arba lygus“) ir naudokite žymėjimą, jei a i £ b i visiems i = 1, ... , n. Jei ir , tada sakysime, kad aibė yra griežtai prieš aibę (arba „griežtai mažiau“, arba „mažiau nei“), ir naudosime žymėjimą . Aibės ir vadinamos palyginamomis, jei , arba Tuo atveju, kai nė vienas iš šių santykių negalioja, aibės ir vadinamos nepalyginamomis. Pavyzdžiui, (0, 1, 0, 1) £ (1, 1, 0, 1), tačiau aibės (0, 1, 1, 0) ir (1, 0, 1, 0) yra nepalyginamos. Taigi santykis £ (dažnai vadinamas pirmenybės ryšiu) yra aibės B n dalinė tvarka. Žemiau pateikiamos iš dalies užsakytų rinkinių B 2, B 3 ir B 4 diagramos.

Įvestas dalinės tvarkos santykis yra nepaprastai svarbi sąvoka, kuri gerokai peržengia mūsų kurso ribas.

Dabar turime galimybę apibrėžti monotoninės funkcijos sąvoką.

Vadinama loginės algebros funkcija monotoniškas, Jei bet kurių dviejų rinkinių ir Taip, kad , Nelygybė turi . Visų logikos algebros monotoniškų funkcijų aibė žymima M, o visų monotoniškų funkcijų aibė, priklausanti nuo n kintamųjų, žymima M(n).

Nesunku pastebėti, kad yra funkcijų, priklausančių M, ir funkcijų, kurios nepriklauso šiai klasei:

0, 1, x, xy, xÚy О M;

x+y, x®y, xºy Ï M .

Parodykime, kad monotoniškų funkcijų klasė M yra uždara klasė. Kadangi xОМ, tai uždarumui pagrįsti pakanka parodyti uždarumą superpozicijos operacijos atžvilgiu, kadangi kintamųjų veikimas yra ypatingas superpozicijos su funkcija x atvejis.

Leisti . Tada užtenka tai parodyti.

Tegu bus atitinkamai funkcijų j, f 1 , ... , f m kintamųjų aibės, o funkcijos j kintamųjų aibė susideda iš tų ir tik tų kintamųjų, kurie yra funkcijose f 1 , ... , f m . Leisti ir būti du kintamojo reikšmių rinkiniai ir . Šie rinkiniai apibrėžia rinkinius kintamos reikšmės , toks . Dėl funkcijų monotoniškumo f 1 , ... , f m

o dėl funkcijos f monotoniškumo

Iš čia gauname

Monotoninių funkcijų, priklausančių nuo n kintamųjų, skaičius nėra tiksliai žinomas. Apatinę ribą galima lengvai gauti:

kur - yra sveikoji n/2 dalis.

Taip pat paprasčiausiai paaiškėja, kad aukščiau pateiktas įvertinimas yra per didelis:

Šių įverčių patikslinimas yra svarbi ir įdomi šiuolaikinių tyrimų užduotis.

Išsamumo kriterijus

Dabar galime suformuluoti ir įrodyti išsamumo kriterijų (Posto teorema), kuris nustato būtinas ir pakankamas sąlygas funkcijų sistemos užbaigtumui. Išsamumo kriterijaus formuluotę ir įrodymą pateikime keliomis būtinomis lemomis, kurios turi nepriklausomą interesą.

Lemma 2.7. Lemma dėl nesavarankiškos dvigubos funkcijos.

Jei f(x 1 , ... , x n)Ï S , tai iš jo galima gauti konstantą, pakeitus funkcijas x ir `x.

Įrodymas. Kadangi fÏS, tada yra kintamųjų reikšmių rinkinys
=(a 1 ,...,a n) toks, kad

f(`a 1 ,...,`a n) = f(a 1 ,...,a n)

Pakeiskime funkcijos f argumentus:

x i pakeičiamas ,

tai yra, įdėkime ir apsvarstykime funkciją

Taigi, mes gavome konstantą (nors nežinoma, kuri konstanta ji yra: 0 ar 1). ð

Lemma 2.8. Lemma apie nemonotoninę funkciją.

Jei funkcija f(x 1 ,...,x n) yra nemonotoniška, f(x 1 ,...,x n) Ï M, tai iš jos galima gauti neigimą pakeitus kintamuosius ir pakeičiant konstantas 0 ir 1.

Įrodymas. Kadangi f(x 1 ,...,x n) Ï M, tada yra jo kintamųjų reikšmių rinkiniai, , , kad , ir bent vienai reikšmei i, a i< b i . Выполним следующую замену переменных функции f:

x i bus pakeistas

Po tokio pakeitimo gauname vieno kintamojo j(x) funkciją, kuriai turime:

Tai reiškia, kad j(x)=`x. Lema įrodyta. ð

Lemma 2.9. Lemma apie netiesinę funkciją.

Jei f(x 1 ,...,x n) Ï L , tai iš jo pakeitę konstantas 0, 1 ir naudojant funkciją `x galime gauti funkciją x 1 &x 2 .

Įrodymas. Pavaizduokime f kaip DNF (pavyzdžiui, tobulą DNF) ir naudokime ryšius:

Pavyzdys. Pateiksime du šių transformacijų taikymo pavyzdžius.

Taigi funkcija, įrašyta disjunktyviąja normaliąja forma, pritaikius nurodytus ryšius, atidarius skliaustus ir paprastas algebrines transformacijas, tampa mod 2 daugianario (Žegalkino daugianario):

kur A 0 yra konstanta, o A i yra kai kurių kintamųjų iš skaičiaus x 1,..., x n, i = 1, 2, ..., r jungtis.

Jei kiekviena jungtis A i susideda tik iš vieno kintamojo, tai f yra tiesinė funkcija, kuri prieštarauja lemos sąlygai.

Vadinasi, funkcijos f Zhegalkin polinome yra terminas, kuriame yra bent du veiksniai. Neprarasdami bendrumo, galime daryti prielaidą, kad tarp šių veiksnių yra kintamieji x 1 ir x 2. Tada daugianarį galima transformuoti taip:

f = x 1 x 2 f 1 (x 3 ,..., x n) + x 1 f 2 (x 3 ,..., x n) + x 2 f 3 (x 3 ,..., x n) + f 4 (x 3,..., x n),

kur f 1 (x 3 ,..., x n) ¹ 0 (kitaip daugianario neapima jungties, turinčios jungtį x 1 x 2).

Tegu (a 3 ,...,a n) yra tokia, kad f 1 (a 3 ,...,a n) = 1. Tada

j(x 1 ,x 2) = f(x 1 ,x 2 , a 3 ,...,a n) = x 1 x 2 +ax 1 +bx 2 +g,

kur a, b, g yra konstantos, lygios 0 arba 1.

Panaudokime turimą neigimo operaciją ir apsvarstykime funkciją y(x 1 ,x 2), gautą iš j(x 1 ,x 2), taip:

y(x 1 ,x 2) = j(x 1 +b, x 2 +a)+ab+g.

Tai akivaizdu

y(x 1 ,x 2) =(x 1 +b)(x 2 +a)+a(x 1 +b)+b(x 2 +a)+g+ab+g = x 1 x 2.

Vadinasi,

y(x 1 ,x 2) = x 1 x 2 .

Lema yra visiškai įrodyta. ð

Lemma 2.10. Pagrindinė išsamumo kriterijaus lema.

Jei loginės algebros funkcijų klasėje F=( f ) yra funkcijų, kurios neišsaugo vienybės, neišsaugo 0, yra nesavarankiškos ir nemonotoniškos:

tada iš šios sistemos funkcijų superpozicijos ir kintamųjų keitimo operacijomis galima gauti konstantas 0, 1 ir funkciją.

Įrodymas. Panagrinėkime funkciją. Tada

.

Yra du galimi tolesni svarstymų atvejai, toliau pateiktame pristatyme nurodyti kaip 1) ir 2).

1). Vienetų rinkinio funkcija turi reikšmę 0:

.

Pakeiskime visus funkcijos kintamuosius kintamuoju x. Tada funkcija

yra, nes

Ir .

Paimkime ne savaime dvigubą funkciją. Kadangi funkciją jau gavome, tai pagal lemą nedvigubai funkcijai (lema 2.7. ) galite gauti konstantą iš. Antrąją konstantą galima gauti iš pirmosios naudojant funkciją. Taigi, pirmuoju nagrinėjamu atveju, gaunamos konstantos ir neigimas. . Antrasis atvejis ir kartu su juo pagrindinė išsamumo kriterijaus lema yra visiškai įrodyta. ð

2.11 teorema. Funkcijų sistemų užbaigtumo kriterijus logikos algebroje (Posto teorema).

Kad funkcijų sistema F = (f i ) būtų baigta, būtina ir pakanka, kad ji nebūtų visiškai įtraukta į bet kurią iš penkių uždarų klasių T 0, T 1, L, S, M, tai yra, kiekvienoje iš T 0 , T 1 , L , S, M klasių F yra bent viena funkcija, kuri nepriklauso šiai klasei.

Būtinybė. Tegul F yra užbaigta sistema. Tarkime, kad F yra vienoje iš nurodytų klasių, pažymėkime jį K, t.y. F Í K. Paskutinis įtraukimas neįmanomas, nes K yra uždara klasė, kuri nėra visa sistema.

Tinkamumas. Tegul visa funkcijų sistema F = (f i ) nėra įtraukta į vieną iš penkių uždarų klasių T 0 , T 1 , L , S , M . Paimkime šias F funkcijas:

Tada, remiantis pagrindine lema (lema 2.10 ) iš funkcijos, kuri neišsaugo 0, funkcijos, kuri neišsaugo 1, nesavarankiškų ir nemonotoninių funkcijų, galima gauti konstantas 0, 1 ir neigimo funkciją:

.

Remiantis netiesinių funkcijų lema (lema 2.9 ) iš konstantų, neigimo ir netiesinės funkcijos galime gauti jungtį:

.

Funkcinė sistema - pilna sistema pagal teoremą apie galimybę pavaizduoti bet kurią logikos algebros funkciją tobulos disjunktyvios normaliosios formos pavidalu (atkreipkite dėmesį, kad disjunkcija gali būti išreikšta konjunkcija ir neigimu formoje ).

Teorema visiškai įrodyta. ð

Pavyzdžiai.

1. Parodykime, kad funkcija f(x,y) = x|y sudaro pilną sistemą. Sukurkime funkcijos x½y verčių lentelę:

x	y	x|y

f(0,0) = 1, todėl x | yÏT 0 .

f(1,1) = 0, todėl x | yÏT 1 .

f(0,0) = 1, f(1,1) = 0, todėl x | yÏM.

f(0,1) = f(1,0) = 1, - priešingose ​​aibėse x | y įgyja tas pačias reikšmes, todėl x | taip .

Galiausiai, ką reiškia funkcijos netiesiškumas?
x | y.

Remdamiesi išsamumo kriterijumi, galime teigti, kad f(x,y) = x | y sudaro pilną sistemą. ð

2. Parodykime, kad funkcijų sistema sudaro pilną sistemą.

Tikrai,.

Taigi tarp mūsų sistemos funkcijų radome: funkciją, kuri neišsaugo 0, funkciją, kuri neišsaugo 1, nesavarankiškas, nemonotonines ir netiesines funkcijas. Remiantis išsamumo kriterijumi, galima teigti, kad funkcijų sistema sudaro pilną sistemą. ð

Taigi, esame įsitikinę, kad išsamumo kriterijus yra konstruktyvus ir efektyvus būdas nustatyti funkcijų sistemų išsamumą logikos algebroje.

Dabar suformuluokime tris užbaigtumo kriterijaus pasekmes.

1 išvada. Bet kuri uždara logikos algebros funkcijų klasė K, kuri nesutampa su visa logikos algebros funkcijų rinkiniu (K¹P 2), yra bent vienoje iš sukonstruotų uždarų klasių.

Apibrėžimas. Uždara K klasė vadinama iš anksto pilnas, jei K yra neužbaigtas ir bet kuriai funkcijai fÏ K klasė K È (f) yra baigta.

Iš apibrėžimo matyti, kad iš anksto užbaigta klasė yra uždara.

2 išvada. Logikos algebroje yra tik penkios iš anksto užbaigtos klasės, būtent: T 0, T 1, L, M, S.

Norėdami įrodyti pasekmę, tereikia patikrinti, ar nė viena iš šių klasių nėra kitoje, o tai patvirtina, pavyzdžiui, ši skirtingų klasių funkcijų lentelė:

	T0	T 1	L	S	M
	+	-	+	-	+
	-	+	+	-	+
	-	-	+	+	-

3 išvada. Iš bet kurios pilnos funkcijų sistemos galima atskirti pilną posistemį, kuriame yra ne daugiau kaip keturios funkcijos.

Iš išsamumo kriterijaus įrodymo matyti, kad galima išskirti ne daugiau kaip penkias funkcijas. Iš pagrindinės lemos įrodymo (Lemma 2.10 ) seka tai yra arba nesavarankiškas, arba neišsaugo vienybės ir nėra monotoniškas. Todėl reikia ne daugiau kaip keturių funkcijų.

- (vėlyv. lot. superpositio, - perdanga, iš lot. superpositus - dedamas ant viršaus) (kompozicija) - loginis-matematinis veiksmas. skaičiavimas, kurį sudaro gavimas iš k.l. pateiktos funkcijos f ir g duotas naujos funkcijos g (f) skaičiavimas (išraiška g... ... Filosofinė enciklopedija

Terminas superpozicija (superpozicija) gali reikšti šias sąvokas: Funkcijų superpozicija (sudėtinga funkcija) Superpozicijos principas yra fizikos ir matematikos principas, apibūdinantis procesų (pavyzdžiui, bangų) superpoziciją ir dėl to ... ... Vikipedija

Funkcijų sudarymas, sudėtingos funkcijos sudarymas iš dviejų funkcijų... Matematinė enciklopedija

Šis terminas turi kitas reikšmes, žr. Superpoziciją. Kvantinė mechanika ... Vikipedija

Šiame straipsnyje ar skyriuje yra šaltinių sąrašas arba išorinės nuorodos, tačiau atskirų teiginių šaltiniai lieka neaiškūs, nes trūksta išnašų... Vikipedija

Diskrečių funkcinių sistemų teorijoje Būlio funkcija yra tipo funkcija, kur yra Būlio aibė, o n yra neneigiamas sveikasis skaičius, kuris vadinamas funkcijos aritetu arba lokalumu. 1 (vienas) ir 0 (nulis) elementai interpretuojami standartiškai ... ... Vikipedija

Vienas iš svarbiausių matematikos ir matematikos pagrindams. logikos sąvokų klasėse, kurios tarnauja kaip paaiškinimai. efektyviai apskaičiuojamos aritmetinės funkcijos ir efektyviai sprendžiamo aritmetinio predikato sąvokos, galiausiai ir... ... Filosofinė enciklopedija

Funkcija, spiečiaus verčių apskaičiavimas gali būti atliekamas naudojant iš anksto nustatytą efektyvią procedūrą arba algoritmą. Būdingas skaičiavimo procesų bruožas yra tai, kad reikiamų problemų kiekių apskaičiavimas atsiranda nuosekliai iš pradinių duomenų... ... Matematinė enciklopedija

Šio straipsnio turinį būtina perkelti į straipsnį „Sudėtingos funkcijos diferencijavimas“. Galite padėti projektui derindami straipsnius. Jei reikia aptarti sujungimo galimybes, pakeiskite šį šabloną šablonu ((sujungti)) ... Vikipedija

- (lot. compositio kompozicija, susiejimas, papildymas, ryšys): Vikižodyne yra straipsnis "kompozicija" Menas Kompozicija (vaizduojamasis menas) yra meninės formos organizuojamasis komponentas, suteikiantis... Vikipedija

Knygos

• Diskreti matematika. Pagrindinės aibių teorinės konstrukcijos. VI dalis, A.I. Širokovas. Vadovas yra skyriaus „Pagrindinės aibių teorinės diskrečiosios matematikos konstrukcijos“ VI dalis. Sk. XI aptariamos šios sąvokos: funkcijų sudėtis (§1); funkcijos,...

Vieno ciklo (be atminties elementų) diskretieji loginiai įrenginiai išvestyje įgyvendina tam tikrą loginės algebros funkcijų rinkinį „F m =(F 1 ,F 2 ,…,F m), kurie kiekvienu laiko momentu priklauso tik nuo įrenginio įėjimų būsenos `x n =(x 1 ,x 2 ,…,x n): „F m = „F m(`x n). Praktiškai tokie įrenginiai yra projektuojami ir gaminami iš atskirų nedalomų elementų, kurie įgyvendina tam tikrą rinkinį (sistemą) ( f) elementariosios algebros funkcijos jungiant vienų elementų išėjimus su kitų įvestimis.

Kuriant loginius įrenginius aktualūs šie klausimai.

1. Pateikiama elementariųjų funkcijų sistema ( f). Kokios yra išvesties funkcijos F i galima gauti naudojant funkcijas iš ( f}?

2. Išvesties Būlio funkcijų rinkinys ( F) (ypač lygus visai logikos algebros funkcijų rinkiniui R 2). Kokia turėtų būti pradinė elementariųjų funkcijų sistema ( f), suteikiant galimybę išvestyje gauti bet kurią iš rinkinio funkcijų ( F}?

Norint pateikti pagrįstą atsakymą į šiuos klausimus, naudojamos funkcijų sistemų superpozicijos, uždarumo ir užbaigtumo sąvokos.

Apibrėžimas. Panagrinėkime loginių jungčių rinkinį ( F), atitinkanti tam tikrą funkcijų sistemą ( f} . Superpozicija baigta{f) yra bet kokia funkcija j, kurią galima realizuoti naudojant formulę per ( F}.

Praktiškai superpozicija gali būti pavaizduota kaip funkcijų pakeitimo iš ( f) kaip funkcijos iš tos pačios aibės argumentus.

1 pavyzdys. Apsvarstykite funkcijų sistemą ( f} = {f 1 (X) =„x, f 2 (x,y)= X&y, f 3 (x,y)=XÚ y). Pakeitimas į funkciją f 3 (x,y) vietoj pirmojo argumento X funkcija f 1 (X), vietoj antrojo - f 2 (x,y), gauname superpoziciją h(x,y)=f 3 (f 1 (X),f 2 (x,y))=`xÚ X& adresu. Fizinis pakeitimo įgyvendinimas pateiktas 1.18 pav.

Apibrėžimas. Leisti M-tam tikras loginės algebros funkcijų rinkinys ( P 2). Visų superpozicijų rinkinys per M paskambino trumpas sujungimas rinkiniai M ir žymimas [ M]. Priimama [ M]pagal originalų rinkinį M paskambino uždarymo operacija. Krūva M paskambino funkciškai uždara klasė, Jei [ M] = M. Poaibis mÍ M paskambino funkciškai užbaigta sistema M, Jei [ m] = M.

Uždarymas [ M] reiškia visą funkcijų rinkinį, kurį galima gauti iš M taikant superpozicijos operaciją, t.y. visi galimi pakaitalai.

Pastabos. 1. Akivaizdu, kad bet kokia funkcijų sistema ( f) yra funkciškai užbaigtas pats savaime.

2 . Neprarasdami bendrumo, galime manyti, kad tapatybės funkcija f(X)=x, kuris nekeičia kintamųjų tiesos verčių, iš pradžių yra bet kurios funkcijų sistemos dalis.

2 pavyzdys. Toliau aptariamoms funkcijų sistemoms ( f) atlikite šiuos veiksmus:

1) rasti uždarymą [ f],

2) išsiaiškinti, ar sistema ( f) uždara klasė,

3) rasti funkcionaliai užbaigtas sistemas ( f}.

Sprendimas.

aš ( f}={0} . Keičiant funkciją ( fº 0) jį gauname į save, t.y. naujų funkcijų nesukuriama. Tai reiškia: [ f] = {f). Nagrinėjama sistema yra funkciškai uždara klasė. Funkciškai užbaigta sistema joje yra viena ir lygi visumai ( f}.

II. ( f} = {0,Ø } . Pakeitimas Ø (Ø X)suteikia identišką funkciją, kuri formaliai nepratęsia pradinės sistemos. Tačiau pakeitę Ø (0) gauname identišką vienetą – naują funkciją, kurios nebuvo pradinėje sistemoje: Ø (0)=1 . Taikant visus kitus pakaitalus neatsiranda naujų funkcijų, pavyzdžiui: ØØ 0 = 0, 0 (Ø X)=0.

Taigi superpozicijos operacijos naudojimas leido gauti platesnį funkcijų rinkinį nei pradinis [ f]=(0,Ø ,1). Tai reiškia griežtą įrašą: ( f} Ì [ f]. Šaltinio sistema ( f) nėra funkciškai uždara klasė. Be pačios sistemos ( f) jame nėra kitų funkciškai pilnų sistemų, nes jos susiaurėjimo nuo vienos funkcijos atveju f= 0 negalima paneigti pakeitimu, o identiško nulio negalima gauti vien iš neigimo funkcijos.

III. ( f) = (& ,Ú ,Ø ).Šios sistemos uždarymas yra visas logikos algebros funkcijų rinkinys P 2, nes bet kurios iš jų formulė gali būti pavaizduota kaip DNF arba CNF, kuri naudoja elementarias funkcijas ( f) = (& ,Ú ,Ø). Šis faktas yra konstruktyvus nagrinėjamos funkcijų sistemos išsamumo įrodymas P 2: [f]=P 2 .

Nuo m P 2 yra begalė kitų funkcijų, išskyrus ( f) = (& ,Ú ,Ø ), tai reiškia griežtą įvykį: ( f}Ì[ f]. Nagrinėjama sistema nėra funkciškai uždara klasė.

Be pačios sistemos, funkcionaliai bus užbaigti posistemiai ( f) 1 = (& ,Ø ) ir ( f) 2 = (Ú ,Ø ). Tai išplaukia iš to, kad naudojant De Morgano taisykles loginio sudėjimo funkcija Ú gali būti išreikšta per (& , Ø), o loginio daugybos funkcija & per (Ú, Ø):

(X & adresu) = Ø (` XÚ` adresu), (X Ú adresu) = Ø ( X &`adresu).

Kiti funkcionaliai užbaigti posistemiai ( f) Ne.

Funkcijų posistemio užbaigtumo tikrinimas ( f) 1 М ( f)visoje sistemoje ( f)gali būti gaminamas maišant ( f) 1 kitam, akivaizdžiai užpildytas ( f) sistema.

Posistemio neužbaigtumas ( f) 1 in ( f)gali būti patikrinta įrodant griežtą [ f 1 ] М [ f].

Apibrėžimas. Poaibis mÍ M paskambino funkcinis pagrindas(pagrindu)sistemos M, Jei [ m] = M, o iš jo pašalinus bet kurią funkciją, likusių rinkinys nėra pilnas M .

komentuoti. Funkcijų sistemos pagrindai f) yra visos jos funkciškai užbaigtos posistemės f) 1, kurio negalima sumažinti neprarandant išsamumo f).

3 pavyzdys. Visoms 2 pavyzdyje aptartoms sistemoms raskite bazes.

Sprendimas.1 ir 2 atvejais tik pačios sistemos yra funkciškai sukomplektuotos ir jų susiaurinti neįmanoma. Vadinasi, jie taip pat yra pagrindai.

3 atveju yra du funkcionaliai užbaigti ( f)posistemės ( f) 1 = (&,Ø ) ir ( f) 2 =(Ú,Ø ), kurios negalima sumažinti neprarandant išsamumo. Jie bus sistemos pagrindas ( f} = {&,Ú,Ø}.

Apibrėžimas. Tegul sistema ( f) yra uždara klasė. Jo poaibis ( f) 1 М ( f) yra vadinami jaunesniųjų klasėje{f), jei ( f) 1 neužbaigtas ( f} ([f 1 ] М [ f]), ir bet kuriai funkcijai j iš sistemos ( f), neįtraukta į ( f) 1 (jО( f} \ {f) 1) tiesa: [ jÈ { f} 1 ] = [f], t.y. pridedant jк ( f) 1 užbaigia ( f} .

Užduotys

1. Patikrinkite funkcijų rinkinių uždarumą:

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

2. Patikrinkite funkcijų sistemų išsamumą P 2:

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

3. Raskite funkcijų sistemos uždarumą ir jos pagrindą:

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

1.10.2 Konstantas išsaugančios funkcijos. T 0 ir T 1 klasės

Apibrėžimas. Funkcija f(`x n) taupo 0 jei f(0,..., 0) = 0. Funkcija f(`x n) taupo 1 jei f(1, ... , 1) = 1.

Daug funkcijų n kintamieji, kuriuose saugomi 0 ir 1, yra atitinkamai pažymėti, T 0 n Ir T 1 n. Visi loginės algebros funkcijų rinkiniai, išsaugantys 0 ir 1 , žymėti T 0 Ir T 1 . Kiekvienas iš rinkinių T 0 ir T 1 yra uždara iš anksto užbaigta klasė R 2 .

Nuo elementarių funkcijų iki T 0 ir T 1 vienu metu įtraukiami, pavyzdžiui, & ir Ú. Bet kokios funkcijos priklausymas klasėms T 0 , T 1 galima patikrinti pagal pirmąją ir paskutinę jo reikšmių vektoriaus reikšmes tiesos lentelėje arba tiesiogiai pakeičiant nulius ir vienetus į formulę analitiškai nurodant funkciją.

Apibrėžimas.Pasikartoti yra pakeitimas, kai tas pats kintamasis vietoj kelių nepriklausomų kintamųjų pakeičiamas funkcija. Tokiu atveju kintamųjų reikšmės rinkiniuose, kurie anksčiau turėjo reikšmes nepriklausomai vienas nuo kito, visada bus vienodos.

UŽDUOTYS

1. Patikrinkite narystę klasėje T 0 Ir T 1 funkcijos:

a) apibendrintas sudėjimas, b) apibendrintas daugyba, c) konstantos, d) xyÚ yz, d) X® adresu® xy, e) XÅ adresu, ir) ( X 1 Å … Å X n) ® ( y 1 Å … Å y m) adresu n,mÎ N.

2. Įrodykite kiekvienos klasės uždarumą T 0 Ir T 1 .

3. Įrodykite, kad jei f(`x n) Ï T 0, tada iš jo, dubliuodami pakaitalą, galite gauti konstantą 1 arba neigimą.

4. Įrodykite, kad jei f(`x n) Ï T 1 , tada iš jo, dubliuodami pakaitalą, galite gauti konstantą 0 arba neigimą.

5. Įrodykite kiekvienos klasės išankstinį užbaigtumą T 0 Ir T 1 (pavyzdžiui, padidintą sistemą sumažinant iki ( f} = {& ,Ú ,Ø }).

6. Raskite klasių galią T 0 n Ir T 1 n.

Tegul būna koks nors rinkinys K, susidedantis iš baigtinio Būlio funkcijų skaičiaus. Funkcijų superpozicija iš šios aibės yra naujos funkcijos, gautos taikant baigtinį dviejų operacijų skaičių;

galite pervardyti bet kurį kintamąjį, įtrauktą į funkciją K;

vietoj bet kurio kintamojo galite įdėti funkciją iš rinkinio K arba anksčiau susidariusi superpozicija.

Superpozicija taip pat vadinama kompleksine funkcija.

Pavyzdys 7. 1. Jei suteikiama viena funkcija X|y(Schaeffer insultas), tada jo superpozicijos, visų pirma, bus šios funkcijos x|x,x|(x|y),x|(y|z) ir tt

Uždarius funkcijų rinkinys nuo K vadinama visų superpozicijų aibe. Funkcinė klasė K paskambino uždaryta, jei jo uždarymas sutampa su pačiu savimi.

Funkcijų rinkinys vadinamas užbaigti, jei jo uždarymas sutampa su visomis loginėmis funkcijomis. Kitaip tariant, visas rinkinys yra tokių funkcijų rinkinys, per kurį galima išreikšti visas kitas Būlio funkcijas.

Neperteklinis visas funkcijų rinkinys vadinamas pagrindu(„neperteklinis“ reiškia, kad jei kuri nors funkcija bus pašalinta iš rinkinio, šis rinkinys nebebus baigtas).

Pavyzdys 7.2. Konjunkcija, disjunkcija ir neigimas yra pilnas rinkinys (tuo įsitikinome 5 skyriuje), bet nėra pagrindas, nes šis rinkinys yra perteklinis, nes naudojant De Morgano taisykles galima pašalinti konjunkciją arba disjunkciją. Bet kuri funkcija gali būti pavaizduota kaip Zhegalkin daugianario (6 skyrius). Aišku, kad funkcijų jungtis, sudėjimas modulo 2 ir konstantos 0 ir 1 yra visa aibė, tačiau šios keturios funkcijos taip pat nėra pagrindas, nes 1+1=0, todėl konstanta 0 gali būti neįtraukta į pilną. aibė (statant daugianario, Zhegalkin konstanta 0 yra būtina, nes išraiška „1+1“ nėra Zhegalkin daugianario).

Nesunku pastebėti, kad tai vienas iš būdų patikrinti kai kurių rinkinių išsamumą KAM yra patikrinti, ar kito rinkinio funkcijos yra išreikštos šio rinkinio funkcijomis (galite patikrinti, kad per funkcijas iš KAM galima išreikšti konjunkciją ir neigimą arba disjunkciją ir neigimą.

Yra tokių funkcijų, kad viena tokia funkcija pati yra pagrindas (čia pakanka patikrinti tik išsamumą; nepertekliškumas akivaizdus). Tokios funkcijos vadinamos Scheffer funkcijomis. Šis pavadinimas atsirado dėl to, kad Schaefferio smūgis yra pagrindas. Prisiminkite, kad Schaeffer pirminis dydis apibrėžiamas pagal šią tiesos lentelę:

Kadangi tai yra akivaizdu, t. y. neigimas yra Schaefferio potėpio superpozicija, o tada disjunkcija , Schaeffer insultas pats yra pagrindas. Be to, Peirce rodyklė yra Scheffer funkcija (studentai gali tai patikrinti patys). 3 ar daugiau kintamųjų funkcijoms yra daug Sheffer funkcijų (žinoma, sunku išreikšti kitas Būlio funkcijas per daugelio kintamųjų Sheffer funkciją, todėl jos retai naudojamos technologijoje).

Atminkite, kad skaičiavimo įrenginys dažniausiai yra pagrįstas visu funkcijų rinkiniu (dažnai pagrindu). Jei įrenginys pagrįstas konjunkcija, disjunkcija ir neigimu, tai šiems įrenginiams svarbi DNF mažinimo problema; Jei įrenginys yra pagrįstas kitomis funkcijomis, naudinga, kad per šias funkcijas būtų galima algoritmiškai sumažinti išraiškas.

Dabar pereikime prie konkrečių funkcijų rinkinių išsamumo paaiškinimo. Norėdami tai padaryti, išvardijame 5 svarbiausias funkcijų klases:

• T 0 yra visų tų loginių funkcijų rinkinys, kurio nulio rinkinio reikšmė yra 0 ( T 0 yra funkcijų klasė, konservuojant 0);
• T 1 yra visų loginių funkcijų rinkinys, kurio vienetų rinkinyje yra 1 reikšmė ( T 1 yra funkcijų klasė, konservavimo vienetas) (atkreipkite dėmesį, kad funkcijų skaičius nuo P kintamieji, priklausantys klasėms T 0 ir T 1, yra lygūs 2 2n-1);
• L- Klasė linijinis funkcijos, t.y. funkcijos, kurių Zhegalkin daugianario yra tik pirmieji kintamųjų laipsniai;
• M- Klasė monotoniškas funkcijas. Leiskite mums išsamiau apibūdinti šių funkcijų klasę. Tegul būna 2 rinkiniai P kintamieji: s1 = (x 1, x 2,..., x n)

s 1 = ( X 1 , X 2 , … , x n) ir s 2 = (y 1 , y 2, … , y p). Sakysime, kad rinkinys s 1 yra mažesnė už aibę s 2 (s 1 £ s 2 ), jei viskas x i £ y i .Akivaizdu, kad ne visi rinkiniai išPkintamieji yra palyginami vienas su kitu (pavyzdžiui, kadan = 2 aibės (0,1) ir (1,0) nėra palyginamos viena su kita). Funkcija nuoPkintamieji vadinamimonotoniškas, jei mažesniame rinkinyje ji užima mažesnę arba vienodą reikšmę. Žinoma, šios nelygybės turėtų būti tikrinamos tik palyginamose aibėse. Akivaizdu, kad nepalyginamos aibės yra tos, kurių vienoje aibėje yra tam tikros (0,1) tipo, o kitoje (1,0) tipo koordinatės atitinkamose vietose (diskrečiojoje matematikoje monotoniškos funkcijos yra kaip „monotoniškai didėjančios funkcijos“, „monotoniškai mažėjančios“ funkcijos čia nenagrinėjamos).

Pavyzdys. Toliau pateiktoje lentelėje pateiktos funkcijos f 1 ,f 2 yra monotoninės funkcijos ir funkcijos f 3 ,f 4 – Ne.

Natūralią kintamųjų tvarką užtikrina tai, kad jei kuri nors aibė yra mažesnė už kitą, ji būtinai yra tiesos lentelėje aukštesnė"didesnis" rinkinys. Štai kodėl jei tiesos lentelėje()viršuje yra nuliai,ir tada vienetai,tada ši funkcija tikrai monotoniška.Tačiau galimos inversijos, t. y. vienas ateina prieš kai kuriuos nulius, bet funkcija vis dar monotoniška(šiuo atveju rinkiniai, atitinkantys „viršutinį“ ir „apatinį“ nulį, turėtų būti nepalyginamas; galima patikrinti, ar tiesos lentelės pateikta funkcija su natūralia kintamųjų aibės tvarka(00010101), yra monotoniškas);

Teorema .T funkcijų klasės 0 ,T 1 ,L,M,S uždarytas.

Šis teiginys tiesiogiai išplaukia iš pačių šių klasių apibrėžimo, taip pat iš uždarumo apibrėžimo.

Būlio funkcijų teorijoje ši Posto teorema yra labai svarbi.

Posto teorema .Kad kuri nors funkcijų rinkinys K būtų baigtas, būtina ir pakanka, kad į jį būtų įtrauktos funkcijos, nepriklausančios kiekvienai T klasei. 0 ,T 1 ,L,M,S.

Prisimink tai Ką būtinybė tai pareiškimus aiškus Taigi Kaip Jeigu tai viskas funkcijas iš įdarbinimas KAMįskaitant V vienas iš išvardyti klases, Tai Ir Visi superpozicijos, A Reiškia, Ir trumpas sujungimas įdarbinimas įskaitant būtų V tai Klasė Ir Klasė KAM Ne galėtų būti pilnas.

Tinkamumas tai pareiškimus yra įrodyta pakankamai sunku, Štai kodėl čia nerodoma.

Iš šios teoremos išplaukia gana paprastas būdas nustatyti tam tikros funkcijų rinkinio užbaigtumą. Kiekvienai iš šių funkcijų nustatoma priklausymas aukščiau išvardytoms klasėms. Rezultatai įvedami į vadinamąjį Pašto lentelė(mūsų pavyzdyje ši lentelė sudaryta 4 funkcijoms, o „+“ ženklas rodo, kad funkcija priklauso atitinkamai klasei, „-“ ženklas reiškia, kad funkcija į ją neįtraukta).

Pagal Posto teoremą, funkcijų rinkinys bus baigtas tada ir tik tada, kai kiekviename Post lentelės stulpelyje bus bent vienas minusas. Taigi iš aukščiau pateiktos lentelės matyti, kad šios 4 funkcijos sudaro visą rinkinį, tačiau šios funkcijos nėra pagrindas. Iš šių funkcijų galite sudaryti 2 pagrindus: f 3 ,f 1 Ir f 3 ,f 2. Pilni rinkiniai yra bet kokie rinkiniai, turintys tam tikrą pagrindą.

Iš Posto lentelės tiesiogiai išplaukia, kad bazinių funkcijų skaičius negali būti didesnis nei 5. Nesunku įrodyti, kad iš tikrųjų šis skaičius yra mažesnis arba lygus 4.