Полные системы связок

Полные системы связок

Рассматриваемая нами система пропозициональных связок (, , , ) полна в следующем смысле:

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

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

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

Ясно, что аналогичная конструкция применима для любой таблицы (с любым числом переменных).

Для формул подобного вида есть специальное название: формулы в дизъюнктивной нормальной форме. Более подробно: литералом называется переменная или отрицание переменной, конъюнктом называется произвольная конъюнкция литералов, а дизъюнктивной нормальной формой называется дизъюнкция конъюнктов. В нашем случае в каждый конъюнкт входит  литералов (где — число переменных), а число конъюнктов равно числу строк с единицами и может меняться от нуля (тогда, правда, получается не совсем формула, а "пустая дизъюнкция", и ее можно заменить какой-нибудь всегда ложной формулой типа ) до (если булева функция всегда истинна).

5. Длина построенной в доказательстве теоремы 3 формулы зависит от числа единиц: формула будет короткой, если единиц в таблице мало. А как написать (сравнительно) короткую формулу, если в таблице мало нулей, а в основном единицы?

Иногда полезна конъюнктивная нормальная форма, которая представляет собой конъюнкцию дизъюнктов. Каждый дизъюнкт состоит из литералов, соединенных дизъюнкциями. Теорему 3 можно теперь усилить так:

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

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

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

6. Проведите второй вариант рассуждения подробно.

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

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

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

8. Докажите, что система связок полна. (Указание: как записать через них дизъюнкцию?)

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

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

10. Пусть — тавтология. Покажите, что найдется формула , которая включает в себя только общие для  и переменные, для которой формулы  и  являются тавтологиями. (Более общий вариант этого утверждения, в котором рассматриваются формулы с кванторами, называется леммой Крейга.)

В принципе мы не обязаны ограничиваться четырьмя рассмотренными связками. Любая булева функция может играть роль связки. Например, можно рассмотреть связку , задаваемую эквивалентностью  (словами:  ложно, лишь если  и  истинны). Через нее выражается отрицание (), после чего можно выразить конъюнкцию, а затем, как мы знаем, и вообще любую функцию. (Знакомые с цифровыми логическими схемами малого уровня интеграции хорошо знакомы с этим утверждением: достаточно большой запас схем И-НЕ позволяет реализовать любую требуемую зависимость выхода от входов.)

Другая интересная полная система связок — сложение по модулю , конъюнкция и константа  (которую можно считать -арной связкой, задающей функцию от нуля аргументов). Представленные в этой системе булевы функции становятся полиномами с коэффициентами в кольце вычетов по модулю . Идея рассматривать булевы функции как полиномы (оказавшаяся неожиданно плодотворной в последние годы) была высказана в 1927 г. российским математиком Иваном Ивановичем Жегалкиным.

Назовем мономом конъюнкцию любого набора переменных или константу  (которую естественно рассматривать как конъюнкцию нуля переменных). Название это естественно, так как при наших соглашениях ( обозначает истину, — ложь) конъюнкция соответствует умножению.

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

Теорема 5 (о полиномах Жегалкина). Всякая булева функция однозначно представляется таким полиномом.

Существование искомого полинома следует из теоремы 4, так как конъюнкция есть умножение, отрицание — прибавление единицы, а дизъюнкцию можно через них выразить (получится ). Надо только заметить, что степени не нужны: переменные принимают значения  и , так что  можно заменить на .

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

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

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

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

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

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

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

· монотонные функции;

· функции, сохраняющие нуль;

· функции, сохраняющие единицу;

· линейные функции;

· самодвойственные функции.

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

Если Вам понравилась эта лекция, то понравится и эта - 6 Нейронные сети.

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

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

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

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

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

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