Superpozice booleovských funkcí. Operace superpozice a uzávěru. Úplnost, základ systému funkcí Co je to superpozice funkcí

Nechť existuje funkce f(x 1 , x 2 , ... , x n) a funkce

pak bude funkce volána funkce superpozice f(x 1 , x 2 , ... , x n) a funkcí .

Jinými slovy: nechť F = ( f j ) - soubor funkcí logické algebry, nemusí být nutně konečný. Funkce f se nazývá superpozice funkcí z množiny F nebo funkce přes F, pokud je získána z funkce nahrazením jedné nebo více jejích proměnných funkcemi z množiny F.

Příklad.

Nechte sadu funkcí

F \u003d (f 1 (x 1), f 2 (x 1, x 2, x 3), f 3 (x 1, x 2)).

Pak superpozice funkcí z F budou například funkce:

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

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

Perfect DNF - superpozice funkcí ze sady

. ð

Definice.

Systém funkcí se nazývá kompletní, lze-li nějakou funkci algebry logiky získat z funkcí tohoto systému pomocí operací superpozice a změny proměnných. ð

Již máme několik kompletních systémů:

;

Protože ;

Protože ;

(x+y, xy, 1). ð

Jak určit podmínky, za kterých je systém kompletní. S pojmem úplnosti úzce souvisí pojem uzavřené třídy.

uzavřené třídy.

Množina (třída) K funkcí algebry logiky se nazývá uzavřená třída, pokud obsahuje všechny funkce získané z K operacemi superpozice a změny proměnných a neobsahuje žádné další funkce.

Nechť K je nějaká podmnožina funkcí z P 2 . Uzávěr množiny K je množina všech booleovských funkcí reprezentovatelných operacemi superpozice a změny funkcí proměnných z množiny K. Uzávěr množiny K označujeme [K].

Z hlediska uzavření lze uvést další definice uzavření a úplnosti (ekvivalentní těm původním):

K je uzavřená třída, jestliže K = [K];

K je úplný systém, jestliže [K] = Р 2 .

Příklady.

* (0), (1) - uzavřené třídy.

* Množina funkcí jedné proměnné je uzavřená třída.

* - uzavřená třída.

* Třída (1, x+y) není uzavřená třída.

Podívejme se na některé z nejdůležitějších uzavřených tříd.

1. T 0- třída funkcí, které zachovávají 0.

Označme T 0 třídu všech funkcí logické algebry f(x 1 , x 2 , ... , x n), které zachovávají konstantu 0, tedy funkce, pro které f(0, ... , 0) = 0.

Je snadné vidět, že existují funkce, které patří do T 0, a funkce, které do této třídy nepatří:

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

Z toho, že W T 0 vyplývá např. to nelze vyjádřit pomocí disjunkce a konjunkce.

Protože tabulka pro funkci f z třídy T 0 v prvním řádku obsahuje hodnotu 0, pak pro funkce z T 0 můžete nastavit libovolné hodnoty pouze na 2 n - 1 sadách hodnot proměnných, tzn.

,

kde je množina funkcí, které zachovávají 0 a závisí na n proměnných.

Ukažme, že T 0 je uzavřená třída. Protože xОT 0 pro ospravedlnění uzavřenosti postačí ukázat uzavřenost vzhledem k operaci superpozice, protože operace změny proměnných je speciálním případem superpozice s funkcí x.

Nechte Pak to stačí ukázat. To druhé vyplývá z řetězce rovnosti

2.T1- třída funkcí, které zachovávají 1.

Označme T 1 třídu všech funkcí logické algebry f(x 1 , x 2 , ... , x n), které zachovávají konstantu 1, tedy funkce, pro které f(1, ... , 1) = 1.

Je snadné vidět, že existují funkce, které patří do T 1, a funkce, které do této třídy nepatří:

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

0, , x+y П T 1 .

Z toho, že x + y П T 0 například vyplývá, že x + y nelze vyjádřit pomocí disjunkce a konjunkce.

Výsledky o třídě T 0 se triviálně přenášejí do třídy T 1 . Máme tedy:

T 1 - uzavřená třída;

.

3. L- třída lineárních funkcí.

Označme L třídu všech funkcí logické algebry f(x 1 , x 2 , ... , x n), které jsou lineární:

Je snadné vidět, že existují funkce, které patří do L, a funkce, které do této třídy nepatří:

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

Dokažme například, že xÚy Ï L .

Předpokládejme opak. Budeme hledat výraz pro xÚy ve tvaru lineární funkce s nedefinovanými koeficienty:

Pro x = y = 0 máme a = 0,

pro x = 1, y = 0 máme b = 1,

pro x = 0, y = 1 máme g = 1,

ale pak pro x = 1, y = 1 máme 1Ú 1 ¹ 1 + 1, což dokazuje, že funkce xÚy je nelineární.

Důkaz uzavřenosti třídy lineárních funkcí je zcela zřejmý.

Protože lineární funkce je jednoznačně definována zadáním n+1 hodnot koeficientu a 0 , ... , a n , je počet lineárních funkcí ve třídě L (n) funkcí závislých na n proměnných 2 n+1 .

.

4.S- třída sebeduálních funkcí.

Definice třídy sebeduálních funkcí je založena na využití tzv. principu duality a duálních funkcí.

Zavolá se funkce definovaná rovností duální k funkci .

Je zřejmé, že tabulku pro duální funkci (se standardním řazením množin hodnot proměnných) získáme z tabulky pro původní funkci invertováním (tj. nahrazením 0 1 a 1 0) sloupce funkčních hodnot. a převrátit to.

Je snadné to vidět

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

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

Z definice vyplývá, že (f*)* = f, tedy funkce f je duální k f*.

