Функционально полные системы логических функций

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. Заданы таблично функции , монотонность которых требуется установить:

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