Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.nature.web.ru/db/msg.html?mid=1158346&uri=node2.html
Дата изменения: Unknown
Дата индексирования: Mon Apr 11 12:34:11 2016
Кодировка: Windows-1251
Научная Сеть >> Н.В.Верещагин, А.Шень Логические формулы и схемы (статья из "Математическое просвещение", сер.3. Вып. 4.)
Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Обратите внимание!
 
  Наука >> Математика >> Алгебра, математическая логика и теория чисел | Популярные статьи
 Написать комментарий  Добавить новое сообщение
 См. также

Популярные статьиМ.Н. Вялый "Сложность вычислительных задач": ШеньВерещагин

Next: 3. Схемы из функциональных Up: Логические формулы и схемы Previous: 1. Высказывания и операции Contents:


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

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

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

Доказательство. Проще всего пояснить это на примере. Пусть, например, булева функция $\varphi(p,q,r)$ задана таблицей 4.


Таблица 4. Таблица значений булевой функции и задающая ее формула
\begin{table}\begin{displaymath} \begin{array}{\vert c\vert c\vert c\vert c\vert... ...\land &q &\land r&) &\phantom{\lor} \\ \end{array}\end{displaymath}\end{table}


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

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

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

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

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

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

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

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

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

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

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

Заметим, что при доказательстве теоремы 3 мы обошлись без импликации. Это и не удивительно, так как она выражается через дизъюнкцию и отрицание:

\begin{displaymath} (p\to q) \leftrightarrow (\lnot p \lor q) \end{displaymath}

(проверьте!). Вообще- то мы могли бы обойтись только конъюнкцией и отрицанием, так как

\begin{displaymath} (p\lor q) \leftrightarrow \lnot(\lnot p \land \lnot q), \end{displaymath}

или только дизъюнкцией и отрицанием, так как

\begin{displaymath} (p\land q) \leftrightarrow \lnot(\lnot p \lor \lnot q), \end{displaymath}

(обе эквивалентности вытекают из законов де Моргана; их легко проверить и непосредственно). Можно сказать, что система связок $\land, \lnot$, а также система связок $\lor, \lnot$ являются полными. (По определению это означает, что с их помощью можно записать любую булеву функцию).

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

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

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

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

В принципе мы не обязаны ограничиваться четырьмя рассмотренными связками. Любая булева функция может играть роль связки. Например, можно рассмотреть связку $(p \texttt{ notand } q)$, задаваемую эквивалентностью

\begin{displaymath} (p \texttt{ notand } q) \leftrightarrow \lnot(p\land q) \end{displaymath}

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

Другая интересная полная система связок - это сложение по модулю $2$, конъюнкция и константа $1$ (которую можно считать $0$- арной связкой, задающей функцию от нуля аргументов).

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

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

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

Доказательство. Чтобы доказать существование искомого полинома, можно сослаться на известное из алгебры утверждение, что всякая функция с аргументами из конечного поля (в данном случае это двухэлементное поле вычетов по модулю $2$) задается полиномом. Правда, в алгебре понятие полинома более общее, разрешены степени. Но это не важно, так как переменные принимают лишь значения $0$ и $1$ и потому степени роли не играют.

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

Можно и не ссылаться на сведения из алгебры, а дать явную конструкцию. Это удобно сделать индукцией по $n$. Пусть мы уже умеем представлять любую булеву функцию от $n-1$ аргументов с помощью полинома. Тогда $\varphi(p_1,\dots,p_n)$ можно представить как
\begin{align*} \varphi(p_1,\dots,p_n) =& \varphi(0, p_2,\dots,p_{n})+{}\\ &{ }+[\varphi(0,p_2,\dots,p_{n})+ \varphi(1,p_2,\dots,p_{n})]p_1 \end{align*}
(проверьте, что все сходится). Остается заметить, что правую часть можно представить полиномом по предположению индукции.

Для единственности также есть другое доказательство: пусть два многочлена равны. Тогда их сумма (или разность - вычисления происходят по модулю $2$) является ненулевым многочленом (содержит какие-то мономы), но тождественно равна нулю. Так не бывает, и это легко доказать по индукции. В самом деле, любой многочлен $A(p_1,\dots,p_n)$ можно представить в виде

\begin{displaymath} A(p_1,\dots,p_n)=B(p_2,\dots,p_n)+p_1C(p_2,\dots,p_n), \end{displaymath}

где $B$ и $C$ - многочлены от меньшего числа переменных. Подставляя сначала $p_1=0$, а затем $p_1=1$, убеждаемся, что многочлены $B$ и $C$ равны нулю во всех точках, и потому (согласно предположению индукции) равны нулю как многочлены (не содержат мономов). $ \qedsymbol$

Задача 11.   Назовем мультилинейной функцией полином от $n$ переменных, в котором все показатели степеней равны либо $0$, либо $1$. (Таким образом, каждый моном в ней есть произведение коэффициента и некоторого набора переменных без повторений). Пусть $F$ - произвольное поле. Будем рассматривать $\bbB =\{0,1\}$ как подмножество $F$. Докажите, что всякая булева функция $\bbB ^n\to\bbB $ однозначно продолжается до мультилинейной функции $F^n\to F$, и коэффициенты в мультилинейной функции будут целыми.

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

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

  • монотонные функции;
  • функции, сохраняющие нуль;
  • функции, сохраняющие единицу;
  • линейные функции;
  • самодвойственные функции.
(Функция $f$ монотонна, если она монотонно неубывает по каждому из своих аргументов. Функция $f$ сохраняет нуль/единицу, если $f(0,\dots,0)=0$ (соответственно $f(1,\dots,1)=1$). Функция $f$ линейна, если она представима многочленом, в котором все мономы содержат не более одной переменной. Наконец, функция $f$ называется самодвойственной, если $f(1-p_1,\dots,1-p_n)=1-f(p_1,\dots,p_n)$.)

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

Next: 3. Схемы из функциональных Up: Логические формулы и схемы Previous: 1. Высказывания и операции Contents:


Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования