Niech będzie jakiś zestaw K, składający się ze skończonej liczby funkcji boolowskich. Superpozycją funkcji z tego zbioru są nowe funkcje otrzymane poprzez zastosowanie skończonej liczby dwóch operacji;

możesz zmienić nazwę dowolnej zmiennej zawartej w funkcji z K;

zamiast dowolnej zmiennej możesz umieścić funkcję ze zbioru K lub wcześniej utworzona superpozycja.

Superpozycję nazywa się także funkcją złożoną.

Przykład 7. 1. Jeśli podano jedną funkcję X|y(skok Schaeffera), to w szczególności jego superpozycje będą następującymi funkcjami x|x,x|(x|y),x|(y|z) itp.

Zamykając zestaw funkcji z K nazywa się zbiorem wszystkich superpozycji. Klasa funkcji K zwany Zamknięte, jeśli jego zamknięcie pokrywa się z samym sobą.

Zbiór funkcji nazywa się kompletny, jeśli jego zamknięcie pokrywa się ze wszystkimi funkcjami logicznymi. Innymi słowy, zbiór kompletny to zbiór takich funkcji, za pomocą których można wyrazić wszystkie inne funkcje logiczne.

Nieredundantny kompletny zestaw funkcji nazywany jest bazą(„nieredundantny” oznacza, że ​​jeśli usuniemy jakąś funkcję ze zbioru, to zestaw ten nie będzie już kompletny).

Przykład 7.2. Koniunkcja, alternatywna i negacja stanowią zbiór kompletny (przekonaliśmy się o tym w rozdziale 5), ale nie stanowią podstawy, ponieważ zbiór ten jest zbędny, gdyż korzystając z reguł De Morgana można usunąć koniunkcję lub alternatywę. Każdą funkcję można przedstawić jako wielomian Zhegalkina (rozdział 6). Jest oczywiste, że koniunkcja funkcji, dodawanie modulo 2 oraz stałe 0 i 1 są pełnym zbiorem, ale te cztery funkcje również nie są podstawą, ponieważ 1+1=0, a zatem stałą 0 można wykluczyć z zupełnego zbiór (do konstruowania wielomianów konieczna jest stała Zhegalkina 0, ponieważ wyrażenie „1+1” nie jest wielomianem Zhegalkina).

Łatwo zauważyć, że jest to jeden ze sposobów sprawdzenia kompletności jakiegoś zbioru DO polega na sprawdzeniu, czy funkcje z tego zbioru mogą być użyte do wyrażenia funkcji innego kompletnego zbioru (możesz sprawdzić, czy funkcje z DO można wyrazić koniunkcję i negację lub alternatywę i negację.

Istnieją takie funkcje, że jedna taka funkcja sama jest bazą (tutaj wystarczy sprawdzić tylko kompletność; nieredundancja jest oczywista). Funkcje takie nazywane są funkcjami Scheffera. Nazwa ta wynika z faktu, że podstawą jest udar Schaeffera. Przypomnijmy, że liczbę pierwszą Schaeffera definiuje poniższa tabela prawdy:

Ponieważ jest to oczywiste, tj. Negacja jest superpozycją skoku Schaeffera, a zatem alternatywna , skok Schaeffera sam w sobie jest podstawą. Podobnie strzałka Peirce'a jest funkcją Scheffera (uczniowie mogą to sprawdzić samodzielnie). Dla funkcji 3 i więcej zmiennych istnieje wiele funkcji Sheffera (oczywiście wyrażenie innych funkcji boolowskich za pomocą funkcji Sheffera dużej liczby zmiennych jest trudne, dlatego są one rzadko stosowane w technologii).

Należy pamiętać, że urządzenie komputerowe najczęściej opiera się na pełnym zestawie funkcji (często na podstawach). Jeżeli urządzenie opiera się na koniunkcji, alternatywie i negacji, to dla tych urządzeń istotny jest problem minimalizacji DNF; Jeśli urządzenie opiera się na innych funkcjach, wówczas przydatna jest możliwość algorytmicznej minimalizacji wyrażeń poprzez te funkcje.

Przejdźmy teraz do wyjaśnienia kompletności poszczególnych zbiorów funkcji. Aby to zrobić, podajemy 5 najważniejszych klas funkcji:

• T 0 to zbiór wszystkich funkcji logicznych, które przyjmują wartość 0 w zbiorze zerowym ( T 0 to klasa funkcji, konserwowanie 0);
• T 1 to zbiór wszystkich funkcji logicznych, które przyjmują wartość 1 w zestawie jednostek ( T 1 to klasa funkcji, jednostka konserwująca) (zwróć uwagę, że liczba funkcji z P zmienne należące do klas T 0 i T 1 są równe 2 2n-1);
• L- Klasa liniowy funkcje, tj. funkcje, dla których wielomian Zhegalkina zawiera tylko pierwsze stopnie zmiennych;
• M- Klasa monotonny Funkcje. Opiszemy bardziej szczegółowo klasę tych funkcji. Niech będą 2 zestawy P zmienne: s1 = (x 1, x 2,..., x n)

s 1 = ( X 1 , X 2 , … , x rz) i s 2 = (y 1 , y 2, … , tak p). Powiemy, że zbiór s 1 jest mniejsze niż zbiór s 2 (s 1 £ s 2 ), jeśli wszystkie x i £ y i .Oczywiście nie wszystkie zestawy zPzmienne są ze sobą porównywalne (na przykład kiedyn = 2 zbiory (0,1) i (1,0) nie są ze sobą porównywalne). Funkcja odPnazywane są zmiennemonotonny, jeśli na mniejszym zestawie przyjmuje mniejszą lub równą wartość. Oczywiście nierówności te należy testować jedynie na zbiorach porównywalnych. Oczywiste jest, że zbiory nieporównywalne to takie, w których w odpowiednich miejscach znajdują się współrzędne typu (0,1) w jednym zbiorze i (1,0) w innym (w matematyce dyskretnej funkcje monotoniczne są po prostu „funkcjami rosnącymi monotonicznie” , funkcje „monotonicznie malejące” nie są tu brane pod uwagę).

Przykład. W poniższej tabeli funkcje F 1 ,F 2 to funkcje monotoniczne i funkcje F 3 ,F 4 - NIE.

Naturalny porządek zmiennych zapewnia fakt, że jeśli jakiś zbiór jest mniejszy od innego, to koniecznie znajduje się on w tabeli prawdy wyższy„większy” zestaw. Dlatego jeśli w tabeli prawdy()na górze są zera,a potem jednostki,to funkcja ta jest zdecydowanie monotoniczna.Możliwe są jednak inwersje, tj. przed niektórymi zerami pojawia się jedynka, ale funkcja jest nadal monotoniczna(w tym przypadku powinny być zbiory odpowiadające „górnemu” i „dolnemu” zerowi niezrównany; można sprawdzić, że funkcja podana przez tabelę prawdy z naturalnym porządkiem zbioru zmiennych(00010101), jest monotoniczny);

Twierdzenie .Klasy funkcji T 0 ,T 1 ,L,M,S. zamknięte.

Stwierdzenie to wynika bezpośrednio z definicji samych tych klas, a także z definicji domkliwości.

W teorii funkcji Boole’a bardzo ważne jest następujące twierdzenie Posta.

Twierdzenie Posta .Aby jakiś zbiór funkcji K był kompletny, konieczne i wystarczające jest, aby zawierał on funkcje, które nie należą do żadnej z klas T 0 ,T 1 ,L,M,S.

Zauważ to Co konieczność Ten sprawozdania oczywiste Więc Jak Jeśli to wszystko Funkcje z rekrutacja DO dołączony V jeden z katalogowany zajęcia, To I Wszystko superpozycje, A Oznacza, I zwarcie rekrutacja dołączony zrobiłbym V Ten Klasa I Klasa DO Nie mógł Być pełny.

Adekwatność Ten sprawozdania jest udowodnione wystarczająco trudny, Dlatego nie pokazano tutaj.

Z twierdzenia tego wynika dość prosty sposób określenia kompletności pewnego zbioru funkcji. Dla każdej z tych funkcji określa się przynależność do klas wymienionych powyżej. Wyniki wpisuje się do tzw Tabela postów(w naszym przykładzie tabela ta jest skompilowana dla 4 funkcji, a znak „+” wskazuje, że funkcja należy do odpowiedniej klasy, znak „-” oznacza, że ​​funkcja nie jest w niej uwzględniona).

Zgodnie z twierdzeniem Posta zbiór funkcji będzie kompletny wtedy i tylko wtedy, gdy w każdej kolumnie tablicy Post będzie co najmniej jeden minus. Zatem z powyższej tabeli wynika, że ​​te 4 funkcje tworzą kompletny zestaw, ale funkcje te nie stanowią podstawy. Z tych funkcji możesz utworzyć 2 bazy: F 3 ,F 1 I F 3 ,F 2. Kompletne zestawy to dowolne zestawy zawierające pewną bazę.

Bezpośrednio z tabeli Posta wynika, że ​​liczba funkcji bazowych nie może być większa niż 5. Nietrudno wykazać, że faktycznie liczba ta jest mniejsza lub równa 4.

Niech będą 2 funkcje:

: A → B i g: D → F

Niech dziedzina definicji D funkcji g będzie zawarta w dziedzinie wartości funkcji f (DB). Następnie możesz zdefiniować nową funkcję - superpozycja (skład, funkcja złożona) funkcje f i g: z= G( (X)).

Przykłady. f(x)=x 2 , g(x)=e x . f:R → R, g: R → R .

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

Definicja

Niech będą dwie funkcje. Wtedy ich skład jest funkcją określoną przez równość:

Właściwości kompozycji

Kompozycja jest asocjacyjna:

Jeśli F= identyfikator X- identyczne mapowanie do X, to jest

.

Jeśli G= identyfikator Y- identyczne mapowanie do Y, to jest

.

Dodatkowe właściwości

Zbiory przeliczalne i niepoliczalne.

Dwa skończone zbiory składają się z równej liczby elementów, jeśli między tymi zbiorami można ustalić zgodność jeden do jednego. Liczba elementów skończonego zbioru jest licznością zbioru.

W przypadku zbioru nieskończonego można ustalić zgodność jeden do jednego między całym zbiorem a jego częścią.

Najprostszym ze zbiorów nieskończonych jest zbiór N.

Definicja. Zbiory A i B nazywane są równowartość(AB), jeśli można nawiązać między nimi korespondencję jeden do jednego.

Jeśli dwa skończone zbiory są równoważne, to składają się z tej samej liczby elementów.

Jeśli zbiory A i B, które są sobie równoważne, są dowolne, to mówimy, że A i B mają to samo moc. (moc = równoważność).

W przypadku zbiorów skończonych pojęcie liczności pokrywa się z pojęciem liczby elementów zbioru.

Definicja. Zestaw tzw policzalny, jeśli możliwe jest ustalenie zgodności jeden do jednego między nim a zbiorem liczb naturalnych. (Oznacza to, że zbiór przeliczalny jest nieskończony, co odpowiada zbiorowi N).

(Oznacza to, że wszystkie elementy zbioru przeliczalnego można ponumerować).

Własności relacji równoważności.

1) AA - zwrotność.

2) AB, następnie BA – symetria.

3) AB i BC, wówczas AC jest przechodniością.

Przykłady.

1) n → 2n, 2,4,6,… - nawet naturalne

2) n→2n-1, 1,3,5,… - nieparzyste naturalne.

Własności zbiorów przeliczalnych.

1. Nieskończone podzbiory zbioru przeliczalnego są przeliczalne.

Dowód. Ponieważ A jest przeliczalne, to A: x 1, x 2,... - odwzorowane A na N.

ВА, В: →1, →2,… - każdemu elementowi B przypisano liczbę naturalną, tj. odwzorowane B na N. Zatem B jest policzalne. Itp.

2. Suma skończonego (przeliczalnego) systemu zbiorów przeliczalnych jest policzalna.

Przykłady.

1. Zbiór liczb całkowitych Z jest przeliczalny, ponieważ zbiór Z można przedstawić jako sumę zbiorów przeliczalnych A i B, gdzie A: 0,1,2,.. i B: -1,-2,-3,...

2. Dużo zamówione pary ((m,n): m,nZ) (tj. (1,3)≠(3,1)).

3 (!) . Zbiór liczb wymiernych jest przeliczalny.

P=. Można ustalić zgodność jeden do jednego między zbiorem nieredukowalnych ułamków Q a zbiorem uporządkowanych par:

To. zbiór Q jest równoważny zbiorowi ((p,q))((m,n)).

Zbiór ((m,n)) – zbiór wszystkich uporządkowanych par – jest przeliczalny. W konsekwencji zbiór ((p,q)) jest przeliczalny, a zatem Q jest przeliczalne.

Definicja. Liczba niewymierna to dowolna nieskończona liczba dziesiętna nieokresowe ułamek, tj.  0 , 1  2 …

Zbiór wszystkich ułamków dziesiętnych tworzy zbiór liczby rzeczywiste (rzeczywiste).

Zbiór liczb niewymiernych jest nieprzeliczalny.

Twierdzenie 1. Zbiór liczb rzeczywistych z przedziału (0,1) jest zbiorem nieprzeliczalnym.

Dowód. Załóżmy odwrotnie, tj. że wszystkie liczby z przedziału (0,1) mogą być ponumerowane. Następnie zapisując te liczby w postaci nieskończonych ułamków dziesiętnych, otrzymujemy ciąg:

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

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

…………………..

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

……………………

Rozważmy teraz liczbę rzeczywistą x=0,b 1 b 2 …b n…, gdzie b 1 to dowolna liczba różna od 11, (0 i 9), b 2 to dowolna liczba różna od 22, (0 i 9 ) ,…, b n - dowolna liczba różna od nn, (0 i 9).

To. x(0,1), ale xx i (i=1,…,n) ponieważ w przeciwnym razie b i = a ii . Doszliśmy do sprzeczności. Itp.

Twierdzenie 2. Dowolny przedział osi rzeczywistej jest zbiorem nieprzeliczalnym.

Twierdzenie 3. Zbiór liczb rzeczywistych jest nieprzeliczalny.

O każdym zbiorze równym zbiorowi liczb rzeczywistych mówi się, że tak jest ciągła moc(łac. kontinuum - ciągłe, ciągłe).

Przykład. Pokażmy, że przedział ma moc kontinuum.

Funkcja y=tg x: →R wyświetla przedział na całej osi liczbowej (wykresie).

Superpozycja funkcji

Superpozycja funkcji f1, ..., fm jest funkcją f otrzymaną poprzez podstawienie tych funkcji względem siebie i zmianę nazw zmiennych.

Niech będą dwa odwzorowania i w dodatku zbiór niepusty. Wtedy superpozycja lub złożenie funkcji jest funkcją zdefiniowaną przez równość dla każdego.

Dziedziną definicji superpozycji jest zbiór.

Funkcja ta nazywana jest funkcją zewnętrzną i wewnętrzną dla superpozycji.

Funkcje przedstawiane jako złożenie „prostszych” funkcji nazywane są funkcjami złożonymi.

Przykładami zastosowania superpozycji są: rozwiązywanie układu równań przez podstawienie; znajdowanie pochodnej funkcji; znalezienie wartości wyrażenia algebraicznego poprzez podstawienie do niego wartości określonych zmiennych.

Funkcje rekurencyjne

Rekurencja to metoda definiowania funkcji, w której wartości zdefiniowanej funkcji dla dowolnych wartości argumentów wyrażane są w znany sposób poprzez wartości zdefiniowanej funkcji dla mniejszych wartości argumentów.

Funkcja pierwotnie rekurencyjna

Definicja pojęcia prymitywnej funkcji rekurencyjnej ma charakter indukcyjny. Polega na określeniu klasy podstawowych prymitywnych funkcji rekurencyjnych oraz dwóch operatorów (superpozycji i prymitywnej rekurencji), które pozwalają na konstruowanie nowych prymitywnych funkcji rekurencyjnych na podstawie już istniejących.

Podstawowe prymitywne funkcje rekurencyjne obejmują następujące trzy typy funkcji:

Funkcja null to funkcja bez argumentów, która zawsze zwraca 0 .

Funkcja sukcesji jednej zmiennej, która wiąże dowolną liczbę naturalną z następującą bezpośrednio po niej liczbą naturalną.

Funkcje, w których z n zmiennych odwzorowuje się dowolny uporządkowany zbiór liczb naturalnych na liczbę z tego zbioru.

Operatory podstawienia i pierwotnej rekurencji definiuje się następująco:

Operator superpozycji (czasami operator podstawienia). Niech będzie funkcją m zmiennych i niech będzie uporządkowanym zbiorem funkcji, każda ze zmiennymi. Wówczas wynikiem superpozycji funkcji w funkcję jest funkcja zmiennych, która wiąże liczbę z dowolnym uporządkowanym zbiorem liczb naturalnych.

Pierwotny operator rekurencji. Niech będzie funkcją n zmiennych i niech będzie funkcją zmiennych. Wówczas wynik zastosowania prymitywnego operatora rekurencji do pary funkcji nazywany jest funkcją zmiennej postaci;

W tej definicji zmienną można rozumieć jako licznik iteracji, - jako funkcję początkową na początku procesu iteracyjnego, która tworzy określoną sekwencję funkcji zmiennych zaczynając od i - jako operator, który jako zmienną wejściową przyjmuje liczbę kroku iteracji, funkcję w danym kroku iteracji i zwraca funkcję w następnym kroku iteracji.

Zbiór pierwotnych funkcji rekurencyjnych jest zbiorem minimalnym, który zawiera wszystkie podstawowe funkcje i jest zamknięty pod określonymi operatorami podstawienia i pierwotnymi operatorami rekurencji.

W terminologii programowania imperatywnego prymitywne funkcje rekurencyjne odpowiadają blokom programu wykorzystującym wyłącznie operacje arytmetyczne, a także operatorowi warunkowemu i operatorowi pętli arytmetycznej (operatorowi pętli, w którym na początku pętli znana jest liczba iteracji). Jeśli programista zacznie posługiwać się operatorem pętli while, w którym liczba iteracji jest z góry nieznana i w zasadzie może być nieskończona, wówczas przechodzi do klasy funkcji częściowo rekurencyjnych.

Wskażmy kilka dobrze znanych funkcji arytmetycznych, które są pierwotnie rekurencyjne.

Funkcję dodawania dwóch liczb naturalnych () można uznać za pierwotną funkcję rekurencyjną dwóch zmiennych, uzyskaną przez zastosowanie pierwotnego operatora rekurencji do funkcji, z których drugą uzyskuje się poprzez podstawienie funkcji głównej do funkcji głównej:

Mnożenie dwóch liczb naturalnych można uznać za pierwotną funkcję rekurencyjną dwóch zmiennych, uzyskaną przez zastosowanie pierwotnego operatora rekurencji do funkcji, z czego drugą uzyskuje się przez podstawienie funkcji podstawowych i do funkcji dodawania:

Symetryczną różnicę (wartość bezwzględną różnicy) dwóch liczb naturalnych () można uznać za pierwotną funkcję rekurencyjną dwóch zmiennych, otrzymaną poprzez zastosowanie następujących podstawień i pierwotnych rekurencji:

Funkcja budowania

Oferujemy Państwu usługę konstruowania wykresów funkcji online, do której wszelkie prawa należą do firmy Desmos. Użyj lewej kolumny, aby wprowadzić funkcje. Można wprowadzić ręcznie lub korzystając z wirtualnej klawiatury znajdującej się na dole okna. Aby powiększyć okno z wykresem, możesz ukryć zarówno lewą kolumnę, jak i wirtualną klawiaturę.

Korzyści z wykresów online

• Wizualna prezentacja wprowadzonych funkcji
• Tworzenie bardzo złożonych wykresów
• Konstrukcja wykresów określonych implicite (na przykład elipsa x^2/9+y^2/16=1)
• Możliwość zapisywania wykresów i otrzymania linku do nich, który staje się dostępny dla każdego w Internecie
• Kontrola skali, koloru linii
• Możliwość kreślenia wykresów punktowo, z wykorzystaniem stałych
• Jednoczesne rysowanie kilku wykresów funkcji
• Wykreślanie współrzędnych biegunowych (użyj r i θ(\theta))

Z nami łatwo jest budować wykresy o różnej złożoności online. Budowa odbywa się błyskawicznie. Usługa jest potrzebna do znajdowania punktów przecięcia funkcji, do przedstawiania wykresów w celu dalszego przenoszenia ich do dokumentu Word jako ilustracji przy rozwiązywaniu problemów oraz do analizowania cech behawioralnych wykresów funkcji. Optymalną przeglądarką do pracy z wykresami na tej stronie serwisu jest Google Chrome. Nie gwarantuje się poprawnego działania w przypadku korzystania z innych przeglądarek.

Jednocyklowe (nie zawierające elementów pamięci) dyskretne urządzenia logiczne realizują na wyjściu pewien zestaw funkcji algebry logicznej `F m =(F 1 ,F 2 ,…,F m), które w każdym momencie zależą wyłącznie od stanu wejść urządzenia `x n =(X 1 ,X 2 ,…,x rz): `F m = `F m(`x n). W praktyce takie urządzenia są projektowane i produkowane z oddzielnych, niepodzielnych elementów, które realizują określony zestaw (system) ( F) elementarne funkcje algebry poprzez połączenie wyjść niektórych elementów z wejściami innych.

Podczas projektowania urządzeń logicznych istotne są następujące pytania.

1. Podano układ funkcji elementarnych ( F). Jakie są funkcje wyjściowe Fi można uzyskać za pomocą funkcji z ( F}?

2. Zbiór wyjściowych funkcji boolowskich ( F) (w szczególności równy całemu zestawowi funkcji algebry logiki R 2). Jaki powinien być początkowy układ funkcji elementarnych ( F), zapewniając możliwość uzyskania na wyjściu dowolnej funkcji zestawu ( F}?

Aby udzielić rozsądnej odpowiedzi na te pytania, stosuje się pojęcia superpozycji, domknięcia i zupełności systemów funkcji.

Definicja. Rozważmy zbiór spójników logicznych ( F), odpowiadający pewnemu systemowi funkcji ( F} . Superpozycja skończona{F) to dowolna funkcja j, którą można zrealizować za pomocą wzoru na ( F}.

W praktyce superpozycję można przedstawić w wyniku podstawienia funkcji z ( F) jako argumenty funkcji z tego samego zestawu.

Przykład 1. Rozważmy system funkcji ( F} = {F 1 (X) =`x, f 2 (x, y)= X&y, f 3 (x, y)=XÚ y). Podstawienie do funkcji F 3 (x, y) zamiast pierwszego argumentu X funkcjonować F 1 (X), zamiast drugiego - F 2 (x, y), otrzymujemy superpozycję H(x, y)=F 3 (F 1 (X), F 2 (x, y))=`xÚ X& Na. Fizyczną realizację podstawienia pokazano na rys. 1.18.

Definicja. Pozwalać M-pewny zbiór funkcji algebry logicznej ( P 2). Zbiór wszystkich superpozycji ponad M zwany zwarcie zestawy M i jest oznaczony przez [ M] Otrzymujący [ M] według oryginalnego zestawu M zwany operacja zamknięcia. Pęczek M zwany funkcjonalnie zamknięta klasa, Jeśli [ M] = M. Podzbiór MÍ M zwany funkcjonalnie kompletny system w formacie M, Jeśli [ M] = M.

Zamknięcie [ M] reprezentuje cały zestaw funkcji, z których można uzyskać M stosując operację superpozycji, tj. wszystkie możliwe substytucje.

Notatki. 1. Oczywiście dowolny układ funkcji ( F) jest sam w sobie funkcjonalnie kompletny.

2 . Bez utraty ogólności możemy założyć, że funkcja tożsamościowa F(X)=x, który nie zmienia wartości prawdziwych zmiennych, jest początkowo częścią dowolnego systemu funkcji.

Przykład 2. Dla omówionych poniżej układów funkcji ( F) wykonaj następujące czynności:

1) znajdź zamknięcie [ F],

2) dowiedzieć się, czy system ( F) zajęcia zamknięte,

3) znaleźć funkcjonalnie kompletne systemy w ( F}.

Rozwiązanie.

I. ( F}={0} . Podstawiając funkcję ( f° 0) otrzymujemy to w siebie, tj. nie są tworzone żadne nowe funkcje. Oznacza to: [ F] = {F). Rozważany system jest klasą funkcjonalnie zamkniętą. Funkcjonalnie kompletny system w nim jest jeden i równy całości ( F}.

II. ( F} = {0,Ø } . Substytucja Ř (Ř X) daje identyczną funkcję, która formalnie nie rozszerza oryginalnego systemu. Natomiast podstawiając Ø (0) otrzymujemy identyczną jednostkę – nową funkcję, której nie było w pierwotnym systemie: Ø (0)=1 . Zastosowanie wszelkich innych podstawień nie powoduje pojawienia się nowych funkcji, np.: Ø Ø 0 = 0, 0(Ř X)=0.

Zatem zastosowanie operacji superpozycji umożliwiło uzyskanie szerszego zestawu funkcji niż pierwotny [ F]=(0,Ř,1). Oznacza to ścisły wpis: ( F} Ì [ F] System źródłowy ( F) nie jest funkcjonalnie zamkniętą klasą. Oprócz samego systemu ( F) nie ma w nim innych funkcjonalnie kompletnych układów, gdyż w przypadku jego zawężenia do jednej funkcji f= 0 nie można zanegować przez podstawienie, a identycznego zera nie można uzyskać na podstawie samej funkcji negacji.

III. ( F) = (& , Ú , Ø ). Zamknięciem tego układu jest cały zbiór funkcji algebry logiki P 2, ponieważ wzór dowolnego z nich można przedstawić jako DNF lub CNF, który wykorzystuje funkcje elementarne ( F) = (&, Ú, Ø). Fakt ten jest konstruktywnym dowodem kompletności rozważanego układu funkcji w P 2: [F]=P 2 .

Od w P 2 zawiera nieskończoną liczbę innych funkcji innych niż ( F) = (& , Ú , Ø ), to oznacza to ścisłe wystąpienie: ( F}Ì[ F] Rozważany system nie jest klasą funkcjonalnie zamkniętą.

Oprócz samego systemu, podsystemy będą kompletne funkcjonalnie ( F) 1 = (&, Ř) i ( F) 2 = (Ú, Ř). Wynika to z faktu, że korzystając z reguł De Morgana, funkcję dodawania logicznego Ú można wyrazić poprzez (& , Ø), a funkcję mnożenia logicznego & poprzez (Ú, Ø):

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

Inne kompletne funkcjonalnie podsystemy w ( F) NIE.

Sprawdzenie kompletności podsystemu funkcyjnego ( F) 1 М ( F)w całym systemie ( F) można wytworzyć przez połączenie ( F) 1 do drugiego, oczywiście uzupełnij w ( F)system.

Niekompletność podsystemu ( F) 1 w ( F) można zweryfikować, udowadniając ścisłe występowanie [ F 1 ] Ü [ F].

Definicja. Podzbiór MÍ M zwany podstawa funkcjonalna(podstawa)systemy m, Jeśli [ M] = M, a po wyeliminowaniu z niej jakiejkolwiek funkcji, zestaw pozostałych nie jest kompletny M .

Komentarz. Podstawy układu funkcji (F) są wszystkimi jego funkcjonalnie kompletnymi podsystemami (F) 1, którego nie można zmniejszyć bez utraty kompletności w (F).

Przykład 3. Znajdź podstawy dla wszystkich układów rozważanych w przykładzie 2.

Rozwiązanie.W przypadkach 1 i 2 jedynie same systemy są kompletne funkcjonalnie i nie da się ich zawęzić. W związku z tym są one również bazami.

W przypadku 3 istnieją dwa funkcjonalnie kompletne w ( F)podsystemy ( F) 1 = (&,Ř ) i ( F) 2 =(Ú,Ř ), którego nie można zmniejszyć bez utraty kompletności. Będą podstawą systemu ( F} = {&,Ú,Ø}.

Definicja. Niech system ( F) jest klasą zamkniętą. Jego podzbiór ( F) 1 М ( F) są nazywane klasa młodzieży w kl{F), Jeśli ( F) 1 nie jest ukończone w ( F} ([F 1 ] Ü [ F]), oraz dla dowolnej funkcji j z układu ( F), nieujęte w ( F) 1 (jO( F} \ {F) 1) prawda: [ JÈ { F} 1 ] = [F], tj. dodanie jк ( F) 1 uzupełnia go w ( F} .

Zadania

1. Sprawdź domkniętość zbiorów funkcji:

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

2. Sprawdź kompletność systemów funkcyjnych w P 2:

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

3. Znajdź domknięcie układu funkcji i jego podstawę:

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

1.10.2 Funkcje przechowujące stałe. Klasy T 0 i T 1

Definicja. Funkcjonować F(`x rz) oszczędza 0 jeśli F(0,..., 0) = 0. Funkcjonować F(`x n) oszczędza 1 jeśli F(1, ... , 1) = 1.

Wiele funkcji N zmienne przechowujące 0 i 1 są odpowiednio oznaczone, T 0 N I T 1 N. Wszystkie zbiory funkcji algebry logicznej, które zachowują 0 i 1 , oznaczać T 0 I T 1. Każdy z zestawów T 0 i T 1 to zamknięta klasa przedukończeniowa w R 2 .

Od funkcji elementarnych do T 0 i T 1 są jednocześnie uwzględnione, na przykład & i Ú. Przynależność dowolnej funkcji do klas T 0 , T 1 można sprawdzić za pomocą pierwszej i ostatniej wartości jego wektora wartości w tabeli prawdy lub bezpośrednio podstawiając zera i jedynki do wzoru podczas analitycznego określania funkcji.

Definicja.Duplikować to podstawienie, w którym tę samą zmienną podstawia się do funkcji zamiast kilku niezależnych zmiennych. W takim przypadku wartości zmiennych w zbiorach, które wcześniej przyjmowały wartości niezależnie od siebie, zawsze będą takie same.

ZADANIA

1.Sprawdź przynależność do klasy T 0 I T 1 Funkcje:

a) uogólnione dodawanie, b) uogólnione mnożenie, c) stałe, d) xyÚ yz, D) X® Na® xy, e) XÅ Na, I)( X 1 Å … Å X n) ® ( y 1 Å … Å y m) o godz n, mÎ N.

2. Udowodnić domkniętość każdej klasy T 0 I T 1 .

3. Udowodnij, że jeśli F(`x n) Ï T 0, to z niego, powielając podstawienie, możesz otrzymać stałą 1 lub negację.

4. Udowodnij, że jeśli F(`x n) Ï T 1 , to z niego, powielając podstawienie, możesz otrzymać stałą 0 lub negację.

5. Udowodnić przedzupełność każdej z klas T 0 I T 1 (na przykład poprzez redukcję systemu rozszerzonego do ( F} = {& ,Ú ,Ø }).

6. Znajdź moc zajęć T 0 N I T 1 N.