Файл: Булевы функции.doc

Шаг 2. Построение треугольника Паскаля. Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю два двух соседних элементов предыдущей строки. Левая сторона треугольника представляет собой значение вспомогательной функции g (табл. 58).

Таблица 58

Шаг 3. Построение полинома Жегалкина. В полином войдут только те слагаемые, которым соответствует единица во вспомогательной функции g.

Для данной функции многочлен Жегалкина имеет вид:

f = 1 + x₃ + x₂ + x₁ x₃ + x₁ x₂ + x₁ x₂ x₃.

Определение. Функция f(x₁, x₂, …, x_n) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:

f(x₁, x₂, …, x_n) = a₁x₁ + … + a_nx_n + a_n+1, где каждое a_i равно 0 или 1.

Булева функция из рассмотренного выше примера не является линейной.

Теорема. Класс L = {f | f = a₀+a₁x₁+…+a_nx_n, a_i{0, 1}} линейных функций замкнут относительно суперпозиций.

2.2.3.3. Монотонные функции

Определение. Если a = (a₁, …, a_n) и b = (b₁, …, b_n) - наборы длины n из 0 и 1, то a  b, если a₁  b₁, …, a_n  b_n.

Пример 47.

Наборы ( 0, 1, 0) и (1, 1, 0) сравнимы, причем ( 0, 1, 0)  (1, 1, 0).

Наборы (0, 1) и (1, 0) несравнимы. Также несравнимы наборы (0, 1) и ( 1, 1, 0).

Определение. Функция f(x₁, x₂, …, x_n) называется монотонной, если для всяких наборов a = (a₁, …, a_n) и b = (b₁, …, b_n) условие a  b влечет f(a)  f(b).

Утверждение. Функция монотонна тогда и только тогда, когда ее сокращенная ДНФ не содержит отрицаний.

Следствие. Функция монотонна тогда и только тогда, когда ее МДНФ не содержит отрицаний.

Пример 48.

Выяснить, являются ли функции монотонными:

1. f = 00100110;

2. f = 00110111.

Решение.

1. Сокращенная ДНФ для функции f = 00100110 имеет вид Поскольку сокращенная ДНФ содержит отрицания, то функция не является монотонной.

2. Сокращенная ДНФ для функции f = 00110111 имеет вид Поскольку сокращенная ДНФ не содержит отрицаний, то функция является монотонной.

Теорема. Класс M = {f | a b  f(a) f(b)} монотонных функций замкнут относительно суперпозиций.

2.2.3.4. Теорема Поста о функциональной полноте

Теорема Поста (признак полноты системы булевых функций). Для того чтобы система булевых функций {f₁, …, f_m} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T₀, T₁, L, M, S нашлась хотя бы одна функция f_i из системы, не принадлежащая этому классу.

Пример.

Выяснить к каким функционально замкнутым классам принадлежит булева функция f=01001110, используя теорему Поста.

Решение.

Строим таблицу значений и треугольник Паскаля (табл. 59):

Таблица 59

Полином Жегалкина имеет вид: f = x₃ + x₂x₃ + x₁ + x₁ x₃.

1. f(0, 0, 0) = 0  fT₀;

2. f(1, 1, 1) = 1  fT₁;

3. f(0, 0, 0) = f(1, 1, 1), а наборы (0, 0, 0) и (1, 1, 1) являются противоположными, то f  S;

4. так как в полиноме Жегалкина присутствуют слагаемые, представляющие собой конъюнкцию нескольких переменных, то f  L;

5. сокращенная ДНФ функции имеет вид: , так как она содержит отрицания, то f  M.

Сведем полученные данные:

Пример 49.

Доказать полноту системы {+, , 1}.

Решение.

Введем обозначения: f₁ = x₁ + x₂, f₂ = x₁  x₂, f₃ = 1. Построим единую таблицу для функций (табл. 60).

Таблица 60