Полные множества булевых функций

1. 1.4 Полные множества булевых функций

2.

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

3. Пример.

Множество функций { ,&, }
является полным множеством в силу
теоремы о представлении любой
булевой функции ДНФ (или КНФ)
Из множества можно удалить
конъюнкцию (дизъюнкцию),
поскольку & (v) можно выразить по
законам де Моргана через ¬ и v (&)

4.

Множество, состоящее из
единственной функции штриха
Шеффера {x | y ( x & y )}
является полным, поскольку
x ( x | x )
x & y ( x | y ) (( x | y ) | ( x | y ))

5.

Множество функций
(базис Жегалкина)
{ ,&,1}
является полным множеством

6.

Полином Жегалкина от n переменных
представление булевой функции в виде
P( x1 ,..., xn )
где
{i1 ,i2 ,..., im } I
ai1i2 ... im xi1 xi2 ...xim
I {1,2,...n} , коэффициенты
полинома ai1i2 ... im {0,1} индексированы
всеми возможными подмножествами
множества I

7. Утверждение

Полином Жегалкина для любой
булевой функции определен
однозначно.

8. Пример

Пусть f=(1,1,0,0,1,0,1,1)
Функция f представляется некоторым
полиномом Жегалкина от 3
переменных, т.е.
f a123x1 x2 x3 a12 x1 x2 a13 x1 x3
a23 x2 x3 a1 x1 a2 x2 a3 x3 a0

9.

f (0,0,0) a0 1
f (0,0,1) a3 a0 a3 1 1
a3 0
f (0,1,0) a2 1 0
a2 1
f (1,0,0) a1 1 1
a1 0

10.

f (1,1,0) a12 x1 x2 a1 x1 a2 x2 a0
a12 1 1 1
a12 1
a23 0
a13 1
a123 1
f x1 x2 x3 x1 x2 x1 x3 x2 1

11. 1.5 Классы Поста

12.

Функцию f называют функцией,
сохраняющей константу 0, если
f(0,0,…,0) = 0
Функцию f называют функцией,
сохраняющей константу 1, если
f(1,1,…,1) = 1
Множество всех функций, сохраняющих
константу 0 обозначим Т0. Множество всех
функций, сохраняющих константу 1 -- Т1.

13.

Пример.
Функция f = (00111101) является
функцией, сохраняющей и
константу 0, и константу 1.
Отрицание не сохраняет ни 0, ни 1.

14.

Пусть f(x1, x2, …, xn ) – булева функция.
Двойственной к ней называется функция
f*(x1, x2, …, xn ) ¬f (¬ x1, ¬ x2, …, ¬ xn ).
Если двойственная функция f* совпадает
с исходной функцией f, то такая функция f
называется самодвойственной.

15.

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

16.

Функцию f монотонная, если
f(α) ≤ f(β) для всех наборов значений
переменных таких, что α ≤ β
Множество всех монотонных
функций принято обозначать через М

17.

Если функция f не является монотонной,
то найдутся два таких набора α, β и
индекс i, что
( 1 ,..., i 1 ,0, i 1 ,... n )
( 1 ,..., i 1 ,1, i 1 ,... n )
и f(α)=1, f(β)=0,
т.е. эти два набора различаются
значениями в точности одной компоненты,
а значение функции равно 0 на большем
наборе и равно 1 на меньшем

18.

Пример.
Функция f = (0011) монотонна.
Отрицание немонотонная функция

19.

Функция f линейная, если f
представима в виде полинома
Жегалкина первой степени, т.е.
f ( x1 ,..., xn ) a1 x1 a2 x2 ... an xn a0
Множество всех линейных функций
обозначают через L

20.

Множества функций Т0, Т1, S , М , L
называются классами Поста

21. Пример

x | y ( x & y )
Штрих Шеффера
не принадлежит ни одному из
классов Поста.
x
y
x|y
0
0
1
0
1
0
1
0
0
1
1
0

22.

Все свойства, кроме нелинейности,
следуют из таблицы этой функции.
Нелинейность доказывается
выводом нелинейного полинома
Жегалкина для штриха Шеффера
x | y ( x & y ) ( x & y ) 1

23.

Множество булевых функций F
называют замкнутым, если любая
формула над F представляет
некоторую функцию из F

24.

Множество F булевых функций
полное,
если замыкание F совпадает с
множеством всех булевых функций

25.

Теорема.
Каждый класс Поста замкнут.

26.

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

27. 1-2. Замкнутость классов T0 и T1

Пусть f , g1, ..., gn из класса T0, т.е.
f(0,0,…,0)=0, gi(0)=0
Тогда f(g1(0),… ,gn(0))=0
Следовательно, подстановка функций
из T0 содержится в классе T0
Для класса T1 доказательство
аналогично.

28. 3. Замкнутость класса S

Пусть f , g1, ..., gn из класса S, т.е.
f=f*, gi= gi*
Показать, что f(g1, ..., gn) из S

29. 4. Замкнутость класса М

Пусть f , g1, ..., gn из класса M
Показать, что f(g1, ..., gn) из M

30. 5. Замкнутость класса L

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

31. Реализация констант 0 и 1

Случай 1
f 0 T1`
f 0 T0
Пусть
f 0 (0,...,0) 1, f 0 (1,...1) 1
т.е.
1 f 0 ( x,..., x)
Тогда
Для получения 0 нужно использовать
g T1
0 g (1,...,1) g ( f 0 ( x,..., x),..., f 0 ( x,..., x))

32.

Аналогично реализуются константы,
если имеется функция f1 T1
f1 T0`

33. Случай 2

f S S Тогда найдется такой
Пусть
набор ( 1 ,..., n )
,что f ( ) f ( )
S
S
Определим функцию
где
Тогда
x, 0 и
x
x, 1
1
n
h( x) f S ( x ,..., x )
0 ,1
h(0) f S ( ) f S ( ) h(1)

34. Реализация отрицания

Если функция fM немонотонная, то с
использованием констант 0 и 1 из нее можно
реализовать отрицание
Для немонотонной функции fM найдутся два таких
набора α и β и индекс i, что
( 1 ,..., i 1 ,0, i 1 ,... n )
( 1 ,..., i 1 ,1, i 1 ,... n )
и f(α)=1, f(β)=0,
Тогда
x f M ( 1 ,..., i 1 , x, i 1 ,..., n )

35.

Если немонотонная функция fM не
сохраняет 0 и 1,
fM(0,..., 0) = 1, fM(1,..., 1) = 0
то
x f M ( x,..., x)

36. Реализация конъюнкции с использованием констант и отрицания

Если функция fL нелинейная, то с
использованием констант и
отрицания из нее можно реализовать
конъюнкцию

37. Критерий Поста

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

38. Необходимость.

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

39. Достаточность

Для доказательства полноты
множества F, удовлетворяющего
условию теоремы, построим
формулы над F для отрицания и
конъюнкции, поскольку множество,
образованное этими функциями,
полно.
Тогда полным и множество F .

40.

По условию теоремы в F найдется
f1 T0
хотя бы одна функция
Если f1 T1 , то можно реализовать
константу 1.
Если f1 T1 , то можно реализовать
отрицание.

41.

По условию теоремы в F найдется хотя бы
f 2. T1
одна функция
Если f 2 T0 , то можно реализовать
константу 0.
Если f 2 T1 , то можно реализовать
отрицание.
Таким образом, могут быть реализованы
либо две константы 0 и 1, либо только
отрицание, либо константы и отрицание

42.

В случае, если из первых двух классов
(T0 , T1) построены только формулы для
констант, с использованием немонотонной
функции fм можно реализовать
отрицание.
Если реализовано только отрицание, с
использованием несамодвойственной
функции fS можно реализовать константы.

43.

Имея константы и отрицание, из
нелинейной функции fL можно
реализовать коньюнкцию.
Таким образом, отрицание и
конъюнкция реализованы
формулами над F .
Множество полно.

44. Пример.

Проверить на полноту множество
булевых функций F { , ,0}
Для исследования используют
критериальную таблицу. Строки
таблицы соответствуют функциям
исследуемого множества, а столбцы
-- классам Поста

45.

T0 T1 S M
~
— +
V
+ +
0
+ — — +
L
— — +
— +
—
+

46.

В множестве F есть функции, не
принадлежащие каждому из пяти
классов Поста.
Согласно теореме Поста, множество
F полное