В научной среде широко известна шутка на эту тему "нелинейность" сравнивается с "не-слоном" - все создания, кроме "слонов", являются "не-слонами". Сходство заключается в том, что большинство систем и явлений в окружающем нас мире нелинейны, за малым исключением. Вопреки этому, в школе нас учат "линейному" мышлению, что очень плохо, с точки зрения нашей готовности к восприятию всепроникающей нелинейности Вселенной, будь то ее физические, биологические, психологические или социальные аспекты. Нелинейность концентрирует в себе одну из основных сложностей познания окружающего мира поскольку следствия, в общей своей массе, не пропорциональны причинам, две причины, при взаимодействии, не аддитивны, то есть следствия являются более сложными, чем простая суперпозиция, функциями причин. То есть, результат, получающийся в результате присутствия и воздействия двух причин, действующих одновременно, не является суммой результатов, полученных в присутствии каждой из причин в отдельности, при отсутствии другой причины.
Определение 9. Ее in на некотором промежутке X определена функция г-ф(лг) с множеством значений Z и на множестве Z определена функция у =/(z), то функция у Лсложной функцией от х (или суперпозицией функции), а переменная z - промежуточной переменной сложной функции.
Контроллинг можно представить как суперпозицию трех классических управленческих функций - учета, контроля и анализа (ретроспективного) . Контроллинг как интегрированная функция управления делает возможным не только подготовку решения, но и обеспечение контроля его выполнения с помощью соответствующих управленческих инструментов.
Как известно /50/, любую временную функцию можно представить как суперпозицию (набор) простых гармоничных функций с разным периодом, амплитудой и фазой. В общем случае P(t) = f(t),
Переходная или импульсная характеристики определяются экспериментально. При их использовании по методу суперпозиции осуществляется сначала разложение выбранной модели входного воздействия на элементарные" функции времени, а затем суммирование откликов на них. Последнюю операцию называют иногда свертыванием, а интегралы в выражениях (24). . . (29) - интегралами свертки. Из них выбирается тот, у которого проще подынтегральная функция.
Эта теорема сводит задачу на условный экстремум к суперпозиции задач на безусловный экстремум. В самом деле, определим функцию 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), где а соответствуют абсциссам вершин трапеции, то выполняется
Построить функцию
Мы предлагаем вашему вниманию сервис по потроению графиков функций онлайн, все права на который принадлежат компании Desmos . Для ввода функций воспользуйтесь левой колонкой. Вводить можно вручную либо с помощью виртуальной клавиатуры внизу окна. Для увеличения окна с графиком можно скрыть как левую колонку, так и виртуальную клавиатуру.
Преимущества построения графиков онлайн
- Визуальное отображение вводимых функций
- Построение очень сложных графиков
- Построение графиков, заданных неявно (например эллипс x^2/9+y^2/16=1)
- Возможность сохранять графики и получать на них ссылку, которая становится доступной для всех в интернете
- Управление масштабом, цветом линий
- Возможность построения графиков по точкам, использование констант
- Построение одновременно нескольких графиков функций
- Построение графиков в полярной системе координат (используйте r и θ(\theta))
С нами легко в режиме онлайн строить графики различной сложности. Построение производится мгновенно. Сервис востребован для нахождения точек пересечения функций, для изображения графиков для дальнейшего их перемещения в Word документ в качестве иллюстраций при решении задач, для анализа поведенческих особенностей графиков функций. Оптимальным браузером для работы с графиками на данной странице сайта является Google Chrome. При использовании других браузеров корректность работы не гарантируется.
Определение функции, области задания и множества значений. Определения, связанные с обозначением функции. Определения сложной, числовой, действительной, монотонной и многозначной функции. Определения максимума, минимума, верхней и нижней граней для ограниченных функций.
СодержаниеФункцией 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 называется множество пар .
Сложные функции
Определение
Пусть заданы функции и .
Причем область определения функции 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)).
Cовершенная ДНФ - суперпозиция функций из множества
. ð
Определение.
Система функций называется полной , если при помощи операций суперпозиции и замены переменных из функций этой системы может быть получена любая функция алгебры логики. ð
Мы уже имеем некоторый набор полных систем:
;
Так как 
;
Так как 
;
{x+y, xy, 1}. ð
Как же определить условия, при которых система полна. С понятием полноты тесно связано понятие замкнутого класса.
Замкнутые классы.
Множество (класс) K функций алгебры логики называется замкнутым классом , если оно содержит все функции, получающиеся из K операциями суперпозиции и замены переменных, и не содержит никаких других функций.
Пусть K - некоторое подмножество функций из P 2 . Замыканием 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, xÚy, 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 , ... , x n), то формула, полученная из А заменой входящих в нее функций на двойственные им, реализует двойственную функцию f*(x 1 , ... , x n).
Обозначим через S класс всех самодвойственных функций из P 2:
S = {f | f* = f }
Легко видеть, что есть функции, принадлежащие S, и функции, этому классу не принадлежащие:
0, 1, xy, xÚy Ï S .
Менее тривиальным примером самодвойственной функции является функция
h(x, y, z) = xy Ú xz Ú yz;
используя теорему о функции, двойственной к суперпозиции, имеем
h*(x, y, z)= (x Ú y)Ù(x Ú z) Ù (y Ù z) = x y Ú 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 .
 |
 |
Введенное отношение частичного порядка - исключительно важное понятие, далеко выходящее за рамки нашего курса.
Теперь мы имеем возможность определить понятие монотонной функции.
Функция алгебры логики называется монотонной
, если для любых двух наборов и , таких, что , имеет место неравенство 
. Множество всех монотонных функций алгебры логики обозначаетcя через М, а множество всех монотонных функций, зависящих от 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 ,..., x n) + x 1 f 2 (x 3 ,..., x n) + x 2 f 3 (x 3 ,..., x n) + f 4 (x 3 ,..., x n),
где 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(x 1 ,x 2) = j(x 1 +b, x 2 +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(x 1 ,x 2) = x 1 x 2 .
Лемма доказана полностью.ð
Лемма 2.10. Основная лемма критерия полноты.
Если в классе F={ f } функций алгебры логики содержатся функции, не сохраняющие единицу, не сохраняющие 0, несамодвойственные и немонотонные:
то из функций этой системы операциями суперпозиции и замены переменных можно получить константы 0, 1 и функцию .
Доказательство . Рассмотрим функцию . Тогда
.
Возможны два случая последующих рассмотрений, в дальнейшем изложении обозначенные как 1) и 2).
1). Функция на единичном наборе принимает значение 0:
.
Заменим все переменные функции переменной x . Тогда функция
есть , ибо
и 
.
Возьмем несамодвойственную функцию . Так как функцию мы уже получили, то по лемме о несамодвойственной функции (лемма 2.7. ) из можно получить константу. Вторую константу можно получить из первой, используя функцию . Итак, в первом рассмотренном случае получены константы и отрицание. . Второй случай, а вместе с ним и основная лемма критерия полноты, полностью доказаны. ð
Теорема 2.11. Критерий полноты систем функций алгебры логики (теорема Поста).
Для того, чтобы система функций F = {f i }была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов 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. В алгебре логики существует только пять предполных классов, а именно:T 0 ,T 1 , L , M , S .
Для доказательства следствия нужно проверить только то, что ни один из этих классов не содержится в другом, что подтверждается, например, следующей таблицей принадлежности функций различным классам:
| T 0 | T 1 | L | S | M | |
| + | - | + | - | + | |
| - | + | + | - | + | |
| - | - | + | + | - |
Следствие 3. Из всякой полной системы функций можно выделить полную подсистему, содержащую не более четырех функций.
Из доказательства критерия полноты следует, что можно выделить не более пяти функций. Из доказательства основной леммы (лемма 2.10
) следует, что 
либо несамодвойственна, либо не сохраняет единицу и не монотонна. Поэтому нужно не более четырех функций.
Пусть есть 2 функции:
: A→B и g: D→F
Пусть область определения D функции g входит в область значений функции f (DB). Тогда можно определить новую функцию – суперпозицию (композицию, сложную функцию) функций f и g: z = g ( (x )).
Примеры. f(x)=x 2 , g(x)=e x . f:R→R, g:R→R.
(g(x))=e 2x , g((x))=.
Определение
Пусть идве функции. Тогда их композицией называется функция, определённая равенством:
Свойства композиции
Композиция ассоциативна:
Если F = id X - тождественное отображение на X , то есть
.
Если G = id Y - тождественное отображение на Y , то есть
.
Дополнительные свойства
Счетные и несчетные множества.
Два конечных множества состоят из равного числа элементов, если между этими множествами можно установить взаимно однозначное соответствие. Число элементов конечного множества – мощность множества.
Для бесконечного множества можно установить взаимно однозначное соответствие между всем множеством и его частью.
Самым простым из бесконечных множеств является множество N.
Определение. Множества А и В называются эквивалентными (АВ), если между ними можно установить взаимно однозначное соответствие.
Если эквивалентны два конечных множества, то они состоят из одного и того же числа элементов.
Если же эквивалентные между собой множества А и В произвольны, то говорят, что А и В имеют одинаковую мощность . (мощность = эквивалентность).
Для конечных множеств понятие мощности совпадает с понятием числа элементов множества.
Определение. Множество называется счетным , если можно установить взаимно однозначное соответствие между ним и множеством натуральных чисел. (Т.е. счетное множество – бесконечное, эквивалентное множеству N).
(Т.е. все элементы счетного множества можно занумеровать).
Свойства отношения равномощности.
1) АА- рефлексивность.
2) АВ, то ВА – симметричность.
3) АВ и ВС, то АС – транзитивность.
Примеры.
1) n→2n, 2,4,6,… - четные натуральные
2) n→2n-1, 1,3,5,…- нечетные натуральные.
Свойства счетных множеств .
1. Бесконечные подмножества счетного множества счетны.
Доказательство . Т.к. А – счетно, то А: х 1 ,х 2 ,… - отобразили А в N.
ВА, В: →1,→2,… - поставили каждому элементу В в соответствиенатуральное число, т.е. отобразили В в N. Следовательно В – счетно. Ч.т.д.
2. Объединение конечной (счетной) системы счетных множеств – счетно.
Примеры .
1. Множество целых чисел Z – счетно, т.к. множество Z можно представить как объединение счетных множеств А и В, где А: 0,1,2,.. и В: -1,-2,-3,…
2. Множество упорядоченных пар {(m,n): m,nZ} (т.е. (1,3)≠(3,1)).
3 (!) . Множество рациональных чисел – счетно.
Q=. Можно установить взаимно однозначное соответствие между множеством несократимых дробейQ и множеством упорядоченных пар:
Т.о. множество Q равномощно множеству {(p,q)}{(m,n)}.
Множество {(m,n)} – множество всех упорядоченных пар – счетно. Следовательно и множество {(p,q)} – счетно, а значит и Q – счетно.
Определение. Иррациональным числом называется произвольная бесконечная десятичная непериодическая дробь, т.е. 0 , 1 2 …
Множество всех десятичных дробей образуют множество вещественных (действительных) чисел.
Множество иррациональных чисел – несчетно.
Теорема 1 . Множество вещественных чисел из промежутка (0,1) – несчетное множество.
Доказательство . Допустим противное, т.е. что все числа интервала (0,1) можно занумеровать. Тогда, записывая эти числа в виде бесконечных десятичных дробей, получим последовательность:
х 1 =0,а 11 а 12 …a 1n …
x 2 =0,a 21 a 22 …a 2n …
…………………..
x n =0,a n 1 a n 2 …a nn …
……………………
Рассмотрим теперь вещественное число х=0,b 1 b 2 …b n …, где b 1 - любая цифра, отличная от а 11 , (0 и 9), b 2 - любая цифра, отличная от а 22 , (0 и 9),…, b n - любая цифра, отличная от a nn , (0 и 9).
Т.о. х(0,1), но хx i (i=1,…,n) т.к. в противном случае, b i =a ii . Пришли к противоречию. Ч.т.д.
Теорема 2. Любой промежуток вещественной оси является несчетным множеством.
Теорема 3. Множество действительных (вещественных) чисел – несчетно.
Про всякое множество, равномощное множеству вещественных чисел говорят, что оно мощности континуума (лат. continuum – непрерывное, сплошное).
Пример . Покажем, что интервал обладает мощностью континуума.
Функция у=tg x: →R отображает интервал на всю числовую прямую (график).
