Контрольная работа

Задачи

L – класс линейных функций.

S – класс самодвойственных функций.

Т0 - класс функций, сохраняющих константу 0.

Множество {1,x1Åx2} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x1 Å x2}] = {f(x1, ..., xn) = c0 Å c1x1 Å ... Å cnxn}. Действительно, по определению формулы над М, функция f(G1, x3), где f – есть сумма по модулю 2, G1 – функция х1 Å х2, будет формулой над М: f(G1, x3) = (x1 Å x2) Å x3.

Важнейшие замкнутые классы.

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

Множество функций М называется замкнутым классом, если [M]=M.

Пример:

1) P₂– замкнутый класс.

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

М – полная система, если [M] = P₂.

3) A = {f(x₁, ..., x_n)| f(1, 1, ..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g₁, ..., g_n Î A, т.е. f(1, 1, ..., 1) = 0, g₁(1, 1, ..., 1) = 0, тогда f(g₁, ..., g_n) Î [A]. Посмотрим, принадлежит ли функция f(g₁, ..., g_n) множеству А. f(g₁(1, ..., 1), g₂(1, ..., 1), ..., g_n(1, ..., 1) = f(0, ..., 0)), но f(0, ..., 0) не обязано быть равным 0. Действительно, пусть g₁(x₁, x₂) = x₁Å x₂, g₂(x) = x ÎA. Возьмем g₂(g₁(x₁, x₂)) = x₁Å x₂Î [A], g₂(g₁(1, 1)) = 1 Å 1 = 0, следовательно, g₂(g₁(x₁, x₂)) Ï A, отсюда [A] ¹ A и А – незамкнутый класс.

Важнейшие замкнутые классы в Р₂

Т₀= { f(x₁, ..., x_n | f(0, ..., 0) = 0, n = 1, 2, ...}. Покажем, что Т₀ является собственным подмножеством Р₂, т.е. Т₀¹ Æ и Т₀Ì Р (не совпадает с Р₂). Для этого достаточно привести примеры функций, входящих в Т₀, и примеры функций из Р₂, не входящих в Т₀: x₁&x₂, x₁Úx₂, xÎТ₀и x₁|x₂, x₁x₂, ÏТ₀. Покажем далее, что [Т₀] = Т₀. Вложение Т₀Í [ Т₀] очевидно, так как по определению формулы любая функция из Т₀ является формулой над Т₀ и, следовательно, принадлежит [Т₀]. Покажем, что [Т₀]Í Т₀. Для этого надо показать, что Ф = f(f₁, ..., f_m) Î [ Т₀], если все функции f, f₁, f₂, f₃, ..., f_m Î Т₀. Надо заметить, что в формуле в качестве функции f₁ могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т₀, поэтому достаточно показать, что Ф = f (f₁, ..., f_m) Î Т₀. Для этого рассмотрим следующую функцию: Ф(0, ..., 0) = f (f₁(0, ..., 0), f₂(0, ..., 0), ...) = f(0, ..., 0) = 0.

Число функций, зависящих от n переменных и принадлежащих Т₀, будет равно

2)T₁– класс функций, сохраняющих константу 1.

T₁= {f(x₁, ...) |f(1, 1, ...) = 1}; x₁&x₂, x₁Úx₂, xÎT₁, х₁Åх₂, x₁x₂ÏT₁, следовательно Т₁– собственное подмножество Р₂.

Покажем, что [T₁] Í T₁, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т₁, можно рассмотреть Ф = f(f₁, ..., f_n) Î [T₁], где f, f₁, ..., f_n Î T₁. Найдем Ф(1, ..., 1) = f(f₁(1, ..., 1), ..., f_n(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f₁, ..., f_n) Î T₁, отсюда следует [T₁] = T₁.

S = {f(x₁, ...)|f* = f }; x, , x₁Åx₂Åx₃ÎS, x₁&x₂, x₁Úx₂, x₁Åx₂ÏS, следовательно, S – собственное подмножество Р₂. |S(n)| = . Покажем, что [S]ÍS. Ф = f(f₁, ..., f_n) Î [S], если f, f₁, ..., f_n Î S, а также, что Ф Î S. По принципу двойственности, Ф* = f*(f₁*, ..., f_n*) = f(f₁, ..., f_n) = Ф, отсюда S – замкнутый класс.

L = {f(x₁, ...)| f = c₀Åc₁x₁Å...Åc_nx_n}; очевидно, L ¹ Æ, с другой стороны

L ¹ P₂, так как x₁&x₂Ï L. Заметим, что тождественная функция принадлежит L и |L(n)| = 2ⁿ⁺¹. Покажем, что [L] Í L. Рассмотрим Ф = f(f₁, ..., f_m), где f, f₁, ..., f_n Î L. Тогда Ф = а₀Å а₁(с₁₀Å с₁₁х₁Å...Å c₁_nx_n₁) Å a₂(c₂₀Å c₂₁x₁Å c₂₂x₂Å ...Å c₂_nx_n₂)Å...Å a_n(c_m₀Åc_m₁x₁Å ... Å c_mnx_nm) = в₀Å в₁х₁Å ...Å в_nх_n Þ ФÎL.

5)М – класс монотонных функций.

Набор = (a₁, ..., a_n) предшествует набору = (b₁, ..., b_n) и обозначается , если для 1£i£n a_i£b_i, например: = (0010), = (0110), тогда . Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования () является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.

Функция f(x₁, ..., x_n) называется монотонной, если для двух наборов и , таких что , выполняется f()f(). Функции 0, 1, x, x₁&x₂, x₁ Ú x₂Î M, x₁¯x₂, x₁Å x₂, x₁~ x₂Ï M.

Для числа монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что М замкнутый класс. Рассмотрим функцию ФÎ[M], Ф = f(f₁, ..., f_m), где f, f₁, ..., f_mÎM, причем можем считать, что все они зависят от n переменных. Пусть набор = (a₁, ..., a_n), = (b₁, ..., b_n). Рассмотрим Ф(a₁, ..., a_n) = f(f₁(a₁, ..., a_n), …, f_m(a₁, ..., a_n)) и Ф(b₁, ..., b_n) = f(f₁(b₁, ..., b_n), ..., f_m(b₁, ..., b_n)). Здесь f₁(a) f₁(b), ..., f_m(a)f_m(b), тогда набор (f₁(a), ..., f_m(a))(f₁(b), ..., f_m(b)), но тогда Ф(a) Ф(b), так как fÎM, отсюда Ф = f(f₁, ..., ) – монотонная функция.

Функция f есть суперпозиция над M, если f реализуется некоторой формулой над M.

Лемма о немонотонной функции. Отрицание можно получить суперпозицией констант 0 и 1, тождественной функции и немонотонной функции.

Доказательство. Пусть f(x₁, ..., x_n) – немонотонная функция. Тогда существуют наборы и , для которых но Пусть i₁, …, i_k есть все те номера аргументов, для которых , p=1, …, k. На всех остальных аргументных местах j имеем a_j = b_j. В выражении заменим нули на местах i₁, …, i_k на x. В результате получим функцию g(x), для которой g(0) = f() = 1 и g(1) = f() = 0. Функция g(x) является отрицанием.

Классы T₀, T₁, L, S, M пересекаются, но не совпадают, что видно из следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.

T₀ T₁ L S M

x + + + + +

- - + + -

+ - + - +

- + + - +

x₁x₂ + + - - +

A={x, , 0, 1, x₁x₂) не является полной системой функций так как всегда есть функции Î Р₂ не входящие в эти классы.

1. Доказать, что пересечение любых двух замкнутых классов замкнуто.

2. Доказать, что объединение двух замкнутых классов не всегда замкнуто