Нормальные формы

В предыдущих уроках этого раздела формулам было придано значение: урок о семантике логики высказываний продолжил каждую оценку на все формулы; урок о семантическом следовании и эквивалентности определил эквивалентность $\varphi \eqsem \psi$ и доказал семантическую замену; урок об обобщённых законах де Моргана и дистрибутивности распространил эти законы на конъюнкции и дизъюнкции из $n$ формул; а урок о функциональной полноте показал, что всякая функция истинности представляется некоторой формулой. Однако функция истинности представляется бесконечным числом формул, которые могут сильно отличаться друг от друга: $(v_1 \rightarrow v_2)$, $\neg(v_1 \wedge \neg v_2)$ и $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ суть три имени одного и того же. Если это так, то в каждом классе эквивалентности стоит выбрать представителя фиксированного вида, который читается без усилий и на котором некоторые вопросы решаются одним взглядом. Это и есть нормальные формы.

Литералы, дизъюнкты и нормальные формы

Напомним из урока об обобщённых законах обозначение конъюнкции и дизъюнкции $n$ формул, определённое рекурсией с ассоциированием влево; конъюнкция и дизъюнкция одной формулы есть сама эта формула.

В том же уроке было доказано, что порядок и группировка членов не меняют формулу с точностью до эквивалентности (обобщённая ассоциативность и независимость от порядка и от повторений); поэтому мы будем писать также $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ без скобок, подразумевая группировку влево.

Литерал есть переменная $v_n$, которая называется положительным литералом, или отрицание $\neg v_n$ переменной, которое называется отрицательным литералом. Противоположный литералу $\ell$ литерал, который мы записываем как $\ell^{*}$, есть литерал той же переменной с другим знаком:

Из определения следует, что $(\ell^{*})^{*} = \ell$. Два литерала образуют контрарную пару, если один из них противоположен другому, как $v_3$ и $\neg v_3$.

Дизъюнкт есть дизъюнкция литералов, $\bigvee_{j=1}^{k} \ell_j$, а элементарная конъюнкция есть конъюнкция литералов, $\bigwedge_{j=1}^{k} \ell_j$, причём $k \geq 1$ в обоих случаях; поэтому один литерал есть одновременно дизъюнкт и элементарная конъюнкция. Говорят, что литерал входит в дизъюнкт или в элементарную конъюнкцию, если он есть один из их $\ell_j$.

Формула находится в дизъюнктивной нормальной форме, если она есть дизъюнкция элементарных конъюнкций, и в конъюнктивной нормальной форме, если она есть конъюнкция дизъюнктов; то есть если она имеет соответственно один из двух следующих видов, где $m$ и $k_1, \ldots, k_m$ суть натуральные числа и каждое $\ell_{i,j}$ есть литерал:

Будем говорить, что $\Phi$ есть дизъюнктивная нормальная форма формулы $\varphi$, если она находится в дизъюнктивной нормальной форме и $\varphi \eqsem \Phi$, и так же для конъюнктивной. Длины $k_i$ могут меняться от одной конъюнкции (или дизъюнкта) к другой: требование одинакового числа литералов во всех заставило бы заполнять повторениями и ничего бы не добавило.

Стоит задержаться на том, что значит «находиться в нормальной форме». Это свойство цепочки кружков и дисков, а не её значения: урок об индукции по натуральным числам и по формулам доказал однозначность разбора, так что вопрос, является ли формула дизъюнкцией и чего именно, имеет единственный ответ. Однако официальные сокращения приводят к тому, что некоторые формулы находятся в нормальной форме, не выглядя так. Импликация $(v_1 \rightarrow v_2)$ определяется как $(\neg v_1 \vee v_2)$: дело не в том, что она эквивалентна этому дизъюнкту, а в том, что она есть та же самая цепочка, и поэтому уже находится в нормальной форме. Ещё неожиданнее двойное отрицание. По определениям $\neg$ и $\vee$ цепочка $(\varphi \vee \varphi)$ есть $\neg(\varphi \downarrow \varphi)$, то есть $\neg\neg\varphi$; откуда $\neg\neg v_1$ не есть литерал, но есть, буква в букву, дизъюнкт $(v_1 \vee v_1)$.

Значение конъюнкций и дизъюнкций

Из урока о семантике берутся значения производных связок: $v(\neg\varphi) = 1 - v(\varphi)$; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$, что равно $1$ тогда и только тогда, когда обе равны $1$; и $v(\varphi \vee \psi) = 0$ тогда и только тогда, когда обе равны $0$. Урок об обобщённых законах де Моргана и дистрибутивности распространил их на $n$ формул индукцией по числу членов в лемме о значении: для всякой оценки $v$ конъюнкция $\bigwedge_{i=1}^{n} \varphi_i$ принимает значение $1$ при $v$ тогда и только тогда, когда каждая $\varphi_i$ принимает значение $1$ при $v$, а дизъюнкция $\bigvee_{i=1}^{n} \varphi_i$ принимает значение $1$ при $v$ тогда и только тогда, когда некоторая $\varphi_i$ принимает значение $1$ при $v$. Эта лемма, которая здесь цитируется без повторения доказательства, есть инструмент, которым вычисляется значение любой нормальной формы.

Второй случай легко упустить: при отрицании нормальной формы тянет написать $\neg\ell_{i,j}$ вместо литерала, а $\neg\neg v_n$ литералом не является. Именно двойное отрицание возвращает результат в шаблон.