1. Приведем доказательство включения [KÇL]Í[K]Ç[L]. Пусть {M_i½iÎI}

– семейство замкнутых классов, содержащих KÇL, {K_j½jÎJ} – семейство замкнутых классов, содержащих K. Тогда, поскольку KÇLÍK, то все K_j содержат KÇL, т.е.

{K_j½jÎJ}Í{M_i½iÎI}.

Отсюда следует, что Ç{K_j½jÎJ}ÊÇ{M_i½iÎI}. Это означает, что [KÇL]Í[K]. Аналогично доказывается включение [KÇL]Í[L]. Следовательно, [KÇL]Í[K]Ç[L].

2. Приведем решение задачи. Пусть K={i(x), xy, xÚy}. Функции q(x) и

n(x) не принадлежат [K], поскольку все функции из K (а следовательно, и из [K]) сохраняют единицу, а функции q(x) и n(x) единицу не сохраняют.

3. Указание. Построить таблицу, задающую функции двойственную к

f функцию и функцию g. В случаях а, в, д и е ответ положительный, в остальных случаях – отрицательный.

4. Указание. Построить таблицу, задающую функцию f и двойственную к ней. Функции n(x), (xy)Ú(xz)Ú(yz) и (xÚy)×(xÚz)×(yÚz) самодвойственны (последние две просто равны), остальные нет.

5. Указание. Рассмотреть таблицы, задающие функции, существенно зависящие от двух переменных.

6. Указание. Проставить значения функций в вершинах диаграммы

частично упорядоченного множества B³.

7. Монотонными являются функции xy+y+x, x®(y®x), (xy)Ú(xz)Ú(yz).

9. Приведем решение задачи. Класс функций {q(x), i(x), xy, xÚy}.обозначим буквой С. Пусть f(x₁,…,x_n) – монотонная функция. Если f(x₁,…,x_n) тождественно равна 0, то f(x₁,…,x_n)=q(x₁)×…×q(x_n). Если же эта функция тождественно равна 1, то f(x₁,…,x_n)=i(x₁)×…×i(x_n). Следовательно, в этих двух случаях функция f принадлежит [C]. Будем считать, что f(x₁,…,x_n) принимает оба значения. Рассмотрим диаграмму Bⁿ частично упорядоченного множества Bⁿ и в вершинах диаграммы проставим значения функции f(x₁,…,x_n). Поскольку функция f монотонна, то из того, что в некоторой вершине функция f принимает значение 1, то и всюду выше она принимает то же значение. (В частности, в нижней вершине диаграмма f принимает значение 0, в верхней – значение 1.) Отсюда следует, что существуют вершины диаграммы a¹, a²,…,a^k такие, что если f(b)=1 для некоторой вершины b, то aⁱ£b для некоторого iÎ{1,…,k}.

Рис. 2.3

Другими словами, {aÎBⁿ½f(a)=1}=D₁ÈD₂È…ÈD_k, где D_i={aÎBⁿ½aⁱ£a} (см. рис. 2.3).

Рассмотрим вектор a¹. Пусть у этого вектора единицы стоят на местах i₁ , i₂,…,i_l. Для упрощения обозначений предположим, что i₁=1,…, i_l=l. Пусть g₁(x₁,…,x_n)=x₁×x₂×…×x_l. Легко видеть, что D₁={aÎBⁿ½g₁(a)=1}. Аналогичным образом существование функций g₂(x₁,…,x_n),…, g_l(x₁,…,x_n), таких, что D₂={aÎBⁿ½g₂(a)=1},…, D_l={aÎBⁿ½g_l(a)=1}. Тогда поскольку множество {aÎBⁿ½f(a)=1} есть объединение D₁È…ÈD_k, получаем равенство:

f(x₁,…,x_n)=g₁(x₁,…,x_n)Ú…Úg_l(x₁,…,x_n).

Мы доказали, что замыкание класса C совпадает с М, т.е. с классом всех монотонных функций. Покажем, что С – базис М. Если из С удалить q(x) то из оставшихся функций нельзя выразить q(x), поскольку они сохраняют 1. Аналогично доказывается, что нельзя удалить i(x).

Докажем, что замыкание класса C′=C\{x×y} не содержит x×y. Предположим противное, пусть x×y выражается (с помощью суперпозиции и переименования аргументов) через функции класса C′ и пусть g(x,y) – самое короткое выражение для этой функции. (В частности это означает, что x×y=g(x,y)). Тогда g(x,y)¹q(h(x,y)), для некоторого h(x,y) поскольку в случае равенства g(x,y)=q(h(x,y)) произведение xy тождественно равно 0. Аналогично заключаем, что g(x,y)¹i(h(x,y). Следовательно, x×y=g(x,y)=g₁(x,y)Úg₂(x,y). Отсюда следует, что g₁(0,0)=g₁(1,0)=g₁(0,1)=0 и g₂(0,0)g₂(1,0)=g₂(0,1)=0, поскольку 0×0=1×0=0×1=0. Далее, так как 1=1×1=g₁(1,1)Úg₂(1,1), то g₁(1,1)=1 или g₂(1,1)=1. Это означает, что в качестве g(x,y) можно взять g₁(x,y) или g₂(x,y), что противоречит выбору функции g(x,y). Следовательно, x×y не принадлежит замыканию класса C\ {x×y}. Аналогично доказывается, что ÏxÚyÏ[C\{xÚy}].

Мы доказали, что {q(x), i(x), x×y, xÚy} – базис класса монотонных функций.

10. Указание. См. решение аналогичной задачи в начале §4.

Линейными являются все функции, кроме первой.

12. Приведем решение задачи 12 г. Пусть K={x+y, x«(yz)}. В силу теоремы Поста, надо в классе K найти функцию, не сохраняющую 0, функцию, не сохраняющую 1, не самодвойственную, немонотонную, нелинейную функцию. Функция x«(yz) не сохраняет 0, поскольку 0«(0×0)=1. Функция x+y не сохраняет 1. Она же несамодвойственна (см. таблицу 2.6) и немонотонна (см. рис. 2.4)

Таблица 2.6

Рис. 2.4

Докажем, что функция x«(y×z) нелинейная. Предположим, что x«(y×z)=a₀+a₁×x+a₂×y+a₃×z. Составим таблицу, задающую функции из левой и правой части равенства (см. таблицу 2.7).

Таблица 2.7

Полученное противоречие показывает, что x«(y×z) – нелинейная функция. (Разумеется, таблицу можно было бы ограничить первыми четырьмя строками).

13. Указание. Применить теорему Поста. В случаях г, ж, и з классы будут полными, в остальных нет.