Язык предикативной логики: алфавиты и цепочки символов

Начнём с одного символа

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

Теперь добавим второй символ

Если мы добавим второй символ к нашему алфавиту, письмо становится богаче, чем в предыдущем алфавите. Теперь мы можем наблюдать за тем, как символы упорядочиваются, например, если 0 и 1 — наши символы, мы можем отличить 01 от 10. Обе цепочки включают те же символы, но в разном порядке. Если самая длинная цепочка, которую мы можем написать, имеет длину N =1,2,3,\cdots, тогда мы можем написать 2^1=2 цепочки длиной 1, 2^2=4 цепочки длиной 2, 2^3=8 цепочки длиной 3, и так далее, в общем 2^N различных цепочек длиной N.

Упражнение: На листе бумаги записаны все различные цепочки, которые можно написать с использованием от 1 до N символов. Сколько всего цепочек записано на листе?

Решение:
Если S_N — сумма всех цепочек длиной 1, 2, 3, и так до N, то мы уже видели, что:

\displaystyle S_N=2^1 + 2^2 + \cdots +2^{N-1} + 2^N

Умножая предыдущее выражение на 2, получаем:

\displaystyle 2 S_N=2^2 + 2^3 + \cdots + 2^N + 2^{N+1}

И, следовательно:

\displaystyle S_N=2 S_N - S_N = 2^{N+1} - 2^1 = 2^{N+1} - 2

Таким образом, общее количество цепочек, записанных на листе, будет 2^{N+1} - 2.

Язык логики высказываний: Синтаксис

Мы видели, что с помощью двух символов мы можем отличать одну цепочку от другой по их длине и порядку расположения. Это важно, поскольку позволяет нам определить синтаксис для построенного нами алфавита. Синтаксис — это набор правил, которые разделяют цепочки символов на две категории: Выражения и Не-Выражения. Если \mathcal{L}_2 — это множество всех цепочек, которые можно построить с символами 0 и 1, тогда синтаксис \mathcal{L}_2 — это подмножество \mathcal{SL}_2\subset\mathcal{L}_2.

Мы можем определить множество \mathcal{SL}_2 со следующими рекурсивными правилами:

1. 00, 11 \in \mathcal{SL}_2
2. Если \alpha, \beta \in \mathcal{SL}_2, то 01\alpha\beta \in \mathcal{SL}_2

С этими двумя правилами мы можем строить выражения языка и проверять, является ли данная цепочка выражением языка. Язык — это алфавит с ассоциированной синтаксисом. Языку, представленному здесь, мы дадим название «Базовый язык двух символов», или \mathcal{B}_2.

Примеры проверки синтаксиса

Чтобы лучше понять эти идеи, давайте рассмотрим следующие примеры:

Пример: Поскольку 00 и 11 содержатся в \mathcal{SL}_2, то 010000, 010011, 011100 и 011111 принадлежат \mathcal{SL}_2; следовательно, они являются выражениями \mathcal{B}_2. Это доказывается применением только что введённых правил.

Конец примера \blacksquare

Упражнение: В предыдущем примере мы видели, как построить выражения из двух других элементарных выражений. Это само по себе не сложная задача; однако обратный процесс, который заключается в проверке, является ли данное выражение выражением, может оказаться немного более сложным.

Определите, используя правила синтаксиса, являются ли следующие последовательности выражениями \mathcal{B}_2:

1. {}012100

2. 101100

3. {}0100010000

4. 0101000011

5. {}01010000010000

6. 01010010000100101000011

Решение:
Прежде чем просмотреть решение, рекомендую сначала попробовать решить самостоятельно, а затем сравнить результаты. Если вы уже это сделали, тогда продолжайте 👍

1. 012100.

   Как мы видим, здесь присутствует символ 2, который не входит в \mathcal{L}_2; следовательно, эта последовательность не может содержаться в \mathcal{SL}_2 и, таким образом, не является выражением \mathcal{B}_2.

2. 101100.

   Здесь мы видим, что последовательность начинается с 10. Исходя из правил синтаксиса, мы можем сделать вывод, что все последовательности длиннее двух символов начинаются с 01, поэтому она не может быть выражением \mathcal{B}_2.