Nechť je funkce vyjádřena pomocí superpozice z hlediska jiných funkcí. Otázkou je, jak vytvořit vzorec, který implementuje ? Označme = (x 1 , ... , x n) všechny různé variabilní symboly vyskytující se v množinách .

Věta 2.6. Pokud funkci j získáme jako superpozici funkcí f, f 1 , f 2 , ... , f m , tzn.

funkce duální k superpozici je superpozice duálních funkcí.

Důkaz.

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

Věta byla prokázána. ð

Princip duality vyplývá z věty: jestliže formule A implementuje funkci f(x 1 , ... , x n), pak formule získaná z A nahrazením funkcí v ní obsažených jejich duály implementuje duální funkci f* (x 1, ..., xn).

Označme S třídu všech autoduálních funkcí z P 2:

S = (f | f* = f)

Je snadné vidět, že existují funkce, které patří do S, a funkce, které do této třídy nepatří:

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

Méně triviálním příkladem samoduální funkce je funkce

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

pomocí superpoziční věty o duální funkci máme

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

Pro sebeduální funkci máme identitu

tak na sadách a , které budeme nazývat opačnými, nabývá sebedvojná funkce opačných hodnot. Z toho vyplývá, že samoduální funkce je zcela určena svými hodnotami v první polovině řádků standardní tabulky. Proto je počet samoduálních funkcí ve třídě S(n) funkcí závislých na n proměnných:

.

Dokažme nyní, že třída S je uzavřená. Protože xОS , k ospravedlnění uzavřenosti stačí ukázat uzavřenost vzhledem k operaci superpozice, protože operace změny proměnných je speciální případ superpozice s funkcí x. Nechte Pak to stačí ukázat. Ten se instaluje přímo:

5. M- třída monotónních funkcí.

Před definováním pojmu monotónní funkce algebry logiky je nutné zavést relaci uspořádání na množině kolekcí jejích proměnných.

Set prý předchází set (nebo „ne větší než“ nebo „menší nebo rovno“) a označení se používá, pokud a i £ b i pro všechna i = 1, ... , n. Jestliže a , pak řekneme, že množina striktně předchází množinu (buď „striktně méně než“ nebo „méně než“ množina ), a použijeme zápis . Množiny a se nazývají srovnatelné, jestliže buď , nebo .V případě, že není splněn žádný z těchto vztahů, množiny a se nazývají neporovnatelné. Například (0, 1, 0, 1) £ (1, 1, 0, 1), ale množiny (0, 1, 1, 0) a (1, 0, 1, 0) jsou nesrovnatelné. Relace £ (často nazývaná relace priority) je tedy částečným řádem na množině B n . Níže jsou schémata částečně uspořádaných sad B 2 , B 3 a B 4 .

Zavedený dílčí objednávkový vztah je mimořádně důležitým pojmem, který daleko přesahuje rámec našeho kurzu.

Nyní jsme schopni definovat pojem monotónní funkce.

Funkce algebry logiky se nazývá monotónní, Pokud pro jakékoli dvě sady a , Takové, že , Nerovnice . Množinu všech monotónních funkcí algebry logiky označujeme M a množinu všech monotónních funkcí závislých na n proměnných M (n).

Je snadné vidět, že existují funkce, které patří do M, a funkce, které do této třídy nepatří:

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

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

Ukažme, že třída monotónních funkcí M je uzavřená třída. Protože xОМ, k ospravedlnění uzavřenosti, stačí ukázat uzavřenost vzhledem k operaci superpozice, protože operace změny proměnných je speciální případ superpozice s funkcí x.

Nechte Pak to stačí ukázat.

Nechť jsou množiny proměnných funkcí j, f 1 , ... , f m a množina proměnných funkce j se skládá z těch a pouze těch proměnných, které se vyskytují ve funkcích f 1 , ... , f m . Nechť a být dvě sady hodnot proměnné a . Tyto množiny definují množiny proměnné hodnoty , takové, že . Vzhledem k monotónnosti funkcí f 1 , ... , f m

a vzhledem k monotónnosti funkce f

Odtud se dostáváme

Počet monotónních funkcí závislých na n proměnných není přesně znám. Nižší odhad lze snadno získat:

kde - je celá část čísla n/2.

Stejně snadné je získat nadhodnocení shora:

Zpřesnění těchto odhadů je důležitým a zajímavým úkolem moderního výzkumu.

Kritérium úplnosti

Nyní jsme schopni formulovat a dokázat kritérium úplnosti (Postův teorém), které určuje nutné a postačující podmínky pro úplnost systému funkcí. Před formulací a důkazem kritéria úplnosti uveďme několik nezbytných lemmat, která jsou rovněž nezávislá.

Lemma 2.7. Lemma o nesamodvojné funkci.

Jestliže f(x 1 , ... , x n)П S , pak z něj můžeme získat konstantu dosazením funkcí x a `x.

Důkaz. Od fÏS existuje množina hodnot proměnných
=(a 1 ,...,a n) takový, že

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

Nahradíme argumenty ve funkci f:

x i je nahrazeno ,

to znamená, že nastavíme a vezmeme v úvahu funkci

Tak jsme dostali konstantu (není však známo, o jaký druh konstanty jde: 0 nebo 1). ð

Lemma 2.8. Lemma na nemonotónní funkci.

Pokud je funkce f(x 1 ,...,x n) nemonotónní, f(x 1 ,...,x n) П M, pak změnou proměnných a dosazením konstant 0 a 1 ji lze negovat.

Důkaz. Protože f(x 1 ,...,x n) П M, existují množiny a hodnoty jeho proměnných, , , takže , a pro alespoň jednu hodnotu i máme i< b i . Выполним следующую замену переменных функции f:

x i bude nahrazeno

Po takové substituci získáme funkci jedné proměnné j(x), pro kterou platí:

To znamená j(x)=`x. Lema je dokázáno. ð

Lemma 2.9. Lemma na nelineární funkci.

Jestliže f(x 1 ,...,x n) П L , pak dosazením konstant 0, 1 a použitím funkce `x z ní lze získat funkci x 1 & x 2.

Důkaz. Reprezentujeme f jako DNF (například dokonalé DNF) a použijeme vztahy:

Příklad. Uveďme dva příklady použití těchto transformací.

Funkce zapsaná v disjunktivní normální formě se tedy po aplikaci výše uvedených vztahů, otevření závorek a jednoduchých algebraických transformací změní na polynom mod 2 (Zhegalkinův polynom):

kde A 0 je konstanta a A i je konjunkce některých proměnných z x 1 ,..., x n , i = 1, 2, ... , r.

Pokud se každá spojka A i skládá pouze z jedné proměnné, pak f je lineární funkce, což je v rozporu s podmínkou lemmatu.

Proto Zhegalkinův polynom pro funkci f obsahuje člen, který obsahuje alespoň dva faktory. Bez ztráty obecnosti můžeme předpokládat, že mezi těmito faktory existují proměnné x 1 a x 2 . Pak lze polynom transformovat takto:

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

kde f 1 (x 3 ,..., x n) ¹ 0 (jinak polynom neobsahuje spojku obsahující spojku x 1 x 2).

Nechť (a 3 ,...,a n) je takové, že f 1 (a 3 ,...,a n) = 1. Potom

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

kde a, b, g jsou konstanty rovné 0 nebo 1.

Použijme negační operaci, kterou máme, a uvažujme funkci y(x 1 ,x 2) vyplývající z j(x 1 ,x 2) takto:

y(x1,x2) = j(x1+b, x2+a)+ab+g.

To je zřejmé

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

Proto,

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

Lema je zcela dokázáno. ð

Lemma 2.10. Hlavní lemma kritéria úplnosti.

Pokud třída F=( f ) funkcí logické algebry obsahuje funkce, které nezachovávají jednotu, nezachovávají 0, nejsou autoduální a nemonotónní:

pak z funkcí tohoto systému lze operacemi superpozice a změny proměnných získat konstanty 0, 1 a funkce .

Důkaz. Uvažujme funkci. Pak

.

Jsou možné dva případy následných úvah, dále označené jako 1) a 2).

1). Funkce na sadě identit má hodnotu 0:

.

Nahraďme všechny proměnné funkce proměnnou x . Pak funkce

je Protože

A .

Vezměte si ne-duální funkci. Protože jsme již funkci získali, pomocí lemmatu nedvojné funkce (lemma 2.7. ) z můžete získat konstantu. Druhou konstantu lze získat z první pomocí . V prvním uvažovaném případě jsou tedy získány konstanty a negace. . Druhý případ a s ním hlavní lemma kritéria úplnosti jsou zcela dokázány. ð

Věta 2.11. Kritérium úplnosti pro systémy funkcí algebry logiky (Postův teorém).

Aby byl systém funkcí F = (f i) úplný, je nutné a postačující, aby nebyl celý obsažen v žádné z pěti uzavřených tříd T 0, T 1, L, S, M, tedy pro každá z tříd To, Ti, L, S, M v F existuje alespoň jedna funkce, která do této třídy nepatří.

Nutnost. Nechť F je úplný systém. Předpokládejme, že F je obsažena v jedné ze specifikovaných tříd, označte ji K, tzn. F Н K. Poslední zahrnutí je nemožné, protože K je uzavřená třída, která není úplným systémem.

Přiměřenost. Nechť systém funkcí F = (f i ) není zcela obsažen v žádné z pěti uzavřených tříd T 0 , T 1 , L , S, M. Vezměme si F funkce:

Poté na základě hlavního lemmatu (lemma 2.10 ) z funkce, která nezachová 0, z funkce, která nezachová 1, nesamostatných a nemonotónních funkcí, můžete získat konstanty 0, 1 a negační funkci:

.

Na základě lemmatu nelineární funkce (Lemma 2.9 ) z konstant, negace a nelineární funkce můžete získat spojení:

.

Funkční systém - úplný systém podle věty o možnosti znázornit libovolnou funkci algebry logiky ve formě dokonalé disjunktivní normální formy (všimněte si, že disjunkci lze vyjádřit konjunkcí a negací ve tvaru ).

Věta je zcela dokázána. ð

Příklady.

1. Ukažme, že funkce f(x,y) = x|y tvoří úplný systém. Sestavme tabulku hodnot funkce x½y:

f(0,0) = 1, tedy x | ypT 0.

f(1,1) = 0, tedy x | yÏT 1.

f(0,0) = 1, f(1,1) = 0, tedy x | jupí .

f(0,1) = f(1,0) = 1, - na opačných množinách x | y nabývá stejných hodnot, proto x | jojo.

Konečně , což znamená nelinearitu funkce
x | y

Na základě kritéria úplnosti můžeme konstatovat, že f(x,y) = x | y tvoří ucelený systém. ð

2. Ukažme, že systém funkcí tvoří ucelený systém.

Opravdu, .

Mezi funkcemi našeho systému jsme tedy našli: funkci, která nezachová 0, funkci, která nezachová 1, nesamoduální, nemonotónní a nelineární funkce. Na základě kritéria úplnosti lze tvrdit, že systém funkcí tvoří ucelený systém. ð

Viděli jsme tedy, že kritérium úplnosti poskytuje konstruktivní a účinný způsob, jak určit úplnost systémů funkcí algebry logiky.

Zformulujme nyní tři důsledky kritéria úplnosti.

Důsledek 1. Jakákoli uzavřená třída K funkcí logické algebry, která se neshoduje s celou množinou funkcí logické algebry (K¹P 2), je obsažena alespoň v jedné z konstruovaných uzavřených tříd.

Definice. Uzavřená třída K se nazývá předkompletní, je-li K neúplné a pro libovolnou funkci fW je třída K È (f)-úplná.

Z definice vyplývá, že předkompletní třída je uzavřená.

Důsledek 2. V algebře logiky existuje pouze pět předkompletních tříd, a to: T 0 ,T 1 , L , M , S .

K prokázání následku je potřeba pouze ověřit, že žádná z těchto tříd není obsažena v té druhé, což potvrzuje například následující tabulka příslušnosti funkcí k různým třídám:

Důsledek 3. Z jakéhokoli úplného systému funkcí lze vyčlenit úplný subsystém obsahující nejvýše čtyři funkce.

Z důkazu kritéria úplnosti vyplývá, že nelze rozlišit více než pět funkcí. Z důkazu hlavního lemmatu (lemma 2.10 ) to následuje je buď nesoběduální, nebo nezachovává identitu a není monotónní. Proto nejsou potřeba více než čtyři funkce.

Ve vědecké komunitě je známý vtip na toto téma „nelinearita“ přirovnáván k „nesloni“ – všichni tvorové, kromě „slonů“, jsou „nesloni“. Podobnost spočívá v tom, že většina systémů a jevů ve světě kolem nás je až na výjimky nelineární. Navzdory tomu nás ve škole učí „lineární“ myšlení, což je velmi špatné z hlediska naší připravenosti vnímat všeprostupující nelinearitu Vesmíru, ať už jde o jeho fyzické, biologické, psychologické či sociální aspekty. Nelinearita sama o sobě soustřeďuje jednu z hlavních obtíží poznávání okolního světa, protože důsledky ve své celkové hmotnosti nejsou úměrné příčinám, obě příčiny se při interakci nesčítají, to znamená, že důsledky jsou více. složitější než jednoduchá superpozice, funkce příčin. To znamená, že výsledek získaný jako výsledek přítomnosti a vlivu dvou příčin působících současně není součtem výsledků získaných za přítomnosti každé z příčin zvlášť, za nepřítomnosti jiné příčiny.

Definice 9. Na nějakém intervalu X je funkce r-f(lz) definována množinou hodnot Z a funkce y = /(z) je definována na množině Z, pak je funkce y komplexní funkcí x (neboli superpozice funkce) a proměnná z - střední proměnná komplexní funkce.

Controlling lze představit jako superpozici tří klasických manažerských funkcí - účetnictví, kontroly a analýzy (retrospektiva). Controlling jako integrovaná manažerská funkce umožňuje nejen připravit řešení, ale také zajistit kontrolu nad jeho implementací pomocí vhodných manažerských nástrojů.

Jak známo /50/, libovolnou časovou funkci lze reprezentovat jako superpozici (množinu) jednoduchých harmonických funkcí s různými periodami, amplitudami a fázemi. Obecně platí, že P(t) = f(t),

Přechodové nebo impulsní odezvy se určují experimentálně. Při jejich použití podle metody superpozice se vybraný vstupní akční model nejprve rozloží na elementární časové funkce a poté se odezvy na ně sečtou. Poslední operace se někdy nazývá konvoluce a integrály ve výrazech (24) .. (29) jsou konvoluční integrály, z nichž je vybrán ten s jednodušším integrandem.

Tato věta redukuje problém podmíněného extrému na superpozici problémů s nepodmíněným extrémem. Vlastně definujeme funkci R (g)

Superpozice ((>(f(x)), kde y(y) je neklesající konvexní funkce jedné proměnné, /(x) je konvexní funkce, je konvexní funkce.

Příklad 3.28. Vraťme se k příkladu 3.27. Na Obr. 3.24 ukazuje jako čárkovanou křivku výsledek superpozice dvou funkcí příslušnosti odpovídajících těm kvantifikátorům, které jsou v tomto příkladu. Pomocí mezní úrovně 0,7 byly získány fuzzy intervaly na ose x. Nyní můžeme říci, že dispečer by měl počkat na změnu plánu.

Jiný způsob, jak definovat funkci F, odlišný od metody superpozice, je ten, že při aplikaci libovolného kvantifikátoru na jiný kvantifikátor dojde k určité monotónní transformaci původní funkce příslušnosti, která redukuje na natahování a posun maxima funkce jedním směrem. nebo jiný.

Příklad 3.29. Na Obr. Obrázek 3.25 ukazuje dva výsledky získané se superpozicí a smykem s protažením pro případ, kdy XA a X často odpovídají kvantifikátoru. Rozdíl se zdá být v tom, že superpozice často vyčleňuje ty hodnoty ve funkci členství, které se často vyskytují. V případě posunu a roztažení můžeme výsledek interpretovat jako výskyt nového kvantifikátoru s hodnotou často-často , kterou lze na přání aproximovat např. hodnotou velmi často.

Ukažte, že superpozice přísně rostoucí funkce a funkce užitku reprezentující nějaký preferenční vztah > je také funkcí užitku reprezentující tento preferenční vztah. Která z následujících funkcí může fungovat jako taková transformace

První ze vztahů (2) není nic jiného než záznam pravidla, podle kterého je každá funkce F(x) patřící do rodiny monotónně neklesající absolutně spojité funkce spojena s jedinou spojitou funkcí w(j). Toto pravidlo je lineární, tzn. platí pro něj princip superpozice

Důkaz. Pokud je zobrazení F spojité, je funkce М0 spojitá jako superpozice spojitých funkcí . Chcete-li dokázat druhou část tvrzení, zvažte funkci

Komplexní e funkce (superpozice)

Metoda funkčních transformací také zahrnuje použití heuristického přístupu. Například použití logaritmických transformací jako operátorů B a C vede k informačním kritériím pro vytváření identifikovatelných modelů a použití výkonného nástroje teorie informace. Nechť operátor B je superpozice operátorů násobení funkcí, (.) a posun funkcí K0 (), operátor C - operátor

Zde budou obecně prezentovány výsledky řešení řady variačních problémů (1)-(3). Metodou sekvenční linearizace (19–21) byly řešeny již v letech 1962–1963, kdy se technologie metody teprve začínala formovat a testovala. Proto se zaměříme jen na některé detaily. Nejprve si všimneme, že funkce C a C2 byly dány poměrně složitými výrazy, které jsou superpozicí pomocných funkcí, včetně funkcí uvedených v tabulce. Proto při řešení konjugované soustavy φ=-fx pomocí funkcí uvedených v tabulce. Takové tabulky obvykle obsahují malý počet hodnot pro sadu uzlů v oblasti změny nezávislého argumentu a mezi nimi je funkce interpolována lineárně, protože použití přesnějších interpolačních metod není opodstatněné kvůli nepřesnost samotných hodnot tabulky (v tabulkách jsou zpravidla specifikovány funkční závislosti experimentálního charakteru). Pro naše účely však potřebujeme diferencovatelné funkce / (x, u), proto bychom měli preferovat hladké metody doplňování tabulkové funkce (například pomocí splajnů).

Nechť nyní (DA a (q) jsou libovolné funkce odpovídající některým hodnotám frekvenčních kvantifikátorů. Obrázek 3.23 ukazuje dvě jednohrotové křivky odpovídající těmto funkcím. Výsledkem jejich superpozice je dvojitá shrbená křivka, znázorněná přerušovaná čára. Co to znamená, když například (ANO je vzácné a (d - často,

Výhodou tohoto způsobu definování F je, že při monotónních transformacích se tvar funkce příslušnosti dramaticky nemění. Její unimodalita či monotonie je zachována a přechod z nového tvaru funkce (2.16) má lichoběžníkový tvar, lineární superpozice (2.15) je pak lichoběžníkové fuzzy číslo (což lze snadno dokázat pomocí pravidla pro výpočet segmentu ). A lze redukovat operace s funkcemi členství na operace s jejich vrcholy. Označíme-li číslo lichoběžníku (2.16) jako (ab, a2, az, a4), kde a odpovídá úsečkám vrcholů lichoběžníku, pak

- (pozdní lat. superpositio, - překrytí, z lat. superpositus - položeno navrch) (složení) - logická matematická operace. kalkul, který spočívá v získání z k.l. dané funkce f a g daného počtu nové funkce g (f) (výraz g ... ... Filosofická encyklopedie

Termín superpozice (překrytí) může označovat následující pojmy: Superpoziční složení funkcí (komplexní funkce) Princip superpozice je princip ve fyzice a matematice, který popisuje superpozici procesů (například vlnění) a v důsledku toho ... ... Wikipedie

Složení funkcí, složení dvou funkcí komplexní funkce ... Matematická encyklopedie

Tento termín má jiné významy, viz superpozice. Kvantová mechanika ... Wikipedie

Tento článek nebo sekce obsahuje seznam zdrojů nebo externích odkazů, ale zdroje jednotlivých prohlášení zůstávají nejasné kvůli nedostatku poznámek pod čarou ... Wikipedia

V teorii diskrétních funkčních systémů je booleovská funkce funkcí typu, kde je booleovská množina a n je nezáporné celé číslo, které se nazývá arita nebo lokalita funkce. Prvky 1 (jedna) a 0 (nula) jsou standardně interpretovány ... ... Wikipedie

Jeden z nejdůležitějších pro základy matematiky a matematiky. logické třídy pojmů, které slouží jako upřesnění obsahují. koncepty efektivně vypočitatelné aritmetické funkce a efektivně rozhodnutého aritmetického predikátu a nakonec a ... ... Filosofická encyklopedie

Funkce, která vypočítává hodnoty roje, může být provedena pomocí předem stanoveného efektivního postupu nebo algoritmu. Charakteristickým rysem výpočetních procesů je výpočet požadovaných hodnot problémů postupně od počátečních dat ... ... Matematická encyklopedie

Obsah tohoto článku je nutné přenést do článku "Diferenciace komplexní funkce". Projektu můžete pomoci konsolidací článků. Pokud potřebujete diskutovat o vhodnosti sloučení, nahraďte tuto šablonu šablonou ((sloučit)) ... Wikipedia

- (lat. compositio kompozice, vazba, doplnění, spojení): Wikipedie má heslo pro „kompozici“ Art Composition (výtvarné umění) je organizující složka umělecké formy, která dává design ... Wikipedia

knihy

• Diskrétní matematika. Základní množinově teoretické konstrukce. Část VI, A. I. Širokov. Příručka je VI částí sekce "Základní množinově teoretické konstrukce diskrétní matematiky". V kap. XI jsou uvažovány tyto pojmy: skladby funkcí (§1); funkce,…

Definice funkce, oblasti nastavení a sady hodnot. Definice související se zápisem funkcí. Definice komplexních, numerických, reálných, monotónních a vícehodnotových funkcí. Definice maxima, minima, horní a dolní meze pro omezené funkce.

Funkce y=f (X) nazývá se zákon (pravidlo, zobrazení), podle kterého je každý prvek x množiny X spojen s jedním a pouze jedním prvkem y množiny Y .

Množina X se nazývá rozsah funkce.
Sada prvků y ∈ Y, které mají předobrazy v množině X , se nazývá sada funkčních hodnot(nebo rozsah).

Doména funkce se někdy nazývají soubor definic nebo soubor úkolů funkcí.

Prvek x ∈ X volal argument funkce nebo nezávislé proměnné.
y prvek ∈ Y volal funkční hodnotu nebo závislá proměnná.

Samotné zobrazení f se nazývá funkční charakteristika.

Charakteristika f má tu vlastnost, že pokud dva prvky a z definiční množiny mají stejné hodnoty: , pak .

Znak označující charakteristiku může být shodný se znakem prvku funkční hodnoty. To znamená, že to můžete napsat takto: Zároveň je vhodné připomenout, že y je prvek z množiny funkčních hodnot a je pravidlem, podle kterého je prvek x spojen s prvkem y .

Samotný proces výpočtu funkce se skládá ze tří kroků. V prvním kroku vybereme prvek x z množiny X . Dále, pomocí pravidla , je prvek x asociován s prvkem množiny Y . Ve třetím kroku je tento prvek přiřazen k proměnné y.

Soukromá hodnota funkce pojmenujte hodnotu funkce pro vybranou (soukromou) hodnotu jejího argumentu.

Graf funkce f se nazývá množina párů.

Komplexní funkce

Definice
Nechte funkce a být dány. Navíc definiční obor funkce f obsahuje množinu hodnot funkce g. Potom každému prvku t z definičního oboru funkce g odpovídá prvek x a toto x odpovídá y . Tato korespondence se nazývá komplexní funkce: .

Také se nazývá komplexní funkce složení nebo superpozice funkcí a je někdy označován jako:

V matematické analýze je obecně přijímáno, že pokud je charakteristika funkce označena jedním písmenem nebo symbolem, pak nastavuje stejnou shodu. V jiných oborech však existuje jiný způsob zápisu, podle kterého jsou zobrazení se stejnou charakteristikou, ale různými argumenty, považována za odlišná. To znamená, že mapování a jsou považovány za odlišné. Vezměme si příklad z fyziky. Předpokládejme, že uvažujeme závislost hybnosti na souřadnici . A máme tu závislost souřadnice na čase . Pak je závislost hybnosti na čase komplexní funkcí. Ale pro stručnost se označuje takto:. S tímto přístupem a jsou různé funkce. Se stejnými hodnotami argumentů mohou dát různé hodnoty. V matematice se tento zápis nepřijímá. Je-li požadována redukce, je nutné zadat novou charakteristiku. Například . Pak je jasně vidět, že a jsou různé funkce.

Platné funkce

Rozsah funkce a množina jejích hodnot mohou být libovolné množiny.
Například číselné posloupnosti jsou funkce, jejichž doménou definice je množina přirozených čísel a množinou hodnot jsou reálná nebo komplexní čísla.
Křížový součin je také funkcí, protože pro dva vektory a existuje pouze jedna hodnota vektoru . Zde je doménou definice množina všech možných párů vektorů. Množina hodnot je množina všech vektorů.
Booleovský výraz je funkce. Jeho definičním oborem je množina reálných čísel (nebo jakákoliv množina, ve které je definována operace srovnání s prvkem „0“). Sada hodnot se skládá ze dvou prvků - „pravda“ a „nepravda“.

Číselné funkce hrají důležitou roli v matematické analýze.

Číselná funkce je funkce, jejíž hodnoty jsou reálná nebo komplexní čísla.

Skutečná nebo skutečná funkce je funkce, jejíž hodnoty jsou reálná čísla.

Maximum a minimum

Reálná čísla mají porovnávací operaci. Proto může být množina hodnot reálné funkce omezena a mít největší a nejmenší hodnoty.

Zavolá se skutečná funkce omezeno shora (zdola), pokud existuje takové číslo M, že pro všechny platí následující nerovnost:
.

Je volána funkce čísla omezený, pokud existuje číslo M takové, že pro všechny:
.

Maximum M (minimum m) funkce f , na nějaké množině X se nazývá hodnota funkce pro nějakou hodnotu jejího argumentu , pro kterou pro všechny ,
.

horní tvář nebo přesná horní hranice skutečná, shora ohraničená, funkce se nazývá nejmenší z čísel, které omezuje rozsah jejích hodnot shora. To znamená, že toto je číslo s, pro které pro všechny a pro libovolné existuje takový argument, jehož hodnota funkce přesahuje s′ : .
Horní mez funkce lze označit takto:
.

Horní mez funkce neomezené shora

spodní obličej nebo přesná spodní hranice reálná, zdola ohraničená, funkce se nazývá největší z čísel, které omezuje rozsah jejích hodnot zdola. To znamená, že toto je číslo i, pro které pro všechny a pro libovolné existuje takový argument , jehož hodnota je menší než i′ : .
Dolní mez funkce lze označit takto:
.

Dolní mez funkce neohraničená zdola je bod v nekonečnu.

Každá reálná funkce na neprázdné množině X má tedy horní a dolní mez. Ale ne každá funkce má maximum a minimum.

Jako příklad uvažujme funkci definovanou na otevřeném intervalu.
Na tomto intervalu je shora omezena hodnotou 1 a níže - hodnota 0 :
pro všechny .
Tato funkce má horní a spodní stranu:
.
Nemá ale žádné maximum a minimum.

Pokud uvažujeme stejnou funkci na intervalu , pak je na této množině omezena nad a pod, má horní a dolní hranice a má maximum a minimum:
pro všechny ;
;
.

Monotónní funkce

Definice rostoucích a klesajících funkcí
Nechť je funkce definována na nějaké množině reálných čísel X . Funkce je volána přísně rostoucí (přísně klesající)
.
Funkce je volána neklesající (nerostoucí), pokud pro všechny platí následující nerovnost:
.

Definice monotónní funkce
Funkce je volána monotónní je-li neklesající nebo nerostoucí.

Vícehodnotové funkce

Příklad vícehodnotové funkce. Jeho větve jsou označeny různými barvami. Každá větev je vlastnost.

Jak vyplývá z definice funkce, každý prvek x z definičního oboru je spojen pouze s jedním prvkem z množiny hodnot. Existují však zobrazení, ve kterých má prvek x několik nebo nekonečný počet obrázků.

Jako příklad zvažte funkci arcsinus: . Je to inverzní funkce sinus a určí se z rovnice:
(1) .
Pro danou hodnotu nezávisle proměnné x patřící do intervalu splňuje tato rovnice nekonečně mnoho hodnot y (viz obrázek).

Zaveďme omezení na řešení rovnice (1). Nechat
(2) .
Za této podmínky odpovídá daná hodnota pouze jednomu řešení rovnice (1). To znamená, že korespondence definovaná rovnicí (1) za podmínky (2) je funkcí.

Místo podmínky (2) lze uložit jakoukoli jinou podmínku formuláře:
(2.n) ,
kde n je celé číslo. Výsledkem je, že pro každou hodnotu n dostaneme vlastní funkci, odlišnou od ostatních. Mnoho z těchto funkcí je vícehodnotová funkce. A funkce určená z (1) za podmínky (2.n) je vícehodnotová funkční větev.

Toto je kolekce funkcí definovaných na nějaké množině.

Vícehodnotová funkční větev je jednou z funkcí zahrnutých do vícehodnotové funkce.

funkce s jednou hodnotou je funkce.

Reference:
O.I. Démoni. Přednášky o matematické analýze. Část 1. Moskva, 2004.
L.D. Kudrjavcev. Kurz matematické analýzy. Svazek 1. Moskva, 2003.
CM. Nikolského. Kurz matematické analýzy. Svazek 1. Moskva, 1983.

Jednocyklová (neobsahující paměťové prvky) diskrétní logická zařízení implementují na výstupu určitou sadu funkcí logické algebry `Fm=(F 1 ,F 2 ,…,Fm), které v každém okamžiku závisí pouze na stavu vstupů zařízení `x n =(X 1 ,X 2 ,…,xn): `F m = `F m(`x n). V praxi jsou taková zařízení navržena a vyrobena ze samostatných nedělitelných prvků, které realizují určitý soubor (systém) ( F) elementární funkce algebry připojením výstupů některých prvků ke vstupům jiných.

Při navrhování logických zařízení jsou relevantní následující otázky.

1. Systém elementárních funkcí ( F). Jaké jsou výstupní funkce F i lze získat pomocí funkcí z ( F}?

2. Sada výstupních booleovských funkcí ( F) (zejména rovný celé množině funkcí algebry logiky R 2). Jaký by měl být počáteční systém elementárních funkcí ( F), který poskytuje možnost získat na výstupu některou z funkcí sestavy ( F}?

Pro rozumnou odpověď na tyto otázky se používají pojmy superpozice, uzavřenost a úplnost systémů funkcí.

Definice. Zvažte sadu logických spojovacích prvků ( F) odpovídající nějakému systému funkcí ( F} . Superpozice skončila{F) je jakákoli funkce j, kterou lze implementovat vzorcem přes ( F}.

V praxi lze superpozici reprezentovat jako výsledek substituce funkcí z ( F) jako argumenty funkce ze stejné množiny.

Příklad 1. Zvažte systém funkcí ( F} = {F 1 (X) =`x, f 2 (x, y)= X&y, f 3 (x, y)=XÚ y). Střídání do funkce F 3 (x, y) místo prvního argumentu X funkce F 1 (X), místo druhého - F 2 (x, y), dostaneme superpozici h(x, y)=F 3 (F 1 (X), f 2 (x, y))=`xÚ X& na. Fyzické provedení substituce je uvedeno na obrázku 1.18.

Definice. Nechat M- nějaká množina funkcí algebry logiky ( P 2). Soubor všech superpozic skončil M volal uzavření sady M a označeno [ M]. Získání [ M]podle původní sady M volal zavírací operace. hromada M volal funkčně uzavřená třída, Pokud [ M] = M. Podmnožina mÍ M volal funkčně kompletní systém v M, Pokud [ m] = M.

Uzavření [ M] je celá sada funkcí, ze kterých lze získat M aplikací operace superpozice, tzn. všechny možné substituce.

Poznámky. 1. Je zřejmé, že jakýkoli systém funkcí ( F) je sám o sobě funkčně kompletní.

2 . Bez ztráty obecnosti můžeme předpokládat, že identická funkce F(X)=x, který nemění pravdivostní hodnoty proměnných, je zpočátku zahrnut do jakéhokoli systému funkcí.

Příklad 2. Pro níže uvedené systémy funkcí ( F) Udělej následující:

1) najít uzávěr [ F],

2) zjistěte, zda systém ( F) uzavřená třída,

3) najít funkčně kompletní systémy v ( F}.

Řešení.

I. ( F}={0} . Při nahrazení funkce ( fº 0) do sebe, dostaneme to, tzn. nejsou generovány žádné nové funkce. Z toho vyplývá: [ F] = {F). Uvažovaný systém je funkčně uzavřená třída. Funkčně úplný systém v něm je jeden a roven celku ( F}.

II. ( F} = {0,Ø } . Náhrada Ø (Ø X) dává identickou funkci, která formálně nerozšiřuje původní systém. Při dosazení Ø (0) však dostaneme identickou jednotku - novou funkci, která v původní soustavě nebyla: Ø (0)=1 . Použití všech ostatních substitucí nevede k novým funkcím, například: ØØ 0 = 0, 0 (Ø X)=0.

Aplikace operace superpozice tedy umožnila získat širší sadu funkcí oproti původní [ F]=(0,Ø,1). To znamená striktní zadání: ( F} Ì [ F]. Zdrojový systém ( F) není funkčně uzavřená třída. Kromě samotného systému F) nejsou v něm žádné další funkčně kompletní systémy, jelikož v případě jeho omezení z jedné funkce f= 0 nelze negovat substitucí a identickou nulu nelze získat z jediné negační funkce.

III. ( F) = (& ,Ú ,Ø ).Uzávěrem tohoto systému je celá množina funkcí logické algebry P 2, protože vzorec kteréhokoli z nich může být reprezentován jako DNF nebo CNF, které využívají elementární funkce ( F) = (& ,Ú ,Ø). Tato skutečnost je konstruktivním důkazem úplnosti uvažovaného systému funkcí v P 2: [F]=P 2 .

Protože v P 2 obsahuje nekonečné množství dalších funkcí kromě ( F) = (& ,Ú ,Ø ), pak to implikuje striktní výskyt: ( F}Ì[ F]. Uvažovaný systém není funkčně uzavřenou třídou.

Kromě samotného systému existují subsystémy ( F) 1 = (& ,Ø ) a ( F) 2 = (Ú ,Ø ). Vyplývá to ze skutečnosti, že pomocí de Morganových pravidel lze funkci logického sčítání Ú vyjádřit pomocí (& , Ø) a funkci logického násobení & pomocí (Ú, Ř):

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

Další funkčně kompletní subsystémy v ( F) Ne.

Kontrola úplnosti subsystému funkcí ( F) 1 М ( F) v celém systému ( F) lze vyrobit redukcí ( F) 1 jinému, zjevně dokončeno v ( F) Systém.

Neúplnost subsystému ( F) 1 in ( F) lze ověřit prokázáním striktního výskytu [ F 1] М [ F].

Definice. Podmnožina mÍ M volal funkční základ(základ)systémy M, Pokud [ m] = M, a po vyloučení jakékoli funkce z něj není sada zbývajících kompletní v M .

Komentář. Základy systému funkcí (F) jsou všechny jeho funkčně kompletní subsystémy (F) 1 , kterou nelze zmenšit bez ztráty úplnosti v (F).

Příklad 3. Pro všechny systémy uvažované v příkladu 2 najděte báze.

Řešení.V případech 1 a 2 jsou funkčně kompletní pouze samotné systémy a není možné je zúžit. Proto jsou také základy.

V případě 3 jsou dva funkčně kompletní v ( F)subsystémy ( F) 1 = (&,Ø ) a ( F) 2 =(Ú,Ø ), který nelze zmenšit bez ztráty úplnosti. Budou základem systému ( F} = {&,Ú,Ø}.

Definice. Nechte systém ( F) je uzavřená třída. Jeho podmnožina ( F) 1 М ( F) jsou nazývány předkompletní třída v{F), Pokud ( F) 1 je neúplný v ( F} ([F 1] М [ F]) a pro jakoukoli funkci j ze systému ( F) není zahrnuto v ( F) 1 (jО( F} \ {F) 1) je pravda: [ jÈ { F} 1 ] = [F], tj. sčítání jk ( F) 1 dokončí v ( F} .

