Тексты лекций / Текст лекции 7

§ 2.5. Полнота системы булевых функций

Полная система. Теорема о полноте двух систем. Критерий полноты системы булевых функций. Базисы. Предполные классы.

Базовые понятия и утверждения

1. Понятие о полноте системы булевых функций. В предыдущем параграфе мы уста-

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

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

Пример 1. а) { , ,¬} - полная система, поскольку любая булева функция представима в виде СДНФ или СКНФ.

б) {0,1, , } - полная система, поскольку любая булева функция представима в виде полинома Жегалкина.

в) { , } - полная система, поскольку любую булеву функцию можно сначала выразить формулой над { , ,¬}, а затем заменить в этой формуле все дизъюнкции формулой

= . В итоге получится формула над { , }.

г) { , } - полная система, поскольку любую булеву функцию можно сначала выразить формулой над { , ,¬}, а затем заменить в этой формуле все конъюнкции формулой

= . В итоге получится формула над { , }.

Следующая теорема обобщает подход, использованный нами для доказательства пол-

ноты систем { , } и { , }.

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

Доказательство. Покажем, как для произвольной булевой функции построить формулу над . Возьмем формулу для над = [ , ,...] (в силу полноты такая формула обязательно существует) и заменим в ней вхождение символов функций , ,...

Пример 2. Докажем,что {|}- полная система. Действительно, пусть = { , }

= | = (|)|(|). Таким образом, каждую функцию полной системы можно задать формулой над . Следовательно, условия теоремы о полноте двух систем выполнены и, значит, = {|}- полная система.

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

2. Критерий полноты системы булевых функций. Наиболее удобный способ про-

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

1

Тема 7 «Полнота системы булевых функций» Олейник Т.А., 2020

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

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

При проверке, выполняются ли для некоторой системы функций = { ,..., } условия критерия Поста, удобно использовать таблицу, которую называют таблицей Поста

заполнен толькоплюсами),тосистема неполна. В противном случае переходим к классу и т.д.

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

а) = { , ↔ ,}; б) = { ↔ ,}.

◄ а) Для удобства рассуждений зададим функции системы таблично (табл. 2.30 и

Заполним таблицу Поста исследуемой системы (табл. 2.32).

2

Класс : перебрав все пары сравнимыхвекторов, убеждаемся, что условие монотонности для функции не нарушается, значит, ; (0,0) ̱(0,1), а (0,0) > (0,1), следовательно, .

Класс : = = , следовательно, .

Таким образом, для каждого класса Поста можно указать функцию системы ,емуне

Посколькуобефункциисистемы принадлежатклассу линейныхфункций,тосистема неполна. ►

Упражнение 2.30. Используя критерий полноты, выяснить, полна ли система буле-

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

3

Теоретические обоснования

Лемма о функции, не сохраняющей 0. Пусть . Тогда формулой над множе-

ством { } можно задать либо константу 1, либо отрицание.

Доказательство. Пусть , т.е. (0,0,...,0) = 1. Отождествим между собой все переменные функции . Получим функцию от одной переменной ( ) = ( , ,..., ).

Возможны два случая: (1,1,...,1) = 0 или (1,1,...,1) = 1.

Впервом случае (0,0,...,0) = 1 и (1,1,...,1) = 0, следовательно, (0) = 1 и (1) = 0, откуда ( ) = .

Вовторомслучае (0,0,...,0) = 1и (1,1,...,1) = 1,следовательно, (0) = 1и (1) = 1, откуда ( ) = 1.■

Лемма о функции, не сохраняющей 1. Пусть . Тогда формулой над множе-

ством { } можно задать либо константу 0, либо отрицание.

Доказательство. Пусть , т.е. (1,1,...,1) = 0. Отождествим между собой все переменные функции . Получим функцию от одной переменной ( ) = ( , ,..., ).

Возможны два случая: (0,0,...,0) = 0 или (0,0,...,0) = 1.

Впервом случае (0,0,...,0) = 0 и (1,1,...,1) = 0, следовательно,

(0) = 0 и (1) = 0, откуда ( ) = 0.

Вовторомслучае (0,0,...,0) = 1и (1,1,...,1) = 0,следовательно, (0) = 1и (1) = 0, откуда ( ) = .■

4

Рассмотримфункцию ( ),заданнуюформулой,полученнойврезультатеподстановки в формулу ( , ,..., )вместо переменных , ,..., чисел ,  ,..., соответ-

ственно, а на остальные места - . Не ограничивая общности рассуждений, можно считать, что

{ ,0,1, } можно задать конъюнкцию.

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

5

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

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

Рассуждаемот противного: предположим, чтонайдется классПоста (обозначим его ),

Следовательно, ( ) ( ). т.е. = . Но этого не может быть, поскольку есть булевы функции, не принадлежащие ни одному из классов Поста (например, штрих Шеффера). Получили противоречие, следовательно, наше предположение было неверным.

Достаточность. Пусть найдутся функции , , , , из такие, что ,, , , . Покажем, что отрицаниеи конъюнкцию можно реализоватьформулами над множеством , , , , . Схема построения соответствующих формул представлена на рис. 2.6.

6

xy, x

Рис. 2.6.

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

Задачи повышенной сложности

2.34.Используя теорему о полноте двух систем, доказать, что { ↓ } полная система.

2.35.Опираясь на доказательство леммы о функции, не сохраняющей 0, реализовать формулой над множеством = (10010000) либо 1, либо отрицание.

2.36.Опираясь на доказательство леммы о функции, не сохраняющей 1, реализовать формулой над множеством = (00010000) либо 0, либо отрицание.

2.37.Опираясь на доказательство леммы о несамодвойственной функции, реализовать формулой над множеством {(01101011), } константы 0 и 1.

2.38.Опираясь на доказательство леммы о немонотонной функции, реализовать формулой над множеством {(01101011),0,1} отрицание.

2.39.Опираясьнадоказательстволеммыонелинейнойфункции,реализоватьформулой над множеством {(11100100), 0, 1} конъюнкцию.

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

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

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

а) классы Поста являются предполными; б) других предполных классов, кроме классов Поста, нет.

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

Ответы и указания к упражнениям

7

Тема 7 «Полнота системы булевых функций» Олейник Т.А., 2020

2.30. а) Полная; б) Неполная. Решение. а) Последовательно заполняем столбцы таблицы Поста данной системы (табл. 3). Поскольку для каждого из классов Поста можно указать функцию системы, ему не принадлежащую, то заключаем, что система полная.

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

2.31. а) Имеем один базис: { 1,  , }. Указание. Проанализируйте таблицу Поста

б) Имеем два базиса: {|} и { ↓ } . Указание. Проанализируйте таблицу Поста данной системы (табл. 6).

8