3. Формальный язык

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

Определение1.1. Множество (слов) L называется (а множество слов принято обычно называть формальным языком) множеством формул пропозициональной логики, если оно удовлетворяет условиям:

1. однобуквенные слова O и I принадлежат языку L;

2. любое однобуквенное слово вида x, где , принадлежит языку L (можно не вполне точно прописать: );

3. если , то ;

4. если и , то и ;

5. если W – формальный язык, удовлетворяющий условиям (1) – (4), то .

Замечания. (1) Определения, аналогичные приведённому выше, называются индуктивными, а аксиомы, подобные (5) – аксиомами индукции.

(2) Само существование языка L – не такой уж тривиальный вопрос (возможно, его задекларированные свойства каким-то образом противоречат друг другу!).

(3) В действительности L – (универсальная) алгебра, в рассматриваемом случае – с пятью операциями (двумя нульарными, одной унарной и двумя бинарными), естественным образом соответствующим элементам функционального базиса.

Пример. Формулу можно воспринимать как результат применения бинарной операции С к формулам и : .

(4) Эта запись, являясь вариантом так называемой «польской записи», позволяет избежать появления скобок.

Теорема 1.1. Язык L существует и единственен.

Доказательство. Заметим, что формальные языки, обладающие свойствами (1) – (4) существуют. Например, таковым является множество всех слов над рассматриваемым алфавитом, или – над любым бòльшим алфавитом. Пусть – множество всех формальных языков, удовлетворяющих этим свойствам (это опять не совсем «правильное» множество, но мы не будем обращать на это внимания).

Далее, заметим, что формальный язык , состоящий из тех и только тех слов, которые входят во все языки множества , также обладает указанными свойствами. Действительно, если, например, , то это означает, что , следовательно , так что . Очевидно, что в случае остальных условий, которые необходимо проверить, рассуждения абсолютно аналогичны. В частности, свойствами (1) – (4) обладает формальный язык .

Покажем, что этот язык обладает также и свойством (5). Пусть это не так, то есть , такой, что . Тогда . Полученное противоречие доказывает рассматриваемое утверждение.

Осталось доказать единственность языка L. Пусть – другой формальный язык, удовлетворяющий свойствам (1) – (5). Тогда он, в частности, удовлетворяет свойствам (1) – (4), поэтому (по свойству (5) языка L). Симметричным образом, , откуда .

QED

Примеры. (1) По какой причине формулой является выражение (то есть )? По той, что она имеет вид , где и являются формулами (свойство (4)). Выражение А, в свою очередь является формулой потому, что имеет вид , где является формулой в силу свойства (2). Тот факт, что выражение В тоже является формулой также следует из того, что свойства (3) и (4) позволяют свести его к тому, что формулами являются x, y, и z.

(2) Почему формулой не является никакое выражение, содержащее некоторый символ, не входящий в ? Потому что существует формальный язык, удовлетворяющий условиям (1) – (4) и не содержащий ни одного слова, в который входит этот «лишний» символ (например – множество всех слов над алфавитом ). Поэтому пропозициональными формулами определённо не являются выражения , и . Отметим одну сравнительно тонкую и малозаметную деталь: в первой «не-формуле» x и y являются не пропозициональными, а, например, действительными переменными, то есть они похожи на элементы V, но таковыми не являются.

(3) Почему формулой не является выражение ? Потому что множество всех слов над алфавитом , из которого исключили единственное слово удовлетворяет условиям (1) – (4), значит не является формулой. Аналогично, формулой не является выражение (из множества всех слов в этом случае следует исключить два: и ). И уже по этой причине формулой не является и рассматриваемое выражение .