3. 0100010000

   Эта последовательность начинается с 01, поэтому она проходит первый тест. Отсюда следует, что для того чтобы она была выражением \mathcal{L}_2, необходимо, чтобы то, что выделено синим, могло быть однозначно разложено на два выражения.

   0100010000

   Если даже соблюдая правила синтаксиса разложение не является уникальным, то определенный синтаксис является неоднозначным и, следовательно, должен быть исправлен.
   

   Анализируя синюю часть, мы имеем следующие возможные разделения:

   00010000	00010000	00010000
   00010000	00010000	00010000
   00010000

   Наблюдая за зелёной частью и принимая во внимание тот факт, что если это не 00 и не 11, то оно должно начинаться с 01, чтобы быть выражением, можно сделать следующие выводы

   0{}0010000❌	00010000	000{}10000❌
   00010000❌	00010000❌	00010000❌
   00010000❌

   Единственная последовательность, которая проходит этот анализ, — это 00010000, где зелёная часть является выражением, а синяя часть разделяется единственным и последовательным с синтаксисом способом: 010000; то есть, 01, за которым следуют два 00, что в совокупности составляет выражение. Следовательно, последовательность 0100010000 разлагается на свои основные составляющие уникальным образом согласно законам синтаксиса, и таким образом, является выражением \mathcal{B}_2.

4. 0101000011

   Для этой последовательности мы можем сделать следующее разделение, которое я выделил цветом:

   0101000011

   По правилам синтаксиса, для того чтобы последовательность длиной более 2 символов была выражением, необходимо, чтобы она начиналась с 01, и после этого должны следовать два выражения, которые я выделил синим и зелёным цветом. Легко видеть, что это разделение уникально, потому что если длина синей или зелёной зоны изменится, любое изменение, каким бы оно ни было, не позволит обеим частям одновременно быть выражением.

5. 01010000010000

   Проанализировав справа налево, мы можем найти следующее разделение:

   
   \underbrace{01\underbrace{01\overbrace{00}\overbrace{00}}_{{выражение}}\underbrace{01\overbrace{00}\overbrace{00}}_{{выражение}}}_{{выражение}}

6. 01010010000100101000011

   Внимательный наблюдатель заметит, что эта последовательность имеет длину 23 и что невозможно построить последовательность нечётной длины с помощью синтаксических законов \mathcal{L}_2, которые строят выражения путём соединения последовательностей чётной длины. Все последовательности \mathcal{SL}_2 имеют чётную длину, следовательно, 01010010000100101000011 не является выражением \mathcal{B}_2.

Конец упражнения \blacksquare

Соглашения обозначений

Работа с нулями и единицами может быть путанной для нашего восприятия и может приводить к ошибкам. Чтобы сделать процесс более удобным для того, как люди интерпретируют вещи, мы можем использовать соглашения обозначений и некоторые мета-символы.

Мета-переменные и коннектор \downarrow

Мета-символ — это символ, используемый для представления цепочек символов целевого языка. Например, при определении синтаксиса \mathcal{SL}_2 для \mathcal{L}_2 использовались символы \alpha и \beta для представления выражений \mathcal{B}_2. Эти символы называются мета-переменными \mathcal{B}_2: мета-символами, которые, будучи замененными на выражения языка, порождают через синтаксис другое выражение языка, как это установлено вторым правилом о элементах \mathcal{SL}_2:

Если \alpha,\beta \in \mathcal{SL}_2, то 01\alpha\beta \in\mathcal{SL}_2

По этой причине эти мета-переменные называют мета-выражениями \mathcal{B}_2.

Чтобы упростить наше написание впредь, мы будем использовать мета-символ \downarrow для обозначения цепочки 01. Этот мета-символ является тем, что мы называем коннектором и известен как Совместное отрицание по семантическим причинам.

С этим мы можем выразить синтаксис \mathcal{SL}_2 на метаязыковом уровне через следующие рекурсивные правила:

1. Все мета-переменные \mathcal{B}_2 являются мета-выражениями \mathcal{B}_2

