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

ФУНКЦИОНАЛЬНАЯ ПОЛНОТА И ЗАМКНУТОСТЬ СИСТЕМ БУЛЕВЫХ ФУНКЦИИ

1. Полные системы булевых функций.
2. Специальные классы булевых функций. Теорема Поста.
3. Понятие базиса. Примеры базисов.

Пост Эмиль Леон (1897-1954) – америк. математик. Труды по математической логике и основаниям математики. Анализировал k-значные логики.

Введение

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

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

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

 

Вопрос 1. Полные системы булевых функций

 

О.1.1. Система булевых функций F = {f₁,f₂,…,f_n} называется полной, если любая булева функция представима в виде суперпозиции функций из этой системы.

 

Система Р₂ – множество всех булевых функций является полной.

 

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

 

Т.1.1. Пусть даны две системы булевых функций F = {f₁,f₂,…,f_n} и G = {g₁,g₂,…,g_k}, относительно которых известно, что первая система F полна, и любая из ее функций может быть выражена с помощью суперпозиции через функции второй системы G. Тогда система G так же является полной системой.

 

Т.1.2. Следующие системы булевых функций являются полными:

1) {,Ú, Ù}; 2) {, Ù}; 3) {, Ú}; 4) {, Å, Ù};

5) {1, Å, Ù}; 6) {®, }; 7) {½}; 8) {¯}.

 

Докажем, например, полноту систем 1) – 3).

 

1) Система F = {,Ú, Ù} - полна, так как любая булева функция может быть представлена в КНФ и ДНФ.

Доказательство полноты систем 2) и 3) основывается на т.1.1.

 

2) Полная система: F = {,Ú, Ù} Þ f₁ =, f₂ = Ú, f₃ = Ù.

Рассмотрим систему G₁ = {, Ù}, где g₁ =, g₂ = Ù.

Тогда f₁ = g₁, f₃ = g₂, По теореме 1.1 система G₁ = {, Ù} полна.

 

3) Аналогично доказывается полнота системы G₂ = {, Ú} с использованием т.1.1 и равносильности

 

Вопрос 2. Специальные классы булевых функций. Теорема Поста

 

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

 

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

1. Класс Р₀ – класс булевых функций, сохраняющих нуль, т.е. функций f(х₁,х₂,…,х_n), для которых f(0,0,…,0) = 0.

Пример 1.

1. Функции 0, х, x₁ Ú x₂, x₁ Ù x₂, x₁ Å x₂ÎР₀.
2. Функции

 

2. Класс Р₁ – класс булевых функций, сохраняющих единицу, т.е. функций f(х₁,х₂,…,х_n), для которых f(1,1,…,1) = 1.

Пример 2.

1. Функции 1, х, x₁ Ú x₂, x₁ Ù x₂, x₁ ® x₂, x₁ «x₂ÎР₁.
2. Функции

 

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

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

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

 

Введем отношение частичного порядка на двоичных наборах переменных х₁,х₂,…,х_n.

 

О.2.1. Если для двух двоичных наборов одинаковой длины a = (a₁,a₂,…,a_n) и b = (b₁,b₂,…,b_n) выполнены условия a₁ ≤ b₁, a₂ ≤ b₂,…, a_n ≤ b_n, то говорят, что набор a предшествует набору b и записывают a ≼ b. В этом случае наборы a и b называются сравнимыми.

При невыполнении условий определения 2.1 наборы a и b называются несравнимыми. Пронаборы разной длины так же говорят, что они несравнимы.

 

Пример 3.

1. Наборы (0,1,0,1) и (1,1,0,1) сравнимы, так как 0 < 1, 1 = 1, 0 = 0, 1 = 1.
2. Наборы (0,1,0,1) и (1,0,1,1) несравнимы, так как 0 < 1, 1 > 0, 0 < 1, 1 = 1.
3. Наборы (0,1,0,1) и (1,1,0) несравнимы, так как имеют разную длину.

 

О.2.2. Булева функция f(х₁,х₂,…,х_n) называется монотонной, если для любых двоичных наборов a и b длины n таких, что a ≼ b, имеет место неравенствоf(a) ≤ f(b).

 

Пример 4.

1. Функции 0, 1, х, x₁ Ú x₂, x₁ Ù x₂ являются монотонными (принадлежат классу М).
2. Функция x₁ ® x₂ не монотонна (не принадлежат классу М), так как f(0,0) = 1 > f(1,0) = 0.

 

Введенные классы булевых функций Р₀, Р₁, S, L, М играют главную роль при описании полных систем булевых функций.

 

Классы Р₀, Р₁, S, L, М неполные и попарно различные, так как можно привести примеры булевых функций, не принадлежащих ни одному из этих классов, и примеры булевых функций, принадлежащих одному из любых двух классов, но не принадлежащих другому.

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

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

 

Пример 5. Функционально замкнутыми классами являются:

1) класс всех булевых функций Р₂;

2) класс, содержащий только тождественные функции вида f(х) = х;

3) класс функций от одной переменной.

 

О.2.4. Функционально замкнутые классы, отличные от пустого класса и от совокупности всех булевых функций, называются собственными функционально замкнутыми классами.

 

Т.2.1. Классы Р₀, Р₁, S, L, М являются собственными функционально замкнутыми классами булевых функций.

 

Т.2.2. (теорема Поста о функциональной полноте)

Для того чтобы система булевых функций F = {f₁,f₂,…,f_n} была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов Р₀, Р₁, S, L, М.

 

Классы Р₀, Р₁, S, L, М называются классами Поста.

 

Следствие

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

 

Если при проверке системы булевых функций F на полноту обнаружится, что все функции системы принадлежат одному из классов Р₀, Р₁, S, L, М, то такая система F является неполной.

 

Если для каждого из класса Р₀, Р₁, S, L, М можно указать функцию системы F, не принадлежащую этому классу, то такая система функций полна.

 

Для проверки выполнения условий теоремы Поста для некоторой системы булевых функций

F = {f₁,f₂,…,f_n} составляется специальная таблица, называемая таблицей Поста.

 

Пример 6.

Ранее была доказана полнота систем F = {,Ú, Ù}, G₁ = {, Ù}, G₂ = {, Ú}. Докажем полноту данных систем с помощью таблицы Поста.

 

В клетках таблицы пишется знак «+» или «-» в зависимости от того, принадлежит рассматриваемая функция заданному функционально замкнутому классу или нет. Для полноты системы функций необходимо и достаточно, чтобы в каждом столбце был хотя бы один минус.

Очевидно, что указанные выше системы F = {,Ú, Ù}, G₁ = {, Ù}, G₂ = {, Ú} полны.

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

 

Другими словами, класс булевых функций К называется предполным (или максимальным), если К – неполный, а для любой булевой функции fÎР₂ и fÏК, класс КÈ{f} - полный.

 

Из о.2.5 Þ предполный класс К является замкнутым. Так как любой функционально замкнутый класс функций в Р₂, не совпадающий с Р₂, лежит внутри одного из классов Поста, то в алгебре логики существуют только пять предполных классов, а именно классы Поста: Р₀, Р₁, S, L, М.

Поделиться:

Воспользуйтесь поиском по сайту: