![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Система B функций из (
) называется (функционально) полной, если любая функция из
может быть записана в виде формулы через функции этой системы.
Примерами полных систем является:
2. B= .
3. B= .
4. B= .
5. B= ,где
.
Функция называется фуннцией Вебба представляет собой аналог функции Шеффера.
Пусть M – произвольное подмножество функции из . З амыканием M называется множество [M] всех функций из
, представленных в виде формул через функции множества M`
Класс M называется (функционально) замкнутым, если замыкание [M]=M.
Таким образом, в терминах замыкания можно определить полноту системы функций, а именно B является полной системой если замыкание [B]= .
Справедлива теорема о функциональной полноте - теорема Кузнецова А.В.:
Можно построить систему замкнутых классов в - M1, M2,…,Ms, каждый из которых не содержит целиком ни одного из остальных классов и такую, что подсистема функций из
полна тогда и только тогда, когда она целиком не содержится ни в одном из классов M1, M2,…,Ms. Это аналог теоремы Поста.
Теорема Кузнецова доказывает, что возможно выразить, условие полноты системы B в терминах принадлежности ее к специальным классам M1, M2,…,Ms, однако практическое построение классов даже при небольших k связано с трудоемкими вычислениями. Поэтому возникает вопрос о поиске других более эффективных критериев полноты. Эта цель достигается за счет введения ограничений, т.е. за счет знания дополнительной информации о системе B.
Существенными называются функции из
, если они существенно зависят не менее чем от двух переменных.
Теорема Яблонского
Пусть система B функций из , где k ³ 3, содержит все функции одной переменной, принимающие не более k -1 значений. Тогда для полноты системы B необходимо и достаточно, чтобы B содержало существенную функцию
, принимающую все k значений.
Следствие (критерий Слупецкого):
Пусть система B функций из , где к ³ 3, содержит все функции одной переменной. Тогда для полноты системы B необходимо и достаточно, чтобы B содержало существенную функцию
, принимающую все k значений.
Непосредственное использование теоремы и ее следствия не всегда удобно, так как для этого необходимо установить наличие в B всех функций одной переменной, принимающих не более k -1 значения, т.е. функций. С ростом k громоздкость вычислений возрастает. Поэтому это требование целесообразно заменить требованием, в котором система функций B порождало бы множество функций одной переменной.
Известно, что функции из B могут быть получены из конкретных систем функций одной переменной.
Теорема 1 (Пикара).
Все функции одной переменной из могут быть порождены тремя функциями:
1. ,
2. ,
3. .
Теорема 2
Все функции одной переменной из могут быть порождены k функциями
и функцией .
Теорема 3 (Мартина).
Функция из
при к ³ 3 является функция Шеффера, тогда и только тогда, когда
порождает все функции одной переменной принимающие не более k -1 значений.
Дата публикования: 2015-03-26; Прочитано: 4048 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!