Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Кроме того, мы не собираемся обосновывать какую-либо математическую теорию (в философском смысле термина «обосновывать»), Наша цель состоит только в том, чтобы придать максимальную логическую отчетливость каждому нашему шагу. Мы располагаем объективным критерием, позволяющим установить, достигнута ли эта скромная цель: если да, то любые логические машины, созданные специально, чтобы применять правила, будут всегда давать в одних и тех же условиях одни и те же результаты .
2.2.3. Синтаксис и значение
Ясно, что, вообще говоря, ученые не строят формальные системы из чисто эстетических соображений или только для собственного удовольствия. Обычно формальная система создается как идеализированный образ чего-то другого — это «другое» можно было бы назвать, например, «теорией», — по отношению к чему эта формальная система и обретает смысл.
Тогда формальная система представляет собой формализацию некоторой теории, образуя синтаксис последней; теория же представляет собой интерпретацию данной формальной системы. Правильно построенные слова (правильные фразы) формальной системы получают смысл в рамках формализуемой теории; обратно, любому высказыванию, имеющему смысл в данной теории, соответствует некоторый класс правильно построенных слов (правильных фраз) в формальной системе.
Вопрос об адекватности данной формальной системы для данной теории — это проблема, относящаяся к методологии науки.42
Часть /. Предварительные сведения из логики и алгебры
Исследование подобных проблем должно, разумеется, вестись как можно более строгими методами, но оно может выходить за рамки математики как таковой.
Мы попытаемся проиллюстрировать все эти общие соображения, снова обратившись к исчислению высказываний, но теперь рассматривая его на гораздо более формальном уровне.
§ 2.3. ФОРМАЛИЗОВАННЫЙ ВАРИАНТ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
2.3.1. Алфавит
Пусть имеется счетное множество абстрактных математических объектов, образующих абстрактный алфавит. Эти объекты находятся во взаимно однозначном соответствии со следующими графическими символами, образующими алфавит:
Я = {], [, =>, а„ ..., а„, ...}.
Пояснения:
«{», «}» и «,» суть символы метаязыка;
«]» и «[» суть имена формальных скобок;
« I» есть имя формального отрицания;
«гэ» есть имя формальной импликации;
at — имена элементарных объектов, называемых атомами и образующих счетное множество.
2.3.2. Формулы
Мы выделим в полугруппе 51* некоторую часть — формальный язык, соответствующий некоторому множеству конкретных формул (служащих представлениями абстрактных формул).
Правила, задающие это множество формул, предписывают определенное «правильное» употребление скобок и символов операций. Вот эти правила:
Fl. Всякий атом есть формула.
F2. Если слово X — формула, то слово ~~1 X — тоже формула.
F3. Если слова X и Y—формулы, то слово гэ Г|— тоже формула.
F4. Никаких других формул нет.
X и Y являются здесь метаязыковыми переменными
Примеры.
?i является формулой в соответствии с Fl;
аг является формулой в соответствии с Fl;
[йі Z3 а2] является формулой в соответствии с F3;
"И [аі ZD а2] является формулой в соответствии с F2;
аз является формулой в соответствии с Fl;
1 [?] id а2] id а3] является формулой в соответствии с F3 и предыдущим замечанием.Г л //. Общие сведения о формальных системах
43
Множество всех формул можно получить, последовательно строя формулы все большей длины.
формулы длины 1—это атомы. Поскольку в формулах ничего не стирается, каждая формула содержит по крайней мере один атом.
формулы длины 2 таковы:
Haj, Па2, ..., На„.....
затем идут формулы длины 3:
I IO1, HHfl2, ..., НПа„.....
формулы длины 4:
-|-|-]а„ HH-Ia2, ..., HHHfls.....
формулы длины 5:
HHHHa11 HHHHfl2,..., ННННа»,,.,
и
[а, =э a,], [a, =d а2], ..., [а„ =d ар], ... и т. д.
Если дано слово M е її*, то всегда можно решить, является ли M формулой.
Если M не содержит атомов, то M не является формулой. Если M содержит атомы, то нужно построить из этих атомов ьсе возможные формулы длины, меньшей или равной длине М. Слово M является формулой тогда и только тогда, когда M является одной из этих формул. Ясно, что указанный процесс определения того, является ли M формулой, может быть «механизирован». При этом для нас здесь неважно, насколько такой процесс «удобен» или «эффективен»; этот вопрос обсуждаться не будет.
Примеры.
I[[не является формулой (в данном выражении нет атомов). [На2:за2] является формулой, поскольку это выражение содержится в множестве всех формул длины ^6, которые можно построить из а2; это множество состоит из следующих формул:
02.
Ha2, H H а2, HHHa2,
HHHHfl2l [а2 =d а2], HHHHHfl2l H [а2 :э а2], [Н а2 =d а2], [а2 =d —і а2].44
Часть /. Предварительные сведения из логики и алгебры
2.3.3. Множество элементарных теорем
Теперь мы рассмотрим другой (формальный) язык, содержащийся в предыдущем; этот язык мы назовем множеством теорем Теоремы соответствуют тому, что в неформальном варианте называлось тавтологиями.