2.4.3 Классы Поста

Определение. Говорят, что булева функция сохраняет 0, если .

Обозначим через множество функций от переменных, сохраняющих 0, а через – множество всех булевых функций, сохраняющих 0, т.е. .

Например, , т.к. ; , т.к. .

Определение. Говорят, что булева функция сохраняет 1, если .

Обозначим через множество функций от переменных, сохраняющих 1, а через – множество всех булевых функций, сохраняющих 1, т.е. .

Например, , т.к. ;

, т.к. .

Упражнение 2.30. а) Какие из функций одной переменной принадлежат, а какие не принадлежат множествам , ?

б) Какие из элементарных функций двух переменных принадлежат, а какие не принадлежат множествам , ?

◄ а) , , , .

б) решить самостоятельно.►

Упражнение 2.31. а) Перечислите векторы значений булевых функций 2-х переменных, сохраняющих 0.

б) Перечислите векторы значений булевых функций 2-х переменных, сохраняющих как 0, так и 1.

в) Сколько имеется булевых функций от переменных, сохраняющих 0?

г) Сколько имеется булевых функций от переменных, сохраняющих 1?

д) Сколько булевых функций содержится во множестве ?

е) Сколько булевых функций содержится во множестве ?

◄ а) и б) решите самостоятельно.

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

г) и д) решите самостоятельно.

е) Разобьем множество на три подмножества: в первое включим функции, сохраняющие 0, но не сохраняющие 1, во второе – функции, сохраняющие 1, но не сохраняющие 0, в третье – функции, сохраняющие как 0, так и 1. В первом подмножестве содержится функций (первая и последняя координаты вектора значений этих функция равны 0), во втором - (первая и последняя координаты вектора значений этих функция равны 1), в третьем - (первая координата вектора значений этих функция равна 0, последняя - 1). Следовательно, .

Другой подход к решению – использование формулы мощности объединения множеств:

►

Определение. Булева функция называется самодвойственной, если , т.е. на любом наборе значений переменных выполняется равенство т.е. .

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

Обозначим через множество самодвойственных функций от переменных, а через – множество всех самодвойственных функций; т.е. .

Упражнение 2.32. Дать определение несамодвойственной функции.

◄ Булева функция несамодвойственная, если существует такой набор значений переменных такой, что .►

Например, , т.к. .

Упражнение 2.33. а) Перечислите самодвойственные функции одной переменной.

б) Перечислите элементарные самодвойственные функции двух переменных.

◄ а) , , , , таким образом, среди функций одного аргумента самодвойственными являются тождественная функция и отрицание.

б) решить самостоятельно.►

Определение. Если для любого ( ), то говорят, что вектор предшествует вектору и пишут .

Обратите внимание, если номер вектора меньше номера вектора (и, значит, в таблице истинности стоит выше ), то это еще не значит, что предшествует . Чтобы выяснить предшествует ли один вектор другому, нужно сравнить их координаты (первую с первой, вторую со второй, и т.д.). Например, вектор предшествует , но не предшествует вектору . Еще примеры: ; . Заметьте, есть пары векторов, в которых ни один из векторов не предшествует другому.

Если имеет место хотя бы одно из соотношений или , то и называют сравнимыми. В противном случае – несравнимыми.

Упражнение 2.32. а) Перечислите булевы вектора, предшествующие .

б) Перечислите булевы вектора, предшествующие .

◄ а) Булев вектор будет предшествовать вектору , если его первая и третья координаты будут либо равны 0, либо 1, а вторая и четвертая равны 0. Этим условиям удовлетворяют вектора , , , а также сам вектор .

б) решить самостоятельно.►

Упражнение 2.35. а) Сколько существует булевых векторов, предшествующих вектору ?

б) Сколько существует булевых векторов, которым предшествует вектор (101000101)?

◄ а) Вектора, предшествующие вектору , имеют вид , где выбираются из множества . Для подсчета используем правило произведения. Вначале выбираем значение (это можно сделать двумя способами – взять 0 или 1), затем выбираем значение (0 или 1), и последним выбираем значение (0 или 1). Следовательно, общее число предшествующих векторов равно .

б) Решить самостоятельно.►

Определение. Говорят, что булева функция монотонна, если для любых наборов и значений переменных, таких что , выполняется неравенство .

Обозначим через множество монотонных функций от переменных, а через – множество всех монотонных функций; т.е. .

Упражнение 2.36. Дать определение немонотонной функции.

◄ Булева функция немонотонная, если найдутся такие наборы и значений переменных, что , а . ►

В случае функции одной переменной функция монотонна при выполнении неравенства . В частном случае двух переменных функция монотонна, если выполняются неравенства: , , , , . Обратите внимание: так как в паре векторов ни один не предшествует другому, то и значения и не сравниваются. Например, функции - монотонны, а функции немонотонны.

Упражнение 2.37. Выяснить, монотонна или нет функция:

а) ; б) .

0	0	0	0	0
0	0	1	1	1
0	1	0	0	0
0	1	1	1	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	0	1

◄ а) Будем последовательно перебирать пары булевых векторов, отбирать из них сравнимые и сопоставлять значения функции на векторах этих пар.

Перебор можно вести, придерживаясь такой схемы: сначала перебираем пары с вектором ,

затем пары с вектором (вектор уже не рассматриваем), затем пары с вектором (вектора и уже не рассматриваем) и т.д.

Вектор предшествует всем прочим булевым векторам длины 3, при этом значение функции на этом векторе, будучи равным нулю, меньше либо равно значениям функции на всех других векторах. Этот факт не позволяет сделать никаких выводов относительно монотонности функции , поэтому переходим к рассмотрению пар с вектором . Вектор предшествует векторам , , , при этом , однако уже . Следовательно, условие монотонности нарушено, и, значит, функция немонотонна.

б) Последовательно перебрав все пары сравнимых векторов, убеждаемся, что функция монотонна.►

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

Определение. Говорят, что булева функция линейна, если степень ее канонического полинома Жегалкина меньше либо равна 1.

Иначе говоря, функция линейна, если ее полином Жегалкина имеет вид .

Обозначим через множество линейных функций от переменных, а через – множество всех линейных булевых функций, т.е. .

Упражнение 2.38. Дать определение нелинейной функции.

◄ Булева функция нелинейна, если степень ее канонического полинома Жегалкина больше либо равна двум. ►

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

Например, все функции одной переменной линейны; , , , линейными не являются.

Упражнение 2.39. а) Выписать полиномы Жегалкина линейных булевых функций от 2-х переменных.

б) Выяснить, сколько имеется линейных булевых функций от переменных.

◄ а) решите самостоятельно.

б) Между булевыми функциями переменных и каноническими полиномами Жегалкина от переменных существует взаимно однозначное соответствие, значит, линейных булевых функций от переменных столько же, сколько канонических полиномов Жегалкина вида . Каждый такой полином Жегалкина определяется набором коэффициентов , а количество таких наборов равно . Значит, .►

Упражнение 2.40. Определите, каким из классов Поста принадлежат функции:

а) ; б) ; а) ; б) .

◄ а) . Имеем:

, следовательно, ;

, следовательно, ;

, следовательно, ;

, а , следовательно, ;

, следовательно, .

б) . Имеем:

, следовательно, ;

, следовательно, ;

, следовательно, ;

, а , следовательно, ;

, следовательно, .

Пункты в) и г) решите самостоятельно.►

Классы , , , , называют классами Поста.

Упражнение 2.41. Определите, каким из классов Поста принадлежат функции

а) ; б) .

◄ а) Удобно работать с функцией, заданной таблично:

0	0	0	0	1	0	0
0	0	1	0	1	0	0
0	1	0	1	1	0	1
0	1	1	1	1	0	1
1	0	0	1	0	1	0
1	0	1	1	0	0	1
1	1	0	1	0	1	0
1	1	1	1	0	0	1

, следовательно, ;

, следовательно, ;

, следовательно, ;

, а , следовательно, .

Чтобы определить, линейна ли функция, найдем ее полином Жегалкина. Воспользуемся для этого методом неопределенных коэффициентов. Начнем с того, что выпишем в общем виде канонический полином Жегалкина от трех переменных:

.

Нам нужно подобрать такие коэффициенты , чтобы на каждом наборе значений переменных выполнялось равенство: :

; мы сократили запись, учтя, что все слагаемые, идущие вслед за , равны нулю на наборе .

; мы сократили запись, учтя, что все слагаемые, идущие вслед за , равны нулю на наборе (далее будем поступать также).

;

;

;

;

.

Теперь можем выписать для функции полином Жегалкина (опустив нулевые члены и единичные коэффициенты): . Поскольку в полиноме Жегалкина есть произведения переменных, делаем вывод: .

б) решите самостоятельно. ►