Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 14

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 101 >> Следующая


Кроме того, мы не собираемся обосновывать какую-либо математическую теорию (в философском смысле термина «обосновывать»), Наша цель состоит только в том, чтобы придать максимальную логическую отчетливость каждому нашему шагу. Мы располагаем объективным критерием, позволяющим установить, достигнута ли эта скромная цель: если да, то любые логические машины, созданные специально, чтобы применять правила, будут всегда давать в одних и тех же условиях одни и те же результаты .

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. Множество элементарных теорем

Теперь мы рассмотрим другой (формальный) язык, содержащийся в предыдущем; этот язык мы назовем множеством теорем Теоремы соответствуют тому, что в неформальном варианте называлось тавтологиями.
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed