Операція - суперпозиція - Технічний словник Том III
Операції суперпозиції та примітивної рекурсії, будучи застосовані до всюди певних функцій, дають у результаті знову усюди певні функції. Операції суперпозиції та примітивної рекурсії, будучи застосовані до всюди певних функцій, дають у результаті знову усюди певні функції. Операція суперпозиції вводиться так само, як і для попередніх функціональних систем: спочатку визначається поняття формули 31 (XL. Операція суперпозиції функцій полягає у підстановці одних арифметичних функцій замість аргументів інших арифметичних функцій. Операцію суперпозиції визначимо наступним чином Щодо операції суперпозиції безліч J % є І. Принципове значення має наступна теорема Вагнера-Престона: довільна І. S ізоморфно вкладена в симетричну І. Визначимо операцію суперпозиції над ймовірнісними автоматами.Так як розглядаються автомати без виходів , то вважаємо, що алфавіт станів першого автомата збігається з вхідним алфавітом другого автомата, до яких застосовується операція суперпозиції. Що стосується операції суперпозиції, то матричну форму запису можна визначити наступним чином. Розглянемо запис операції суперпозиції в матричній формі. Нехай А і В – деякі автомати Милі з S3, a RA – гц (х/у) та RB гм (х/у) – відповідно матриці з'єднань цих автоматів. Визначимо тепер операцію суперпозиції графів, яка, як буде показано нижче, на автоматичному рівні відповідає послідовній роботі двох або більше автоматів. Попередньо зауважимо, що аналітичний запис операції суперпозиції графів не такий прозорий, як попередні операції. Це пояснюється специфікоюпослідовної роботи автоматів Набагато зручніше операцію суперпозиції задавати в матричній формі, яка буде наведена в § 6 цього розділу. Отже, операція суперпозиції зберігає допустимість функцій. Алгоритм розкладання автоматів по операції суперпозиції аналогічний алгоритму, наведеному для графів (див. гл. Клас Рвич замкнутий щодо операції суперпозиції. Легко бачити, що операція суперпозиції є асоціативною операцією.
Необхідність випливає з визначення операції суперпозиції та поняття й-правильної клітинної ма-матриці. Клас детермінованих функцій замкнутий щодо операції суперпозиції. Тоді клас 21 замкнений щодо операції суперпозиції. З визначення операції перестановки випливає справедливість таких тверджень. Замкненість множини РА % щодо операції суперпозиції випливає з принципу двоїстості. Встановимо замкнутість РА % щодо операції до подвійних функцій. Породжувальними операціями класу S є операції суперпозиції та обмеженого підсумовування. Граф G не розкладемо за операцією суперпозиції. У затвердженні 2.1 як операцію суперпозиції використовується нерегулярна суперпозиція, за допомогою якої визначаються функції сп. При вивченні функціональних систем з операцією суперпозиції дослідження в першу чергу проводяться за наступними двома тісно пов'язаними темами. Сімейство (1Л) замкнуте щодо операції суперпозиції: послідовне застосування двох гфеутворень з параметрами г і г2 оквіллонтно перетворення з параметрами Ti-ьга. Підмножини множини Pk, замкнуті щодо операції суперпозиції, називаємо замкнутими класами. Далі розглядаємо лише замкнуті класи, які містять усі селекторні функції. Підмножинаабстрактних автоматів 3) за операцією суперпозиції утворює групу ЗХ. Q є замикання множини Q щодо операцій суперпозиції та обмеженого підсумовування. Класи / г-значної логіки, замкнуті щодо розширеної операції суперпозиції // Вісник МДУ. Таким чином, на множині Р2 задана операція суперпозиції. Pk, k 2, замкнутий щодо операцій суперпозиції та перестановки з довільною нескінченною безліччю кутових наборів, породжується функціями від k змінних, і, отже, безліч усіх таких класів є кінцевим. Доказ цього факту проводиться у два етапи.
Класи функцій тризначної логіки, замкнуті щодо операцій суперпозиції та перестановки // Вісник МДУ. Перш ніж провести індуктивний перехід, розкладемо загальну нерегулярну операцію суперпозиції на чотири простіші операції. Усі симетрії диференціального рівняння утворюють групу з операцією суперпозиції, звану групою всіх симетрії цього рівняння. У результаті було обрано функціональні системи з операцією суперпозиції і з носіями, що з функцій багатозначної логіки, функцій натурального аргументу і автоматних функцій. Вибір операції суперпозиції як єдиної операції в функціональних системах, що вивчаються, обумовлений низкою причин. Насамперед операція суперпозиції є по суті базовою операцією в теорії функціональних систем. Зазвичай вона входить у сукупність Про операцій системи чи виходить із операцій У вигляді похідної операції. Результати, отримані для функціональних систем з операцією суперпозиції, як правило, є відправними точками (а найчастіше і орієнтирами) у дослідженнях з функціональних систем з іншими операціями. Важливо й те, що операція суперпозиції досить добреформалізується та алгебраїзується. Це дозволяє здійснювати плідний обмін ідеями та методами між теорією функціональних систем з одного боку та універсальною алгеброю, математичною логікою та теорією алгоритмів – з іншого. Будь-який параметрично замкнутий клас булевих функцій замкнутий щодо операції суперпозиції. Справедливість виразів (7.34) та (7.35) випливає з визначень операції суперпозиції, одиничного та зворотного автоматів. Аналогічний сенс тут мають суперпозиція функцій з Р та операція суперпозиції. Далі вводиться поняття еквівалентності формул S2l і 93: Ц2193, якщо відповідні їм функції /q і fcQ рівні. Аналогічний зміст тут мають суперпозицію функцій з ty і операцію суперпозиції. Далі вводиться поняття еквівалентності формул 31 і 33: 31 Я5, якщо відповідні їм функції / та / % рівні. Про таку множину говорять, що вона замкнута щодо операції суперпозиції функцій, або, інакше, що суперпозиція є внутрішньою операцією для такої множини. У зв'язку з цим є важливим вивчення таких посилень операції суперпозиції, які, з одного боку, не є настільки сильними, щоб давати кінцеве безліч замкнутих класів, а з іншого боку дозволяють досить просто знаходити результат застосування цих операцій до функцій. Тоді потужність безлічі класів в Pk, замкнутих щодо операцій суперпозиції та перестановки з безліччю кутових наборів W, кінцева. Тоді потужність безлічі класів в Pk, замкнутих щодо операцій суперпозиції та перестановки типу II з безліччю кутових наборів W, кінцева. Тоді потужність безлічі класів в Pk, замкнутих щодо операцій суперпозиції та перестановки типу II з безліччю кутових наборів W, дорівнює потужності континууму. Тоді потужністьбезлічі класів Pk, замкнутих щодо операцій суперпозиції і перестановки типу I з безліччю кутових наборів W, дорівнює потужності континууму. Тоді потужність безлічі класів в Pk, замкнутих щодо операцій суперпозиції та перестановки з безліччю кутових наборів W, лічильна.