Языки и исчисления

Развитие математики идёт по пути придумывания новых символов и правил получения слов, состоящих из этих символов. По большому счёту, математики постоянно играют в различные разновидности одной и той же игры. Эта игра называется "Игрой в слова". Символы и правила Игры меняются, но часто оказываются причудливо связанными с предыдущими вариантами игры. Иногда выясняется, что целое множество, ранее не связанных между собой игр, можно объединить в одну с очень простыми правилами. Придумывание подобных суперигр доставляет математику наибольшее удовольствие. Любая формальная теория является некоторым языком со своим алфавитом, словами и способами получения (вывода) новых слов. Определим детальнее эти понятия.

Язык

Алфавит — непустое, конечное множество \(\Sigma\) символов. Символом может быть что угодно, лишь бы мы могли однозначно отличать один символ от другого. Понятие символа не столь тривиально, как кажется на первый взгляд. Один и тот же символ в различных местах "текста" может иметь несколько различное "написание". Например, в тексте \(ab{\mathrm a}ba\), третья буква чуть отличается от первой и последней. Однако, мы можем договориться считать их одним и тем же символом. Ещё большее разнообразие начертаний символов возникает в рукописных текстах. Таким образом, должен быть способ не только различать, но и надёжно отождествлять символы. Игры в которых символы слов имеют вероятностное значение, обычно не рассматриваются, хотя и очень любопытны. Например, в микромире существуют тождественные частицы, при помощи которых можно кодировать символы. Однако их положение в "тексте" иногда принципиально вероятностное.

Слово — конечная цепочка (упорядоченная последовательность) символов. Число символов в слове называется его длиной. Слово может быть и пустым (нулевой длины). Такое слово часто обозначается как \(\varepsilon\). Из двух слов можно получить третье при помощи конкатенации. Так, если \(a_i\) и \(b_i\) — символы, а \(\alpha=a_1a_2...a_n\) и \(\beta=b_1b_2...b_m\) — слова, то их конкатенация равна \(\alpha\beta=a_1a_2...a_nb_1b_2...b_m\). Слово \(\alpha\) — это префикс (начало) слова \(\alpha\beta\), а \(\beta\) — его суффикс (окончание). Обращение слова \(\alpha^R\) — это слово с обратным порядком букв: \(a_n...a_2a_1\). При этом \((\alpha\beta)^R=\beta^R\alpha^R\) и если \(\alpha^R=\alpha\), то такое симметричное слово называется палиндромом.

Множество всех слов из алфавита \(\Sigma\) обозначают \(\Sigma^*\). К этому множеству принадлежит и пустое слово \(\varepsilon\). Так как алфавит — это конечное множество и слова имеют конечную длину, множество \(\Sigma^*\) счётно.

Язык — это некоторое подмножество \(\mathbb{L}\) множества всех слов: \(\mathbb{L}\subseteq\Sigma^*\). Пустое слово \(\varepsilon\) может как присутствовать в языке, так и отсутствовать. Язык, не содержащий слов, как обычно, обозначается символом \(\varnothing\) или пустыми скобками \(\{\}\). Язык из одного пустого слова — это \(\{\varepsilon\}\) и т.д. Предполагается, что существуют правила, которые позволяют отличать слово, входящее в язык, от не принадлежащего ему слова.

Правильно построенные формулы

\(\diamond\) В качестве примера, приведём язык \(\mathbb L_P\) правильно построенных формул логики высказываний (propositions). Его алфавит — это множество символов: \[ \Sigma=\{\neg,~\&,~\vee,~\to,~\equiv,~(,~),~X\}. \] Запятая не является символом, а служит только разделителем. Слово, принадлежащее языку, будем называть формулой и зададим по индукции:

Слова \((X)\), \((XX)\),... — это элементарные высказывания (не содержащие логических связок). Обычно их обозначают отдельными буквами \(A\), \(B\),... из начала алфавита. Впрочем, для введения счётного числа высказываний достаточно одного символа \(X\). Произвольные формулы в книге обозначаются буквами из конца алфавита: \(P,Q,R,...\) Они состоят из элементарных высказываний и логических связок. \(\square\)

