Дивитися, що таке "Суперпозиція функцій" в інших словниках. Дивитися сторінки, де згадується термін суперпозиція функцій Знайти графічну суперпозицію ліній

Ознайомимося з поняттям суперпозиції (чи накладання) функцій, що у тому, що замість аргументу цієї функції підставляється деяка функція від іншого аргументу. Наприклад, суперпозиція функцій дає функцію аналогічно виходять і функції

У загальному вигляді, припустимо, що функція визначена в деякій області а функція визначена в області причому значення її всі містяться в області Тоді змінна z, як кажуть, через посередництво у, і сама є

За заданим спочатку знаходять відповідне йому (за правилом, що характеризується знаком значення у з, а потім встановлюють відповідне цьому значенню у (за правилом,

значення, що характеризується знаком, і вважають відповідним обраному х. Отримана функція від функції або складна функція і є результатом суперпозиції функцій

Припущення, що значення функції не виходять за межі тієї області, в якій визначена функція дуже істотно: якщо його опустити, то може вийти і безглуздість. Наприклад, вважаючи ми можемо розглядати лише такі значення х, котрим бо інакше вираз мало б сенсу.

Ми вважаємо корисним тут підкреслити, що характеристика функції, як складної, пов'язана не з природою функціональної залежності z від х, а лише зі способом завдання цієї залежності. Наприклад, нехай для у в для

Тут функція виявилася заданою у вигляді складної функції.

Тепер, коли повністю з'ясовано поняття суперпозиції функцій, ми можемо точно охарактеризувати найпростіший з тих класів функцій, які вивчаються в аналізі: це, перш за все, перелічені вище елементарні функції, а потім всі ті, які з них виходять за допомогою чотирьох арифметичних дій і суперпозицій , послідовно застосованих кінцеве число разів. Про них говорять, що вони виражаються через елементарні у кінцевому вигляді; іноді їх також називають елементарними.

Згодом, опанувавши найскладнішим аналітичним апаратом (нескінченні ряди, інтеграли), ми познайомимося й іншими функціями, також грають значної ролі у аналізі, але вже які виходять межі класу елементарних функций.

Побудувати функцію

Ми пропонуємо до вашої уваги сервіс з потроєння графіків функцій онлайн, всі права на який належать компанії Desmos. Для введення функцій скористайтесь лівою колонкою. Можна вводити вручну або за допомогою віртуальної клавіатури внизу вікна. Для збільшення вікна з графіком можна приховати як ліву колонку, і віртуальну клавіатуру.

Переваги побудови графіків онлайн

Візуальне відображення функцій, що вводяться
Побудова дуже складних графіків
Побудова графіків, заданих неявно (наприклад, еліпс x^2/9+y^2/16=1)
Можливість зберігати графіки та отримувати на них посилання, яке стає доступним для всіх в інтернеті.
Управління масштабом, кольором ліній
Можливість побудови графіків за точками, використання констант
Побудова одночасно кількох графіків функцій
Побудова графіків у полярній системі координат (використовуйте r та θ(\theta))

З нами легко в режимі онлайн будувати графіки різної складності. Побудова провадиться миттєво. Сервіс затребуваний знаходження точок перетину функцій, зображення графіків для подальшого їх переміщення у Word документ як ілюстрацій під час вирішення завдань, для аналізу поведінкових особливостей графіків функций. Оптимальним браузером для роботи з графіками на цій сторінці є Google Chrome. У разі використання інших браузерів коректність роботи не гарантується.

У науковому середовищі широко відомий жарт на цю тему "нелінійність" порівнюється з "не-слоном" - всі створіння, крім "слонів", є "не-слонами". Подібність полягає в тому, що більшість систем і явищ в навколишньому світі нелінійні, за малим винятком. Всупереч цьому, у школі нас вчать "лінійному" мисленню, що дуже погано, з точки зору нашої готовності до сприйняття всепроникаючої нелінійності Всесвіту, чи то її фізичні, біологічні, психологічні чи соціальні аспекти. Нелінійність концентрує в собі одну з основних складностей пізнання навколишнього світу оскільки слідства, в загальній своїй масі, не пропорційні до причин, дві причини, при взаємодії, не адитивні, тобто наслідки є більш складними, ніж проста суперпозиція, функціями причин. Тобто результат, що отримується в результаті присутності та впливу двох причин, що діють одночасно, не є сумою результатів, отриманих у присутності кожної з причин окремо, за відсутності іншої причини.

Визначення 9. Її in на деякому проміжку X визначено функцію г-ф(лг) з безліччю значень Z і на множині Z визначено функцію у =/(z), то функцію у складної функцією від х (або суперпозицією функції), а змінна z - проміжної змінної складної функції.

Контролінг можна як суперпозицію трьох класичних управлінських функцій - обліку, контролю та аналізу (ретроспективного) . Контролінг як інтегрована функція управління уможливлює як підготовку рішення, а й забезпечення контролю його виконання з допомогою відповідних управлінських інструментів.

Як відомо /50/, будь-яку тимчасову функцію можна як суперпозицію (набір) простих гармонійних функцій з різним періодом, амплітудою і фазою. У випадку P(t) = f(t),

Перехідна чи імпульсна характеристики визначаються експериментально. При їх використанні за методом суперпозиції здійснюється спочатку розкладання обраної моделі вхідного впливу на елементарні функції часу, а потім підсумовування відгуків на них. Останню операцію називають іноді згортанням, а інтеграли у виразах (24). них вибирається той, у якого найпростіше підінтегральна функція.

Ця теорема зводить завдання на умовний екстремум до суперпозиції задач на безумовний екстремум. Справді, визначимо функцію R(g)

Суперпозиція ((>(f(x)), де у(у) - неубутня опукла функція одного змінного, /(х) - опукла функція є опуклою функцією.

Приклад 3.28. Повернемося до прикладу 3.27. На рис. 3.24 показаний у вигляді штрих-пунктирної кривої результат суперпозиції двох функцій приналежності, відповідних тим квантифікаторам, які є в цьому прикладі. За допомогою рівня відсічення зі значенням 0,7 отримані нечіткі інтервали на осі абсцис. Тепер ми можемо сказати, що диспетчер має очікувати зміни плану

Інший спосіб визначення функції F, відмінний від способу суперпозиції, полягає в тому, що при застосуванні будь-якого квантифікатора до іншого квантифікатора відбувається певне монотонне перетворення вихідної функції приналежності, що зводиться до розтягування та зсуву максимуму функції в той чи інший бік.

Приклад 3.29. На рис. 3.25 показано два результати, отримані за допомогою суперпозиції та зсуву з розтягуванням, для випадку, коли ХА та X відповідають квантифікатору часто. Різниця полягає, мабуть, у тому, що суперпозиція вичленює у функції власності часто ті значення, які часто зустрічаються. У разі зсуву і розтягування ми можемо інтерпретувати результат як поява нового квантифікатора зі значенням часто-часто, який можна за бажання апроксимувати, наприклад, значенням дуже часто.

Покажіть, що суперпозиція строго зростаючої функції та функції корисності , що представляє деяке відношення переваги >, також є корисною функцією , що представляє це відношення переваги. Які з наведених нижче функцій можуть виступати в якості такого перетворення

Перше із співвідношень (2) являє собою не що інше, як запис правила, згідно з яким кожної функції F(x), що належить сімейству монотонно незменшуваних абсолютно безперервних функцій, ставиться у відповідність одна і тільки одна безперервна функція w(j). Це лінійно , тобто . для нього вірний принцип суперпозиції

Доведення. Якщо F відображається безперервно, функція М0 неперервна як суперпозиція безперервних функцій . Щоб довести другу частину затвердження, розглянемо функцію

Складні функції (суперпозиції)

Метод функціональних перетворень передбачає також використання евристичного підходу. Наприклад, використання логарифмічних перетворень як операторів В і С призводить до інформаційних критеріїв побудови моделей, що ідентифікуються, і використання потужного інструменту теорії інформації . Нехай оператор являє собою суперпозицію операторів множення на функцію,(.) і зсуву на функцію К0(), оператор С - оператор

Тут буде загалом наведено результати вирішення низки варіаційних завдань (1)-(3). Вони вирішувалися методом послідовної лінеаризації (19-21) ще 1962-1963 рр., коли технологія методу лише починала складатися і проходила перевірку. Тому ми зупинимося лише на деяких деталях. Насамперед зауважимо, що функції С і С2 були задані досить складними виразами, що є суперпозицією допоміжних функцій, у тому числі і таблично заданих. Тому при вирішенні сполученої системи ф=-fx використанням функцій, заданих таблично. Зазвичай подібні таблиці містять невелику кількість значень для набору вузлів у сфері зміни незалежного аргументу, а між ними функція інтерполується лінійно, оскільки застосування більш точних методів інтерполяції не виправдане через неточність самих табличних значень (зазвичай таблицями задаються функціональні залежності експериментального характеру). Однак для наших цілей потрібні функції, що диференціюються / (х, і), тому слід віддати перевагу гладким методам заповнення таблично заданої функції (наприклад, за допомогою сплайнів).

Нехай тепер (ТАК і (д - довільні функції, що відповідають якимось значенням квантифікаторів частоти. На рис. 3.23 показані дві одногорбі криві, що відповідають цим функціям. Результат їх суперпозиції - двогорба крива, показана штриховою лінією. Який її сенс Якщо, наприклад, (ТАК є рідко, а (д - часто,

Перевага такого способу визначення F полягає в тому, що при монотонних перетвореннях вид функції власності змінюється не кардинально. Її унімодальність або монотонність зберігається, і перехід від нового виду функції (2.16) мають трапецієподібну форму, то і лінійна суперпозиція (2.15) є трапецієподібним нечітким числом (що легко доводиться при використанні сегментного правила обчислень). І можна звести операції з функціями приналежності до операцій зі своїми вершинами. Якщо позначити трапецієподібне число (2.16) як (аь а2, аз, а4), де а відповідають абсцис вершин трапеції, то виконується

Визначення функції, області завдання та безлічі значень. Визначення, пов'язані із позначенням функції. Визначення складної, числової, дійсної, монотонної та багатозначної функції. Визначення максимуму, мінімуму, верхньої та нижньої граней для обмежених функцій.

Зміст

функцією y = f (x)називається закон (правило, відображення), згідно з яким кожному елементу x множини X ставиться у відповідність один і тільки один елемент y множини Y .

Безліч X називається областю визначення функції.
Безліч елементів y ∈ Y, які мають прообрази у множині X , називається безліччю значень функції(або областю значень).

Область визначенняфункції іноді називають безліччю визначенняабо безліччю завданняфункції.

Елемент x ∈ Xназивають аргументом функціїабо незалежної змінної.
Елемент y ∈ Yназивають значенням функціїабо залежною змінною.

Саме відображення f називається характеристикою функції.

Характеристика f має тим властивістю, що й два елементи і з множини визначення мають рівні значення: , то .

Символ, що позначає характеристику, може збігатися із символом елемента значення функції. Тобто можна записати так: . При цьому варто пам'ятати, що y – це елемент з безлічі значень функції, а – це правило, за яким для елемента x ставиться у відповідність елемент y.

Сам процес обчислення функції складається із трьох кроків. На першому кроці ми вибираємо елемент x з множини X . Далі, за допомогою правила , елементу x ставиться у відповідність елемент множини Y . На третьому етапі цей елемент присвоюється змінною y.

Приватним значенням функціїназивають значення функції при вибраному (приватному) значенні її аргументу.

Графіком функції fназивається безліч пар.

Складні функції

Визначення
Нехай задані функції та . Причому область визначення функції містить безліч значень функції g . Тоді кожному елементу t області визначення функції g відповідає елемент x , а цьому x відповідає y . Таку відповідність називають складною функцією: .

Складну функцію також називають композицією чи суперпозицією функційі іноді позначають так: .

У математичному аналізі прийнято вважати, що й характеристика функції позначена однією літерою чи символом, вона задає те саме відповідність. Однак, в інших дисциплінах, зустрічається й інший спосіб позначень, згідно з яким відображення з однією характеристикою, але різними аргументами вважаються різними. Тобто, відображення і вважаються різними. Наведемо приклад із фізики. Допустимо ми розглядаємо залежність імпульсу від координати. І нехай ми маємо залежність координати від часу. Тоді залежність імпульсу від часу є складною функцією. Але її, для стислості, позначають так: . За такого підходу і - це різні функції. При однакових значеннях аргументів можуть давати різні значення. У математиці таке позначення не прийнято. Якщо потрібно скорочення, слід ввести нову характеристику. Наприклад. Тоді явно видно, що і це різні функції.

Дійсні функції

Область визначення функції та безліч її значень можуть бути будь-якими множинами.
Наприклад, числові послідовності - це функції, областю визначення яких є безліч натуральних чисел, а безліччю значень - речові чи комплексні числа.
Векторний твір теж функція, оскільки для двох векторів є лише одне значення вектора . Тут областю визначення є безліч всіх можливих пар векторів. Безліч значень є безліч всіх векторів.
Логічне вираз є функцією. Її область визначення - це безліч дійсних чисел (або будь-яка множина, в якій визначено операцію порівняння з елементом "0"). Безліч значень і двох елементів - “істина” і “брехня”.

У математичному аналізі велику роль відіграють числові функції.

Числова функція- це функція, значеннями якої є дійсні чи комплексні числа.

Дійсна або речова функція- Це функція, значеннями якої є дійсні числа.

Максимум та мінімум

Справжні числа мають операцію порівняння. Тому безліч значень дійсної функції може бути обмеженим і мати найбільше та найменше значення.

Дійсна функція називається обмеженою зверху (знизу)якщо існує таке число M , що для всіх виконується нерівність:
.

Числова функція називається обмеженоюякщо існує таке число M , що для всіх :
.

Максимум M (мінімум m )функції f, на деякій множині X називають значення функції при деякому значенні її аргументу, при якому для всіх,
.

Верхньою граннюабо точним верхнім кордономдійсною, обмеженою зверху функції називають найменше з чисел, що обмежує область її значень зверху. Тобто це таке число s, для якого для всіх і для будь-якого, знайдеться такий аргумент, значення функції якого перевищує s′:.
Верхня грань функції може позначатися так:
.

Верхньою гранню необмеженої зверху функції

Нижньою граннюабо точним нижнім кордономдійсною, обмеженою знизу функції називають найбільше з чисел, що обмежує область її значень знизу. Тобто це таке число i , для якого для всіх і для будь - якого , знайдеться такий аргумент , значення функції якого менше ніж i : .
Нижня грань функції може позначатися так:
.

Нижньою гранню необмеженої знизу функціїє нескінченно віддалена точка.

Таким чином, будь-яка дійсна функція, на не порожній множині X, має верхню та нижню грані. Але не будь-яка функція має максимум і мінімум.

Як приклад розглянемо функцію, задану на відкритому інтервалі.
Вона обмежена, у цьому інтервалі, зверху значенням 1 і знизу – значенням 0 :
для всіх .
Ця функція має верхню та нижню грані:
.
Але вона не має максимуму та мінімуму.

Якщо ми розглянемо тугіше функцію на відрізку, то вона на цій множині обмежена зверху і знизу, має верхню і нижню грані і має максимум і мінімум:
для всіх ;
;
.

Монотонні функції

Визначення зростаючої та спадної функцій
Нехай функція визначена на деякому множині дійсних чисел X . Функція називається строго зростаючою (строго спадаючою)
.
Функція називається невтратною (незростаючою)якщо для всіх таких що виконується нерівність:
.

Визначення монотонної функції
Функція називається монотонної, якщо вона незнижена або незростаюча.

Багатозначні функції

Приклад багатозначної функції. Різними кольорами позначені її гілки. Кожна гілка є функцією.

Як випливає з визначення функції, кожному елементу x з області визначення ставиться у відповідність тільки один елемент з безлічі значень. Але існують такі відображення, в яких елемент x має кілька чи нескінченну кількість образів.

Як приклад розглянемо функцію арксинус: . Вона є зворотною до функції синусі визначається з рівняння:
(1) .
При заданому значенні незалежної змінної x , що належить інтервалу цього рівняння задовольняє нескінченно багато значень y (див. малюнок).

Накладемо на рішення рівняння (1) обмеження. Нехай
(2) .
За такої умови, заданого значення відповідає лише одне рішення рівняння (1). Тобто відповідність, що визначається рівнянням (1), за умови (2) є функцією.

Замість умови (2) можна накласти будь-яку іншу умову виду:
(2.n) ,
де n – ціле. В результаті, для кожного значення n ми отримаємо свою функцію, відмінну від інших. Безліч подібних функцій є багатозначною функцією. А функція, що визначається з (1) за умови (2.n) є гілкою багатозначної функції.

Це сукупність функцій, визначених на деякій множині.

Гілка багатозначної функції- це одна з функцій, що входять до багатозначної функції.

Однозначна функція- Це функція.

Використана література:
О.І. Бісів. Лекції з математичного аналізу. Частина 1. Москва, 2004.
Л.Д. Кудрявці. Курс математичного аналізу. Том 1. Москва, 2003.
С.М. Микільський. Курс математичного аналізу. Том 1. Москва, 1983.

Нехай є функція f(x 1 , x 2 , ... , x n) та функції

тоді функцію називатимемо суперпозицією функції f(x 1 , x 2 , ... , x n) та функцій .

Іншими словами: нехай F = ( f j ) - набір функцій алгебри логіки, не обов'язково кінцевий. Функція f називається суперпозицією функцій з множини F або функцією над F, якщо вона отримана з функції шляхом заміни однієї або декількох змінних функціями з множини F.

приклад.

Нехай задано безліч функцій

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

Тоді суперпозиціями функцій з F будуть, наприклад, функції:

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

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

Досконала ДНФ - суперпозиція функцій з множини

. ð

Визначення.

Система функцій називається повноїякщо за допомогою операцій суперпозиції та заміни змінних з функцій цієї системи може бути отримана будь-яка функція алгебри логіки. ð

Ми вже маємо певний набір повних систем:

;

Так як ;

(x + y, xy, 1). ð

Як визначити умови, за яких система повна. Із поняттям повноти тісно пов'язане поняття замкнутого класу.

Замкнені класи.

Безліч (клас) K функцій алгебри логіки називається замкнутим класом, якщо воно містить усі функції, що виходять з K операціями суперпозиції та заміни змінних, і не містить жодних інших функцій.

Нехай K - деяке підмножина функцій з P2. Замиканням K називається безліч всіх булевих функцій, представлених за допомогою операцій суперпозиції та заміни змінних функцій з множини K. Замикання множини K позначається через [K].

У термінах замикання можна дати інші визначення замкнутості та повноти (еквівалентні вихідним):

K-замкнений клас, якщо K = [K];

K – повна система, якщо [K] = Р 2 .

приклади.

* (0), (1) – замкнуті класи.

* Безліч функції однієї змінної - замкнутий клас.

* - замкнутий клас.

* Клас (1, x+y) не є замкнутим класом.

Розглянемо деякі найважливіші замкнуті класи.

1. Т 0- Клас функцій, що зберігають 0.

Позначимо через Т 0 клас всіх функцій алгебри логіки f(x 1 , x 2 , ... , x n), які зберігають константу 0, тобто функцій, котрим f(0, ... , 0) = 0.

Легко бачити, що є функції, що належать Т 0 і функції, що цьому класу не належать:

0, x, xy, xUy, x+y Î T 0 ;

З того, що T 0 випливає, наприклад, що не можна виразити через диз'юнкцію і кон'юнкцію.

Оскільки таблиця для функції f з класу Т 0 у першому рядку містить значення 0, то для функцій з Т 0 можна задавати довільні значення тільки на 2 n - 1 наборі змінних змін, тобто

де - безліч функцій, що зберігають 0 і залежать від змінних n.

Покажемо, що Т0 – замкнутий клас. Оскільки xÎT 0 то для обгрунтування замкнутості досить показати замкнутість щодо операції суперпозиції, оскільки операція заміни змінних є окремим випадком суперпозиції з функцією x.

Нехай. Тоді достатньо показати, що . Останнє випливає з ланцюжка рівностей

2. T 1- Клас функцій, що зберігають 1.

Позначимо через Т 1 клас всіх функцій алгебри логіки f(x 1 , x 2 , ... , x n), які зберігають константу 1, тобто функцій, котрим f(1, ... , 1) = 1.

Легко бачити, що є функції, що належать Т 1 і функції, що цьому класу не належать:

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

0, , x+y Ï T 1 .

З того, що x + y Ï T 0 випливає, наприклад, що x + y не можна виразити через диз'юнкцію та кон'юнкцію.

Результати про клас Т0 тривіально переносяться на клас Т1. Таким чином, маємо:

Т 1 – замкнутий клас;

3. L- Клас лінійних функцій.

Позначимо через L клас всіх функцій алгебри логіки f(x 1 , x 2 , ... , x n), що є лінійними:

Легко бачити, що є функції, що належать L і функції, що цьому класу не належать:

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

Доведемо, наприклад, що xÚy Ï L .

Припустимо неприємне. Шукатимемо вираз для xÚy у вигляді лінійної функції з невизначеними коефіцієнтами:

При x = y = 0 маємо a = 0,

при x = 1, y = 0 маємо b = 1,

при x = 0, y = 1 маємо g = 1,

але тоді за x = 1, y = 1 маємо 1Ú 1 ¹ 1 + 1, що доводить нелінійність функції xÚy.

Доказ замкнутості класу лінійних функцій цілком очевидний.

Оскільки лінійна функція однозначно визначається завданням значень n+1 коефіцієнта a 0 , ... , a n число лінійних функцій у класі L (n) функцій, що залежать від n змінних дорівнює 2 n+1 .

4. S- Клас самодвійних функцій.

Визначення класу самодвійних функцій ґрунтується на використанні так званого принципу двоїстості та двоїстих функцій.

Функція, яка визначається рівністю, називається двоїстої до функції .

Очевидно, що таблиця для двоїстої функції (при стандартній упорядкованості наборів значень змінних) виходить з таблиці для початкової функції інвертуванням (тобто заміною 0 на 1 і 1 на 0) стовпця значень функції та його перевертання.

Легко бачити, що

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

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

З визначення випливає, що (f*)* = f, тобто функція f є двоїстою до f*.

Нехай функція виражена за допомогою суперпозиції через інші функції. Постає питання, як побудувати формулу, що реалізує ? Позначимо через = (x 1 , ... , x n) всі різні символи змінних, які у наборах .

Теорема 2.6.Якщо функція j отримана як суперпозиція функцій f, f 1, f 2, ..., f m, тобто

функція, подвійна до суперпозиції, є суперпозиція двоїстих функцій.

Доведення.

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

Теорему доведено. ð

З теореми випливає принцип двоїстості: якщо формула А реалізує функцію f(x 1 , ... , xn), то формула, отримана з А заміною функцій, що входять до неї, на подвійні ним, реалізує двоїсту функцію f*(x 1 , ... , Xn).

Позначимо через S клас всіх самодвійних функцій з P 2:

S = (f | f * = f)

Легко бачити, що є функції, що належать S, і функції цього класу не належать:

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

Менш тривіальним прикладом самодвійної функції є функція

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

використовуючи теорему про функцію, подвійну до суперпозиції, маємо

h * (x, y, z) = (x U y) = (x U z) = (y = z) = x y U x z Ú y z; h = h *; h Î S.

Для самодвійної функції має місце тотожність

так що на наборах і , які ми називатимемо протилежними, самодвійна функція приймає протилежні значення. Звідси випливає, що самодвійна функція повністю визначається своїми значеннями першій половині рядків стандартної таблиці. Тому число самодвійних функцій у класі S(n) функцій, що залежать від n змінних, дорівнює:

Доведемо тепер, що клас S замкнутий. Оскільки xÎS , для обгрунтування замкнутості досить показати замкнутість щодо операції суперпозиції, оскільки операція заміни змінних є окремий випадок суперпозиції з функцією x. Нехай. Тоді достатньо показати, що . Останнє встановлюється безпосередньо:

5. М- Клас монотонних функцій.

Перш ніж визначати поняття монотонної функції логіки алгебри, необхідно ввести відношення впорядкованості на безлічі наборів її змінних.

Кажуть, що набір передує набору (або "не більше", або "менше або дорівнює"), і застосовують позначення , якщо a i £ b i для всіх i = 1, ..., n. Якщо і , то будемо говорити, що набір суворо передує набору (або "суворо менше", або "менше" набору), і використовувати позначення . Набори і називаються порівнянними, якщо , або .У разі, коли жодне з цих співвідношень не виконується, набори називаються незрівнянними. Наприклад, (0, 1, 0, 1) £ (1, 1, 0, 1), але набори (0, 1, 1, 0) та (1, 0, 1, 0) незрівнянні. Тим самим відношення £ (його часто називають ставленням попередження) є частковим порядком на множині n . Нижче наведені діаграми частково впорядкованих множин 2 , 3 і 4 .

Введене ставлення часткового порядку - винятково важливе поняття, що далеко виходить за межі нашого курсу.

Тепер ми маємо змогу визначити поняття монотонної функції.

Функція логіки алгебри називається монотонноїякщо для будь-яких двох наборів і , таких, що , має місце нерівність . Безліч всіх монотонних функцій алгебри логіки позначається через М, а безліч усіх монотонних функцій, що залежать від n змінних - через М (n).

Легко бачити, що є функції, що належать M , і функції цього класу не належать:

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

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

Покажемо, що клас монотонних функцій М – замкнутий клас. Так як xÎМ, то для обґрунтування замкнутості достатньо показати замкнутість щодо операції суперпозиції, оскільки операція заміни змінних є окремим випадком суперпозиції з функцією x.

Нехай. Тоді достатньо показати, що .

Нехай - набори змінних, відповідно, функцій j, f 1 , ... , f m , причому безліч змінних функції j складається з тих і тільки змінних, які зустрічаються у функцій f 1 , ... , f m . Нехай і-два набори значень змінної, причому. Ці набори визначають набори значень змінних , такі, що . Через монотонність функцій f 1 , ... , f m

і через монотонність функції f

Звідси отримуємо

Число монотонних функцій, що залежать від n змінних, достеменно невідомо. Легко може бути отримана оцінка знизу:

де є ціла частина від n/2.

Так само просто виходить завищена оцінка зверху:

Уточнення цих оцінок – важливе та цікаве завдання сучасних досліджень.

Критерій повноти

Тепер ми можемо сформулювати і довести критерій повноти (теорему Посту), що визначає необхідні та достатні умови повноти системи функцій. Попередимо формулювання та підтвердження критерію повноти кількома необхідними лемами, що мають і самостійний інтерес.

Лемма 2.7.Лемма про несамовласну функцію.

Якщо f(x 1 , ... , x n) S, то з неї шляхом підстановки функцій x і `x можна отримати константу.

Доведення. Оскільки fÏS, то знайдеться набір змінних змін
=(a 1 ,...,a n) такий, що

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

Замінимо аргументи у функції f:

x i замінюється на ,

тобто покладемо, і розглянемо функцію

Тим самим ми отримали константу (щоправда, невідомо, яка це константа: 0 чи 1). ð

Лемма 2.8.Лемма про немонотонну функцію.

Якщо функція f(x 1 ,...,x n) немонотонна, f(x 1 ,...,x n) M, то з неї шляхом заміни змінних та підстановки констант 0 і 1 можна отримати заперечення.

Доведення. Оскільки f(x 1 ,...,x n) Ï M, то знайдуться набори та значень її змінних, , , такі що , причому хоча б для одного значення i має місце a i< b i . Выполним следующую замену переменных функции f:

x i замінимо на

Після такої підстановки отримаємо функцію однієї змінної j(x), для якої маємо:

Це означає, що j(x)=`x. Лемма доведена. ð

Лемма 2.9.Лемма про нелінійну функцію.

Якщо f(x 1 ,...,x n) L, то з неї шляхом підстановки констант 0, 1 і використання функції `x можна отримати функцію x 1 &x 2 .

Доведення. Представимо f у вигляді ДНФ (наприклад, досконалої ДНФ) та скористаємося співвідношеннями:

приклад. Наведемо два приклади застосування зазначених перетворень.

Таким чином, функція, записана в диз'юнктивній нормальній формі, після застосування зазначених співвідношень, розкриття дужок і нескладних перетворень алгебри переходить в поліном по mod 2 (поліном Жегалкіна):

де A 0 константа, а А i - кон'юнкція деяких змінних з числа x 1, ..., x n, i = 1, 2, ..., r.

Якщо кожна кон'юнкція A i складається з однієї змінної, то f - лінійна функція, що суперечить умові леми.

Отже, в поліномі Жегалкіна для функції f знайдеться член, в якому міститься не менше двох співмножників. Без обмеження спільності вважатимуться, що з цих сомножителей присутні змінні x 1 і x 2 . Тоді поліном можна перетворити так:

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

де f 1 (x 3, ..., x n) ¹ 0 (інакше поліном не входить кон'юнкція, що містить кон'юнкцію x 1 x 2).

Нехай (a 3 ,...,a n) такі, що f 1 (a 3 ,...,a n) = 1.

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

де a, b, g – константи, рівні 0 або 1.

Скористаємося операцією заперечення, яка у нас є, і розглянемо функцію y(x 1 ,x 2), що виходить з j(x 1 ,x 2) таким чином:

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

Очевидно, що

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

Отже,

y(x1, x2) = x1x2.

Лемма доведена повністю. ð

Лемма 2.10.Основна лема критерію повноти.

Якщо в класі F=( f ) функцій алгебри логіки містяться функції, що не зберігають одиницю, не зберігають 0, несамовласні та немонотонні:

то з функцій цієї системи операціями суперпозиції та заміни змінних можна отримати константи 0, 1 та функцію .

Доведення. Розглянемо функцію. Тоді

Можливі два випадки наступних розглядів, у подальшому викладі позначені як 1) та 2).

1). Функція на одиничному наборі набирає значення 0:

Замінимо всі змінні функції змінної x. Тоді функція

є, бо

і .

Візьмемо несамовласну функцію. Так як функцію ми вже отримали, то по лемі про несамовій функцію (лема 2.7. ) можна отримати константу. Другу константу можна отримати із першої, використовуючи функцію . Отже, у першому розглянутому випадку отримано константи та заперечення. . Другий випадок, а разом із ним і основна лема критерію повноти, повністю доведені. ð

Теорема 2.11.Критерій повноти систем функцій логіки алгебри (теорема Посту).

Для того, щоб система функцій F = (fi )була повною, необхідно і достатньо, щоб вона повністю не містилася в жодному з п'яти замкнутих класів T 0 , T 1 , L , S, M, тобто для кожного з класів T 0 , T 1 , L , S, Mв F знайдеться хоча б одна функція, що цьому класу не належить.

Необхідність. Нехай F – повна система. Припустимо, що F міститься у одному із зазначених класів, позначимо його через K, тобто. F Í K. Останнє включення неможливе, оскільки K - замкнутий клас, що не є повною системою.

Достатність. Нехай система функцій F = (f i )цілком не міститься в жодному з п'яти замкнутих класів T 0 , T 1 , L , S, M. Візьмемо у Fфункції:

Тоді на основі основної леми (лема 2.10 ) з функції, що не зберігає 0, функції не зберігає 1, несамовласної та немонотонної функцій можна отримати константи 0, 1 і функцію заперечення :

На підставі леми про нелінійну функцію (лема 2.9 ) з констант, заперечення та нелінійної функції можна отримати кон'юнкцію:

Система функцій - повна система за теоремою про можливість представлення будь-якої функції логіки алгебри у вигляді досконалої диз'юнктивної нормальної форми (зауважимо, що диз'юнкція може бути виражена через кон'юнкцію і заперечення у вигляді ).

Теорему доведено повністю. ð

приклади.

1. Покажемо, що функція f(x,y) = x|y утворює повну систему. Побудуємо таблицю значень функції x½y:

x	y	x\|y

f(0,0) = 1, отже, x | yÏT 0 .

f(1,1) = 0, отже, x | yÏT 1 .

f(0,0) = 1, f(1,1) = 0, отже, x | yÏM.

f(0,1) = f(1,0) = 1 - на протилежних наборах x | y набуває однакових значень, отже x | yÏS .

Нарешті, що означає нелінійність функції
x | y.

З критерію повноти можна стверджувати, що f(x,y) = x | y утворює повну систему. ð

2. Покажемо, що система функцій утворює повну систему.

Справді, .

Тим самим серед функцій нашої системи знайдені: функція, що не зберігає 0, функція, що не зберігає 1, несамовласна, немонотонна та нелінійна функції. На підставі критерію повноти можна стверджувати, що система функцій утворює повну систему. ð

Таким чином, ми переконалися, що критерій повноти дає конструктивний та ефективний спосіб з'ясування повноти систем функцій алгебри логіки.

Сформулюємо тепер три наслідки із критерію повноти.

Наслідок 1. Будь-який замкнутий клас Kфункцій логіки алгебри, що не збігається з усім безліччю функцій логіки алгебри (K¹P 2), міститься принаймні в одному з побудованих замкнутих класів.

Визначення.Замкнений клас K називається передповним, якщо K неповний і для будь-якої функції f K клас K È (f) - повний.

З визначення випливає, що предповний клас є замкнутим.

Наслідок 2.В алгебрі логіки існує тільки п'ять предповних класів, а саме: T0, T1, L, M, S.

Для доказу слідства треба перевірити лише те, що жоден із цих класів не міститься в іншому, що підтверджується, наприклад, наступною таблицею приналежності функцій різним класам:

T 0	T 1	L	S	M
+	-	+	-	+
-	+	+	-	+
-	-	+	+	-

Наслідок 3.З будь-якої повної системи функцій можна назвати повну підсистему, що містить трохи більше чотирьох функцій.

З доказу критерію повноти випливає, що можна виділити трохи більше п'яти функцій. Із доказу основної леми (лема 2.10 ) випливає, що або несамовласна, або не зберігає одиницю і не монотонна. Тому потрібно трохи більше чотирьох функцій.