3.5. Лекция Функционально полные системы логических функций
1. Многочлен Жегалкина
2 Замкнутые классы
3. Теорема Поста
Функционально полные системы логических функций
Система логических функций называется Функционально полной системой, если любая логическая функция может быть выражена через функции
с помощью их суперпозиции (быть выражена формулой над
).
Из (3.3) следует, что система является функционально полной. Очевидно, что любая система
, через функции которой можно выразить конъюнкцию, дизъюнкцию и отрицание, будет полной. Действительно, для любой функции f можно взять булеву формулу (по(3.3.-
, (3.3.)
) или (3.24.)), и все булевы операции в них заменить формулами над , представляющими эти операции. Несложно также доказать утверждение.
Утверждение: если система - функционально полная и любая
может быть выражена суперпозицией через функции
, тогда система
тоже функционально полная.
В качестве примера рассмотрим системы: ,
,
. Для доказательства функциональной полноты первой системы воспользуемся тем ,что система
полная,
,
,
и
,
.
Тогда ,
(т. е. выражена через
и
), а
. Полнота системы
доказывается аналогично, но с использованием равносильности
. Для доказательства полноты системы
(Отрицание обратной импликации х2, но не х1 j4: 0 1 0 0 ) воспользуемся полнотой системы
и тем, что
,
.
Рассмотрим систему . Это полная система, так как можно опереться на полноту системы
и равносильность
. По таблицам истинности можно проверить, что выполняются тождества:
1) ; 1’)
;
2) ; 2’)
;
3) ; 3’)
;
4) ; 4’) если
, то
.
5) ;
6) ;
7) .
Следовательно, в силу полноты системы и перечисленных тождеств любую булеву функцию можно представить в виде многочлена от своих переменных.
2. Многочлен Жегалкина.
Многочленом Жегалкина Называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: å xi1, ... , xik Å aj, причём на каждом наборе <i1, ... , ik> все ij (j=1, ... , k) различны, aj Î{0,1}.
Из тождеств 3 и 3` следует, что каждая булева функция может быть представлена многочленом Жегалкина. Так как и число различных функций m переменных равно , и число многочленов Жегалкина равны
, то представление логической функции многочленом Жегалкина единственно.
Рассмотрим примеры представления различных функций многочленом Жегалкина:
,
,
.
Мы рассмотрели достаточные условия функциональной полноты системы логических функций. Установим теперь критерий полноты системы логических функций.
2.Замкнутые классы
Пусть имеется набор логических функций ,
, где
– множество логических функций и переменных. Напомним, что
. Замыканием F (обозначим
) называется множество всех булевых функций, реализуемых над F:
,
Где func j - означает функцию, реализуемую формулой j, а – множество функций, реализуемых формулами j на F.
Отметим следующие свойства замыкания:
1. ;
2. ;
3. ;
4. .
Класс (множество) функций F называется Замкнутым , если [F] = F. Рассмотрим следующие классы функций:
1. T0 – класс функций, сохраняющих 0:
;
2. T1 – класс функций, сохраняющих 1:
;
3. S – класс самодвойственных функций:
;
4. L – класс линейных функций:
,
Где – константы такие, что
, “+” означает сложение по модулю 2 (вместо
), а знак конъюнкции опущен. Последнее определение требует, чтобы функция f, представленная многочленом Жегалкина, была линейна.
5. М – класс монотонных функций:
,
Где и
наборы
= <
1,…,
N >,
= <
1,…,
N >,
;
.
Справедлива теорема.
Теорема 3.5. Классы Т0, Т1, S, L, M Замкнуты
Доказательство. Чтобы доказать, что некоторый класс – замкнутый, достаточно показать, что если функция реализована в виде формулы над
, то она принадлежит
. Доказать, что произвольная формула обладает достаточным свойством, можно с помощью индукции по структуре формулы. База индукции очевидна: функции из
реализованы как тривиальные формулы над
. Таким образом, осталось обосновать индукционные переходы для пяти рассматриваемых классов.
1. Пусть ,
и
. Тогда
.
2. Пусть ,
и
.
Тогда .
3. Пусть ,
и
.
Тогда
.
4. Пусть ,
и
.
Тогда : ,
………………………………..
.
Подставляя эти формулы в формулу для , имеем:
.
5. Пусть ,
и
.
Тогда
.
В качестве примера приведем для некоторых булевых функций таблицу принадлежности их рассмотренным классам.
Таблица 3.5.
|
|
|
|
|
|
0 |
+ |
– |
– |
+ |
+ |
1 |
– |
+ |
– |
+ |
+ |
|
– |
– |
+ |
+ |
– |
|
+ |
+ |
– |
– |
– |
|
+ |
+ |
– |
– |
– |
Следует отметить, что рассмотренные классы попарно различимы, не пусты и не совпадают с .
Обсудив замкнутые классы и замыкание для полного класса логических функций, можем записать
,
Т. е. любая функция реализуема над .
3. Теорема Поста.
Теорема 3.6. (Теорема Поста). Система булевых логических полна тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую нуль, хотя бы одну функцию, не сохраняющую единицу, хотя бы одну несамодвойственную функцию, хотя бы одну не монотонную функцию и хотя бы одну нелинейную функцию:
.
Доказательство. Необходимость. От противного.
Пусть и
. Если обозначить
,
,
,
,
, то
, но это противоречит определению замкнутых классов
,
, и т. д.
Достаточность.
Пусть .
Тогда
.
Функции не обязательно различны и не обязательно исчерпывают
.
Построение проведем в три этапа: на первом этапе строятся формулы, реализующие константы 0 и 1, которые потребуются на третьем этапе. На втором этапе строим формулу, реализующую отрицание. На третьем – формулу, реализующую конъюнкцию.
Этап 1. Строим формулу, реализующую 1.
Пусть . Тогда
.
Возможны два случая: и
.
1) , тогда формула
реализует 1;
2) , тогда формула
реализует отрицание.
В этом случае рассмотрим функцию . Имеем:
.
Пусть теперь .
Тогда
.
Таким образом, , отсюда
. Если
, то константа построена. В противном случае
реализует 0, и значит
реализует 1. Построение 0 аналогично, только вместо
необходимо использовать
.
Этап 2. Построим формулу, реализующую отрицание. Рассмотрим функцию . Пишем:
.
Тогда . Но
Другими словами,
– это множество индексов
, для которых
.
Пусть , где
, если
, и
, если
.
Тогда
.
Имеем
.
Здесь означает замену во всех вычислениях
на
.
Этап 3. Построим формулу, реализующую конъюнкцию. Рассмотрим функцию . Имеем:
. Но
, следовательно, в полиноме Жегалкина существует нелинейное слагаемое, содержащее конъюнкции и состоящее, по крайней мере, из двух переменных. Пусть для определенности, это
и
. Тогда
, причем
. Следовательно,
.
Пусть ,
,
и
.
Пусть далее .
Тогда
Докажем, например, что система Является полной. Составим для этого так называемую таблицу Поста, в которой принадлежность каждой функции из
К определенному классу будем обозначать символом «+», а не принадлежность – «-». В силу теоремы для полноты
Достаточно по одному «-» в столбце.
Для Получим:
-
-
-
-;
-для анализа монотонности изобразим граф, в котором
Вершины соответствуют всем наборам аргументов, а стрелки направлены от набора К
, если
. В нашем случае на всех дугах выполняется условие:
Таким образом функция
монотонна.
Проведенному анализу соответствует первая строка таблицы Поста.
|
|
|
|
|
|
|
+ |
+ |
- |
- |
+ |
|
+ |
+ |
- |
- |
+ |
|
- |
- |
+ |
+ |
- |
Точно так же выполним анализ для функций и
и заполним таблицу, из которой сразу становится очевидным, что система
- полная.
Система функций Называется Независимой, Если никакая функция
Не представима суперпозицией функции из
Независимая система функцией называется Базисом функционально замкнутого класса
, если всякая функция из
Есть суперпозиция из
. Например система функций
Независима, так как для
и
можно записать:
И т. д. и таким образом система
является базисом всех логических функций.
Задачи И упражнения
1. Разложите по переменным функцию
.
2. Для функции найдите СДНФ и СКНФ.
3. Найдите СДНФ и СКНФ для функций:
А) равно 1 тогда и только тогда, когда большинство переменных равно 1;
Б) равно 1 тогда и только тогда, когда
.
4. Перейти к СДНФ в формулах:
А) , б)
, в)
.
5. Перейти к КНФ в формулах:
А) , б)
, в)
.
6. Выразить с помощью суперпозиции:
А) через
; б)
через
; в)
Через
;
Г) через
(штрих Шеффера); д)
через
(стрелка Пирса).
7. Представить многочленом Жегалкина:
А) ; б)
; в).
; г)
.
8. Доказать, что самодвойственная функция на противоположных наборах переменных принимает противоположные значения.
9. Доказать, что число самодвойственных функций от переменных равно
.
10. Доказать, что число линейных функций от переменных равно
.
11. Доказать функциональную полноту систем функций: ,
.
12. Перейти от КНФ к СКНФ для формул:
А) , б)
, в)
.
13. Представить многочленом Жегалкина следующие формулы:
А), б)
, в)
.
14. Доказать, что множество всех дизъюнкций является замкнутым
Классом.
15. Доказать, что всякая булева формула, не содержащая отрицание, представляет монотонную функцию, отличную от 0 и1.
16. Заданы таблично функции , монотонность которых требуется установить:
|
|
|
|
|
|
|
0 0 0 0 1 1 1 1 |
0 0 1 1 0 0 1 1 |
0 1 0 1 0 1 0 1 |
0 1 0 1 1 0 0 1 |
0 0 1 1 0 1 1 1 |
1 0 1 0 1 1 0 0 |
0 1 1 1 0 0 0 0 |
17. Класс функций, который можно получить суперпозициями из системы , является замкнутым классом и называется Замыканием
и обозначается
. Докажите, что класс монотонных функций является замыканием системы
.
18. Доказать, что если не монотонна, то существует такая подстановка
константы, что функция оставшейся одной переменной является отрицанием.
19. Доказать, что система функций , где
содержит хотя бы одну немонотонную и одну нелинейную функцию, является функционально полной.
20. Доказать, что пересечение двух функционально замкнутых классов есть функционально замкнутый класс.
21. Доказать, что если , где
- замкнутый класс, то
и
- тоже замкнутый класс.
22. Доказать незамкнутость классов функций:
А) класс функций от двух переменных;
Б) класс функций, сохраняющих нуль, но не сохраняющих единицу.
23. Доказать, что объединение функционально замкнутых классов может не быть функционально замкнутым.
24. Доказать, что нельзя выразить с помощью суперпозиций:
А) через
и ~; б)
через
.
25. Проверить с помощью теоремы Поста полноту следующих систем логических функций:
А) {+, ~}; б) {}; в) {0, ~}; г) {~,
, 0}; д){|}; е){¯}.
Будут ли эти системы функций независимыми?
26. Доказать, что для класса k1 всех функций базисами являются:
А) {,
}; б) {½}; в) { ¯ }.
27. Доказать, что единственно полными системами из одной двухместной функции являются {|} и {¯}.
28. Доказать, что - базис для класса
.
29. Доказать, что число булевых функций от n переменных, среди которых к фиктивных, равно .
30. Какие функции являются двойственными для +, ~, |, ¯?
31. Построить СДНФ и СКНФ для .
32. Проверить принадлежность классам функций ¯, |,
, ®, Å.
33. Доказать, что .
34. Для каждой булевой функции двух переменных найдите двойственную.
35. Доказать, что , где А – логическая формула.