Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Долгое время, по крайней мере во Франции, исследование логических правил было предоставлено «логикам», которые обыч- Г л //. Общие сведения о формальных системах
39
но не знали математики (и работы которых считались бесперспективными).
Эта ситуация изменилась, как только математики стали заниматься математическими объектами, столь малоинтуитивными по своему характеру, что для их понимания «логики здравого смысла» оказалось недостаточно.
Переход от «наивных аксиоматических теорий» к «формальным системам» связан с осознанием того факта, что само понятие «логических правил» содержит в себе нечто неясное и потому нуждается в уточнении. Но тогда исследователь оказывается в ситуации, которая аналогична ситуации на уровне аксиом: мы по своему произволу выбирали аксиому Евклида или аксиому Лобачевского; точно так же мы можем по своему произволу выбирать одни или другие правила вывода и получать тем самым разные формальные системы.
2.2.2. Метаязык
Формальная система имеет дело с языком L, который строится над некоторым алфавитом її с помощью аксиом и правил вывода. В свое время мы уточним это, а пока нам достаточно заметить следующее. Чтобы говорить об элементах формальной системы, о ее правилах и т. д., приходится пользоваться каким-то языком; этот язык должен содержать имена объектов, имена отношений и т. п. В данном переводе настоящей книги для этой цели применяется обычный русский язык, дополненный некоторыми символами, отличными от символов самой формальной системы.
Пример. Рассмотрим формальную систему, определенную над алфавитом її = {а, Ь, с}; в ней будет использоваться конкатенация.
Чтобы говорить о словах этой формальной системы, мы будем прибегать к таким именам, как
'abaca',
образованным из букв алфавита с помощью одинарных кавычек, или к таким обозначениям, как Л, В и т. д.
Заметим, что специальные (одинарные) кавычки будут использоваться для выделения упоминаний о словах формальной системы, а обычные (двойные) кавычки — для выделения упоминаний о символах, используемых для обозначения слов формальной системы.
Для обозначения операции конкатенации будем применять символ « • » и писать, например, так:
Если А = 'abaca' и если В = 'Ьа\
то A-B = 'abacaba'. 40
Часть /. Предварительные сведения из логики и алгебры
Знак « = » обозначает здесь, что выражение, стоящее слева от него, и выражение, стоящее справа от него, — это два разных имени одного и того же объекта.
Сказанное выше уже, видимо, позволяет читателю получить некоторое предварительное представление о метаязыке. Одни авторы обозначают этим термином определенную систему знаков, для описания которой требуется в свою очередь некоторый метамета-язык. Другие называют метаязыком объединение обычного естественного языка и набора специальных знаков, позволяющее описать формальную систему. Мы будем в основном придерживаться второй точки зрения, чтобы избежать иерархии метаязыков, ненужной для наших целей.
Метаязыковые символы, употребляемые в дальнейшем, будут определяться с помощью по возможности однозначных и логически отчетливых русских фраз. Таким образом, эти символы по существу представляют собой сокращения.
Пример. Пусть алфавит формальной системы есть 21 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -}.
Мы хотим определить два множества слов, а именно множество «целых чисел без знака» и множество «целых чисел». Чтобы сформулировать правила образования этих множеств, мы введем мета-языковую переменную С, которая принимает любое значение из множества {0,1, ..., 9}, метаязыковую переменную ESS1), принимающую значение из множества «целых чисел без знака», и метаязыковую переменную Е, принимающую значение из множества «целых чисел».
Ломаные скобки «(» и «)» будут использоваться для разграничения вхождений переменных; вертикальная черточка «|» обозначает союз или в одном из его значений (читатель сам уточнит, в каком именно); наконец, символ «::=» означает разрешение заменить то, что стоит слева от него, каким-либо из выражений, стоящих справа от него и разделенных вертикальными черточками. Для обозначения конкатенации используется «классический» типографский прием — простое соположение (без специального знака).
Приведем правила порождения интересующих нас множеств.
Правило 1: (ESS) :: = (C)\(ESS) (С).
Правило 2: (E):: = (ESS) | + (ESS) | - (ESS).
Применяя правило 1, мы можем получить, например,
(ESS) :: = 3, (ESS) : : = 35;
') ESS = Entier Sans Signe. — Прим. перев. Г л //. Общие сведения о формальных системах
41
применение правила 2 к последнему результату дает, например,
(?)::= —35.
Предположим, что алфавит некоторой формальной системы содержит букву «Л» и имеется правило: «Если А и В — слова типа б, то слово А-Л'В — тоже слово типа 0». Русское выражение «если..., то ..» представляется в данном контексте абсолютно однозначным; однако сугубо для краткости записи его можно заменить метаязыковым символом, например символом « Ф ».
В этом месте читатель может быть удивлен следующим обстоятельством. «Разоблачив» нечеткость и недостаточность «логики здравого смысла», мы тем не менее включаем в наш метаязык такие выражения, как «если..., то...» (замаскировав его обозначением Ф), «разделительное или» и т. д. На это мы ответим, что для общения, для передачи мыслей использовать какой-нибудь «язык» необходимо; но мы ограничиваем употребление метаязыка исключительно описанием правил, т. е. мы используем «логику здравого смысла» не для самих логических выводов, а только для описания их структуры, для того, чгобы понять «правила игры».