Операции с языками

Так как языки являются множествами слов, к ними можно применять стандартные множественные операции (объединение, пересечение, вычитание и т.п.) для получения новых языков. Кроме этого, возможны и специфические операции. Например, конкатенация языков \(\mathbb A\) и \(\mathbb B\) — это язык \(\mathbb L=\mathbb A\cdot \mathbb B=\{\alpha\beta~|~\alpha\in \mathbb A,~~\beta\in\mathbb B\}\), т.е. множество всех конкатенаций слов обоих языков.

\(\diamond\) Пусть есть два конечных языка, содержащих по 2 не пустых слова: \(\mathbb A=\{0,~ 01\}\) и \(\mathbb B=\{1,~ 11\}\). Тогда \(\mathbb A\cdot \mathbb B=\{01,~ 011,~ 0111\}\). При этом слово \(011\in \mathbb A\cdot \mathbb B\) получается двумя способами: \(0\cdot 11\) и \(01\cdot 1\) \(\square\).

Несложно проверить, что конкатенация языков удовлетворяет следующим тождествам: \[ (\mathbb A\cdot \mathbb B )\cdot \mathbb C = \mathbb A \cdot (\mathbb B\cdot \mathbb C ),~~~~~~~~ \mathbb A \cdot\{\varepsilon\} = \{\varepsilon\} \cdot \mathbb A = \mathbb A. \] Считается, что конкатенация с пустым множеством \(\varnothing\) равна \(\varnothing\). Степень языка \(\mathbb L^n\) это \(n\) конкатенаций \(\mathbb L\cdot...\cdot \mathbb L\) и \(\mathbb L^0=\{\varepsilon\}\) Замыканием Клини \(\mathbb L^*\) называют объединение всех степеней языка \(\mathbb L^*=\mathbb L^0\cup \mathbb L^1\cup \mathbb L^2\cup...\)

Модель языка

Модель языка — это отображение \(\mathbb{L}\mapsto \mathbb{M}\) всех слов языка \(\mathbb{L}\), на некоторое множество \(\mathbb{M}\), т.е. с каждым словом связывается некоторый элемент множества \(\mathbb{M}\). Если задана модель, то говорят, что введена семантика ("смысл") слов языка. Обычно элементов в множестве \(\mathbb{M}\) существенно меньше, чем слов в языке (хотя это и не обязательно). Бинарной моделью является отображение на множество из двух элементов, которые можно, например, обозначать как \(\F\) и \(\T\).

\(\lhd\) Примером бинарной модели является бинарная логика. Для построения такой модели, необходимо каждому элементарному высказыванию из счётного множества \(\mathbb{V}=\{(X),(XX),...\}\) "присвоить" значение \(\F\) или \(\T\). Затем задать таблицы истинности для каждой логической связки. В результате будет определено отображение любого слова языка \(\mathbb L_P\) (правильно построенной формулы) на множество \(\mathbb M = \{\F,\T\}\). \(\square\)

В принципе, для языка \(\mathbb L_P\) можно построить модель с множеством \(\mathbb M\), состоящим из любого числа элементов. Так, многозначные логики предполагают, что значение высказывания может принимать, например, три значения (нет, возможно, да). Могут быть нечёткие логики с непрерывным значением истинности в интервале \([0...1]\) и т.д. Всё это различные модели языка \(\mathbb L_P\). Далее, в соответствии с данным на определением, мы будем называть бинарную модель интерпретацией языка.

Если формула (слово \(\mathbb L_P\)) в данной интерпретации \(\mathbb{L}_P\mapsto\mathbb{M}=\{\F,\,\T\}\) соответствует \(\T\), то говорят, что она истинная. Это обозначается таким образом: \(\Rightarrow_\mathbb{M} F\). Тавтология истинна в любой интерпретации: \(\Rightarrow F\).

