Лекции по высшей математике
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 5.00 (1 Голос)

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. Доказать, что , где А – логическая формула.

Функционально полные системы логических функций - 5.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить