Ať je nějaká sada K, skládající se z konečného počtu booleovských funkcí. Superpozicí funkcí z této množiny jsou nové funkce získané aplikací konečného počtu dvou operací;

můžete přejmenovat libovolnou proměnnou obsaženou ve funkci z K;

místo libovolné proměnné můžete vložit funkci ze sady K nebo dříve vytvořená superpozice.

Superpozice se také nazývá komplexní funkce.

Příklad 7. 1. Pokud je zadána jedna funkce X|y(Schaefferův tah), pak jeho superpozicemi budou zejména následující funkce x|x,x|(x|y),x|(y|z) atd.

Zavíráním sada funkcí z K se nazývá množina všech superpozic. Funkční třída K volal ZAVŘENO, pokud se jeho uzavření shoduje s ním samotným.

Zavolá se sada funkcí kompletní, pokud se jeho uzavření shoduje se všemi logickými funkcemi. Jinými slovy, úplná množina je množina takových funkcí, jejichž prostřednictvím lze vyjádřit všechny ostatní booleovské funkce.

Neredundantní kompletní sada funkcí se nazývá základ(„neredundantní“ znamená, že pokud bude některá funkce ze sady odstraněna, tato sada již nebude kompletní).

Příklad 7.2. Konjunkce, disjunkce a negace jsou kompletní množina (o tom jsme se přesvědčili v části 5), ale nejsou základem, protože tato množina je nadbytečná, protože pomocí De Morganových pravidel lze konjunkci nebo disjunkci odstranit. Jakákoli funkce může být reprezentována jako Zhegalkinův polynom (část 6). Je jasné, že funkce konjunkce, sčítání modulo 2 a konstanty 0 a 1 jsou kompletní množina, ale tyto čtyři funkce také nejsou základem, protože 1+1=0, a proto lze konstantu 0 vyloučit z úplné množina (pro konstrukci polynomů je nutná Zhegalkinova konstanta 0, protože výraz „1+1“ není Zhegalkinův polynom).

Je snadné vidět, že je to jeden ze způsobů, jak zkontrolovat úplnost některé sady NA je zkontrolovat, že funkce z této sady lze použít k vyjádření funkcí jiné kompletní sady (můžete zkontrolovat, že funkce z NA lze vyjádřit konjunkci a negaci nebo disjunkci a negaci.

Jsou funkce takové, že jedna taková je sama základem (zde stačí zkontrolovat pouze úplnost, neredundance je zřejmá). Takové funkce se nazývají Schefferovy funkce. Tento název je dán tím, že základem je Schaefferův zdvih. Připomeňme, že Schaefferovo prvočíslo je definováno následující pravdivostní tabulkou:

Protože je zřejmé, že negace je superpozicí Schaefferova tahu a disjunkce pak Schaefferův zdvih je sám o sobě základem. Stejně tak Peirceova šipka je Schefferova funkce (studenti si to mohou sami ověřit). Pro funkce 3 a více proměnných existuje spousta Shefferových funkcí (samozřejmě vyjádřit jiné booleovské funkce pomocí Shefferovy funkce velkého počtu proměnných je obtížné, proto se v technologii používají jen zřídka).

Všimněte si, že výpočetní zařízení je nejčastěji založeno na úplné sadě funkcí (často na základech). Pokud je zařízení založeno na konjunkci, disjunkci a negaci, pak je pro tato zařízení důležitý problém minimalizace DNF; Pokud je zařízení založeno na jiných funkcích, pak je užitečné mít možnost algoritmicky minimalizovat výrazy prostřednictvím těchto funkcí.

Přejděme nyní k objasnění úplnosti konkrétních sad funkcí. K tomu uvádíme 5 nejdůležitějších tříd funkcí:

• T 0 je množina všech těch logických funkcí, které mají hodnotu 0 na nulové sadě ( T 0 je třída funkce, konzervování 0);
• T 1 je množina všech logických funkcí, které mají hodnotu 1 na jednotkové sadě ( T 1 je třída funkcí, konzervační jednotka) (všimněte si, že počet funkcí z P proměnné patřící do tříd To a Ti se rovnají 2 2n-1);
• L- Třída lineární funkce, tj. funkce, pro které Zhegalkinův polynom obsahuje pouze první stupně proměnných;
• M- Třída monotónní funkcí. Popišme třídu těchto funkcí podrobněji. Nechť jsou 2 sady P proměnné: s1 = (x 1, x 2,..., x n)

s 1 = ( X 1 , X 2 , … , x n) a s 2 = (y 1 , y 2, … , y p). Řekneme, že množina s 1 je menší než množina s 2 (s 1 £ s 2 ), pokud jsou všechny x i £ y i .Je zřejmé, že ne všechny soubory zPproměnné jsou vzájemně srovnatelné (například kdyžn = 2 množiny (0,1) a (1,0) nejsou vzájemně srovnatelné). Funkce odPse nazývají proměnnémonotónní, pokud na menším souboru má menší nebo stejnou hodnotu. Tyto nerovnosti by se samozřejmě měly testovat pouze na srovnatelných sestavách. Je jasné, že nesrovnatelné množiny jsou ty, ve kterých jsou na odpovídajících místech nějaké souřadnice typu (0,1) v jedné množině a (1,0) v jiné (v diskrétní matematice jsou monotónní funkce jen „monotónně rostoucí funkce“ , funkce „monotónně klesající“ zde nejsou brány v úvahu).

Příklad. V následující tabulce funkce F 1 ,F 2 jsou monotónní funkce a funkce F 3 ,F 4 - Ne.

Přirozené pořadí proměnných je zajištěno tím, že pokud je některá množina menší než jiná množina, pak se nutně nachází v pravdivostní tabulce vyšší"větší" sada. Proto pokud v tabulce pravdy()nahoře jsou nuly,a pak jednotky,pak je tato funkce rozhodně monotónní.Jsou však možné inverze, tj. jednička předchází nějaké nuly, ale funkce je stále monotónní(v tomto případě by množiny odpovídající „horní“ jedničce a „dolní“ nule měly být nesrovnatelný; lze ověřit, že funkce daná pravdivostní tabulkou s přirozeným řádem množiny proměnných(00010101), je monotónní);

Teorém .Třídy funkcí T 0 ,T 1 ,L,M,S uzavřeno.

Toto tvrzení vyplývá přímo z definice těchto tříd samotných, stejně jako z definice uzavřenosti.

V teorii booleovských funkcí je velmi důležitá následující Postova věta.

Postova věta .Aby byla nějaká množina funkcí K úplná, je nutné a postačující, aby obsahovala funkce, které nepatří do každé z tříd T 0 ,T 1 ,L,M,S.

Všimněte si, že Co nutnost tento prohlášení zřejmé Tak Jak Li to je vše funkcí z nábor NA zahrnuta PROTI jeden z uvedeny třídy, Že A Všechno superpozice, A Prostředek, A zkrat nábor zahrnuta bych PROTI tento Třída A Třída NA Ne mohl být plný.

Přiměřenost tento prohlášení je prokázáno dost obtížný, Proto zde není zobrazeno.

Z této věty vyplývá celkem jednoduchý způsob, jak určit úplnost určité množiny funkcí. Pro každou z těchto funkcí je určeno členství ve třídách uvedených výše. Výsledky se zapisují do tzv Příspěvková tabulka(v našem příkladu je tato tabulka sestavena pro 4 funkce a znaménko „+“ označuje, že funkce patří do odpovídající třídy, znaménko „-“ znamená, že funkce v ní není zahrnuta).

Podle Postova teorému bude množina funkcí úplná právě tehdy, když je v každém sloupci Post tabulky alespoň jedno mínus. Z výše uvedené tabulky tedy vyplývá, že tyto 4 funkce tvoří kompletní sadu, ale tyto funkce nejsou základem. Z těchto funkcí můžete vytvořit 2 základy: F 3 ,F 1 A F 3 ,F 2. Kompletní množiny jsou jakékoli množiny obsahující nějaký základ.

Přímo z Postovy tabulky vyplývá, že počet bázových funkcí nemůže být větší než 5. Není těžké dokázat, že ve skutečnosti je tento počet menší nebo roven 4.

Nechť jsou 2 funkce:

: A→B a g: D→F

Nechť je definiční obor D funkce g zahrnut do definičního oboru hodnot funkce f (DB). Poté můžete definovat novou funkci - superpozice (kompozice, komplexní funkce) funkce f a g: z= G( (X)).

Příklady. f(x)=x2, g(x)=ex. f:R→R, g:R→R .

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

Definice

Nechť jsou dvě funkce. Pak je jejich složení funkcí definovanou rovností:

Vlastnosti složení

Složení je asociativní:

Li F= id X- identické mapování s X, to je

.

Li G= id Y- identické mapování s Y, to je

.

Další vlastnosti

Počitatelné a nepočitatelné množiny.

Dvě konečné množiny se skládají ze stejného počtu prvků, pokud lze mezi těmito množinami ustavit korespondenci jedna ku jedné. Počet prvků konečné množiny je mohutností množiny.

Pro nekonečnou množinu lze vytvořit vzájemnou korespondenci mezi celou množinou a její částí.

Nejjednodušší z nekonečných množin je množina N.

Definice. Množiny A a B se nazývají ekvivalent(AB), pokud mezi nimi lze navázat osobní korespondenci.

Pokud jsou dvě konečné množiny ekvivalentní, pak se skládají ze stejného počtu prvků.

Pokud jsou množiny A a B, které jsou si navzájem ekvivalentní, libovolné, pak říkají, že A a B mají totéž Napájení. (moc = ekvivalence).

U konečných množin se pojem mohutnosti shoduje s pojmem počtu prvků množiny.

Definice. Sada se nazývá počitatelný, pokud je možné stanovit vzájemnou korespondenci mezi ním a množinou přirozených čísel. (To znamená, že spočetná množina je nekonečná, ekvivalentní množině N).

(To znamená, že všechny prvky počitatelné množiny lze očíslovat).

Vlastnosti vztahu ekvimoci.

1) AA - reflexivita.

2) AB, pak BA – symetrie.

3) AB a BC, pak AC je tranzitivita.

Příklady.

1) n→2n, 2,4,6,… - i přirozené

2) n→2n-1, 1,3,5,… - liché přirozené.

Vlastnosti spočetných množin.

1. Nekonečné podmnožiny spočetné množiny jsou spočetné.

Důkaz. Protože A je spočetné, pak A: x 1, x 2,... - mapováno A na N.

ВА, В: →1,→2,… - přiřadilo každému prvku B přirozené číslo, tzn. mapováno B na N. Proto B je spočetné. Atd.

2. Sjednocení konečné (spočetné) soustavy spočetných množin je spočetné.

Příklady.

1. Množina celých čísel Z je spočetná, protože množinu Z lze reprezentovat jako sjednocení spočetných množin A a B, kde A: 0,1,2,.. a B: -1,-2,-3,...

2. Spousty objednal páry ((m,n): m,nZ) (tj. (1,3)≠(3,1)).

3 (!) . Množina racionálních čísel je spočetná.

Q=. Mezi množinou ireducibilních zlomků Q a množinou uspořádaných dvojic lze vytvořit vzájemnou korespondenci:

Že. množina Q je ekvivalentní množině ((p,q))((m,n)).

Množina ((m,n)) – množina všech uspořádaných dvojic – je spočetná. V důsledku toho je množina ((p,q)) spočetná, a proto je spočetná i Q.

Definice. Iracionální číslo je libovolné nekonečné desetinné číslo neperiodické zlomek, tzn.  0 , 1  2 …

Množina všech desetinných zlomků tvoří množinu reálná (reálná) čísla.

Množina iracionálních čísel je nepočitatelná.

Věta 1. Množina reálných čísel z intervalu (0,1) je nepočitatelná množina.

Důkaz. Předpokládejme opak, tj. že všechna čísla v intervalu (0,1) lze očíslovat. Když pak tato čísla zapíšeme ve formě nekonečných desetinných zlomků, dostaneme posloupnost:

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 …

……………………

Uvažujme nyní reálné číslo x=0,b 1 b 2 …b n…, kde b 1 je libovolné číslo odlišné od a 11, (0 a 9), b 2 je libovolné číslo odlišné od a 22, (0 a 9 ) ,…, b n - libovolné číslo odlišné od a nn, (0 a 9).

Že. x(0,1), ale xx i (i=1,…,n), protože jinak b i =a ii . Dospěli jsme k rozporu. Atd.

Věta 2. Jakýkoli interval reálné osy je nespočitatelná množina.

Věta 3. Množina reálných čísel je nespočitatelná.

O jakékoli množině rovné množině reálných čísel se říká, že je nepřetržitý výkon(lat. kontinuum - spojitý, spojitý).

Příklad. Ukažme, že interval má sílu kontinua.

Funkce y=tg x: →R zobrazí interval na celé číselné ose (grafu).

Superpozice funkcí

Superpozice funkcí f1, ..., fm je funkce f získaná vzájemným dosazením těchto funkcí a přejmenováním proměnných.

Nechť jsou dvě zobrazení a navíc neprázdná množina. Pak superpozice nebo složení funkcí je funkce definovaná rovností pro každého.

Definiční obor superpozice je množina.

Funkce se nazývá vnější a vnitřní funkce pro superpozici.

Funkce prezentované jako složení „jednodušších“ se nazývají komplexní funkce.

Příklady použití superpozice jsou: řešení soustavy rovnic substitucí; nalezení derivace funkce; nalezení hodnoty algebraického výrazu dosazením hodnot zadaných proměnných do něj.

Rekurzivní funkce

Rekurze je metoda definování funkce, ve které jsou hodnoty definované funkce pro libovolné hodnoty argumentů vyjádřeny známým způsobem prostřednictvím hodnot definované funkce pro menší hodnoty argumentů.

Primitivně rekurzivní funkce

Definice pojmu primitivní rekurzivní funkce je induktivní. Skládá se ze zadání třídy základních primitivních rekurzivních funkcí a dvou operátorů (superpozice a primitivní rekurze), které vám umožňují konstruovat nové primitivní rekurzivní funkce založené na těch stávajících.

Mezi základní primitivní rekurzivní funkce patří následující tři typy funkcí:

Nulová funkce je funkce bez argumentů, která se vždy vrací 0 .

Funkce posloupnosti jedné proměnné, která spojuje libovolné přirozené číslo s bezprostředně následujícím přirozeným číslem.

Funkce, kde z n proměnných mapuje libovolnou uspořádanou množinu přirozených čísel na číslo z této množiny.

Operátory substituce a primitivní rekurze jsou definovány takto:

Operátor superpozice (někdy substituční operátor). Nechť je funkcí m proměnných a nechť je uspořádaná množina funkcí, každá s proměnnými. Pak výsledkem superpozice funkcí do funkce je funkce proměnných, která spojuje číslo s libovolnou uspořádanou množinou přirozených čísel.

Operátor primitivní rekurze. Nechť je funkcí n proměnných a nechť je funkcí proměnných. Potom se výsledek aplikace primitivního rekurzního operátoru na dvojici funkcí nazývá funkce proměnné tvaru;

V této definici lze proměnnou chápat jako iterační čítač, - jako počáteční funkci na začátku iteračního procesu, který vytváří určitou sekvenci proměnných funkcí počínaje, a - jako operátor, který bere jako proměnný vstup počet iterační krok, funkci v daném iteračním kroku a vrátí funkci v dalším iteračním kroku.

Sada primitivních rekurzivních funkcí je minimální sada, která obsahuje všechny základní funkce a je uzavřena pod zadanými operátory substituce a primitivní rekurze.

Z hlediska imperativního programování odpovídají primitivní rekurzivní funkce programovým blokům, které používají pouze aritmetické operace, stejně jako podmíněný operátor a operátor aritmetické smyčky (operátor smyčky, ve kterém je na začátku smyčky znám počet iterací). Pokud programátor začne používat operátor cyklu while, u kterého je počet iterací předem neznámý a v zásadě může být nekonečný, přechází do třídy částečně rekurzivních funkcí.

Uveďme řadu známých aritmetických funkcí, které jsou primitivně rekurzivní.

Funkce sčítání dvou přirozených čísel () může být považována za primitivní rekurzivní funkci dvou proměnných, získanou aplikací primitivního rekurzního operátoru na funkce a z nichž druhá se získá dosazením hlavní funkce do hlavní funkce:

Násobení dvou přirozených čísel lze považovat za primitivní rekurzivní funkci dvou proměnných, získanou aplikací primitivního rekurzního operátoru na funkce a z nichž druhá se získá dosazením základních funkcí a do funkce sčítání:

Symetrický rozdíl (absolutní hodnota rozdílu) dvou přirozených čísel () lze považovat za primitivní rekurzivní funkci dvou proměnných, získanou aplikací následujících substitucí a primitivních rekurzí:

Funkce sestavení

Nabízíme vám službu pro vytváření grafů funkcí online, ke které patří veškerá práva společnosti Desmos. Pro zadání funkcí použijte levý sloupec. Můžete zadat ručně nebo pomocí virtuální klávesnice v dolní části okna. Pro zvětšení okna s grafem můžete skrýt jak levý sloupec, tak virtuální klávesnici.

Výhody online mapování

• Vizuální zobrazení zadaných funkcí
• Vytváření velmi složitých grafů
• Konstrukce grafů zadaných implicitně (například elipsa x^2/9+y^2/16=1)
• Možnost ukládat grafy a dostávat na ně odkaz, který bude dostupný všem na internetu
• Ovládání měřítka, barvy čáry
• Možnost vykreslování grafů po bodech, pomocí konstant
• Vykreslování několika funkčních grafů současně
• Vykreslování v polárních souřadnicích (použijte r a θ(\theta))

