10. Замкнутые классы функций.
Определение 2. Пусть задана некоторая система БФ = {1, 2, …}. Систему ’ называют замыканием класса , если класс ’ содержит все БФ, которые могут быть выражены через функции класса . Обозначается ’ = [].
Определение 3. Класс называется замкнутым, если его замыкание совпадает с ним самим, т.е. = [] (этот класс состоит из всех булевых функций, которые можно получить суперпозициями из Ф).
Примеры.
Р2 – замкнутый класс, т.к. Р2 = [Р2 ].
Класс функций F0 ={, , }. Замыканием класса является класс [F0] = Р2. Следовательно, заданная класс не является замкнутым.
Рассмотрим некоторые примеры замкнутых классов функций.
1. Класс
функций, сохраняющих ноль.
.
К этому классу относятся,
например, функции
;
;
;
.
2. Класс
функций, сохраняющих единицу.
3. Класс S самодвойственных функций составляют функции, на противоположных наборах принимающие противоположные значения:
.
4. Класс М монотонных функций.
Для двоичных векторов и, где
,
,
вводится следующее отношение частичного
порядка. Считается, что
(говорят,
что набор
предшествует набору
),
если
для
.
Класс M определяется
следующим образом:
.
5. Класс линейных функций L составляют функции, которые представляются полиномом Жегалкина первой степени.
Проверка принадлежности булевой функции замкнутым классам 1-4 осуществляется по таблице истинности. Проверка принадлежности булевой функции классу L осуществляется путем построения полинома Жегалкина.
Примечание. Здесь
– множество всех булевых функций n
переменных.
11. Функциональная полнота.
Теорема (о функциональной полноте).
Для того, чтобы система булевых функций
была полной, необходимо и достаточно,
чтобы она целиком не содержалась ни в
одном из пяти классов
,
,
,
,
.
В тех задачах, где требуется выяснить,
является ли данная система булевых
функций
полной, мы будем составлять таблицы,
которые называются таблицами Поста.
Для проверки функциональной полноты системы булевых функций строится так называемая таблица Поста, в которой отмечается принадлежность функций замкнутым классам. Если в каждом столбце таблицы Поста есть хотя бы один минус, система полна, в противном случае – нет.
Минимальная функционально полная система называется базисом пространства булевых функций.
Например, следующие системы
,
,
являются полными.
Практическая работа по теме 4.
Задание 1. Определить существенные/не существенные переменные БФ. Функция задана набором значений (11110011).
Решение. Для удобства приведем таблицу истинности.
-
1
x2
x3
f(x1, x2 ,x3)
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
Проверим, является ли переменная 1 существенной или фиктивной.
k=1, длина отрезка 8, половины не равны – переменная существенная.
Проверим, является ли переменная 2 существенной или фиктивной.
k=2, длина отрезка 4, половины не равны – переменная существенная.
Проверим, является ли переменная 3 существенной или фиктивной.
k=3, длина отрезка 2, половины равны – переменная несущественная.
Задание 2. Для заданной булевой функции построить двойственную функцию
Решение.
Задание 3. Построить СДНФ, СКНФ и полином Жегалкина для функции (11110011).
Решение. Таблица истинности данной булевой функции приведена ранее.
СДНФ имеет вид:
.
СКНФ имеет вид:
.
Построим полином Жегалкина.
Имеем функцию от 3-х переменных. Тогда общий вид ПЖ:
f(x1, x2, x3)= c1x1x2x3+ c2x1x2 + c3 x1x3 + c4x2x3 + c5x1 + c6x2 + c7x3 + c8.(1)
На наборе (000):
f(000) =
c1*0*0*0+c2*0*0+c3*0*0+c4*0*0+c5*0+c6*0+c7*0+c8=1
c8=1
На наборе (001):
f(001) = c1*0*0*0+c2*0*0+c3*0*0+c4*0*0+c5*0+c6*0+c7*1+c8=1 c7+1=1 c7=0
На наборе (010):
f(010) = c1*0*1*0+c2*0*1+c3*0*0+c4*1*0+c5*0+c6*1+c7*0+c8=1 c6+1=1 c6=0
На наборе (011):
f(011) = c1*0*1*1+c2*0*1+c3*0*1+c4*1*1+c5*0+c6*1+c7*1+c8=1 c4+ c6+ c7 +c8=1
c4+0+0+1=1 c4=0
На наборе (100):
f(100) = c1*1*0*0+c2*1*0+c3*1*0+c4*0*0+c5*1+c6*0+c7*0+c8=0 c5+c8=0
c5+1=0 c5=1
На наборе (101):
f(101) = c1*1*0*1+c2*1*0+c3*1*1+c4*0*1+c5*1+c6*0+c7*1+c8=0 c3+ c5+ c7 +c8=0
c3+1+0+1=0 c3=0
На наборе (110):
f(110) = c1*1*1*0+c2*1*1+c3*1*0+c4*1*0+c5*1+c6*1+c7*0+c8=1 c2+ c5+ c6 +c8=1
c2+1+0+1=1 c2=1
На наборе (111):
f(111) = c1*1*1*1+c2*1*1+c3*1*1+c4*1*1+c5*1+c6*1+c7*1+c8=1
c1+1+0+0+1+0+0+1=1
c1+1=1 c1=0
Подставляя найденные значения коэффициентов в уравнение (1), получим полином Жегалкина для заданной булевой функции: f(x1,x2,x3)=x1*x2+x1+1.
Задание 3.
1. Используя критерий полноты, определить,
полна ли система F в P2.
.
Решение. Проверим принадлежность
замкнутым классам функции
.
Построим таблицу истинности данной
функции.
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
,
следовательно
.
,
следовательно
.
,
следовательно,
.
,
следовательно,
.
Функция представляет собой полином
Жегалкина первой степени, следовательно,
.
Результаты можно занести в первую строку таблицы Поста. Остальные функции исследуются аналогично.
Построим таблицу Поста для заданной системы функций:
|
|
|
S |
M |
L |
|
+ |
- |
- |
- |
+ |
|
+ |
+ |
- |
+ |
- |
1 |
- |
+ |
- |
+ |
+ |
В каждом столбце таблицы имеется минус, следовательно, система A функционально полна.
2. Выяснить, является ли заданная система булевых функций полной
Решение.
Построим таблицу истинности заданной функции:
|
|
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Проверим принадлежность функции основным замкнутым классам.
Очевидно (по определению), что
,
.
Так как
,
то
.
Найдем полином Жегалкина:
.
Следовательно,
.
Так как (0,0)
(1,1), но
,
то
.
Таблица Поста для системы
имеет вид.
-
-
-
-
-
-
Итак, - полная система.
3. Выяснить, является ли заданная система
булевых функций полной
-
+
-
-
+
+
-
+
-
+
+
+
+
-
-
+
+
+
+
+
-
Функция самодвойственна, так как
Функция немонотонная, так как (0,0,1) (0,1,1), но 1=0+0+1>0+1+1=0.
Система
- полная система.
4. Выяснить, является ли заданная система булевых функций полной
-
-
-
+
+
-
+
+
+
-
-
Функция самодвойственная, так как
Итак, все функции системы
целиком принадлежит классу
.
Следовательно, по теореме о полноте
не является полной.