Логическое следование

Формула \(F\) логически следует из формул \(\Gamma=\{\Gamma_1,\Gamma_2,...\}\), т.е. \(\Gamma\Rightarrow F\), если для всякой интерпретации \(\mathbb{M}\), когда любая \(\Gamma_i\) истинна: \(\Rightarrow_\mathbb{M} \Gamma_i\), то истинна и формула: \(\Rightarrow_\mathbb{M} F\). Вместо символа \(\Rightarrow\) часто также используют символ \(\models\). Ранее было показано, что

Кроме логического следствия (определяемого при помощи интерпретаций), важную роль играет формальный вывод, который будет обозначаться символом \(\vdash\). В выводе из одних формул \(\Gamma_1,...,\Gamma_n\) по некоторым правилам получаются другие формулы: \(\Gamma_1,...,\Gamma_n\,\vdash F\). При этом логическая интерпретация формул роли не играет. Вывод — это просто алгоритм получения одних слов из других, чтобы эти слова не обозначали. Дадим соответствующие определения.

Исчисление

Исчислением называют язык \(\mathbb{L}\), на алфавите \(\Sigma\), в котором задано множество слов (формул) \(\mathbb{A}=\{A_1,...,A_m\}\), называемых аксиомами и правила вывода \(\mathbb{R}\) (получения) новых формул. Правило вывода — это предписание, при помощи которого из \(n\) формул определённого вида получается новая формула. Формально, правило вывода с \(n\) посылками, это \(n+1\) -местное отношение \(\mathbb{R}\subseteq \mathbb{L}\times \mathbb{L}\times ... \times \mathbb{L}\) (\(n+1\) раз): \[ \Gamma_1,...,\Gamma_n~~\vdash~F. \] Обычно последовательность посылок \(\Gamma_1,...,\Gamma_n\) в правиле роли не играет.

Вывод

Выводом (доказательством) формулы \(F\) в данном исчислении называется последовательность формул \(F_1\,,...,\,F_m\), в которой каждая формула является либо аксиомой, либо получена по некоторому правилу вывода из предшествующих формул, а последняя формула \(F_m\) — это \(F\).

\(\diamond\) Пусть есть алфавит \(\Sigma=\{a~b\}\) из двух символов. Определим исчисление с четырьмя аксиомами: \[ (\mathbf{A_1}):~a,~~~~~~(\mathbf{A_2}):~b,~~~~~({\bf A_3}):~aa,~~~~~(\mathbf{A_4}):~bb \] и двумя правилами вывода: \[ (\mathbf{R_a}):~W~\vdash~aWa,~~~~~~~~~(\mathbf{R_b}):~W~\vdash~bWb, \] где \(W\) — любое, ранее выведенное, слово. Выведем, например, в этом исчислении слово \(babbab\): \[ {~~~\,bb\,~~~}_{1:~\mathbf{A_4}},~~~{~~\,abba\,~~}_{2:~\mathbf{R_a}(1)}, ~~~{~\,babbab\,~}_{3:~\mathbf{R_b}(2)}. \] Первое слово вывода (номера рядом с формулой) — это аксиома \((\mathbf{A_4})\). Для получения второго слова, применено правило \((\mathbf{R_a})\), в котором в качестве \(W\) взято первое выведенное слово. Аналогично, в конце применяется правило \((\mathbf{R_b})\). Предлагается проверить, что в этом языке выводятся только палиндромы (слова одинаково читающиеся слева-направо и справа-налево). Зачем нужны \((\bf{A_3})\) и \((\bf{A_4})\)? \(\square\)

Исчисления делают математические рассуждения формальными на столько, на сколько это по-видимому вообще возможно. Подобные цепочки слов (в \(\mathbb L_P\) формул) можно загружать в компьютер и он, "не понимая" смысла символов и слов, может проверить корректность вывода и даже самостоятельно такие выводы находить.