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

раскроем скобки под знаком отрицания (конъюнкция действует аналогично умножению)

==

при сложении по модулю 2 , т. е. 1Å1=0. Получаем

==

По законам дистрибутивности относительно конъюнкции и сложения по модулю 2 раскрываем скобки дальше

==

Воспользуемся законом идемпотентности xx=x

==.

Получили полином Жегалкина – .

2) f(x, y, z) = (xÛz)Úy=

Сначала избавимся от эквиваленции по формуле

====

Раскроем скобки по законам дистрибутивности

======

По правилам сложения по модулю 2

=.

Получили полином Жегалкина – .

Упражнения

Привести к виду полинома Жегалкина следующие формулы:

1) f(x, y, z)=. Ответ: .

2) f(x, y, z)=. Ответ: .

3) f(x, y, z)=. Ответ: .

2.2. Замкнутые классы и полнота

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

Замыканием множества булевых функций N называется множество [N] всех суперпозиций функций из множества N. Свойства замыканий:

1)  N Í [N];

2)  [[N]] = [N];

3)  N1 Í N2 Þ [N1 ] Í [N2];

4)  [N1] È [N2] Í [N1 È N2].

Доказательство. Свойство 1) имеет место при условии, что булевые функции из множества N мы рассматриваем как результат применения операции суперпозиции.

2) " f Î [[N]] Þ f = C(h1, …, hn), hi Î [N], 1£ i £ n Þ hi =Ci(g1,…,gm), gjÎ N, 1 £ j £ m Þ f =C( C1(g1, … ,gm, … , Cn(g1, … , gm)) Þ f Î [N] Þ [[N]] Í [N]. Обратное включение следует из свойства 1.

3) " f Î [N1] Þ f =C(g1, … , gm), giÎ N1 Þ gi Î N2, i = 1, m Þ f Î [N2] Þ [N1] Í [N2].

4)" f Î [N1] È [N2] Þ f = C(g1, … , gn), gi Î N1 Ú gi Î N2, Þ gi Î N1È N2 Þ f Î [N1 È N2] Þ [N1]È [N2] Í [N1È N2 ]. <

Множество N называется замкнутым, если [N] = N. Для доказательства замкнутости множества, очевидно, достаточно доказать, что любая суперпозиция функции из множества вновь функция из этого же множества. Пять важнейших замкнутых классов:

1)  Класс Т0 = {f| f(0,…, 0) = 0} – класс функций, сохраняющих 0, т. е. на наборе (0,…,0) функция принимает значение 0.

2)  Класс Т1 = {f| f(1,…, 1) = 1}, – класс функций, сохраняющих 1, т. е. на наборе (1,…,1) функция принимает значение 1.

3)  Класс L = {f | f = e0 Å e1x1 Å … Å enxn, ei = 0 Ú 1} , – класс линейных функций, т. е. полином Жегалкина этих функций не содержит смешанных конъюнкций.

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

5)  Класс S = {f| f = f*}, – класс самодвойственных функций.

Обозначим через Р2 множество всех булевых функций. Класс N булевых функций называется полным, если [N] = Р2.

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

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

Функции конъюнкция, дизъюнкция и отрицание образуют полный класс, но не базис, так как дизъюнкция – суперпозиция конъюнкции и отрицания. Система {0, 1, Ù, Å } полна, так как любую булеву функцию можно представить в виде полинома Жегалкина.

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

Доказательство. Даны два класса булевых функций N1 = {f1, …} и N2 = {g1, …} . Первый класс полный и каждая его функция – суперпозиция функций второго класса.

" f Î P2 Þ f = C( f1, …), fi = Ci( g1, …) Þ f Î [N2] Þ P2 Í [N2] Þ P2 = [N2] . <

Упражнения

Докажите полноту классов:

1)  {Ù, Ø}; (Решение: очевидно, что этот класс полный, так как любую функцию мы можем представить в виде СДНФ, а затем выразить все дизъюнкции через конъюнкцию и отрицание по закону Моргана),

2)  {Ú, Ø}; (Указание: аналогично 1),

3)  {Þ, Ø}; (Решение: Импликация выражается через дизъюнкцию и отрицание, далее по 2),

4)  {0, Þ},

5)  {|}. (Решение: штрих Шеффера – это отрицание конъюнкции, следовательно, по 1 мы получаем полную систему).

2.2.2. Классы функций, сохраняющих константы

Булева функция сохраняет константу 0, если на нулевом наборе значений переменных принимает значение 0, сохраняет константу 1, если на единичном наборе значений переменных принимает значение 1. Классы функций, сохраняющих константы, обозначаются соответственно Т0 и Т1. Функции тождественная, конъюнкция и дизъюнкция сохраняют обе константы; отрицание не сохраняет их; сумма по модулю 2 сохраняет 0, но не сохраняет 1; импликация сохраняет 1, но не сохраняет 0.

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

Доказательство. Разобьем множество всех булевых функций на пары “функция и ее отрицание”. В паре одна и только одна функция сохраняет константу ноль. Следовательно, число всех различных n-местных булевых функций, сохраняющих константу 0, равно половине общего числа всех n-местных булевых функций. Ясно, что такое же утверждение верно и для функций, сохраняющих константу 1. <

ТЕОРЕМА. Классы функций, сохраняющих константы 0 и 1, замкнуты.

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

f(0,…,0)) = f1(0,…,0, f2(0,…,0)) = f1(0,…,0) = 0 Þ f Î T0..

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

Точно также доказывается замкнутость класса Т1. <

Упражнение