Суперпозиция функций. Суперпозиция функций (сложная функция)

Соответствием G между множествами А и В называется подмножество . Если , то говорят, что b

соответствует а. Множество всех соответствующих элементу

Называется образом элемента а. Множество всех которым соответствует элемент , называется

прообразом элемента b .

Множество пар (Ь, а) таких, что называется обратным по

отношению к G и обозначается . Понятия образа и прообраза для

" G и взаимно обратны.

Примеры. 1) Поставим в соответствие натуральному числу п

множество действительных чисел . Образом числа 5

будет полуинтервал

(так обозначают наибольшее целое, меньшее или равное X ). Прообразом числа 5 при этом соответствии является бесконечное множество: полуинтервал .

В терминах замыкания можно дать другие определения замкнутости и полноты (эквивалентные исходным):

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:

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 .

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

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

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

Однотактные (не содержащие элементов памяти) дискретные логические устройства реализуют на выходе некоторый набор функций алгебры логики `F m = (F 1 ,F 2 ,…,F m ), которые в каждый момент времени зависят только от состояния входов устройства `х n = (x 1 ,x 2 ,…,x n ): `F m = `F m (`х n ). Практически такие устройства проектируют и изготавливают из отдельных неделимых элементов, реализующих некоторый набор (систему) {f } элементарных функций алгебры путем присоединения выходов одних элементов ко входам других.

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

1. Задана система элементарных функций {f }. Какие выходные функции F i можно получить, используя функции из {f }?

2. Задано множество выходных булевых функций {F } (в частности, равное всему множеству функций алгебры логики Р 2). Какой должна быть исходная система элементарных функций {f }, обеспечивающая возможность получения на выходе любой из функций множества {F }?

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

Определение. Рассмотрим множество логических связок {F }, соответствующее некоторой системе функций {f }. Суперпозицией над {f } называется любая функция j, которую можно реализовать формулой над {F }.

Практически суперпозицию можно представить как результат подстановки функций из {f } в качестве аргументов в функции из этого же множества.

Пример 1 . Рассмотрим систему функций {f }= {f 1 (х ) =`х, f 2 (х,у )= х &у, f 3 (х,у )= х Úу } . Подставляя в функцию f 3 (х,у ) вместо первого аргумента х функцию f 1 (х ), вместо второго - f 2 (х,у ), получим суперпозицию h (х,у )= f 3 (f 1 (х ), f 2 (х,у ))=`х Ú х & у . Физическая реализация подстановки дана на рис.1.18.

Определение. Пусть М -некоторое множество функций алгебры логики(P 2). Множество всех суперпозиций над М называется замыканием множества М и обозначается [М ]. Получение [М ]по исходному множеству М называется операцией замыкания . Множество М называется функционально замкнутым классом , если [М ] = М . Подмножество m Í M называется функционально полной системой в М , если [m ] = М .

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

Замечания. 1. Очевидно, любая система функций {f } является функционально полной в себе самой.

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

Пример 2 . Для рассмотренных ниже систем функций {f } выполнить следующие действия:

1) найти замыкание [f ],

2) выяснить, будет ли система {f } замкнутым классом,

3) найти функционально полные системы в {f }.

Решение .

I. {f }={0}. При подстановке функции {fº 0} в саму себя получаем ее же, т.е. никаких новых функций не образуется. Отсюда следует: [f ] = {f }. Рассмотренная система является функционально замкнутым классом. Функционально полная система в ней одна и равна всей {f }.

II. {f }= {0,Ø }. Подстановка Ø (Ø х )дает тождественную функцию, которая формально не расширяет исходную систему. Однако при подстановке Ø (0) получим тождественную единицу - новую функцию, которой не было в исходной системе: Ø (0)=1. Применение всех других подстановок не приводит к появлению новых функций, например: ØØ 0= 0, 0(Ø х )=0.

Таким образом, применение операции суперпозиции позволило получить более широкое по сравнению с исходным множество функций [f ]={0,Ø ,1}. Отсюда следует строгое вхождение: {f } Ì [f ]. Исходная система {f }не является функционально замкнутым классом. Кроме самой системы {f }других функционально полных систем в ней нет, поскольку в случае её сужения из одной функции f= 0 нельзя путем подстановки получить отрицание, а из одной функции отрицания нельзя получить тождественный нуль.

III. {f } = {& ,Ú ,Ø }.Замыканием данной системы является все множество функций алгебры логики P 2 , так как формулу любой из них можно представить в виде ДНФ либо КНФ, в которых используются элементарные функции {f } = {& ,Ú ,Ø}. Данный факт является конструктивным доказательством полноты рассмотренной системы функций в P 2: [f ] =P 2 .

Поскольку в P 2 содержится бесконечное множество других функций, отличных от {f } = {& ,Ú ,Ø }, то отсюда следует строгое вхождение: {f }Ì[f ]. Рассмотренная система не является функционально замкнутым классом.

Помимо самой системы функционально полными в ней будут подсистемы {f } 1 = {& ,Ø } и {f } 2 = {Ú ,Ø }. Это следует из того, что при помощи правил де Моргана функцию логического сложения Úможно выразить через {& ,Ø},а функцию логического умножения & - через {Ú, Ø}:

(х & у ) = Ø (`х Ú`у ), (х Ú у ) = Ø (х &`у ).

Других функционально полных подсистем в {f } нет.

Проверку полноты подсистемы функций {f } 1 Ì {f }во всей системе {f }можно производить путем сведения {f } 1 к другой, заведомо полной в {f }системе.

Неполноту подсистемы {f } 1 в {f }можно проверить, доказав строгое вхождение [f 1 ] Ì [f ].

Определение. Подмножество m Í M называют функциональным базисом (базисом ) системы М , если [m ] = М , а после исключения из нее любой функции множество оставшихся не полно в М .

Замечание . Базисами системы функций {f} являются все ее функционально полные подсистемы {f} 1 , которые невозможно уменьшить без потери полноты в {f} .

Пример 3 . Для всех систем, рассмотренных в Примере 2, найти базисы.

Решение .В случаях 1 и 2 функционально полными являются только сами системы и сузить их невозможно. Следовательно, они же являются и базисами.

В случае 3 есть две функционально полные в {f }подсистемы {f } 1 = {&,Ø } и {f } 2 ={Ú,Ø }, которые невозможно сократить без потери полноты. Они будут базисами системы {f } = {&,Ú,Ø}.

Определение. Пусть система {f }является замкнутым классом. Ее подмножество {f } 1 Ì {f }называют предполным классом в {f }, если {f } 1 не полно в {f } ([f 1 ] Ì [f ]), а для любой функции jиз системы{f }, не входящей в {f } 1 (jÎ{f } \ {f } 1) справедливо: [j È {f } 1 ] = [f ], т.е. прибавление jк {f } 1 делает ее полной в {f }.

Задачи

1. Проверить замкнутость множеств функций:

а) {Ø }; б) {1, Ø }; в) {(0111); (10)};г) {(11101110); (0110)};д) {(0001); (00000001); (0000000000000001); … }.

2. Проверить полноту систем функций в P 2:

а) {0,Ø }; б) {(0101) , (1010) }; в) {¯ }; г) {(0001) , (1010) }.

3. Найти замыкание системы функций и ее базис:

а) {0 , 1 , Ø }; б) {(1000) , (1010), (0101) }; в) {(0001) , (1110), (10) }; г) {(1010) , (0001), (0111) }.

1.10.2 Функции, сохраняющие константы. Классы Т 0 и Т 1

Определение. Функция f (`х n ) сохраняет 0, если f (0,..., 0) = 0. Функция f (`х n ) сохраняет 1, если f (1, ... , 1) = 1.

Множества функций n переменных, сохраняющих 0 и 1, обозначают, соответственно, Т 0 n и Т 1 n . Все множества функций алгебры логики, сохраняющих 0 и 1, обозначают Т 0 и Т 1 . Каждое из множеств Т 0 и Т 1 является замкнутым предполным классом в Р 2 .

Из элементарных функций в Т 0 и Т 1 одновременно входят, например, &и Ú. Принадлежность любой функции к классам Т 0 , Т 1 можно проверить по первому и последнему значению ее вектора значений в таблице истинности либо непосредственной подстановкой нулей и единиц в формулу при аналитическом задании функции.

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

ЗАДАЧИ

1.Проверить принадлежность к классам Т 0 и Т 1 функций:

а) обощенного сложения, б) обощенного умножения, в) констант, г) ху Ú yz , д) х ® у ® ху , е) х Å у , ж)( х 1 Å… Å х n) ® ( y 1 Å… Å y m) при n,m Î N.

2. Доказать замкнутость каждого из классов Т 0 и Т 1 .

3. Доказать, что если f (`х n ) ÏТ 0 , то из нее путем дублирующей подстановки можно получить константу 1 либо отрицание.

4. Доказать, что если f (`х n ) ÏТ 1 , то из нее путем дублирующей подстановки можно получить константу 0 либо отрицание.

5. Доказать предполноту каждого из классов Т 0 и Т 1 (например, сведением дополненной системы к {f } = {& ,Ú ,Ø }).

6. Найти мощность классов Т 0 n и Т 1 n .