Множества. Комбинаторика. Отношения (стр. 11 )

1) Найдите число всех различных n-местных булевых функций, сохраняющих константы 0 и 1 одновременно. Замкнут ли класс таких функций?

2.2.3. Класс самодвойственных булевых функций

Если f* = f, то функция f называется самодвойственной. Множество всех самодвойственных булевых функций обозначается через S.

Функции х, Ø х самодвойственные. Функции Ù и Ú двойственны друг другу и поэтому несамодвойственные. Возьмем два набора из нулей и единиц a и b. Называем их противоположными, если на соответствующих местах у них расположены противоположные элементы 0 и 1, т. е. там, где в наборе a стоит 0, то в наборе b стоит 1, а там, где в наборе a стоит 0, то в наборе b стоит 0.

ТЕОРЕМА. Булева функция самодвойственная тогда и только тогда, когда на противоположных наборах значений переменных принимает противоположные значения.

Доказательство. f* = f Û Ø f(х1,…,хn) = f( Øx1 ,…,Ø xn). <

ТЕОРЕМА. Число всех различных n-местных самодвойственных булевых функций равно 22.

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

ТЕОРЕМА. Класс S замкнут.

Доказательство. Пусть f1, f2 Î SÞ Ø f1(х1,…,хn)=f1( Øx1 ,…,Ø xn), Ø f2(х1,…,хn) = f2(Øx1 ,…,Ø xn), f = f1(x1,…, xn –1, f2(y1,…,ym)) Þ

f* = Ø f1(Øх1,…,Øхn –1, f2(Øy1,…,Ø ym))= Ø f1(Øx1 ,…,Ø xn –1,Ø f2(y1,…,ym)) = f1(х1,…,хn-1), f2(y1,…,ym))= f Þ f Î S.

Общий случай можно получить многократным повторением этого рассуждения. <

Упражнение

1) Найдите число всех различных n-местных булевых функций, принимающих одинаковые значения на одних и тех же наборах значений переменных. Замкнут ли класс таких функций?

2.2.4. Класс монотонных булевых функций

Введем на множестве всех n-местных двоичных векторов частичный порядок: вектор a = <а1, …, аn> предшествует вектору b = <b1, …, bn> тогда и только тогда, когда a1 £b1, …, an £ bn. Записываем это так: a µ b.

Булева функция называется монотонной, если из того, что a предшествует b, следует, что f(a)£ f(b), где f(a) = f(a1, …, an). Множество всех монотонных булевых функций обозначим через М.

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

ТЕОРЕМА. Класс М замкнут.

Доказательство. Пусть f1(х1, …, хn) Î М, f2(у1, …, уm) Î M,

a1 £ b1, …, an +m -1 £ bn+m –1 Þ f2(an,…, an+m –1) £ f2(bn, …, bn+m –1).

Рассмотрим функцию f = f1(x1, …, xn –1, f2(y1, …, ym)). Для нее f(a1, …, an+m –1) = f1(a1, …, an –1, f2(an, …, an+m –1)) £ f1(b1, …, bn –1 , f2 (bn,…, bn+m –1)) = f(b1, …, bn+m –1) Þ f Î M.

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

Упражнения

1) Докажите, что функции Шеффера и Пирса немонотонные.

Доказательство: Построим таблицы истинности этих функций:

x	y	x½y	x¯
0	0	1	1
0	1	1	0
1	0	1	0
1	1	0	0

Рассмотрим штрих Шеффера: набор (1, 0) предшествует набору (1, 1), но значение функции на наборе (1, 0) равно 1, что больше, чем значение функции на наборе (1,1).

Для стрелки Пирса аналогично. Набор (0,0) предшествует (0,1), но значение функции на нем больше. Следовательно, ни штрих Шеффера, ни стрелка Пирса не являются монотонными функциями.

2) Доказать самостоятельно, что h(x, y, z) = xyÚ xzÚ yz монотонная.(Указание: постройте таблицу истинности для данной функции).

2.2.5. Класс линейных булевых функций

Сумма по модулю два монотонных элементарных конъюнкций называется полиномом Жегалкина. Наибольший ранг монотонных элементарных конъюнкций, входящих в полином Жегалкина, называется его степенью. Булева функция, представимая в виде полинома Жегалкина степени не выше первой, называется линейной. В соответствии с этим определением константы 0 и 1 отнесем к линейным булевым функциям.

Множество всех линейных булевых функций обозначается через L.

Этому классу принадлежат тождественная функция, функция отрицание, сумма по модулю два, эквиваленция. Конъюнкция, дизъюнкция, импликация – нелинейные булевы функции. Точно также, как доказывали ранее, можно доказать следующие теоремы.

ТЕОРЕМА. Число всех различных n-местных линейных булевых функций равно 2n +1. <

ТЕОРЕМА. Класс линейных булевых функций замкнут. <

Составим таблицу принадлежности элементарных булевых функций к важнейшим замкнутым классам.

	0	1	x	Ø	Ù	Ú	Þ	Û	Å	½	¯	h
Т0	1	0	1	0	1	1	0	0	1	0	0	1
T1	0	1	1	0	1	1	1	1	0	0	0	1
L	1	1	1	1	0	0	0	1	1	0	0	0
M	1	1	1	0	1	0	0	0	0	0	0	1
S	0	0	1	1	0	0	0	0	0	0	0	1

1 – означает, что функция принадлежит данному классу.

0 – означает, что функция не принадлежит данному классу.

2.2.6. Три леммы

ТЕОРЕМА (лемма о несамодвойственной булевой функции).

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

Доказательство. Пусть f Ï S Þ f ¹ f* . Это означает, что найдется набор значений переменных, для которого f(a1, …, an) ¹ `f(`a1, …,` an), т. е. f(a1, …, an) = f(`a1, …,` an). Если х при ai=1, ji(х) = íx при ai = 0, 1£ i £ n, то ji(0) = `ai, ji(1) = ai и для функции j (x) = f(j1(x), …, jn(x)) от одной переменной х имеем

j(0) = f(j1(0), …, jn(0)) = f(a1, …, an); j(1) = f(j1(1),…,jn(1) = f(a1,…,an),

т. е. j(0) = j(1) Þ j = сonst. <