S námi je snadné vytvářet online grafy různé složitosti. Stavba je provedena okamžitě. Služba je žádaná pro hledání průsečíků funkcí, pro zobrazení grafů pro jejich další přesun do dokumentu Wordu jako ilustrace při řešení problémů a pro analýzu behaviorálních rysů funkčních grafů. Optimálním prohlížečem pro práci s grafy na této webové stránce je Google Chrome. Při použití jiných prohlížečů není zaručena správná funkce.

Jednocyklová (neobsahující paměťové prvky) diskrétní logická zařízení implementují na výstupu určitou sadu funkcí logické algebry `F m =(F 1 ,F 2 ,…,F m), které v každém okamžiku závisí pouze na stavu vstupů zařízení `x n =(X 1 ,X 2 ,…,x n): `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 propojením výstupů některých prvků se vstupy jiných.

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

1. Je dán 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), poskytující možnost získat na výstupu kteroukoli z funkcí sestavy ( F}?

K poskytnutí rozumné odpovědi na tyto otázky se používají pojmy superpozice, uzavřenost a úplnost systémů funkcí.

Definice. Podívejme se na 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 realizovat pomocí vzorce nad ( F}.

V praxi může být superpozice reprezentována 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. 1.18.

Definice. Nechat M-určitá sada funkcí logické algebry( P 2). Soubor všech superpozic skončil M volal zkrat sady M a je označeno [ M]. Příjem [ M]podle původní sady M volal operace uzavření. 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] představuje celou sadu 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 identita funguje F(X)=x, který nemění pravdivostní hodnoty proměnných, je zpočátku součástí jakéhokoli systému funkcí.

Příklad 2. Pro systémy funkcí popsaných níže ( 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) přijímáme to do sebe, tzn. nevytvářejí se žá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 získáme identickou jednotku - novou funkci, která v původní soustavě nebyla: Ø (0)=1 . Aplikace všech ostatních substitucí nevede ke vzniku nových funkcí, například: ØØ 0 = 0, 0 (Ø X)=0.

Použití operace superpozice tedy umožnilo získat širší sadu funkcí, než byla 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ě ucelené systémy, jelikož v případě jeho zúžení z jedné funkce f= 0 nelze negovat substitucí a stejnou nulu nelze získat pouze z negační funkce.

III. ( F) = (& ,Ú ,Ø ).Uzávěrem tohoto systému je celá množina funkcí algebry logiky P 2, protože vzorec kteréhokoli z nich může být reprezentován jako DNF nebo CNF, který používá 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 .

Od 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 budou funkčně kompletní i 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í & prostřednictvím (Ú, Ø):

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

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

Kontrola úplnosti funkčního subsystému ( F) 1 М ( F) v celém systému ( F) lze vyrobit kombinací ( 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 odstranění jakékoli funkce z něj není sada zbývajících kompletní 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. V důsledku toho jsou také základy.

V případě 3 jsou dvě 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 juniorská třída v{F), Pokud ( F) 1 není kompletní v ( F} ([F 1] М [ F]) a pro jakoukoli funkci j ze systému ( F), není zahrnuto v ( F) 1 (jО( F} \ {F) 1) pravda: [ jÈ { F} 1 ] = [F], tj. přidání jk ( F) 1 dokončí v ( F} .

Úkoly

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

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

2. Zkontrolujte úplnost funkčních systémů 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é ukládají 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, jsou označeny, resp. T 0 n A T 1 n. Všechny sady funkcí logické algebry, které zachovávají 0 a 1 , označovat 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 jsou současně zahrnuty například & a Ú. Příslušnost jakékoli funkce k třídám T 0 , T 1 lze zkontrolovat první a poslední hodnotou jeho vektoru hodnot v pravdivostní tabulce nebo přímým dosazením nul a jedniček do vzorce při analytickém zadávání funkce.

Definice.Duplikát je substituce, ve které je stejná proměnná nahrazena funkcí místo několika nezávislých proměnných. V tomto případě budou hodnoty proměnných v sadách, které dříve nabíraly hodnoty nezávisle na sobě, 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) xyÚ yz, d) X® na® xy, e) XÅ na, a)( X 1 Å … Å X n) ® ( y 1 Å … Å y m) v n,mÎ N.

2. Dokažte uzavřenost každé třídy T 0 A T 1 .

3. Dokažte, že pokud F(`x n) Ï T 0, pak z ní duplikací substituce můžete 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.