§ 2.4. Классы Поста и полнота

2.4.1. Понятие о полноте системы булевых функций

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

Упражнение 2.25. Доказать, что - полная система.

◄ Возможны два случая:

1. . Тогда и может быть реализована в виде СКНФ.

2. . Тогда может быть реализована в виде СДНФ.

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

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

Докажем это утверждение. Пусть - произвольная функция из . Надо показать, что ее можно реализовать формулой над . Рассуждаем так. В силу полноты реализуется формулой над , т.е. . В свою очередь, по условию реализуются формулами над , т.е. . Следовательно, в формуле мы можем исключить вхождение символов функций , заменив их соответствующими формулами: . Полученное выражение определяет формулу над , реализующую .

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

а) ; б) ; в) ; г) .

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

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

в) и г) докажите самостоятельно. ►

2.4.2. Реализация булевых функций полиномом Жегалкина

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

Вначале рассмотрим эту задачу на конкретном примере. Для функции имеем:

.

В ходе преобразований мы воспользовались несколькими доказанными ранее (упр. 2.12) равносильностями: , , , , , .

Аналогичным образом можно поступать с произвольной функцией: сначала реализовать ее в виде СДНФ или СКНФ; затем, воспользовавшись законом де Моргана, избавиться от дизъюнкции; раскрыть скобки, воспользовавшись дистрибутивностью операций сложения по модулю два и конъюнкции; после этого полученное выражение упростить, используя тождества , , , , . В результате функция окажется реализована формулой, представляющей собой сумму (по модулю два) конъюнкций переменных. Формулы такого вида называют полиномами Жегалкина.

Дадим строгое определение полинома Жегалкина. Пусть M – произвольное подмножество булевого куба , , - номер вектора , - его вес, - номера отличных от нуля координат вектора .

Определение. Формула вида

, (***)

где суммирование ведется по модулю два, а коэффициенты равны либо 0, либо 1, называется полиномом Жегалкина от переменных.

Если суммирование в формуле (***), ведется по всем булевым векторам длины n, слагаемые идут в порядке возрастания номеров булевых векторов и , то говорят, что полином Жегалкина записан в канонической форме.

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

Возможно, строгое определение канонического полинома Жегалкина показалось Вам неясным. Лучший способ его осознать – переформировать применительно к какому-нибудь частному случаю, например, случаю 2-х переменных.

Рассуждаем так. Согласно определению в формуле (***) слагаемых столько, сколько булевых векторов в множестве , т.е. 4; слагаемые идут в порядке возрастания номеров булевых векторов, т.е. первое слагаемое соответствует булевому вектору (0,0), второе - (0,1), третье - (1,0), четвертое - (1,1). Слагаемые представляют собой конъюнкции, в которые входят только те переменные, значения которых в соответствующем булевом векторе равны 1, конъюнкции помножены на числовой коэффициент. Таким образом, слагаемое, соответствующее булевому вектору (0,0) (его номер 0), имеет вид ; слагаемое, соответствующее булевому вектору (0,1) (его номер 1), имеет вид ; слагаемое, соответствующее булевому вектору (1,0) (его номер 2), имеет вид ; слагаемое, соответствующее булевому вектору (1,1) (его номер 3), имеет вид . Итак, канонический полином Жегалкина от 2-х переменных - это формула вида .

Рассуждая аналогично, выпишем в общем виде канонический полином Жегалкина от 3-х переменных - (Это удобно делать, имея перед глазами таблицу истинности функции трех переменных, поскольку в этой таблице булевы вектора перечисляются в нужном нам порядке).

Упражнение 2.27. Найти число канонических полиномов Жегалкина от переменных.

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

Заметим, что каждый полином Жегалкина от n переменных можно записать в канонической форме. Например, полином Жегалкина от двух переменных в канонической форме запишется так: .

Выше на примере функции мы показали, как можно реализовать функцию в виде полинома Жегалкина. Полученный полином можно переписать в канонической форме . В связи с этим естественно задаться вопросом: каждую ли булеву функцию можно реализовать в виде канонического полинома Жегалкина? Оказывается, да. Действительно, с произвольной функцией можно действовать так же как с функцией : сначала реализовать ее в виде СДНФ или СКНФ; затем, воспользовавшись законом де Моргана, избавиться от дизъюнкции; раскрыть скобки, воспользовавшись дистрибутивностью операций сложения по модулю два и конъюнкции; после этого полученное выражение упростить, используя тождества , , , , . В результате функция окажется реализованной в виде полинома Жегалкина, который легко переписать в канонической форме.

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

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

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

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

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

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

а) ; б) ;

в) ; г) .

◄ а) .

б) .

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

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

Упражнение 2.29. Используя метод неопределенных коэффициентов, найти полином Жегалкина, реализующий функцию:

а) ; б) ;

в) ; г) .

◄ а) Зададим функцию таблично:

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

Канонический полином Жегалкина от двух переменных имеет вид: . Поэтому должны выполняться равенства:

;

;

;

.

Откуда последовательно находим , , , . Таким образом, .

б)

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

Запишем в общем виде канонический полином Жегалкина от трех переменных:

.

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

; ;

;

;

;

;

;

.

Коэффициенты найдены и можно записать канонический полином Жегалкина: .

Каноническая форма полинома Жегалкина довольно громоздкая и в практическом плане не имеет каких-либо преимуществ перед любой другой формой. Поэтому имеет смысл упростить полученное выражение, опустив нулевые члены и единичные сомножители: .

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