Operácia superpozície funkcií. Superpozícia funkcií. Vlastnosti boolovských funkcií

Nech existuje funkcia f(x 1 , x 2 , ... , x n) a funkcie

potom zavoláme funkciu superpozícia funkcie f(x 1 , x 2 , ... , x n) a funkcie .

Inými slovami: nech F = ( f j ) - súbor funkcií logickej algebry, ktorý nemusí byť nutne konečný. Funkcia f sa nazýva superpozícia funkcií z množiny F alebo funkcia nad F, ak sa získa z funkcie nahradením jednej alebo viacerých jej premenných funkciami z množiny F.

Príklad.

Nech je daný súbor funkcií

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

Potom superpozície funkcií z F budú napríklad funkcie:

j1 (x2, x 3) = f3 (f1 (x 2), f1 (x 3));

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

Dokonalé DNF - superpozícia funkcií zo sady

. ð

Definícia.

Systém funkcií je tzv plný Ak použijeme operácie superpozície a náhrady premenných, z funkcií tohto systému možno získať akúkoľvek funkciu algebry logiky. ð

Už máme určitý súbor kompletných systémov:

;

Pretože ;

Pretože ;

(x+y, xy, 1). ð

Ako môžeme určiť podmienky, za ktorých je systém kompletný? S pojmom úplnosť úzko súvisí pojem uzavretej triedy.

Uzavreté triedy.

Množina (trieda) K funkcií algebry logiky sa nazýva uzavretá trieda, ak obsahuje všetky funkcie získané z K operáciami superpozície a zmeny premenných a neobsahuje žiadne ďalšie funkcie.

Nech K je nejaká podmnožina funkcií z P 2 . Uzáver množiny K je množina všetkých booleovských funkcií, ktoré možno znázorniť pomocou operácií superpozície a zmeny premenných funkcií z množiny K. Uzáver množiny K označujeme [K].

Pokiaľ ide o uzavretie, môžeme uviesť ďalšie definície uzavretia a úplnosti (ekvivalentné pôvodným):

K je uzavretá trieda, ak K = [K];

K je úplný systém, ak [K] = P 2 .

Príklady.

* (0), (1) - uzavreté triedy.

* Množina funkcií jednej premennej je uzavretá trieda.

* - uzavretá trieda.

* Trieda (1, x+y) nie je uzavretá trieda.

Pozrime sa na niektoré z najdôležitejších uzavretých tried.

1. T 0- trieda funkcií, ktoré zachovávajú 0.

Označme T 0 triedu všetkých funkcií algebry logiky f(x 1, x 2, ... , x n) so zachovaním konštanty 0, teda funkcií, pre ktoré f(0, ... , 0 ) = 0.

Je ľahké vidieť, že existujú funkcie, ktoré patria do T 0, a funkcie, ktoré do tejto triedy nepatria:

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

Z toho, že Ï T 0 vyplýva napríklad, že sa nedá vyjadriť pomocou disjunkcie a konjunkcie.

Keďže tabuľka pre funkciu f z triedy T 0 obsahuje v prvom riadku hodnotu 0, tak pre funkcie z T 0 môžete nastaviť ľubovoľné hodnoty len na 2 n - 1 množine hodnôt premenných, tzn.

,

kde je množina funkcií, ktoré zachovávajú 0 a závisia od n premenných.

Ukážme, že T 0 je uzavretá trieda. Keďže xÎT 0 , potom na zdôvodnenie uzavretosti stačí ukázať uzavretosť vzhľadom na operáciu superpozície, keďže operácia meniacich sa premenných je špeciálnym prípadom superpozície s funkciou x.

Nechajte . Potom to stačí ukázať. To posledné vyplýva z reťazca rovnosti

2. T 1- trieda funkcií zachovávajúca 1.

Označme T 1 triedu všetkých funkcií algebry logiky f(x 1, x 2, ... , x n) so zachovaním konštanty 1, teda funkcií, pre ktoré f(1, ... , 1 ) = 1.

Je ľahké vidieť, že existujú funkcie, ktoré patria do T 1, a funkcie, ktoré nepatria do tejto triedy:

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

0, , x+y Ï T 1 .

Z toho, že x + y Ï T 0 napríklad vyplýva, že x + y nemožno vyjadriť pomocou disjunkcie a konjunkcie.

Výsledky o triede T 0 sa triviálne prenášajú do triedy T 1 . Máme teda:

T 1 - uzavretá trieda;

.

3. L- trieda lineárnych funkcií.

Označme L triedu všetkých funkcií algebry logiky f(x 1 , x 2 , ... , x n), ktoré sú lineárne:

Je ľahké vidieť, že existujú funkcie, ktoré patria do L a funkcie, ktoré nepatria do tejto triedy:

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

Dokážme napríklad, že xÚy Ï L .

Predpokladajme opak. Budeme hľadať výraz pre xÚy v tvare lineárnej funkcie s neurčitými koeficientmi:

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

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

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

ale potom pre x = 1, y = 1 máme 1v 1 ¹ 1 + 1, čo dokazuje nelinearitu funkcie xy.

Dôkaz uzavretosti triedy lineárnych funkcií je celkom zrejmý.

Keďže lineárna funkcia je jednoznačne určená zadaním hodnôt n+1 koeficientu a 0, ... , a n , počet lineárnych funkcií v triede L (n) funkcií závislých od n premenných sa rovná 2 n+1.

.

4. S- trieda sebadvojných funkcií.

Definícia triedy sebaduálnych funkcií je založená na využití takzvaného princípu duality a duálnych funkcií.

Zavolá sa funkcia definovaná rovnosťou dvojitá funkcia .

Je zrejmé, že tabuľka pre duálnu funkciu (so štandardným usporiadaním množín premenných hodnôt) sa získa z tabuľky pre pôvodnú funkciu invertovaním (tj nahradením 0 1 a 1 0) stĺpca funkčných hodnôt. a prevrátiť ho.

Je ľahké to vidieť

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

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

Z definície vyplýva, že (f*)* = f, čiže funkcia f je duálna k f*.

Nech je funkcia vyjadrená pomocou superpozície cez iné funkcie. Otázkou je, ako vytvoriť vzorec, ktorý implementuje ? Označme = (x 1, ..., x n) všetky rôzne variabilné symboly nachádzajúce sa v množinách.

Veta 2.6. Ak sa funkcia j získa ako superpozícia funkcií f, f 1, f 2, ..., f m, tj.

funkcia duálna k superpozícii je superpozícia duálnych funkcií.

Dôkaz.

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

Veta bola dokázaná. ð

Princíp duality vyplýva z vety: ak vzorec A realizuje funkciu f(x 1 , ... , x n), potom vzorec získaný z A nahradením funkcií v ňom zahrnutých ich duálnymi realizuje duálnu funkciu f *(x 1, ..., xn).

Označme S triedu všetkých samoduálnych funkcií z P 2:

S = (f | f* = f)

Je ľahké vidieť, že existujú funkcie, ktoré patria do S, a funkcie, ktoré nepatria do tejto triedy:

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

Menej triviálnym príkladom samoduálnej funkcie je funkcia

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

Použitím vety o funkcii dual to superposition máme

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

Pre dvojakú funkciu platí identita

tak na súpravách a , ktoré budeme nazývať opačné, samoduálna funkcia nadobúda opačné hodnoty. Z toho vyplýva, že samoduálna funkcia je úplne určená jej hodnotami v prvej polovici riadkov štandardnej tabuľky. Preto sa počet samoduálnych funkcií v triede S (n) funkcií v závislosti od n premenných rovná:

.

Dokážme teraz, že trieda S je uzavretá. Keďže xÎS , potom na zdôvodnenie uzavretosti stačí ukázať uzavretosť vzhľadom na operáciu superpozície, keďže operácia meniacich sa premenných je špeciálnym prípadom superpozície s funkciou x. Nechajte . Potom to stačí ukázať. Ten sa inštaluje priamo:

5. M- trieda monotónnych funkcií.

Pred definovaním pojmu monotónna funkcia v algebre logiky je potrebné zaviesť vzťah usporiadania na množine množín jej premenných.

Hovorí sa, že set prichádza pred setom (alebo „nie viac ako“ alebo „menej alebo rovné“) a označenie použite, ak a i £ b i pre všetky i = 1, ... , n. Ak a , potom povieme, že množina striktne predchádza množine (alebo „striktne menej“ alebo „menej ako“ množina), a použijeme zápis . Množiny a sa nazývajú porovnateľné, ak buď , alebo , V prípade, že ani jeden z týchto vzťahov neplatí, množiny a sa nazývajú neporovnateľné. Napríklad (0, 1, 0, 1) £ (1, 1, 0, 1), ale množiny (0, 1, 1, 0) a (1, 0, 1, 0) sú neporovnateľné. Relácia £ (často nazývaná relácia priority) je teda čiastočným usporiadaním na množine B n. Nižšie sú uvedené schémy čiastočne usporiadaných súprav B 2, B 3 a B 4.

Zavedený parciálny objednávkový vzťah je mimoriadne dôležitý pojem, ktorý ďaleko presahuje rámec nášho kurzu.

Teraz máme možnosť definovať pojem monotónna funkcia.

Volá sa funkcia logickej algebry monotónna, Ak pre akékoľvek dve množiny a , Tak, že , Nerovnosť platí . Množinu všetkých monotónnych funkcií algebry logiky označujeme M a množinu všetkých monotónnych funkcií závislých od n premenných označujeme M(n).

Je ľahké vidieť, že existujú funkcie, ktoré patria do M a funkcie, ktoré nepatria do tejto triedy:

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

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

Ukážme, že trieda monotónnych funkcií M je uzavretá trieda. Keďže xОМ, potom na zdôvodnenie uzavretosti stačí ukázať uzavretosť vzhľadom na operáciu superpozície, keďže operácia meniacich sa premenných je špeciálnym prípadom superpozície s funkciou x.

Nechajte . Potom to stačí ukázať.

Nech sú množiny premenných, respektíve funkcie j, f 1 , ... , f m , a množina premenných funkcie j pozostáva z tých a len tých premenných, ktoré sa vyskytujú vo funkciách f 1 , ... , f m . Dovoliť a byť dve sady hodnôt premennej a . Tieto množiny definujú množiny premenné hodnoty , také že . Vzhľadom na monotónnosť funkcií f 1 , ... , f m

a vzhľadom na monotónnosť funkcie f

Odtiaľto sa dostaneme

Počet monotónnych funkcií závislých od n premenných nie je presne známy. Spodnú hranicu možno ľahko získať:

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

Tiež sa ukazuje, že je to príliš vysoký odhad zhora:

Spresnenie týchto odhadov je dôležitou a zaujímavou úlohou moderného výskumu.

Kritérium úplnosti

Teraz sme schopní sformulovať a dokázať kritérium úplnosti (Postov teorém), ktoré určuje nevyhnutné a postačujúce podmienky pre úplnosť systému funkcií. Pred formuláciou a dôkazom kritéria úplnosti uvedieme niekoľko nevyhnutných lém, ktoré majú nezávislý význam.

Lema 2.7. Lema o nesebaduálnej funkcii.

Ak f(x 1 , ... , x n)Ï S , potom z neho možno získať konštantu dosadením funkcií x a `x.

Dôkaz. Od fÏS potom existuje množina hodnôt premenných
=(a 1 ,...,a n) také, že

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

Nahradime argumenty vo funkcii f:

x i sa nahrádza výrazom ,

to znamená, že položme a zvážime funkciu

Takto sme dostali konštantu (hoci nie je známe, ktorá konštanta to je: 0 alebo 1). ð

Lema 2.8. Lema o nemonotónnej funkcii.

Ak je funkcia f(x 1 ,...,x n) nemonotónna, f(x 1 ,...,x n) Ï M, potom z nej možno získať negáciu zmenou premenných a dosadením konštánt 0 a 1.

Dôkaz. Keďže f(x 1 ,...,x n) Ï M, potom existujú množiny hodnôt jeho premenných, , tak, že a aspoň pre jednu hodnotu i, a i< b i . Выполним следующую замену переменных функции f:

x i bude nahradené

Po takejto substitúcii dostaneme funkciu jednej premennej j(x), pre ktorú platí:

To znamená, že j(x)=`x. Lema je dokázaná. ð

Lema 2.9. Lema o nelineárnej funkcii.

Ak f(x 1 ,...,x n) Ï L , tak z neho dosadením konštánt 0, 1 a pomocou funkcie `x získame funkciu x 1 &x 2 .

Dôkaz. Predstavme f ako DNF (napríklad dokonalé DNF) a použite vzťahy:

Príklad. Uveďme dva príklady aplikácie týchto transformácií.

Funkcia napísaná v disjunktívnej normálnej forme sa teda po použití naznačených vzťahov, otvárania zátvoriek a jednoduchých algebraických transformácií stáva polynómom mod 2 (Zhegalkinovým polynómom):

kde A 0 je konštanta a A i je konjunkcia niektorých premenných z čísla x 1,..., x n, i = 1, 2, ..., r.

Ak každá spojka A i pozostáva len z jednej premennej, potom f je lineárna funkcia, čo je v rozpore s podmienkou lemy.

V dôsledku toho v Zhegalkinovom polynóme pre funkciu f existuje člen, ktorý obsahuje aspoň dva faktory. Bez straty všeobecnosti môžeme predpokladať, že medzi týmito faktormi sú premenné x 1 a x 2. Potom je možné polynóm transformovať 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 (inak polynóm neobsahuje spojku obsahujúcu spojku x 1 x 2).

Nech (a 3 ,...,a n) je také, ž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 sú konštanty rovné 0 alebo 1.

Použime operáciu negácie, ktorú máme a uvažujme funkciu y(x 1 ,x 2) získanú z j(x 1 ,x 2) takto:

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

To je zrejmé

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

teda

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

Lema je úplne dokázaná. ð

Lema 2.10. Hlavná lemma kritéria úplnosti.

Ak trieda F=( f ) funkcií algebry logiky obsahuje funkcie, ktoré nezachovávajú jednotu, nezachovávajú 0, nie sú samoduálne a nemonotónne:

potom z funkcií tohto systému pomocou operácií superpozície a nahradenia premenných možno získať konštanty 0, 1 a funkciu.

Dôkaz. Zoberme si funkciu. Potom

.

Existujú dva možné prípady následných úvah, ktoré sú v nasledujúcej prezentácii označené ako 1) a 2).

1). Funkcia na jednotke má hodnotu 0:

.

Všetky premenné funkcie nahraďme premennou x. Potom funkcia

existuje, pretože

A .

Zoberme si nesebeckú funkciu. Keďže sme funkciu už získali, potom pomocou lemy na nesebecuálnej funkcii (lemma 2.7. ) môžete získať konštantu z. Druhú konštantu možno získať z prvej pomocou funkcie. Takže v prvom uvažovanom prípade sa získajú konštanty a negácia. . Druhý prípad a s ním aj hlavná lemma kritéria úplnosti sú úplne dokázané. ð

Veta 2.11. Kritérium úplnosti systémov funkcií v algebre logiky (Postova veta).

Aby bola sústava funkcií F = (f i) úplná, je potrebné a postačujúce, aby nebola celá obsiahnutá v žiadnej z piatich uzavretých tried T 0, T 1, L, S, M, teda napr. každá z tried To, T1, L, S, M v F existuje aspoň jedna funkcia, ktorá nepatrí do tejto triedy.

Nevyhnutnosť. Nech F je úplný systém. Predpokladajme, že F je obsiahnutá v niektorej z uvedených tried, označme ju K, t.j. F Í K. Posledné zaradenie nie je možné, keďže K je uzavretá trieda, ktorá nie je úplným systémom.

Primeranosť. Nech celý systém funkcií F = (f i) nie je obsiahnutý v žiadnej z piatich uzavretých tried T 0 , T 1 , L , S , M. Zoberme si nasledujúce funkcie v F:

Potom na základe hlavnej lemy (lemma 2.10 ) z funkcie, ktorá nezachová 0, z funkcie, ktorá nezachová 1, z nesamoduálnych a nemonotónnych funkcií sa dajú získať konštanty 0, 1 a negačná funkcia:

.

Na základe lemy o nelineárnych funkciách (lemma 2.9 ) z konštánt, negácie a nelineárnej funkcie získame konjunkciu:

.

Funkčný systém - úplný systém podľa vety o možnosti reprezentovať akúkoľvek funkciu algebry logiky vo forme dokonalej disjunktívnej normálnej formy (všimnite si, že disjunkciu možno vyjadriť konjunkciou a negáciou v tvare ).

Veta je úplne dokázaná. ð

Príklady.

1. Ukážme, že funkcia f(x,y) = x|y tvorí úplný systém. Zostavme si tabuľku hodnôt funkcie x½y:

X	r	x|y

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

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

f(0,0) = 1, f(1,1) = 0, teda x | yÏM.

f(0,1) = f(1,0) = 1, - na opačných množinách x | y nadobúda rovnaké hodnoty, preto x | yÏS .

Nakoniec, čo znamená nelinearita funkcie?
x | r.

Na základe kritéria úplnosti môžeme konštatovať, že f(x,y) = x | y tvorí ucelený systém. ð

2. Ukážme, že systém funkcií tvorí ucelený systém.

Naozaj,.

Medzi funkciami nášho systému sme teda našli: funkciu, ktorá nezachováva 0, funkciu, ktorá nezachová 1, nesebaduálne, nemonotónne a nelineárne funkcie. Na základe kritéria úplnosti možno tvrdiť, že systém funkcií tvorí ucelený systém. ð

Preto sme presvedčení, že kritérium úplnosti poskytuje konštruktívny a efektívny spôsob, ako určiť úplnosť systémov funkcií v algebre logiky.

Sformulujme teraz tri dôsledky z kritéria úplnosti.

Dôsledok 1. Akákoľvek uzavretá trieda K funkcií algebry logiky, ktorá sa nezhoduje s celou množinou funkcií logickej algebry (K¹P 2), je obsiahnutá aspoň v jednej zo skonštruovaných uzavretých tried.

Definícia. Uzavretá trieda K sa nazýva predplné, ak je K neúplné a pre ľubovoľnú funkciu fÏ K je trieda K È (f) úplná.

Z definície vyplýva, že predkompletná trieda je uzavretá.

Dôsledok 2. V algebre logiky existuje iba päť predkompletných tried, a to: T 0, T 1, L, M, S.

Ak chcete dokázať dôsledok, stačí skontrolovať, či žiadna z týchto tried nie je obsiahnutá v druhej, čo potvrdzuje napríklad nasledujúca tabuľka funkcií patriacich do rôznych tried:

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

Dôsledok 3. Z akéhokoľvek úplného systému funkcií je možné rozlíšiť úplný podsystém obsahujúci najviac štyri funkcie.

Z dôkazu o kritériu úplnosti vyplýva, že nie je možné rozlíšiť viac ako päť funkcií. Z dôkazu hlavnej lemy (Lemma 2.10 ) z toho vyplýva je buď nesebaduálna, alebo nezachováva jednotu a nie je monotónna. Preto nie sú potrebné viac ako štyri funkcie.

Zoznámime sa s pojmom superpozícia (alebo impozícia) funkcií, ktorá spočíva v dosadení funkcie z iného argumentu namiesto argumentu danej funkcie. Napríklad superpozícia funkcií dáva funkciu a podobne sa získajú funkcie

Vo všeobecnosti predpokladajme, že funkcia je definovaná v určitej doméne a funkcia je definovaná v doméne a jej hodnoty sú všetky obsiahnuté v doméne. Potom premenná z, ako sa hovorí, cez y, je sama funkciou

Pri danej hodnote najprv nájdu hodnotu y, ktorá jej zodpovedá (podľa pravidla charakterizovaného znamienkom), a potom nastavia zodpovedajúcu hodnotu y (podľa pravidla

charakterizované znamienkom, jeho hodnota sa považuje za zodpovedajúcu zvolenému x. Výsledná funkcia z funkcie alebo komplexnej funkcie je výsledkom superpozície funkcií

Predpoklad, že hodnoty funkcie neprekračujú hranice oblasti Y, v ktorej je funkcia definovaná, je veľmi významný: ak sa vynechá, môže dôjsť k absurdnosti. Napríklad za predpokladu, že môžeme brať do úvahy iba tie hodnoty x, pre ktoré by inak výraz nedával zmysel.

Tu považujeme za užitočné zdôrazniť, že charakterizácia funkcie ako komplexnej nesúvisí s povahou funkčnej závislosti z na x, ale len so spôsobom, akým je táto závislosť špecifikovaná. Napríklad, nech pre y v pre Potom

Tu sa ukázalo, že funkcia je špecifikovaná ako komplexná funkcia.

Teraz, keď je koncept superpozície funkcií úplne pochopený, môžeme presne charakterizovať najjednoduchšie triedy funkcií, ktoré sa študujú v analýze: sú to predovšetkým vyššie uvedené elementárne funkcie a potom všetky tie, ktoré sa z nich získajú. pomocou štyroch aritmetických operácií a superpozícií postupne aplikovaných konečný počet krát. Hovorí sa, že sú vyjadrené prostredníctvom elementárneho vo svojej konečnej podobe; niekedy sa nazývajú aj elementárne.

Následne po zvládnutí zložitejšieho analytického aparátu (nekonečné rady, integrály) sa zoznámime s ďalšími funkciami, ktoré tiež zohrávajú dôležitú úlohu v analýze, ale už presahujú triedu elementárnych funkcií.

Téma: „Funkcia: pojem, metódy priraďovania, hlavné charakteristiky. Inverzná funkcia. Superpozícia funkcií."

Epigraf lekcie:

„Naštuduj si niečo a nepremýšľaj o tom

naučené - absolútne zbytočné.

Myslieť na niečo bez toho, aby ste to študovali

predbežný predmet úvahy -

Konfucius.

Účel a psychologické a pedagogické ciele vyučovacej hodiny:

1) Všeobecný vzdelávací (normatívny) cieľ: Zopakujte si so študentmi definíciu a vlastnosti funkcie. Zaviesť pojem superpozícia funkcií.

2) Ciele matematického rozvoja žiakov: používanie neštandardného vzdelávacieho a matematického materiálu na pokračovanie rozvoja mentálnej skúsenosti žiakov, zmysluplnej kognitívnej štruktúry ich matematickej inteligencie, vrátane schopností logicko-deduktívneho a induktívneho, analytického a syntetického reverzibilného myslenia, algebraického a figuratívno-grafického myslenia , zmysluplného zovšeobecňovania a konkretizácie, k reflexii a samostatnosti ako metakognitívnej schopnosti žiakov; pokračovať v rozvoji kultúry písanej a ústnej reči ako psychologických mechanizmov vzdelávacej a matematickej inteligencie.

3) Výchovné úlohy: pokračovať v osobnom vzdelávaní u žiakov s kognitívnym záujmom o matematiku, zodpovednosť, zmysel pre povinnosť, akademickú samostatnosť, komunikatívnu schopnosť spolupracovať so skupinou, učiteľom, spolužiakmi; autogogická spôsobilosť pre súťažne vzdelávaciu a matematickú činnosť, snaha o vysoké a najvyššie výsledky (akmeický motív).

Typ lekcie: učenie sa nového materiálu; podľa kritéria vedúceho matematického obsahu - praktická lekcia; podľa kritéria typu informačnej interakcie medzi žiakmi a učiteľom - hodina spolupráce.

Vybavenie lekcie:

1. Náučná literatúra:

1) Kudryavtsev matematickej analýzy: Učebnica. pre študentov vysokých škôl a vysokých škôl. V 3 zväzkoch T. 3. – 2. vyd., prepracované. a dodatočné – M.: Vyššie. škola, 1989. – 352 s. : chorý.

2) Demidovičove úlohy a cvičenia v matematickej analýze. – 9. vyd. – M.: Vydavateľstvo „Nauka“, 1977.

2. Ilustrácie.

Počas vyučovania.

1. Oznámenie témy a hlavného výchovno-vzdelávacieho cieľa vyučovacej hodiny; stimulovanie zmyslu pre povinnosť, zodpovednosť a kognitívny záujem študentov o prípravu na stretnutie.

2.Opakovanie učiva na základe otázok.

a) Definujte funkciu.

Jedným zo základných matematických pojmov je pojem funkcie. Pojem funkcie je spojený s vytvorením vzťahu medzi prvkami dvoch množín.

Nech sú dané dve neprázdne sady a. Zavolá sa zhoda f, ktorá zodpovedá každému prvku len s jedným prvkom funkciu a napíše y = f(x). Tiež hovoria, že funkcia f zobrazuje veľa nad mnohými.

https://pandia.ru/text/79/018/images/image003_18.gif" width="63" height="27">.gif" width="59" height="26"> sa nazýva súbor významov funkciu f a označujeme E(f).

b) Číselné funkcie. Funkčný graf. Metódy špecifikovania funkcií.

Nech je funkcia daná.

Ak prvky množín a sú reálne čísla, potom sa volá funkcia f číselná funkcia . Volá sa premenná x argument alebo nezávislá premenná a y – funkciu alebo závislá premenná(od x). Pokiaľ ide o samotné množstvá x a y, hovorí sa, že sú v funkčná závislosť.

Funkčný graf y = f(x) je množina všetkých bodov roviny Oxy, pre každý z nich x je hodnota argumentu a y je zodpovedajúca hodnota funkcie.

Pre špecifikáciu funkcie y = f(x) je potrebné špecifikovať pravidlo, ktoré umožňuje pri znalosti x nájsť zodpovedajúcu hodnotu y.

Najbežnejšie tri spôsoby špecifikácie funkcie sú: analytický, tabuľkový a grafický.

Analytická metóda: Funkcia je špecifikovaná ako jeden alebo viacero vzorcov alebo rovníc.

Napríklad:

Ak nie je zadaná oblasť definície funkcie y = f(x), predpokladá sa, že sa zhoduje s množinou všetkých hodnôt argumentu, pre ktoré má zodpovedajúci vzorec zmysel.

Analytická metóda špecifikácie funkcie je najpokročilejšia, pretože zahŕňa metódy matematickej analýzy, ktoré umožňujú plne študovať funkciu y = f(x).

Grafická metóda: Nastaví graf funkcie.

Výhodou grafickej úlohy je jej prehľadnosť, nevýhodou nepresnosť.

Tabuľková metóda: Funkcia je špecifikovaná tabuľkou série hodnôt argumentov a zodpovedajúcich funkčných hodnôt. Napríklad známe tabuľky hodnôt goniometrických funkcií, logaritmické tabuľky.

c) Hlavné charakteristiky funkcie.

1. Zavolá sa funkcia y = f(x), definovaná na množine D dokonca , ak sú splnené podmienky a f(-x) = f(x); zvláštny , ak sú splnené podmienky a f(-x) = -f(x).

Graf párnej funkcie je symetrický okolo osi Oy a nepárna funkcia je symetrická podľa počiatku. Napríklad – párne funkcie; a y = sinx, https://pandia.ru/text/79/018/images/image014_3.gif" width="73" height="29"> – funkcie všeobecného tvaru, t. j. ani párne, ani nepárne .

2. Nech je funkcia y = f(x) definovaná na množine D a nech . Ak pre ľubovoľné hodnoty argumentov nasleduje nasledujúca nerovnosť: , potom sa zavolá funkcia zvyšujúci sa na scéne; Ak , potom sa zavolá funkcia neklesajúci na https://pandia.ru/text/79/018/images/image021_1.gif" width="117" height="28 src=">potom sa funkcia zavolá. klesajúci na ; - nezväčšujúce sa .

Funkcie zvýšenia, nezväčšovania, znižovania a neznižovania na množine https://pandia.ru/text/79/018/images/image023_0.gif" width="13" height="13">hodnota D (x +T)D a platí rovnosť f(x+T) = f(x).

Na vykreslenie grafu periodickej funkcie periódy T stačí nakresliť ho na ľubovoľný segment dĺžky T a pravidelne v ňom pokračovať v celej oblasti definície.

Všimnime si hlavné vlastnosti periodickej funkcie.

1) Algebraický súčet periodických funkcií s rovnakou periódou T je periodická funkcia s periódou T.

2) Ak má funkcia f(x) periódu T, tak funkcia f(ax) má periódu T/a.

d) Inverzná funkcia.

Nech je daná funkcia y = f(x) s doménou definície D a množinou hodnôt E..gif" width="48" height="22">, potom funkcia x = z(y) s doménou definície E a je definovaná množina hodnôt D Takáto funkcia sa volá z(y). obrátene na funkciu f(x) a zapisuje sa v tomto tvare: . Hovorí sa, že funkcie y = f(x) a x = z(y) sú vzájomne inverzné. Na nájdenie funkcie x = z(y), inverznej k funkcii y = f(x), stačí vyriešiť rovnicu f(x) = y pre x.

Príklady:

1. Pre funkciu y = 2x je inverzná funkcia funkcia x = ½ y;

2. Pre funkciu inverzná funkcia je funkcia .

Z definície inverznej funkcie vyplýva, že funkcia y = f(x) má inverznú funkciu práve vtedy, ak f(x) špecifikuje korešpondenciu jedna ku jednej medzi množinami D a E. Z toho vyplýva, že prísne monotónna funkcia má inverznú funkciu . Navyše, ak funkcia rastie (klesá), potom sa zvyšuje (klesá) aj inverzná funkcia.

3. Štúdium nového materiálu.

Komplexná funkcia.

Nech je funkcia y = f(u) definovaná na množine D a funkcia u = z(x) na množine a pre príslušnú hodnotu . Potom je na množine definovaná funkcia u = f(z(x)), ktorá sa volá komplexná funkcia od x (alebo superpozícia špecifikované funkcie, príp funkcia z funkcie ).

Volá sa premenná u = z(x). stredný argument komplexná funkcia.

Napríklad funkcia y = sin2x je superpozíciou dvoch funkcií y = sinu a u = 2x. Komplexná funkcia môže mať niekoľko medziľahlých argumentov.

4. Riešenie niekoľkých príkladov pri tabuli.

5. Záver vyučovacej hodiny.

1) teoretické a aplikované výsledky praktickej hodiny; diferencované hodnotenie úrovne duševných skúseností žiakov; úroveň ich zvládnutia témy, kompetencie, kvalita ústneho a písomného matematického prejavu; preukázaná úroveň kreativity; úroveň nezávislosti a reflexie; miera iniciatívy, kognitívneho záujmu o jednotlivé metódy matematického myslenia; úroveň spolupráce, intelektuálna súťaživosť, túžba po vysokej úrovni vzdelávacej a matematickej aktivity atď.;

2) oznámenie odôvodnených známok, bodov lekcie.

Nech je nejaká sada K pozostávajúce z konečného počtu booleovských funkcií. Superpozíciou funkcií z tejto množiny sú nové funkcie získané aplikáciou konečného počtu dvoch operácií;

môžete premenovať akúkoľvek premennú zahrnutú vo funkcii z K;

namiesto akejkoľvek premennej môžete vložiť funkciu z množiny K alebo predtým vytvorená superpozícia.

Superpozícia sa nazýva aj komplexná funkcia.

Príklad 7. 1. Ak je daná jedna funkcia X|r(Schaefferov zdvih), potom budú jeho superpozíciami najmä nasledujúce funkcie x|x,x|(x|y),x|(y|z) atď.

Uzavretím súbor funkcií z K sa nazýva množina všetkých superpozícií. Funkčná trieda K volal ZATVORENÉ, ak sa jeho uzavretie zhoduje so sebou samým.

Súbor funkcií sa nazýva kompletný, ak sa jeho uzavretie zhoduje so všetkými logickými funkciami. Inými slovami, úplná množina je množina takých funkcií, prostredníctvom ktorých možno vyjadriť všetky ostatné booleovské funkcie.

Neredundantný kompletný súbor funkcií sa nazýva základ(„neredundantné“ znamená, že ak sa zo sady odstráni nejaká funkcia, táto sada už nebude kompletná).

Príklad 7.2. Konjunkcia, disjunkcia a negácia sú kompletnou množinou (presvedčili sme sa o tom v časti 5), ale nie sú základom, pretože táto množina je nadbytočná, keďže pomocou De Morganových pravidiel je možné konjunkciu alebo disjunkciu odstrániť. Akákoľvek funkcia môže byť reprezentovaná ako Zhegalkinov polynóm (časť 6). Je jasné, že funkcie konjunkcia, sčítanie modulo 2 a konštanty 0 a 1 sú kompletnou množinou, ale tieto štyri funkcie tiež nie sú základom, keďže 1+1=0, a preto konštantu 0 možno vylúčiť z kompletného množina (na zostavenie polynómov je potrebná Zhegalkinova konštanta 0, pretože výraz „1+1“ nie je Zhegalkinovým polynómom).

Je ľahké vidieť, že je to jeden zo spôsobov, ako skontrolovať úplnosť niektorého súboru TO je skontrolovať, či funkcie inej kompletnej sady sú vyjadrené prostredníctvom funkcií z tejto sady (môžete to skontrolovať pomocou funkcií z TO možno vyjadriť konjunkciu a negáciu alebo disjunkciu a negáciu.

Sú funkcie také, že jedna takáto funkcia je sama o sebe základom (tu stačí skontrolovať len úplnosť, neredundancia je zrejmá). Takéto funkcie sa nazývajú Schefferove funkcie. Tento názov je spôsobený skutočnosťou, že Schaefferov zdvih je základom. Pripomeňme, že Schaefferovo prvočíslo je definované nasledujúcou pravdivostnou tabuľkou:

Keďže je zrejmé, že negácia je superpozícia Schaefferovho ťahu a disjunkcia potom , Schaefferov zdvih je sám o sebe základ. Rovnako aj šípka Peirce je Schefferova funkcia (študenti si to môžu sami overiť). Pre funkcie 3 a viacerých premenných existuje veľa Shefferových funkcií (samozrejme, vyjadrenie iných booleovských funkcií pomocou Shefferovej funkcie veľkého počtu premenných je zložité, preto sa v technológii používajú len zriedka).

Všimnite si, že výpočtové zariadenie je najčastejšie založené na kompletnom súbore funkcií (často na základoch). Ak je zariadenie založené na konjunkcii, disjunkcii a negácii, potom je pre tieto zariadenia dôležitý problém minimalizácie DNF; Ak je zariadenie založené na iných funkciách, potom je užitočné mať možnosť algoritmicky minimalizovať výrazy prostredníctvom týchto funkcií.

Prejdime teraz k objasneniu úplnosti konkrétnych súborov funkcií. Na tento účel uvádzame 5 najdôležitejších tried funkcií:

• T 0 je množina všetkých tých logických funkcií, ktoré majú hodnotu 0 na nulovej množine ( T 0 je funkčná trieda, konzervovanie 0);
• T 1 je množina všetkých logických funkcií, ktoré majú hodnotu 1 na množine jednotiek ( T 1 je funkčná trieda, konzervačná jednotka) (všimnite si, že počet funkcií z P premenné patriace do tried To a Ti sa rovnajú 2 2n-1);
• L- Trieda lineárne funkcie, teda funkcie, pre ktoré Zhegalkinov polynóm obsahuje len prvé stupne premenných;
• M- Trieda monotónna funkcie. Opíšme triedu týchto funkcií podrobnejšie. Nech sú 2 sady P premenné: s1 = (x 1, x 2,..., x n)

s 1 = ( X 1 , X 2 , … , x n) a s 2 = (r 1 , r 2, … , y p). Povieme, že množina s 1 je menšia ako množina s 2 (s 1 £ s 2 ), ak sú všetky x i £ y i .Je zrejmé, že nie všetky súbory zPpremenné sú navzájom porovnateľné (napríklad keďn = 2 množiny (0,1) a (1,0) nie sú navzájom porovnateľné). Funkcia odPpremenné sa nazývajúmonotónna, ak na menšom súbore má menšiu alebo rovnakú hodnotu. Samozrejme, tieto nerovnosti by sa mali testovať len na porovnateľných zostavách. Je jasné, že neporovnateľné množiny sú tie, v ktorých sú na zodpovedajúcich miestach nejaké súradnice typu (0,1) v jednej množine a (1,0) v inej (v diskrétnej matematike sú monotónne funkcie len „monotónne rastúce funkcie“ , funkcie „monotónne klesajúce“ sa tu neberú do úvahy).

Príklad. V nasledujúcej tabuľke funkcie f 1 ,f 2 sú monotónne funkcie a funkcie f 3 ,f 4 - Nie.

Prirodzené poradie premenných je zabezpečené tým, že ak je niektorá množina menšia ako iná množina, potom sa nevyhnutne nachádza v pravdivostnej tabuľke vyššie„väčšia“ sada. Preto ak v tabuľke pravdy()navrchu sú nuly,a potom jedničky,potom je táto funkcia určite monotónna.Sú však možné inverzie, t.j. jednička sa nachádza pred nejakými nulami, ale funkcia je stále monotónna(v tomto prípade by množiny zodpovedajúce „hornej“ jednotke a „dolnej“ nule mali byť neporovnateľné; je možné skontrolovať, či funkcia daná pravdivostnou tabuľkou s prirodzeným poradím množiny premenných(00010101), je monotónna);

Veta .Triedy funkcií T 0 ,T 1 ,L,M,S zatvorené.

Toto tvrdenie vyplýva priamo z definície týchto tried samotných, ako aj z definície uzavretosti.

V teórii booleovských funkcií je veľmi dôležitá nasledujúca Postova veta.

Postova veta .Aby bola nejaká množina funkcií K úplná, je potrebné a postačujúce, aby obsahovala funkcie, ktoré nepatria do každej z tried T 0 ,T 1 ,L,M,S.

Poznač si to Čo nevyhnutnosť toto Vyhlásenia zrejmé Takže Ako Ak to je všetko funkcie od nábor TO zahrnuté V jeden od uvedené triedy, To A Všetky superpozície, A znamená, A skrat nábor zahrnuté by V toto Trieda A Trieda TO nie mohol byť plný.

Primeranosť toto Vyhlásenia je dokázané dosť ťažké, Preto tu nie je zobrazené.

Z tejto vety vyplýva pomerne jednoduchý spôsob, ako určiť úplnosť určitej množiny funkcií. Pre každú z týchto funkcií je určené členstvo v triedach uvedených vyššie. Výsledky sa zapisujú do tzv Tabuľka príspevkov(v našom príklade je táto tabuľka zostavená pre 4 funkcie a znamienko „+“ označuje, že funkcia patrí do zodpovedajúcej triedy, znamienko „-“ znamená, že funkcia v nej nie je zahrnutá).

Podľa Postovej vety bude množina funkcií úplná vtedy a len vtedy, ak je v každom stĺpci tabuľky Post aspoň jedno mínus. Z vyššie uvedenej tabuľky teda vyplýva, že tieto 4 funkcie tvoria ucelený súbor, avšak tieto funkcie nie sú základom. Z týchto funkcií môžete vytvoriť 2 základy: f 3 ,f 1 A f 3 ,f 2. Kompletné množiny sú akékoľvek množiny obsahujúce nejaký základ.

Priamo z Postovej tabuľky vyplýva, že počet bázových funkcií nemôže byť väčší ako 5. Nie je ťažké dokázať, že v skutočnosti je tento počet menší alebo rovný 4.

Funkcia f získaná z funkcií f 1 , f 2 ,…f n pomocou operácií substitúcie a premenovania argumentov sa nazýva superpozícia funkcie.

Akýkoľvek vzorec, ktorý vyjadruje funkciu f ako superpozíciu iných funkcií, určuje spôsob jej výpočtu, t. j. vzorec možno vypočítať, ak sú vypočítané hodnoty všetkých jeho podvzorcov. Hodnotu podvzorca možno vypočítať zo známeho súboru hodnôt binárnych premenných.

Pomocou každého vzorca môžete obnoviť tabuľku logickej funkcie, ale nie naopak, pretože Každá logická funkcia môže byť reprezentovaná niekoľkými vzorcami v rôznych základoch

Volajú sa vzorce F i a F j reprezentujúce rovnakú logickú funkciu f i ekvivalent . Takže ekvivalentné vzorce sú:

1. f 2 (x 1 ; x 2) = (x 1 x`x 2)=ù(`x 1 Úx 2)= ù(x 1 ®x 2);

2. f 6 (x 1 ; x 2)=(`x 1 ×x 2 Úx 1 ×`x 2)= ù(x 1 “x 2)=(x 1 Åx 2);

3. f 8 (x 1 ; x 2)=(`x 1 x`x 2)= ù(x 1 Úx 2)=(x 1 ¯x 2);

4. f 14 (x 1 ;x 2)=(`x 1 Ú`x 2)= ù(x 1 xx 2)=x 1 ½x 2;

5. f 9 (x 1 ;x 2)=((`x 1 ×`x 2)Ú(x 1 ×x 2))=(x 1 “x 2) ;

6. f 13 (x 1 ;x 2)= (`x 1 Úx 2)=(x 1 ®x 2).

Ak ktorýkoľvek vzorec F obsahuje podformulu F i, potom nahradenie F i ekvivalentom Fj nezmení hodnotu vzorca F pre žiadnu množinu booleovských vektorov, ale zmení formu jeho popisu. Novo získaný vzorec F' je ekvivalentný vzorcu F.

Na zjednodušenie zložitých algebraických výrazov sa vykonávajú booleovské funkcie ekvivalentné transformácie pomocou zákonov Booleovej algebry a pravidlá nahrádzania A substitúcia ,

Pri písaní vzorcov booleovskej algebry nezabudnite:

· počet ľavých zátvoriek sa rovná počtu pravých zátvoriek,

· neexistujú dve susediace logické spojky, t.j. medzi nimi musí byť vzorec,

· neexistujú dva susediace vzorce, t.j. musí medzi nimi existovať logická súvislosť,

· logické spojenie „ד je silnejšie ako logické spojenie „Ú“,

· ak „ù“ odkazuje na vzorec (F 1 ×F 2) alebo (F 1 Ú F 2), potom by sa v prvom rade mali vykonať tieto transformácie podľa De Morganovho zákona: ù(F 1 ×F 2) = ` F 1 Ú` F 2 alebo ù(F 1 ÚF 2)=`F 1 ×`F 2 ;

· operácia " × “ je silnejšie ako „Ú“, čo umožňuje vynechať zátvorky.

Príklad: vykonať ekvivalentné transformácie vzorca F=x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 .

· podľa zákona komutativnosti:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×`x 2 Úx 3 ×x 4 ;

· podľa zákona distribúcie:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×(`x 2 Úx 4);

· podľa zákona distribúcie:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×(`x 1 Ú`x 2 Úx 4);

· podľa zákona distribúcie:

F=x 3 ×((x 1 ×x 2 ×`x 4)Ú(`x 1 Ú`x 2 Úx 4));

· podľa De Morganovho zákona:

F=x 3 ×((x 1 ×x 2 ×`x 4)Úù(x 1 ×x 2 ×`x 4));

· podľa zákona o rozpore:

Teda x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 =x 3 .

Príklad: vykonávať transformácie vzorcov

F=(x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2 );

· podľa De Morganovho zákona

F=(x 1 ×`x 2 Ú`x 1 ×x 2)×(`x 1 Ú`x 2)Ú(x 1 ×x 2)×(`x 1 Úx 2)×(x 1 Ú`x 2);

· podľa zákona distribúcie:

F=x 1 ×`x 2 Ú`x 1 ×x 2 Úx 1 ×x 2 ;

· podľa zákonov komutatívnosti a distributivity:

F= `x 1 ×x 2 Úx 1 ×(`x 2 Úx 2);

· podľa zákona o rozpore:

F= `x 1 × x 2 Úx 1 ;

· podľa Poretského zákona

Teda (x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2 ) = (x 2 Úx 1).

Príklad: transformovať vzorec F=ù(`x 1 Úx 2)Ú((`x 1 Úx 3)×x 2).

· podľa De Morganovho zákona:

F= ù(`x 1 Úx 2)×ù((`x 1 Úx 3)×x 2);

· podľa De Morganovho zákona:

F=x 1 ×`x 2 ×(ù(`x 1 Úx 3)Ú`x 2);

· podľa De Morganovho zákona:

F=x 1 x`x 2 x(x 1 x`x 3 Ú`x 2);

