Повторить краткие теоретические сведения и разобрать задачи с решениями.

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

Функции, сохраняющие константу 0 или 1;

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

Монотонные функции;

Линейные функция.

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

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

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

-Хотя бы одна функция, не сохраняющая 0.

-Хотя бы одна функция, не сохраняющая 1.

-Хотя бы одна нелинейная функция.

-Хотя бы одна немонотонная функция.

-Хотя бы одна несамодвойственная функция.

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

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

Обозначим через T₀ класс всех булевых функций f(x₁,x₂,...,x_n), сохраняющих константу 0, то есть функций, для которых выполнено равенство f(0,0,...,0)=0. Очевидно, что функции 0, x, x₁& x₂, x₁Ú x₂, x₁Å x₂ принадлежат классу T₀, а функции 1, , x₁® x₂ в него не входят.

Поскольку таблица для функций f(x₁,x₂,...,x_n) из класса T₀в первой строке содержит фиксированное значение 0, то в T₀ попадает функций, т.е. ровно половина всех булевых функций.

Покажем, что T₀ - замкнутый класс. Так как он содержит тождественную функцию, то для обоснования его замкнутости достаточно показать, что функция Ф=f(f₁,...,f_m) принадлежит классу T₀, если только f, f₁,..., f_m принадлежат этому классу.

Ф(0,0,...,0)= f(f₁(0,0,...,0),...,f_m(0,0,...,0))= f(0,0,...,0)=0.

Класс функций, сохраняющих константу 1

Обозначим через T₁ класс всех булевых функций f(x₁,x₂,...,x_n), сохраняющих константу 1, то есть функций, для которых выполнено равенство f(1,1,...,1)=1. Этому классу принадлежат функции 1, x, x₁& x₂, x₁Ú x₂, x₁® x₂ и не принадлежат функции 1, , x₁Åx₂.

Покажем, что класс T₁ состоит из функций, двойственных функциям из класса T₀ (говорят, что класс T₁ двойственен классу T₀).

Пусть f(x₁,x₂,...,x_n) принадлежит T₁, т.е. выполняется равенство f(1,1,...,1)=1. Тогда, воспользовавшись определением двойственной функции, получим: f*(0,0,...,0)= ( , ,..., )= (1,1,...,1)=0. Это значит, что f*(x₁,x₂,...,x_n) принадлежит классу T₀.

Из взаимной двойственности классов T₀ и T₁ следует, что T₁ также является замкнутым классом и что он содержит столько же булевых функций, что и класс T₀.

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

Класс S включает в себя все самодвойственные функции, то есть такие функции, для которых выполняется равенство: f(x₁,x₂,...,x_n)=f*(x₁,x₂,...,x_n). Очевидно, что функции x и самодвойственные (см. табл. 1.7). Менее тривиальным примером самодвойственной функции является функция h(x₁,x₂,x₃)=x₁x₂Ú x₁x₃Ú x₂x₃. Покажем, что это действительно так.

Составим двойственную к функцию * и преобразуем ее:

h*(x₁,x₂,x₃) = (x₁Úx₂) & (x₁Úx₃) & (x₂Úx₃) = (x₁Úx₂x₃) & (x₂Úx₃) = x₁x₂Ú x₁x₃Ú x₂x₃ = h(x₁,x₂,x₃).

Для самодвойственной функции имеет место тождество: f(x₁,...,x_n); иначе говоря, на наборах (a₁,...,a_n) и , которые называются противоположными, самодвойственная функция принимает противоположные значения.

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

Докажем, что класс S замкнут. Поскольку он содержит тождественную функцию, достаточно показать, что функция Ф=f(f₁,...,f_m) является самодвойственной, если функции f, f₁,..., f_m самодвойственны. Последнее устанавливается непосредственно:

Ф*= f*(f₁*,...,f_m*)= f*(f₁,...,f_m)= f(f₁,...,f_m)= Ф.

Класс монотонных функций

Для двух наборов =(a₁,...,a_n) и =(b₁,..., b_n), выполнено отношение предшествования , если a₁£b₁, ..., a_n£b_nи хотя бы в одной координате i выполнено условие a_i < b_i.

Пример. (0, 1, 0, 1) (1, 1, 0, 1), а наборы (0, 1) и (1, 0) не сравнимы.

Очевидно, что отношение предшествования рефлексивно, антисимметрично, транзитивно и представляет собой, таким образом, отношение частичного порядка на множестве Bⁿ=B´B´...´B.

Функция f(x₁,...,x_n) называется монотонной, если для любых двух наборов и таких, что , имеет место неравенство: f( )£f( ).

Например, функции 0, 1, x, x₁&x₂, x₁Ú x₂ монотонные, а функции , x₁® x₂, x₁Åx₂ монотонными не являются.

Обозначим через M множество всех монотонных функций. Покажем, что класс монотонных функций замкнут. Поскольку тождественная функция принадлежит множеству M, то достаточно показать, что функция Ф=f(f₁,...,f_m) является монотонной, если функции f, f₁,..., f_m монотонны.

Пусть и - два набора длины n значений переменных x₁,...,x_n, причем . Так как функции f₁,..., f_m монотонны, то выполняются соотношения f_i( )£f_i( ) при 1 £ i £ m, , поэтому набор (f₁( ),..., f_m( )) предшествует набору (f₁( ),..., f_m( )) или эти наборы равны.

В обоих случаях в силу монотонности функции f справедливо неравенство:

f (f₁( ),..., f_m( )) £ f (f₁( ),..., f_m( )),

откуда следует, что Ф ( ) £ Ф ( ), т.е. Ф - функция монотонная.

Наборы и называются соседними по i-й координате, если

=(a₁,..., a _i_-1, a _i, a _i₊₁,... a _n), = (a₁,..., a _i_-1, , a _i₊₁,... a _n).

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

Он содержит функции 0, 1, x, , x₁Åx₂ и не содержит функций x₁&x₂ и x₁Ú x₂. Выше было показано, что этот класс также замкнут.

Таблица 1 не содержит двух одинаковых столбцов. Это хорошо иллюстрирует тот факт, что замкнутые классы T₀, T₁, S, M и L попарно различны (знак “+” здесь показывает, что функция содержится в классе, а “-” обозначает обратную ситуацию).

Таблица 1

f	T₀	T₁	S	M	L
0	+	-	-	+	+
1	-	+	-	+	+
x	+	+	+	+	+
	-	-	+	-	+
x₁&x₂	+	+	-	+	-
x₁Ú x₂	+	+	-	+	-

Система функций {f₁, f₂,..., f_k} называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

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

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

Каждая функция из P₂ может быть выражена при помощи полинома по модулю 2.

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

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

Пример. x | y = Ú = = (xy) Å

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

Контрольные вопросы.

1. Какие существуют классы Поста?

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

Задания.

Определить к каким классам Поста относятся булевы функции:

1в.