2. Если \alpha и \beta являются мета-переменными \mathcal{B}_2, то \downarrow\alpha\beta является мета-выражением \mathcal{B}_2

Используя эти правила, мы можем писать мета-выражения, которые, при замене всех их мета-переменных выражениями и коннекторами в их форме, представленной нулями и единицами, получаются выражениями \mathcal{B}_2. Каждое такое мета-выражение относится к бесконечному семейству выражений \mathcal{B}_2: множеству всех выражений \mathcal{B}_2, которые можно представить с этой структурой. Это и есть то, что означает иметь формальный язык.

Примеры использования совместного отрицания

Пример: Из мета-выражения \downarrow\alpha\downarrow\beta\gamma можно получить следующие выражения, производя замены:

1. Заменяя \alpha := 00, \beta := 011100 и \gamma := 010011

   Получаем выражение:

   010001011100010011

2. Если заменить \alpha := 011100, \beta := 0111011100 и \gamma := 0111010011

   Получается:

   010111000101110111000111010011

Мета-выражение \downarrow\alpha\downarrow\beta\gamma не только проще для восприятия, чем любое другое выражение, удовлетворяющее его форме, но и представляет все выражения, которые можно получить из него, заменяя его мета-переменные выражениями.

Конец примера \blacksquare

Когда происходит замена мета-переменной, она происходит во всех местах, где она встречается

Пример: Рассмотрим мета-выражение \downarrow\downarrow\alpha\beta\downarrow\alpha\gamma

1. Если заменить \alpha:=11, то получим:

   \downarrow\downarrow 11\beta\downarrow 11\gamma

2. Если теперь сделать \beta:=011100, результат будет:

   \downarrow\downarrow 11011100\downarrow 11\gamma

3. И если теперь сделать замену \gamma:=011111, то получится:

   \downarrow\downarrow 11011100\downarrow 11011111

4. Наконец, заменив \downarrow:=01, мы придем к следующему выражению:

   0101110111000111011111

Конец примера \blacksquare

Перестановка и скобки

Проверить, что это мета-выражение, не особенно сложно, но это требует счета символов без риска потерять счет в процессе. Этот риск быстро возрастает с увеличением длины мета-выражения. Существует ли способ представить его более читабельным образом? Да, мы можем использовать скобки и переставить мета-выражение в соответствии с нашим естественным способом группировки вещей. Чтобы проиллюстрировать эту точку зрения, рассмотрим следующее мета-выражение:

\downarrow\alpha\downarrow\downarrow\alpha\beta\alpha

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

\downarrow\alpha\beta:=(\alpha\downarrow\beta)

Пример: Рассмотрим мета-выражение \downarrow\alpha\downarrow\downarrow\beta\gamma\delta. Если применить введение скобок и перестановку, то оно преобразится следующим образом:

Это последнее мета-выражение намного легче читать и проверять, чем оригинальное, потому что каждый блок скобок представляет собой мета-выражение, состоящее из легко различимых элементов: общего отрицания посередине и мета-выражения с каждой стороны.

Конец примера \blacksquare

Производные связки

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

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

Вокализация выражений исчисления высказываний

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

Синтез и размышления о языке логики высказываний

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

Матрица за Матрицей позади понимания всех вещей

Ещё одно последнее замечание. Логика высказываний и математика во многом основаны на логике высказываний, которая, в свою очередь, построена на базовом языке из единиц и нулей. Означает ли это, что через это мы пришли к «Матрице» позади логики и математики? Возможно. Но также возможно рассматривать базовый язык для базового языка, из которого можно было бы воссоздать всё остальное; однако, чтобы найти такой язык, нам потребовалось бы найти ещё более фундаментальные понятия, чем понятия порядка и количества (те, которые использовались для создания первого базового языка). Поиск базового языка основы подразумевает размышления о наиболее фундаментальных аспектах того, что значит «понимать вещи». Если углубиться дальше, если удастся докопаться до сути, можно было бы сказать, что ты увидел «Матрицу за Матрицей позади понимания всех вещей», и возможно, что этот процесс фундаментирования можно продолжать до бесконечности, придавая новый слой глубины знаниям на каждом основополагающем шаге.