Критерий полноты системы булевых функций (теорема

Поста) - система полна в том и только в том случае, если для каждого рз классов в системе существует функция, не

Принадлежащая этому классу, иначе говоря, система полна, если рыполнены 5 условий

Функции - не обязательно различные

Предварительно рассмотрим 3 утверждения, которые 'демонстрируют, как суперпозициями функций системы, удовлетворяющей условию теоремы Поста, выразить функции известных полных систем Лемма 1. Суперпозициями несамодвойственной функции

и функции можно получить функцию-константу Если , то существует набор такой, что

Построим суперпозицию , где вместо

|ждого переменного функции подставляется либо X, либо Югда [ввиду (*}] =

Таким образом а это означает, чтс - константа

Следствие. Из функции и константы можно получить другую

рнстанту

Лемма 2. Суперпозициями немонотонной функции

и функций-констант 0 и 1 можно получить функцию Если , то существуют наборы и

такие, что и

, т.е. . Пусть - набор,

где каждое - либо переменная X, либо константа и определяется следующим образом:

Отметим, что если X - О, то ; если X = 1, то . Пусть

. Тогда , т.е.

Лемма 3. Суперпозициями нелинейной функции функции и функций-констант 0 и 1 можно получить конъюнкцию

Построим для функции многочлен Жегалкина. В силу нелинейности среди слагаемых найдется содержащее не менее 2 множителей. Пусть это переменные Тогда все слагаемые

разбиваются на 4 группы: содержащие обе переменные только

одну из них и не содержащие ни одной. Объединяя

слагаемые и вынося за скобки соответствующие множители в каждой j из трех первых групп, получим:

Функции зависят от переменных , причем не

равна тождественно 0, - иначе не было бы ни одного слагаемого с произведением. . Подставим в функцию вместо переменных

тот набор констант , для которого _;

при этом функции обращаются в некоторые константы;

обозначим их соответственно . Получим функцию двух

переменных

Теперь произведем еще одну подстановку: в функцию подставим функцию вместо вместо . в

Зависимости от значений каждая из этих функций представляет

собой либо , так что фактически мы подставляем либо

Переменную, либо ее отрицание. Получаем функцию , равную

[после раскрытия робок]

[после сокращений] т.е. сумму по модулю 2

конъюнкции и константы . Если последняя равна 0, то

построение закончено; в противном случае, т.е. если

то нужно подставить в функцию :

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

Достаточность выводится из лемм 1 -3. Пусть в системе есть функции ' (некоторые из них могут

ювпадать). Суперпозиция - функция одной

юременной, имеющая столбец значений ; аналогично,

- функция со столбцом значений

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

- функция . По

лемме 1, из функций можно получить константы 0 и 1.

(2)в противном случае . Тогда

По лемме 2, из функций и констант можно получить функцию

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

По лемме 3, из функций , отрицания и констант 0 и 1

можно получить конъюнкцию . В свою очередь, конъюнкция и

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

Для проверки конкретной системы на полноту можно заполнить для функций системы так называемую таблицу Поста: см. табл.9, в которой исследуется система ("+" означает принадлежность

функции данному предполному классу).

Принадлежность трех данных функций классам проверяется

по их таблицам очень просто. Также несложно проверить принадлежность их классу М (заметим, что если и не равна 0 тождественно, то

она не монотонна). Очевидно также, что , свойство

следуе^т из соотношения

Функцияне самодвойственна, поскольку двойственная

/

ей, как мы знаем, другая функция - конъюнкция. Далее,

нелинейна, так как ее многочлен Жегалкина содержит

произведение . Легко проверяется также заполнение последней

строки табл.9 - для функции-константы 1. Наконец, согласно теореме Поста, для полноты системы в каждом столбце таблицы Поста должен быть хотя бы один минус.

В таблице 11 для каждого из пяти рассмотренных выше классов знаками "+" и '•'-" показана принадлежность ему ряда известных функций: всех 4 функций одной переменной, 6 функций двух переменных и 2 функций трех переменных. В отличие от предыдущей таблицы функции здесь представлены столбцами. Заметим, что в каждой Строке таблицы имеется знак "-"; другими словами, для каждого из пяти классов есть не принадлежащая ему функция и, следовательно, ни один из них не совпадает с множеством всех логических функций , а каждый является частью

Несколько примеров полных систем рассмотрены нами в §1. Отметим интересный факт: из табл.11 можно заключить, что система, Состоящая из одной функции - штриха Шеффера - полна.

Упражнение. Проверьте, что Убедитесь теперь, что

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

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

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

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

Примеры: 1) Система - независимая.

Упражнение. Убедиться в этом, используя соотношения и замкнутость классов L и Т.

2) Система не является независимой, поскольку, как мы знаем, можно выразить через или, наоборот -через и

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

В примерах 1-3 представлены полные системы функций. Теперь рассмотрим пример независимой системы для замкнутого класса, не

совпадающего с

Система не полная, так как обе функции линейны, и

представляет базис класса L Действительно,

а каждая линейная функция

выражается через Независимость функций системы

также легко проверить

Некоторые следствия теоремы Поста.

Следствие 1. Всякий замкнутый класс содержится целиком

хотя бы в одном из 5 предполных классов иначе он

представлял бы полную систему и, в силу замкнутости, равнялся бы

Следствие 2 объясняет название предполных классов если к какому-нибудь из них, допустим (для других классов рассмотрение аналогичное) добавить любую не принадлежащую ему функцию то Замыкание системы совпадает с Действительно, система

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

Иначе говоря, между предполным классом и не может существовать промежуточный замкнутый класс. Отсюда -

Следствие 3. В существуют лишь 5 предполных классов, т е. обладающих свойством, сформулированным в следствии 2 Это рассмотренные • - 'и

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