Функциональная полнота

Функции истинности

Урок о семантике логики высказываний сопоставил каждой формуле при каждой оценке истинностное значение и показал, что это значение зависит лишь от значений входящих в неё переменных; откуда всякая формула с $n$ переменными имеет таблицу истинности из $2^{n}$ строк. Вопрос этого урока обратный. Пусть дана произвольная таблица, то есть столбец единиц и нулей, произвольно выписанный рядом с $2^{n}$ строками: найдётся ли формула, для которой она является таблицей? Если это так для всякой таблицы, то в языке нет выразительных пробелов: всё, что можно сказать об истинностном значении $n$ высказываний в зависимости от их значений, говорится формулой. А поскольку в этом курсе всякая составная формула есть стрелка Пирса, ответ скажет также, достаточно ли одной связки, чтобы сказать всё.

Что используется из предыдущих уроков

Оценка есть функция $v$ из множества переменных $\{v_1, v_2, \ldots\}$ в $\{0, 1\}$, где $1$ означает истину, а $0$ ложь; её продолжение на все формулы, которое тоже обозначается $v$, определено рекурсией: $v((\varphi \downarrow \psi)) = 1$ тогда и только тогда, когда $v(\varphi) = 0$ и $v(\psi) = 0$. Исходя из официальных сокращений, тот же урок вычислил в теореме о значениях производных связок значение каждой связки; записанные через суммы и произведения, эти значения таковы для всякой оценки $v$ и всяких формул $\varphi$ и $\psi$:

Кроме того, $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$, что равно $1$ тогда и только тогда, когда $v(\varphi) = v(\psi)$, и $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$, что равно $1$ тогда и только тогда, когда $v(\varphi) \neq v(\psi)$. Поскольку значения суть $0$ или $1$, квадрат значения равен самому значению, $v(\varphi)\,v(\varphi) = v(\varphi)$, а произведение значений равно $1$ тогда и только тогда, когда каждый множитель равен $1$; оба наблюдения будут использоваться без повторения. Используется также лемма о совпадении: если две оценки совпадают на переменных формулы $\varphi$, то есть на переменных, являющихся подформулами $\varphi$, они придают $\varphi$ одно и то же значение. Из урока о семантическом следовании и эквивалентности берётся семантическая эквивалентность: $\varphi \eqsem \psi$, когда $v(\varphi) = v(\psi)$ для всякой оценки $v$. Наконец, действует соглашение о буквах из урока о формализации: $p$, $q$ и $r$ обозначают переменные $v_1$, $v_2$ и $v_3$.

Функции истинности и их число

Пусть $n$ есть натуральное число. Строка из $n$ значений есть последовательность $a = (a_1, \ldots, a_n)$, в которой каждое $a_i$ равно $0$ или $1$; множество всех таких строк обозначается $\{0, 1\}^{n}$. Функция истинности от $n$ аргументов есть функция

которая сопоставляет каждой строке истинностное значение. Она задаётся таблицей: строки записываются в порядке таблицы, начиная с той, в которой все значения равны $1$ (для двух аргументов: $1\,1$, $1\,0$, $0\,1$, $0\,0$), и рядом с каждой строкой записывается её значение. Таким образом, функция истинности есть таблица истинности без формулы: правый столбец, в заголовке которого ничего не написано.

Формулы, представляющие функции

Формула и функция истинности связаны следующим образом. Если $\varphi$ есть формула, переменные которой находятся среди $v_1, \ldots, v_n$, то говорят, что $\varphi$ представляет функцию истинности $f$ от $n$ аргументов, если для всякой оценки $v$

то есть если таблица $\varphi$, записанная с переменными $v_1, \ldots, v_n$, есть таблица $f$. Условие на переменные не является мелочью: формула $(p \wedge q)$ не представляет никакой функции от одного аргумента, потому что её значение зависит не только от значения $p$.

Формул с переменными среди $v_1, \ldots, v_n$ бесконечно много, а функций лишь $2^{2^{n}}$; следовательно, многие формулы представляют одну и ту же функцию, и утверждение говорит, что это в точности формулы, эквивалентные друг другу. Остаётся узнать, всякая ли функция представляется некоторой формулой или же некоторые таблицы остаются без формулы, которая бы их имела.