Операция суперпозиции функций. Суперпозиция функций. Свойства булевых функций

Пусть имеется функция 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 ) следует, что либо несамодвойственна, либо не сохраняет единицу и не монотонна. Поэтому нужно не более четырех функций.

Познакомимся с понятием суперпозиции (или наложения) функций, которая состоит в том, что вместо аргумента данной функции подставляется некоторая функция от другого аргумента. Например, суперпозиция функций даёт функцию аналогично получаются и функции

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

По заданному из сначала находят соответствующее ему (по правилу, характеризуемому знаком значение у из У, а затем устанавливают соответствующее этому значению у (по правилу,

характеризуемому знаком значение его и считают соответствующим выбранному х. Полученная функция от функции или сложная функция и есть результат суперпозиции функций

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

Мы считаем полезным здесь же подчеркнуть, что характеристика функции, как сложной, связана не с природой функциональной зависимости z от х, а лишь со способом задания этой зависимости. Например, пусть для у в для Тогда

Здесь функция оказалась заданной в виде сложной функции.

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

Впоследствии, овладев более сложным аналитическим аппаратом (бесконечные ряды, интегралы), мы познакомимся и с другими функциями, также играющими важную роль в анализе, но уже выходящими за пределы класса элементарных функций.

Тема: «Функция: понятие, способы задания, основные характеристики. Обратная функция. Суперпозиция функций.»

Эпиграф урока:

«Изучать что-либо и не задумываться над

выученным - абсолютно бесполезно.

Задумываться над чем-либо, не изучив

предварительно предмет раздумий-

Конфуций.

Цель и психолого-педагогические задачи урока :

1) Общеобразовательная (нормативная) цель : повторить со студентами определение и свойства функции. Ввести понятие суперпозиции функций.

2) Задачи математического развития студентов : на нестандартном учебно-математическом материале продолжить развитие ментального опыта учащихся, содержательной когнитивной структуры их математического интеллекта, в том числе, способностей к логико-дедуктивному и индуктивному, аналитическому и синтетическому обратимому мышлению, к алгебраическому и образно-графическому мышлению, к содержательному обобщению и конкретизации, к рефлексии и самостоятельности как метакогнитивной способности студентов; продолжить развитие культуры письменной и устной речи как психологических механизмов учебно-математического интеллекта.

3) Воспитательные задачи : продолжить личностное воспитание у студентов познавательного интереса к математике, ответственности, чувства долга, академической самостоятельности, коммуникативного умения сотрудничать с группой, преподавателем, согруппниками; аутогогической способности к соревновательной учебно-математической деятельности , стремления к высоким и высшим ее результатам (акмеический мотив).

Тип урока : изучение нового материала; по критерию ведущего математического содержания - урок-практикум; по критерию типа информационного взаимодействия учащихся и преподавателя – урок сотрудничества.

Оборудование урока:

1. Учебная литература:

1) Кудрявцев математического анализа: Учеб. для студентов университетов и вузов. В 3 т. Т. 3. – 2-е изд., перераб. и доп. – М.: Высш. шк., 1989. – 352 с. : ил.

2) Демидович задач и упражнений по математическому анализу. – 9-е изд. – М.: Издательство «Наука», 1977.

2. Иллюстрации.

Ход урока .

1.Объявление темы и главной образовательной цели урока; стимулирование чувства долга, ответственности, познавательного интереса студентов при подготовке к сессии .

2.Повторение материала по вопросам.

a) Дать определение функции.

Одним из основных математических понятий является понятие функции. Понятие функции связано с установлением зависимости между элементами двух множеств.

Пусть даны два непустых множества и . Соответствие f, которое каждому элементу сопоставляет один и только один элемент , называется функцией и записывается y = f(x). Говорят еще, что функция f отображает множество на множество .

https://pandia.ru/text/79/018/images/image003_18.gif" width="63" height="27">.gif" width="59" height="26"> называется множеством значений функции f и обозначается E(f).

б) Числовые функции. График функции. Способы задания функций.

Пусть задана функция .

Если элементами множеств и являются действительные числа, то функцию f называют числовой функцией . Переменная x при этом называется аргументом или независимой переменной, а y – функцией или зависимой переменной (от x). Относительно самих величин x и y говорят, что они находятся в функциональной зависимости .

Графиком функции y = f(x) называется множество всех точек плоскости Oxy, для каждой из которых x является значением аргумента, а y – соответствующим значением функции.

Чтобы задать функцию y = f(x), необходимо указать правило, позволяющее, зная x, находить соответствующее значение y.

Наиболее часто встречаются три способа задания функции: аналитический, табличный, графический.

Аналитический способ : функция задается в виде одной или нескольких формул или уравнений.

Например:

Если область определения функции y = f(x) не указана, то предполагается, что она совпадает с множеством всех значений аргумента, при которых соответствующая формула имеет смысл.

Аналитический способ задания функции является наиболее совершенным, так как к нему приложены методы математического анализа, позволяющие полностью исследовать функцию y = f(x).

Графический способ : задается график функции.

Преимуществом графического задания является его наглядность, недостатком – его неточность.

Табличный способ : функция задается таблицей ряда значений аргумента и соответствующих значений функции. Например, известные таблицы значений тригонометрических функций, логарифмические таблицы.

в) Основные характеристики функции.

1. Функция y = f(x),определенная на множестве D, называется четной , если выполняются условия и f(-x) = f(x); нечетной , если выполняются условия и f(-x) = -f(x).

График четной функции симметричен относительно оси Oy, а нечетной – относительно начала координат. Например, – четные функции; а y = sinx, https://pandia.ru/text/79/018/images/image014_3.gif" width="73" height="29"> – функции общего вида, т. е. не четные и не нечетные.

2.Пусть функция y = f(x) определена на множестве D и пусть . Если для любых значений аргументов из неравенства вытекает неравенство: , то функция называется возрастающей на множестве ; если , то функция называется неубывающей на https://pandia.ru/text/79/018/images/image021_1.gif" width="117" height="28 src=">то функция наз. убывающей на ; - невозрастающей .

Возрастающие, невозрастающие, убывающие и неубывающие функции на множестве https://pandia.ru/text/79/018/images/image023_0.gif" width="13" height="13">D значение (x+T)D и выполняется равенство f(x+T) = f(x).

Для построения графика периодической функции периода T достаточно построить его на любом отрезке длины T и периодически продолжить его во всю область определения.

Отметим основные свойства периодической функции.

1) Алгебраическая сумма периодических функций, имеющих один и тот же период T, есть периодическая функция с периодом T.

2) Если функция f(x) имеет период T, то функция f(ax) имеет период T/a.

г) Обратная функция.

Пусть задана функция y = f(x) с областью определения D и множеством значений E..gif" width="48" height="22">, то определена функция x = z(y) с областью определения E и множеством значений D. Такая функция z(y) называется обратной к функции f(x) и записывается в следующем виде: . Про функции y = f(x) и x = z(y) говорят, что они являются взаимно обратными. Чтобы найти функцию x = z(y), обратную к функции y = f(x), достаточно решить уравнение f(x) = y относительно x.

Примеры :

1. Для функции y = 2x обратной функцией является функция x = ½ y;

2. Для функции обратной функцией является функция .

Из определения обратной функции вытекает, что функция y = f(x) имеет обратную тогда и только тогда, когда f(x) задает взаимно однозначное соответствие между множествами D и E. Отсюда следует, что любая строго монотонная функция имеет обратную . При этом, если функция возрастает (убывает), то обратная функция также возрастает (убывает).

3. Изучение нового материала.

Сложная функция.

Пусть функция y = f(u) определена на множестве D, а функция u = z(x) на множестве , причем для соответствующее значение . Тогда на множестве определена функция u = f(z(x)), которая называется сложной функцией от x (или суперпозицией заданных функций, или функцией от функции ).

Переменную u = z(x) называют промежуточным аргументом сложной функции.

Например, функция y = sin2x есть суперпозиция двух функций y = sinu и u = 2x. Сложная функция может иметь несколько промежуточных аргументов.

4. Решение нескольких примеров у доски.

5. Заключение урока.

1) теоретико-прикладные итоги практического занятия; дифференцированная оценка уровня ментального опыта учащихся; уровня усвоения ими темы, компетентности, качества устной и письменной математической речи; уровня проявленного творчества; уровня самостоятельности и рефлексии; уровня инициативы, познавательного интереса к отдельным методам математического мышления; уровней сотрудничества, интеллектуальной состязательности, стремления к высоким показателям учебно-математической деятельности и др.;

2) объявление аргументированных отметок, поурочного балла.

Пусть имеется некоторый набор K , состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называются новые функции, полученные с помощью конечного числа применения двух операций;

можно переименовать любую переменную, входящую в функцию из K ;

вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию.

Суперпозицию еще иначе называют сложной функцией.

Пример 7. 1. Если дана одна функция х |y (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x , x| (x|y ), x| (y|z ) и т. д.

Замыканием набора функций из K называется множество всех суперпозиций. Класс функций K называется замкнутым , если его замыкание совпадает с ним самим.

Набор функций называется полным , если его замыкание совпадает со всеми логическими функциями. Иначе говоря, полный набор - это множество таких функций, через которые можно выразить все остальные булевы функции.

Неизбыточный полный набор функций называется базисом (“неизбыточный” означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным).

Пример 7.2. Конъюнкция, дизъюнкция и отрицание являются полным набором (в этом убедились в разд. 5), но не являются базисом, так как это набор избыточен, поскольку с помощью правил де Моргана можно удалить конъюнкцию или дизъюнкцию. Любую функцию можно представить в виде полинома Жегалкина (разд. 6). Ясно, что функции конъюнкция, сложение по модулю 2 и константы 0 и 1 являются полным набором, но эти четыре функции также не являются базисом, поскольку 1+1=0, и поэтому константу 0 можно исключить из полного набора (для построения полиномов Жегалкина константа 0 необходима, поскольку выражение “1+1” не является полиномом Жегалкина).

Легко видеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание.

Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна). Такие функции называются шефферовскими функциями. Это название связано с тем, что штрих Шеффера является базисом. Напомним, что штрих Шеффера определяется следующей таблицей истинности:

Так как очевидно , т. е. отрицание является суперпозицией штриха Шеффера, а дизъюнкция тогда , штрих Шеффера сам является базисом. Аналогично, стрелка Пирса является шефферовской функцией (студенты могут проверить это сами). Для функций 3-х или более переменных шефферовских функций очень много (конечно, выражение других булевых функций через шефферовскую функцию большого числа переменных сложно, поэтому в технике они редко используются).

Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах). Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции.

Перейдем теперь к выяснению полноты конкретных наборов функций. Для этого перечислим 5 важнейших классов функций:

• Т 0 - это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т 0 - это класс функций, сохраняющих 0);
• Т 1 - это набор всех логических функций, которые на единичном наборе принимают значение 1 (Т 1 - это класс функций, сохраняющих единицу ) (заметим, что число функций от п переменных принадлежащих классам Т 0 и Т 1 равно 2 2n-1);
• L - класс линейных функций т. е. функций, для которых полином Жегалкина содержит только первые степени переменных;
• М - класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 2 набора из п переменных: s1 = (x 1 , x 2 ,..., x n)

s 1 = (х 1 , х 2 , … , х п ) и s 2 = (y 1 , y 2, … , y п) . Будем говорить, что набор s 1 меньше набора s 2 (s 1 £ s 2 ), если все х i £ y i . Очевидно, что не все наборы из п переменных сравнимы между собой (например, при п = 2 наборы (0,1) и (1,0) не сравнимы между собой). Функция от п переменных называется монотонной , если на меньшем наборе она принимает меньшее или равное значение. Разумеется, эти неравенства должны проверяться только на сравнимых наборах. Понятно, что несравнимые наборы - это те, в которых есть некоторые координаты типа (0,1) в одном наборе и (1,0) в другом на соответствующих местах (в дискретной математике монотонные функции это только как бы “монотонно возрастающие функции”, “монотонно убывающие” функции здесь не рассматриваются).

Пример. В нижеследующей таблице функции f 1 , f 2 являются монотонными функциями, а функции f 3 , f 4 - нет.

Естественный порядок переменных обеспечивает тот факт, что если какой-то набор меньше другого набора, то он обязательно расположен в таблице истинности выше “большего” набора. Поэтому если в таблице истинности () вверху стоят нули , а затем единицы , то эта функция точно является монотонной . Однако возможны инверсии, т. е. единица стоит до каких-то нулей , но функция является все равно монотонной (в этом случае наборы, соответствующие “верхней” единице и “нижнему” нулю должны быть несравнимы ; можно проверить, что функция, задаваемая таблицей истинности при естественном порядке набора переменных (00010101), является монотонной);

Теорема . Классы функций Т 0 , Т 1 , L , M , S замкнуты .

Это утверждение следует непосредственно из определения самих этих классов, а также из определения замкнутости.

В теории булевых функций очень большое значение имеет следующая теорема Поста.

Теорема Поста . Для того чтобы некоторый набор функций K был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классов T 0 , T 1 , L , M , S .

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным.

Достаточность этого утверждения доказывается довольно сложно, поэтому здесь не приводится.

Из этой теоремы следует довольно простой способ выяснения полноты некоторого набора функций. Для каждой из этих функций выясняется принадлежность к перечисленным выше классам. Результаты заносятся в так называемую таблицу Поста (в нашем примере эта таблица составлена для 4-х функций, причем знаком “+” отмечается принадлежность функции соответствующему классу, знак “-” означает, что функция в него не входит).

В соответствии с теоремой Поста набор функций будет полным тогда и только тогда, когда в каждом столбце таблицы Поста имеется хотя бы один минус. Таким образом, из приведенной таблицы следует, что данные 4 функции образуют полный набор, но эти функции не являются базисом. Из этих функций можно образовать 2 базиса: f 3 , f 1 и f 3 , f 2 . Полными наборами будут любые наборы содержащие, какой-либо базис.

Непосредственно из таблицы Поста следует, что число базисных функций не может быть больше 5. Нетрудно доказать, что на самом деле это число меньше или равно 4.

Функция f, получаемая из функций f 1 , f 2 ,…f n с помощью операций подстановки и переименования аргументов, называется суперпозицией функций.

Всякая формула, выражающая функцию f как суперпозицию других функций, задаёт способ её вычисления, т. е. формулу можно вычислить, если вычислены значения всех её подформул. Значение подформулы можно вычислить по известному набору значений двоичных переменных.

По каждой формуле можно восстановить таблицу логической функции, но не наоборот, т.к. каждой логической функции можно представить несколько формул в различных базисах

Формулы F i и F j представляющие одну и ту же логическую функцию f i, называются эквивалентными . Так, эквивалентными формулами являются:

1. f 2 (x 1 ; x 2)=(x 1 ×`x 2)=ù(`x 1 Úx 2)= ù(x 1 ®x 2);

2. f 6 (x 1 ; x 2)=(`x 1 ×x 2 Úx 1 ×`x 2)= ù(x 1 «x 2)=(x 1 Åx 2);

3. f 8 (x 1 ; x 2)=(`x 1 ×`x 2)= ù(x 1 Úx 2)=(x 1 ¯x 2);

4. f 14 (x 1 ;x 2)=(`x 1 Ú`x 2)= ù(x 1 ×x 2)=x 1 ½x 2 ;

5. f 9 (x 1 ;x 2)=((`x 1 ×`x 2)Ú(x 1 ×x 2))=(x 1 «x 2) ;

6. f 13 (x 1 ;x 2)= (`x 1 Úx 2)=(x 1 ®x 2).

Если какая-либо формула F содержит подформулу F i , то замена F i на эквивалентную F j не изменяет значения формулы F при любом наборе булевого вектора, но изменяет форму её описания. Вновь полученная формула F` эквивалентна формуле F.

Для упрощения сложных алгебраических выражений булевой функции выполняют эквивалентные преобразования , используя законы булевой алгебры и правила подстановки и замещения ,

При написании формул булевой алгебры следует помнить:

· число левых скобок равно числу правых скобок,

· нет двух рядом стоящих логических связок, т. е. между ними должна быть формула,

· нет двух рядом стоящих формул, т. е. между ними должна быть логическая связка,

· логическая связка “×” сильнее логической связки “Ú”,

· если “ù ” относится к формуле (F 1 ×F 2) или (F 1 Ú F 2), то прежде всего следует выполнить эти преобразования по закону де Моргана: ù(F 1 ×F 2)=`F 1 Ú`F 2 или ù(F 1 ÚF 2)=`F 1 ×`F 2 ;

· операция “× ” сильнее “Ú”, что позволяет опускать скобки.

Пример : выполнить эквивалентные преобразования формулы F=x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 .

· по закону коммутативности:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×`x 2 Úx 3 ×x 4 ;

· по закону дистрибутивности:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×(`x 2 Úx 4);

· по закону дистрибутивности:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×(`x 1 Ú`x 2 Úx 4);

· по закону дистрибутивности:

F=x 3 ×((x 1 ×x 2 ×`x 4)Ú(`x 1 Ú`x 2 Úx 4));

· по закону де Моргана:

F=x 3 ×((x 1 ×x 2 ×`x 4)Úù(x 1 ×x 2 ×`x 4));

· по закону противоречия:

Таким образом x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 =x 3 .

Пример: выполнить преобразования формулы

F=(x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2);

· по закону де Моргана

F=(x 1 ×`x 2 Ú`x 1 ×x 2)×(`x 1 Ú`x 2)Ú(x 1 ×x 2)×(`x 1 Úx 2)×(x 1 Ú`x 2);

· по закону дистрибутивности:

F=x 1 ×`x 2 Ú`x 1 ×x 2 Úx 1 ×x 2 ;

· по законам коммутативности и дистрибутивности:

F= `x 1 ×x 2 Úx 1 ×(`x 2 Úx 2);

· по закону противоречия:

F= `x 1 ×x 2 Úx 1 ;

· по закону Порецкого

Таким образом (x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2)= (x 2 Úx 1).

Пример: выполнить преобразование формулы F=ù(`x 1 Úx 2)Ú((`x 1 Úx 3)×x 2).

· по закону де Моргана:

F= ù(`x 1 Úx 2)×ù((`x 1 Úx 3)×x 2);

· по закону де Моргана:

F=x 1 ×`x 2 ×(ù(`x 1 Úx 3)Ú`x 2);

· по закону де Моргана:

F=x 1 ×`x 2 ×(x 1 ×`x 3 Ú`x 2);

· по закону дистрибутивности:

F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ;

· по закону поглощения:

Таким образом ù(`x 1 Úx 2)×((`x 1 Úx 3)×x 2)= x 1 ×`x 2 .

Пример : выполнить преобразование формулы:

F=ù(x 1 ®x 2)×(`x 3 Ú`x 4)Ú(x 1 ¯x 2)×ù(x 3 ×x 4).

1) преобразовать формулу в базис булевой алгебры:

F=ù(`x 1 Úx 2)×(`x 3 Ú`x 4)Úù(x 1 Úx 2)× ù(x 3 ×x 4);

2) опустить знак “` “ до двоичных переменных:

F=(x 1 ×`x 2)×(`x 3 Ú`x 4)Ú(`x 1 ×`x 2)×(`x 3 Ú`x 4);

3) преобразовать формулу по закону дистрибутивности:

F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ×`x 4 Ú`x 1 ×`x 2 ×`x 3 Ú`x 1 ×`x 2 ×`x 4 ;

4) вынести за скобку `x 2 по закону дистрибутивности:

F=`x 2 ×(x 1 ×`x 3 Úx 1 ×`x 4 Ú`x 1 ×`x 3 Ú`x 1 ×`x 4);

5) преобразовать по закону дистрибутивности:

F=`x 2 ×(`x 3 ×(x 1 Ú`x 1)Ú`x 4 ×(x 1 Ú`x 1));

6) использовать закон противоречия:

F=`x 2 ×(`x 3 Ú`x 4)

Свойства булевых функций

Часто возникает вопрос: всякая ли булева функция представима суперпозицией формул f 0 , f 1 ,..f 15 ? Для того, чтобы определить возможность формирования любой булевой функции с помощью суперпозиции этих формул, необходимо определить их свойства и условия использования функционально полной системы.

Самодвойственные булевы функции

самодвойственной , если f(x 1 ;x 2 ;…x n)=`f(`x 1 ;`x 2 ;…`x n).

Например, функции f 3 (x 1 ;x 2)=x 1 , f 5 (x 1 ;x 2)=x 2 , f 10 (x 1 ;x 2)=`x 2 и f 12 (x 1 ;x 2)=`x 1 являются самодвойственными, т. к. при изменении значения аргумента они изменяют свое значение.

Любая функция, полученная с помощью операций суперпозиции из самодвойственных булевых функций, сама является самодвойственной. Поэтому множество самодвойственных булевых функций не позволяет формировать не самодвойственные функции.

Монотонные булевы функции

Функция f(x 1 ; x 2 ;…x n) называется монотонной , если для каждого s 1i £s 2i булевых векторов (s 11 ; s 12 ;……;s 1n) и (s 21 ;s 22 ;……;s 2n) выполняется условие: f(s 11 ;s 12 ;…;s 1i ;…;s 1n)£f(s 21 ;s 22 ;…;s 2i ;…;s 2n).

Например, для функций f(x 1 ; x 2) монотонными функциями являются:

если (0; 0)£(0; 1), то f(0; 0)£f(0; 1),

если (0; 0)£(1; 0), то f(0; 0)£f(1; 0),

если (0; 1)£(1; 1), то f(0; 1)£f(1; 1),

если (1; 0)£(1; 1), то f(1; 0)£f(1; 1).

Таким условиям удовлетворяют следующие функции:

f 0 (x 1 ; x 2)=0; f 1 (x 1 ; x 2)=(x 1 ×x 2); f 3 (x 1 ; x 2)=x 1 ; f 5 (x 1 ; x 2)=x 2 ; f 7 (x 1 ;x 2)=(x 1 Úx 2); f 15 (x 1 ; x 2)=1.

Любая функция, полученная с помощью операции суперпозиции из монотонных булевых функций, сама является монотонной. Поэтому множество монотонных функций не позволяет формировать не монотонные функции.

Линейные булевы функции

Алгебра Жегалкина, опирающаяся на базис F 4 ={×; Å; 1}, позволяет любую логическую функцию представить полиномом, каждый член которого есть конъюнкция I булевых переменных булевого вектора в пределах 0£i£n:

P(x 1 ; x 2 ;…x n)=b 0 ×1 Å b i ×x i Å 1 £ j ¹ k £ n b j ×x j ×x k Å……Å b 2n-1 ×x 1 ×x 2 ×...×x n.

Например, для логических функций f 8 (x 1 ; x 2)

полином Жегалкина имеет вид: P(x 1 ; x 2)=1Å x 1 Å x 2 Å x 1 ×x 2 .

Преимущества алгебры Жегалкина состоят в “арифметизации” логических формул, а недостатки - в сложности, особенно при большом числе двоичных переменных.

Полиномы Жегалкина, не содержащие конъюнкции двоичных переменных, т.е. P(x 1 ; x 2 ;…;x n)=b 0 ×1Åb 1 ×x 1 Å…Åb n ×x n называют линейными .

Например, f 9 (x 1 ; x 2)=1Åx 1 Åx 2 , или f 12 (x 1 ;x 2)=1Åx 1 .

Основные свойства операции сложения по модулю 2 приведены в таблице 1.18.

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

коэффициенты b i полинома Жегалкина, составив систему уравнений по всем известным наборам двоичных переменных.

Пример : дана булева функция f(x 1 ;x 2)=x 1 Úx 2 . Значение этой функции известны для всех наборов булевых переменных.

F(0;0)=0=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;

f(1;0)=1=b 0 ×1Å b 1 ×1Å b 2 ×0Å b 3 ×1×0;

f(1;1)=1=b 0 ×1Å b 1 ×1Å b 2 ×1Å b 3 ×1×1;

Откуда находим b 0 =0; b 1 =1; b 2 =1; b 3 =1.

Следовательно, (x 1 Úx 2)=x 1 Åx 2 Åx 1 ×x 2 , т. е. дизъюнкция есть нелинейная булева функция.

Пример : дана булева функция f(x 1 ;x 2)=(x 1 ®x 2). Значение этой функции также известны для всех наборов двоичных переменных.

F(0;0)=1=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;

f(0;1)=1=b 0 ×1Å b 1 ×0 Å b 2 ×1Å b 3 ×0×1;

f(1;0)=0=b 0 ×1Åb 1 ×1Åb 2 ×0Åb 3 ×1×0;

f(1;1)=1=b 0 ×1Åb 1 ×1Åb 2 ×1Åb 3 ×1×1;

Откуда находим b 0 =1; b 1 =1; b 2 =0; b 3 =1.

Следовательно, (x 1 ®x 2)=1Å x 2 Å x 1 ×x 2 .

В таблице 1.19 приведены полиномы Жегалкина для основных представителей булевых функций из таблицы 1.15.

Если дано аналитическое выражение логической функции и неизвестны ее значения для различных наборов двоичных переменных, то можно построить полином Жегалкина, опираясь на конъюнктивный базис алгебры Буля F 2 ={` ; ×}:

Пусть f(x 1 ; x 2)=(x 1 Úx 2).

Тогда (x 1 Úx 2)=ù(`x 1 ×`x 2)=((x 1 Å 1)×(x 2 Å 1))Å 1=x 1 ×x 2 Å x 1 ×1Å x 2 ×1Å 1×1Å1=

(x 1 Åx 2 Åx 1 ×x 2).

Пусть f(x 1 ;x 2)=(x 1 ®x 2).

Тогда (x 1 ®x 2)=(`x 1 Úx 2)=ù(x 1 ×`x 2)=x 1 ×(x 2 Å 1)Å 1=x 1 ×x 2 Å x 1 ×1Å 1= =(1Åx 1 Åx 1 ×x 2).

Пусть f(x 1 ;x 2)=(x 1 «x 2).

Тогда (x 1 «x 2)=(`x 1 ×`x 2 Úx 1 ×x 2)=ù(ù(`x 1 ×`x 2)×ù(x 1 ×x 2))=(((x 1 Å1)×(x 2 Å1))Å1)× ×(x 1 ×x 2 Å)Å1=(x 1 ×x 2 Åx 1 Åx 2 Å1Å1)×(x 1 ×x 2 Å1)Å1=x 1 ×x 2 Åx 1 ×x 2 Åx 1 ×x 2 Åx 1 Å

x 1 ×x 2 Åx 2 Å1=(1Åx 1 Åx 2).

Любая функция, полученная с помощью операции суперпозиции из линейных логических функций, сама является линейной. Поэтому множество линейных функций не позволяет формировать нелинейные функции.

1.5.6.4. Функции, сохраняющие “0”

Функция f(x 1 ; x 2 ;...x n) называется сохраняющей “0”, если для наборов значений двоичных переменных (0; 0;...0) функция принимает значение f(0; 0;…0)=0.

Например, f 0 (0; 0)=0, f 3 (0; 0)=0, f 7 (0; 0)=0 и др.

Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “0”, сама является функцией, сохраняющей “0” Поэтому множество функций, сохраняющих “0”, не позволяет формировать функции, не сохраняющие “0”.

1.5.6.5. Функции, сохраняющие “1”

Функция f(x 1 ; x 2 ;…x n) называется сохраняющей “1”, если для наборов значений двоичных переменных (1; 1;…1) функция принимает значение f(1;1;…1)=1.

Например, f 1 (1; 1)=1, f3(1; 1)=1, f 5 (1; 1)=1 и др.

Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “1”, сама является сохраняющей “1”. Поэтому множество функций, сохраняющих “1”, не позволяет формировать функции, не сохраняющие “1”.