Úkoly

1. Zkontrolujte uzavřenost množin funkcí:

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

2. Zkontrolujte úplnost systémů funkcí v P 2:

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

3. Najděte uzávěr systému funkcí a jeho základ:

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

1.10.2 Funkce, které zachovávají konstanty. Třídy T0 a T1

Definice. Funkce F(`x n) šetří 0 pokud F(0,..., 0) = 0. Funkce F(`x n) šetří 1 pokud F(1, ... , 1) = 1.

Spousta funkcí n proměnné, které ukládají 0 a 1 označují, resp. T 0 n A T 1 n. Všechny sady funkcí algebry logiky, které zachovávají 0 a 1 , určit T 0 A T 1. Každá ze sad T 0 a T 1 je uzavřená předkompletní třída v R 2 .

Od elementárních funkcí až po T 0 a T 1 zahrnuje například & a Ú. Příslušnost jakékoli funkce k třídám T 0 , T 1 lze zkontrolovat první a poslední hodnotou jejího vektoru hodnot v pravdivostní tabulce nebo přímou substitucí nul a jedniček ve vzorci, když je funkce analyticky specifikována.

Definice.Duplikát se nazývá taková substituce, kdy se místo několika nezávislých proměnných do funkce dosadí stejná proměnná. Hodnoty proměnných v sadách, které dříve nabíraly hodnoty nezávisle na sobě, budou zároveň vždy stejné.

ÚKOLY

1.Zkontrolujte členství ve třídě T 0 A T 1 funkce:

a) zobecněné sčítání, b) zobecněné násobení, c) konstanty, d) huÚ yz, e) X® na® hu, e) XÅ na, a)( X 1 Å … Å X n) ® ( y 1 Å … Å y m) kdy n,mÎ N.

2. Dokažte, že každá ze tříd je uzavřená T 0 A T 1 .

3. Dokažte, že pokud F(`x n) Ï T 0 , pak z ní lze duplikací substituce získat konstantu 1 nebo negaci.

4. Dokažte, že pokud F(`x n) Ï T 1 , pak z toho duplikováním substituce můžete získat konstantu 0 nebo negaci.

5. Dokažte předkompletnost každé z tříd T 0 A T 1 (například zmenšením rozšířeného systému na ( F} = {& ,Ú ,Ø }).

6. Najděte sílu tříd T 0 n A T 1 n.