· podľa zákona distribúcie:

F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ;

· podľa zákona absorpcie:

Teda ù(`x 1 Úx 2)×((`x 1 Úx 3)×x 2)= x 1 ×`x 2 .

Príklad: Preveďte vzorec:

F=ù(x 1 ®x 2)×(`x 3 Ú`x 4)Ú(x 1 ¯x 2)×ù(x 3 ×x 4).

1) transformovať vzorec na základ Booleovej algebry:

F=ù(`x 1 Úx 2)×(`x 3 Ú`x 4)Úù(x 1 Úx 2)× ù(x 3 ×x 4);

2) vynechajte znak „`“ pred binárnymi premennými:

F=(x 1 ×`x 2)×(`x 3 Ú`x 4)Ú(`x 1 ×`x 2)×(`x 3 Ú`x 4);

3) transformovať vzorec podľa distributívneho zákona:

F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ×`x 4 Ú`x 1 ×`x 2 ×`x 3 Ú`x 1 ×`x 2 ×`x 4 ;

4) vložte `x 2 zo zátvoriek podľa distributívneho zákona:

F=`x 2 ×(x 1 ×`x 3 Úx 1 ×`x 4 Ú`x 1 ×`x 3 Ú`x 1 ×`x 4);

5) transformovať podľa zákona distributivity:

F=`x 2 ×(`x 3 ×(x 1 Ú`x 1)Ú`x 4 ×(x 1 Ú`x 1));

6) použite zákon rozporu:

F=`x 2 × (`x 3 Ú`x 4)

Vlastnosti boolovských funkcií

Často vyvstáva otázka: je každá booleovská funkcia reprezentovateľná superpozíciou vzorcov f 0, f 1,..f 15? Aby bolo možné určiť možnosť vytvorenia ľubovoľnej booleovskej funkcie pomocou superpozície týchto vzorcov, je potrebné určiť ich vlastnosti a podmienky na použitie funkčne úplného systému.

Samoduálne booleovské funkcie

self-duálny , ak f(x 1 ;x 2 ;...x n)=`f(`x 1 ;`x 2 ;…`x n).

Napríklad funkcie f 3 (x 1 ; x 2) = x 1 , f 5 ( x 1 ; x 2) = x 2 , f 10 (x 1 ; x 2) = `x 2 a f 12 (x 1 ;x 2)=`x 1 sú samoduálne, pretože keď sa zmení hodnota argumentu, zmenia svoju hodnotu.

Každá funkcia získaná operáciami superpozície zo samoduálnych booleovských funkcií je sama osebe samoduálna. Preto množina samoduálnych booleovských funkcií neumožňuje vytváranie nesamoduálnych funkcií.

Monotónne booleovské funkcie

Zavolá sa funkcia f(x 1 ; x 2 ;...x n). monotónna , ak pre každé s 1i £s 2i boolovské vektory (s 11 ; s 12 ;……;s 1n) a (s 21 ;s 22 ;……;s 2n) je splnená nasledujúca podmienka: f(s 11 ;s 12 ;… ;s 1i ;…;s 1n)£f(s 21 ;s 22 ;…;s 2i ;…;s 2n).

Napríklad pre funkcie f(x 1 ; x 2) sú monotónne funkcie:

ak (0; 0) £ (0; 1), potom f(0; 0) £ f (0; 1),

if (0; 0)£(1; 0), potom f(0; 0)£f(1; 0),

if (0; 1) £ (1; 1), potom f(0; 1) £ f (1; 1),

ak (1; 0) £ (1; 1), potom f(1; 0) £ f(1; 1).

Nasledujúce funkcie spĺňajú tieto podmienky:

f° (x 1; x 2) = 0; f1(x1; x2)=(x1xx2); f3(x1; x2)=x1; f5(x1; x2)=x2; f 7 (x 1 ;x 2) = (x 1 Úx 2); f15 (x 1; x 2) = 1.

Akákoľvek funkcia získaná pomocou operácie superpozície z monotónnych booleovských funkcií je sama osebe monotónna. Súbor monotónnych funkcií preto neumožňuje vytváranie nemonotónnych funkcií.

Lineárne booleovské funkcie

Zhegalkinova algebra, založená na základe F 4 =(×; Å; 1), umožňuje reprezentovať akúkoľvek logickú funkciu polynómom, ktorého každý člen je konjunkciou I booleovských premenných booleovského vektora v rámci 0£i£ n:

P(x 1 ; x 2 ;…x n)=b 0 ×1 Å b i ×x i Å 1 £ j ¹ k £ n b j ×x j ×x k Å……Å b 2n-1 ×x 1 ×x 2 ×... ×x n.

Napríklad pre logické funkcie f 8 (x 1 ; x 2)

Zhegalkinov polynóm má tvar: P(x 1; x 2) = 1Å x 1 Å x 2 Å x 1 xx 2.

Výhodou Zhegalkinovej algebry je „aritmetizácia“ logických vzorcov, zatiaľ čo nevýhodou je zložitosť, najmä pri veľkom počte binárnych premenných.

Zhegalkinove polynómy, ktoré neobsahujú konjunkcie binárnych premenných, t.j. P(x 1 ; x 2 ;…;x n)=b 0 ×1Åb 1 ×x 1 Å…Åb n ×x n sa nazýva lineárne .

Napríklad f 9 (x 1 ; x 2) = 1Åx 1 Åx 2 alebo f 12 (x 1 ; x 2) = 1 Åx 1 .

Hlavné vlastnosti operácie sčítania modulo 2 sú uvedené v tabuľke 1.18.

Ak je logická funkcia špecifikovaná tabuľkou alebo vzorcom v akomkoľvek základe, t.j. Ak poznáte hodnoty booleovskej funkcie pre rôzne sady booleovských premenných, môžete vypočítať všetky

koeficienty b i Zhegalkinovho polynómu, zostavujúce sústavu rovníc pre všetky známe množiny binárnych premenných.

Príklad: daná boolovská funkcia f(x 1 ;x 2)=x 1 Úx 2. Hodnoty tejto funkcie sú známe pre všetky sady booleovských premenných.

F(0;0)=0=b 0 x 1 Á b 1 x 0 Á b 2 x 0 Á b 3 x 0 x 0;

f(1;0)=1=b 0 x 1 Á b 1 x 1 Á b 2 x 0 Á b 3 x 1 x 0;

f(1;1)=1=b 0 x 1 Á b 1 x 1 Á b 2 x 1 Á b 3 x 1 x 1;

Kde nájdeme b 0 = 0; b1 = 1; b2 = 1; b3 = 1.

V dôsledku toho (x 1 Úx 2) = x 1 Åx 2 Åx 1 ×x 2, t. j. disjunkcia je nelineárna booleovská funkcia.

Príklad: daná boolovská funkcia f(x 1 ;x 2)=(x 1 ®x 2). Hodnoty tejto funkcie sú známe aj pre všetky sady binárnych premenných.

F(0;0)=l=b 0 x 1 Á b 1 x 0 Á b 2 x 0 Á b 3 x 0 x 0;

f(0;1)=1=b 0 x 1 Á b 1 x 0 Á b 2 x 1 Á b 3 x 0 x 1;

f(1;0)=0=b 0 x 1 Áb 1 x 1 Áb 2 x 0 Áb 3 x 1 x 0;

f(1;1)=1=b 0 x 1 Áb 1 x 1 Áb 2 x 1 Áb 3 x 1 x 1;

Kde nájdeme b 0 =1; b1 = 1; b2 = 0; b3 = 1.

Preto (x 1 ® x 2) = 1 Á x 2 Å x 1 x x 2.

Tabuľka 1.19 ukazuje Zhegalkinove polynómy pre hlavných predstaviteľov booleovských funkcií z tabuľky 1.15.

Ak je daný analytický výraz pre logickú funkciu a jeho hodnoty sú neznáme pre rôzne množiny binárnych premenných, potom je možné zostaviť Zhegalkinov polynóm na základe konjunktívnej bázy Booleovej algebry F 2 =(` ; ×) :

Nech f(x 1 ; x 2) = (x 1 Úx 2).

Potom (x 1 Úx 2)=ù(`x 1 ×`x 2)=((x 1 Å 1)×(x 2 Å 1))Å 1=x 1 ×x 2 Å x 1 × 1Å x 2 × 1Å 1×1Å1=

(x 1 Åx 2 Åx 1 xx 2).

Nech f(x 1 ; x 2) = (x 1 ® x 2).

Potom (x 1 ®x 2)=(`x 1 Úx 2)=ù(x 1 ×`x 2)=x 1 ×(x 2 Å 1)Å 1=x 1 ×x 2 Å x 1 × 1Å 1 = = (1Åx 1 Åx 1 ×x 2).

Nech f(x 1 ;x 2)=(x 1 “x 2).

Potom (x 1 “x 2)=(`x 1 ×`x 2 Úx 1 ×x 2)=ù(ù(`x 1 ×`x 2)×ù(x 1 ×x 2))=((( x 1 Å1)×(x 2 Å1))Å1)× ×(x 1 ×x 2 Å)Å1=(x 1 ×x 2 Åx 1 Åx 2 Å1Å1)×(x 1 ×x 2 Å1)Å1=x 1 ×x 2 Åx 1 ×x 2 Åx 1 ×x 2 Åx 1 Å

x 1 ×x 2 Åx 2 Å1=(1Åx 1 Åx 2).

Každá funkcia získaná pomocou operácie superpozície z lineárnych logických funkcií je sama o sebe lineárna. Preto množina lineárnych funkcií neumožňuje tvorbu nelineárnych funkcií.

1.5.6.4. Funkcie, ktoré ukladajú „0“

Funkcia f(x 1 ; x 2 ;...x n) sa nazýva zachovávajúca „0“, ak pre množiny hodnôt binárnych premenných (0; 0;...0) funkcia nadobúda hodnotu f(0; 0;…0)=0.

Napríklad f 0 (0; 0) = 0, f 3 (0; 0) = 0, f 7 (0; 0) = 0 atď.

Akákoľvek funkcia získaná pomocou operácie superpozície z funkcií, ktoré zachovávajú „0“, je sama osebe funkciou, ktorá zachováva „0“. Preto množina funkcií, ktoré zachovávajú „0“, neumožňuje vytváranie funkcií, ktoré nezachovávajú „0“.

1.5.6.5. Funkcie, ktoré ukladajú „1“

Funkcia f(x 1 ; x 2 ;…x n) sa nazýva zachovávajúca „1“, ak pre množiny hodnôt binárnych premenných (1; 1;…1) funkcia nadobúda hodnotu f(1;1;…1 )=1.

Napríklad f 1 (1; 1) = 1, f3 (1; 1) = 1, f 5 (1; 1) = 1 atď.

Akákoľvek funkcia získaná pomocou operácie superpozície z funkcií, ktoré zachovávajú „1“, si sama zachováva „1“. Preto množina funkcií, ktoré zachovávajú „1“, neumožňuje vytváranie funkcií, ktoré nezachovávajú „1“.