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

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

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

функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
самодвойственныые функции [math]S[/math] ,
монотонные функции [math]M[/math] ,
линейные функции [math]L[/math] .

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

Класс функций сохраняющих ноль [math]T_0[/math] .

Определение:

Говорят, что функция сохраняет ноль, если [math]f(0, 0, \ldots, 0) = 0[/math] .

Класс функций сохраняющих единицу [math]T_1[/math] .

Определение:

Говорят, что функция сохраняет единицу, если [math]f(1, 1, \ldots, 1) = 1[/math] .

Класс самодвойственных функций [math]S[/math] .

Определение:

Говорят, что функция самодвойственна (англ. self-dual), если [math]f(\overline,\ldots,\overline)=\overline[/math] . Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.

Класс монотонных функций [math]M[/math] .

Определение:

Говорят, что функция монотонна (англ. monotonic function) , если [math]\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\ldots,a_n)\leqslant f(b_1,\ldots,b_n)[/math] .

Класс линейных функций [math]L[/math] .

Определение:

Говорят, что функция линейна (англ. linear function), если существуют такие [math]a_0, a_1, a_2, \ldots, a_n[/math] , где [math]a_i \in \<0, 1\>, \forall i=\overline<1,n>[/math] , что для любых [math]x_1, x_2, \ldots, x_n[/math] имеет место равенство: [math]f(x_1, x_2, \ldots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\ldots\oplus a_n\cdot x_n[/math] .

Количество линейных функций от [math]n[/math] переменных равно [math]

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

Формулировка и доказательство критерия Поста

Необходимость.

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора [math]K[/math] входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор [math]K[/math] не мог бы быть полным.

Достаточность.

Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным.

Рассмотрим функцию, не сохраняющую ноль — [math]f_0[/math] (то есть функцию, для которой [math]f_0(0) = 1[/math] ). Тогда [math] f_0(1)[/math] может принимать два значения:
1. [math]f_0(1) = 1[/math] , тогда [math]f_0(x, x, x, \ldots, x) = 1[/math] .
2. [math]f_0(1) = 0[/math] , тогда [math]f_0(x, x, x, \ldots, x) = \neg x[/math] .
1. [math]f_1(0) = 0[/math] , тогда [math]f_1(x, x, x, \ldots, x) = 0[/math] .
2. [math]f_1(0) = 1[/math] , тогда [math]f_1(x, x, x, \ldots, x) = \lnot x[/math] .
Таким образом, возможны четыре варианта:
- Мы получили функцию [math] \neg [/math] .
Используем несамодвойственную функцию [math]f_s[/math] . По определению, найдется такой вектор [math]x_0[/math] , что [math]f_s(x_0) = f_s(\lnot x_0)[/math] . Где [math]x_0 = (x_<01>, x_<02>, \ldots, x_<0k>)[/math] .

Рассмотрим [math]f_s(x^>, x^>, \ldots, x^>)[/math] , где либо [math]x^> = x[/math] , при [math]x_ <0i>= 1[/math] . Либо [math]x^> = \lnot x[/math] , при [math]x_ <0i>= 0 [/math] . Нетрудно заметить, что [math]f_s(0) = f_s(1) \Rightarrow f_s = \operatorname [/math] . Таким образом мы получили одну из констант.
- Мы получили [math] \neg [/math] и [math]0 \Rightarrow[/math] имеем константу, равную [math]1[/math] , поскольку [math]\lnot 0 = 1[/math] .
- Мы получили [math] \neg [/math] и [math]1 \Rightarrow[/math] имеем константу, равную [math]0[/math] , поскольку [math]\lnot 1 = 0[/math] .
- Мы получили [math]1[/math] и [math]0[/math] .
Рассмотрим немонотонную функцию [math]f_m[/math] . Существуют такие [math]x_1, x_2, \ldots, x_n[/math] , что [math]f_m(x_1, x_2, \ldots, x_, 0 , x_, \ldots, x_n) = 1[/math] , [math]f_m(x_1, x_2, \ldots, x_, 1 , x_, \ldots, x_n) = 0[/math] , зафиксируем все [math]x_1, x_2, \ldots, x_n[/math] , тогда [math]f_m(x_1, x_2, \ldots, x_, x, x_, \ldots, x_n)= \lnot x[/math] .

В итоге имеем три функции: [math] \neg [/math] , [math]0[/math] , [math]1[/math] .

Используем нелинейную функцию [math]f_l[/math] . Среди нелинейных членов [math]f_l[/math] (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем [math]x_1[/math] и [math]x_2[/math] . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде [math]g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus

1][/math] , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).

Рассмотрим несколько вариантов:
1[/math] . Возьмем отрицание от [math]g_l[/math] и член [math]\oplus

В итоге получим функцию [math] \neg [/math] , а также либо функцию [math] \wedge [/math] , либо функцию [math] \vee [/math] . Поскольку функцию [math] \wedge [/math] можно выразить через [math] \vee [/math] и [math] \neg [/math] , а функцию [math] \vee [/math] через [math] \wedge [/math] и [math] \neg [/math] , то мы получили базис [math] \wedge [/math] , [math] \vee [/math] , [math] \neg [/math] . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде [math]x \land \lnot x[/math] .

Примеры

Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math] , [math]T_1[/math] , [math]S[/math] , [math]M[/math] , [math]L[/math] .

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

Широко известны такие полные системы булевых функций:
- [math]\left\<\land,\lor,\neg\right\>[/math] (конъюнкция, дизъюнкция, отрицание);
- [math]\left\<\land,\oplus,1\right\>[/math] (конъюнкция, сложение по модулю два, константа один).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

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

Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]\left\<\oplus,1\right\>[/math] можно назвать базисом класса линейных функций.

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

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

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

Другие примеры решений о булевых функциях:
- Булевы формулы
- Таблицы истинности
- КНФ, ДНФ, СДНФ, СКНФ, полином Жегалкина
- Минимизация ДНФ булевых функций
Задачи и решения о классах Поста и полноте

Задача 1. Является ли полной система булевых функций, состоящая из дизъюнкции и импликации?

Задача 2. Доказать полноту (или неполноту) приведенной системы булевых функций.

$$ f_1=x_1 \wedge x_2,\, f_2=0, \, f_3=x_1 \sim x_2.$$

Задача 3. Определить, к каким классам Поста относится $F = \neg x1 x3 \vee x1 \neg x3$, добавить (если это необходимо) к $F$ элементарные функции, чтобы полученное множество было полным.

Задача 4. Является ли полной система функций?

Задача 5. а) Используя эквивалентные преобразования получить тупиковую ДНФ;
б)Построить функционально полную систему функций так, чтобы эта система была базисом и содержала $f (x, y, z, p)$

$$f (x, y, z, p)= \bar p \downarrow y \to z \vee p \Leftrightarrow y \oplus z |x \Leftarrow p$$

Задача 6. Проверить леммы о нелинейной, немонотонной и несамодвойственной функциях для функции

Задача 7. Даны функции $f$ (таблица 2) и $w$ (таблица 3).
а) Вычислить таблицу значений функции $f$.
б) Найти минимальные ДНФ функций $f$ и $w$.
в) Выяснить полноту системы $\$. Если система не полна, дополнить систему функцией $g$ до полной системы.
г) Из функциональных элементов, реализующих функции полной системы $\$ или $\$, построить функциональные элементы, реализующие базовые функции $\<\vee, \wedge, \neg, 0, 1\>$

$$ f=((x_3 \to (x_1\sim x_2))\oplus (\overline \to \overline))\to (\overline|\overline),\\ w = (0, 1, 1, 0, 0, 1, 0, 1). $$

Решение задач на заказ

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

Классы Поста. Полнота системы функций

Математик Эмиль Пост ввел следующие замкнутые классы булевых функций:
- $T_0$ — Сохраняющие константу 0
- $T_1$ — Сохраняющие константу 1
- $S$ — Самодвойственные функции
- $M$ — Монотонные функции
- $L$ — Линейные функции
Теорема Поста (о полноте): Набор булевых функций $K$ является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов $S,M,L,T0,T1$.

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

Лекции 7, 8

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Системы булевых функций

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

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

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

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

Теорема 11.2. Следующие системы булевых функций являются полными:

Доказательство. Полнота первой системы доказана в теореме 10.5. Это можно использовать для доказательства полноты остальных систем, приведенных в теореме.

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

Аналогично, для проверки полноты системы нужно выразить конъюнкцию через дизъюнкцию и отрицание. Соответствующее тождество известно (см. теорему 9.5, пункт а).

Полнота системы вытекает из полноты системы и тождества теоремы 9.5, пункт б, выражающего дизъюнкцию через конъюнкцию и отрицание, а полнота системы — из полноты системы и тождества теоремы 9.5, пункт в, выражающего дизъюнкцию через импликацию.

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

Итак, теорема доказана.

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

Специальные классы булевых функций

Говорят, что булева функция сохраняет 0, если . Обозначим — класс всех булевых функций, сохраняющих 0.

Говорят, что булева функция сохраняет 1, если . Обозначим — класс всех булевых функций, сохраняющих 1.

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

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

где — постоянные, равные либо 0, либо 1. Символом играют главную роль при описании полных систем булевых функций. В следующей теореме устанавливаются два важных свойства этих классов и одновременно рассматриваются примеры функций, принадлежащих и не принадлежащих каждому из них.

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

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

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

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

Аналогично проверяется замкнутость класса , то есть

то есть , и значит .

Пусть далее и и . Тогда

Наконец, пусть , то есть, например,

то есть .Теорема доказана.

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

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

Эта теорема доказана американским математиком Э. Постом в 1921 г.

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

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

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

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

Начнем с , для которой . Введем функцию . Для нее имеем: или 1. Следовательно, или .

Аналогично, из , для которой , строим функцию . Для нее имеем: или 0. Следовательно, или .

Таким образом, получаем одну из следующих четырех пар функций: и (1); и 0 (2); и 1 (3); 0 и 1 (4).

В каждом из случаев (2) и (3) имеем тогда по три функции (например, если есть функции и получается как (то есть ). Для нее , то есть

для некоторого набора из нулей и единиц. Следовательно, для этого набора

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

Следовательно, — константа. Поскольку в нашем распоряжении имеется отрицание , то из этой константы (0 или 1) можно получить и другую константу (1 или О соответственно). Итак, в случае (1) имеем функции .

Рассмотрим случай (4). Здесь к константам 0 и 1 необходимо получить функцию . Для этого привлечем немонотонную функцию (то есть ). Ее немонотонность означает: найдутся такие наборы из нулей и единиц и , что

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

Тогда ясно, что . Следовательно, должно быть . Значит, .

Итак, из данной системы функций с помощью суперпозиций нами сконструированы функции .

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

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

Заметим, что мы можем подставлять 0 вместо , так как функция 0 нами уже получена. Тогда ясно, что

Следовательно, или . Заметим, что . Значит, можно представить в виде , где или 1. Кроме того, ясно, что функцию одного аргумента можно представить в виде линейного полинома Жегалкина: . Таким образом, имеет вид:

Рассмотрим всевозможные случаи для коэффициентов .

Если , то рассмотрим функцию

(Заметим, что мы можем подставлять вместо , так как функция "отрицание" нами уже получена.)

Если , то рассмотрим функцию

Если же , то (штрих Шеффера).

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