Введение к работе
Актуальность темы. Категориальная грамматика — раздел математической лингвистики, описывающий формальные законы синтаксических категорий в естественных и искусственных языках. Одно из центральных мест в нём занимает исчисление Ламбека, которое было введено в статье [1] для изучения свойств формальных языков. Формальным языком называется произвольное множество непустых слов (конечных последовательностей символов) над некоторым конечным алфавитом. В лингвистических приложениях при описании синтаксиса естественного языка алфавитом (в математическом смысле) является множество всех словоформ рассматриваемого фрагмента естественного языка. При этом множество всех грамматически правильных предложений образует формальный язык. Другие важные примеры формальных языков над тем же алфавитом — множество всех именных групп, множество всех групп сказуемого и т. д.
Исчисление Ламбека описывает свойства трёх бинарных операций над формальными языками: операции умножения, операции правого деления и операции левого деления (эти операции обозначаются соответственно , / и \). Произведение языков состоит из всевозможных попарных конкатенации их элементов. Результат правого деления языка А на В (обозначается А/В) определяется как множество всех таких непустых слов у, что {у}*В С А. Результат левого деления языка А на В (обозначается В\А) определяется как множество всех таких непустых слов 7, что B*{f} С А.
Исчисление Ламбека описывает утверждения вида А С В, где А и В — термы, составленные из переменных по формальным язы-
[1] Lambek J. The mathematics of sentence structure // American Mathematical Monthly. — 1958. — Vol. 65, no. 3. — P. 154-170. — Русский перевод: Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сборник переводов / Под ред. Ю. А. Шрейдера и др. — М.: Мир, 1964. — С. 47-68.
кам с помощью операций , \ и /. Аксиомы и правила этого исчисления утверждают, что
-
отношение С рефлексивно и транзитивно,
-
умножение ассоциативно,
-
С С А/В тогда и только тогда, когда С» В С А,
-
С С В\А тогда и только тогда, когда В*С С А.
Для описания синтаксиса естественных языков Бар-Хиллел в 1950-х годах ввёл понятие базовой категориальной грамматики (см. [2]). Каждая базовая категориальная грамматика приписывает словоформам рассматриваемого фрагмента естественного языка термы, составленные с помощью операций \ и "/' Содержательно каждый такой терм служит обозначением для Некоторой синтаксической категории, т. е. некоторого класса словоформ и словосочетаний с одинаковой синтаксической сочетаемостью. В грамматике выделен один терм (обычно он обозначает класс всех грамматически правильных предложений). Последовательность словоформ допускается данной грамматикой, если соответствующую последовательность термов можно сократить так, что останется только выделенный терм. При этом разрешается сократить соседние термы А/В и В (получается А), а также В и В\А (тоже получается А).
Грамматики Ламбека отличаются от базовых категориальных грамматик тем, что в них разрешены более сложные сокращения (которые определяются вышеупомянутым исчислением Ламбека). Согласно терминологии, принятой для базовых категориальных грамматик, термы исчисления Ламбека, составленные с помощью операций , \ и /, называются синтаксическими категориями, синтаксическими типами или просто типами, а простейшие термы (переменные) называются примитивными типами. Следуя обозначениям, используемым для базовых категориальных грамматик, вместо АС В в исчислении Ламбека обычно пишут А —> В.
В конце 50-х — начале 60-х годов возник вопрос о связи категориальных грамматик (в том числе грамматик Ламбека) с
[2] Bar-Hillel Y. A quasi-arithmetical notation for syntactic description // Langugage. — 1953. — Vol. 29. — P. 47-58.
иерархией порождающих грамматик Хомского, включающей четыре вложенных друг в друга класса: порождающие грамматики (самый большой класс), грамматики непосредственно составляющих, контекстно-свободные грамматики и автоматные грамматики. В I960 году Бар-Хиллел, Гайфман и Шамир доказали, что формальный язык может быть задан некоторой базовой категориальной грамматикой тогда и только тогда, когда он является контекстно-свободным, т. е. может быть задан некоторой контекстно-свободной грамматикой (см. [3]). Они высказали гипотезу, что то же самое имеет место для грамматик Ламбека (см., например, [4]). Доказательство одной половины этой гипотезы (а именно того, что любой контекстно-свободный язык задаётся некоторой грамматикой Ламбека) фактически совпадает с соответствующим доказательством для базовых категориальных грамматик. Вопрос об обратном включении оставался открытым в течение многих лет. В. Бушковским были получены частичные результаты, относящиеся к фрагменту без правого деления и умножения и к фрагменту без умножения с некоторым ограничением на вложенность разносторонних делений (см. [5, 6]). Положительный ответ для
[3] Bar-Hillel Y., Gaifman С, and Shamir Е. On categorial and phrase-structure grammars // Bull. Res. Council Israel Sect. F. — 1960. — Vol. 9F. — P. 1-16.
[4] Chomsky N. Formal properties of grammars // Handbook of Mathematical Psychology / Editors R. D. Luce et al. — New York: Wiley, 1963. — Vol. 2. — P. 323-418.
[5] Buszkowski W. The equivalence of unidirectional Lambek categorial grammars and context-free grammars // Zeitschrift fur mathema-tische Logik und Grundlagen der Mathematik. — 1985. — Vol. 31. — P. 369-384.
[6] Buszkowski W. On generative capacity of the Lambek calculus // Logics in AI: European Workshop JELIA '90. Amsterdam, The Netherlands, September 1990. Proceedings / Editor J. van Eijck. — Berlin etc.: Springer-Verlag, 1991. — P. 139-152. — (Lecture Notes in Computer Science; Vol. 478. Lecture Notes in Artificaial Intelligence).
исчисления Ламбека в целом получен в диссертации [7] (доказано, что формальный язык может быть задан некоторой грамматикой Ламбека тогда и только тогда, когда он является контекстно-свободным).
Некоторые современные приложения исчисления Ламбека к изучению естественных языков приводятся в книгах [8, 9, 10].
С исчислением Ламбека связаны и другие нетривиальные математические проблемы. Ряд вопросов касается интерпретации исчисления Ламбека на различных математических структурах (см. обзорные статьи [11, 12]).
Наиболее широкий класс интерпретаций исчисления Ламбека образуют полугруппы с делением. Полугруппой с делением называется полугруппа {Н, ), рассматриваемое вместе с частичным порядком їС, причём для любых элементов а,Ь Є Н существует такой элемент а/Ь Є Н (правое частное элемента а по 6), что условия х ^ а/6 и х*Ь ^ а эквивалентны, и существует такой элемент Ь\а Є Н (левое частное элемента о по Ь), что условия х ^ Ь\а и Ь»х ^ а эквивалентны
[7] Пентус М. Р. Исчисление Ламбека и формальные грамматики: Дис. ... канд. физ.-мат. наук: 01.01.06. — Защищена 01.03.1996; Утв. 14.06.1996; 01910048811. — М., 1996. — 69 с. — Би-блиогр.: с. 67-69.
[8] Categorial Grammars and Natural Language Structures j Editors R. T. Oehrle, E. Bach, and D. Wheeler. — Dordrecht: Reidel, 1988.
[9] Moortgat M. Categorial Investigations. Logical and Linguistic Aspects of the Larnbek Calculus: Ph.D. thesis. — Dordrecht: Foris, 1988. — XVII, 270 p.
[10] Carpenter B. Type-Logical Semantics. — Cambridge etc.: The MIT Press, 1997. — XXI, 575 p. — (Language, Speech, and Communication) .
[11] Dosen K. A brief survey of frames for the Larnbek calculus // Zeitschrift fur mathematische Logik und Grundlagen der Mathematik. — 1992. — Vol. 38, no. 2. — P. 179-187.
[12] Ono H. Semantics for substructural logics // Substructural Logics j Editors K. Dosen and P. Schroeder-Heister. — Oxford: Clarendon Press, 1993. — P. 259-291. — (Studies in Logic and Computation; 2).
(см. [13]). В некоторых работах вместо а/Ь пишут а:Ь, а вместо Ь\а пишут а::Ь.
Интерпретация исчисления Ламбека в полугруппе с делением Н задаётся произвольной функцией v, ставящей в соответствие примитивным типам элементы Н. Интерпретирующая функция v продолжается естественным образом на все типы. Утверждение А — В является истинным при данной интерпретации, если v(A) <: v(B). ^
Простой проверкой всех аксиом и правил можно убедиться, что исчисление Ламбека корректно относительно интерпретаций в полугруппах с делением, т. е. в исчислении Ламбека выводятся только те утверждения, которые истинны при каждой такой интерпретации. Другими словами, любая полугруппа с делением вместе с интерпретирующей функцией v задаёт модель исчисления Ламбека.
Нетрудно проверить, что исчисление Ламбека полно относительно этого класса моделей, т. е. в исчислении Ламбека выводятся все утверждения, которые истинны во всех таких моделях. Возник естественный вопрос о возможности усиления этого результата путём доказательства полноты относительно какого-нибудь меньшего класса моделей исчисления Ламбека.
К. Дошен рассмотрел следующую конструкцию. Частично упорядоченной полугруппой называется такая полугруппа с частичным порядком, где полугрупповая операция монотонна. Множество всех таких подмножеств Л частично упорядоченной полугруппы G, что из а ^ Ь и і А следует а Є А, является полугруппой с делением относительно порядка С и операции
А*В ^± {с G | с $С ab для некоторых а Є А, 6 Є В}.
В 1985 году К. Дошен [14] доказал полноту исчисления Ламбека относительно моделей на таких полугруппах с делением.
[13] Fuchs L. Partially Ordered Algebraic Systems. — Oxford: Perg-amon Press, 1963. — Русский перевод: Фукс Л. Частично упорядоченные алгебраические системы / Пер. с англ. И. В. Стеллецкого. — М.: Мир, 1965. — 342 с.
[14] Dosen К. A Completeness Theorem for the Lambek Calculus of Syntactic Categories // Zeitschrifi fur raathematische Logik und Grund-lagen der Mathematik. — 1985. — Vol. 31. — P. 235-241.
В 1986 году В. Бушковский [15] опубликовал доказательство полноты относительно ещё более узкого класса моделей исчисления Ламбека^ Он рассматривал в качестве полугруппы с делением множество всех подмножеств произвольной полугруппы G. При этом в качестве, порядка снова использовалось отношение С, а в качестве операции умножения — операция *, определяемая так:
А»В ^ {аЬ | а A, b Є В}.
Такие полугруппы с делением представляют частный случай полугрупп С'делением, рассмотренных Дошеном (достаточно на G в качестве отношения частичного порядка ввести отношение равенства). Таким образом, результат Вушковского сильнее результата Дошена. Особый интерес представляют модели исчисления Ламбека на множестве подмножеств свободной полугруппы (частный случай моделей, рассмотренных Бушковским). Эти модели обычно называются языковыми моделями исчисления Ламбека или L-моделями, так как в них , \ и / обозначают умножение, левое деление и правое деление формальных языков, определённые на стр. 1. Именно эта интерпретация рассматривалась в 1958 г. при формулировке исчисления Ламбека. Корректность исчисления Ламбека относительно L-моделей следует непосредственно из корректности относительно интерпретаций в полугруппах с делением. Вопрос о полноте относительно L-моделей долгое время оставался открытым (см., например, [6, 11, 15, 16, 17]). Конструкция Вушковского непригодна для доказательства полноты относительно L-моделей, так как согласно этой конструкции по невыводимой секвенции строится контрмодель
[15] Buszkowski W. Completeness Results for Lambek Syntactic Calculus (J Zeitschrift fur rnathematische Logik und Grundlagen der Mathematik. — 1986. — Vol. 32. — P. 13-28.
[16] Zielonka W. Axiomatizability of Ajdukiewicz-Lambek calculus by means of cancellation schemes // Zeitschrift fur rnathematische Logik und Grundlagen der Mathematik. — 1981. — Vol. 27, no. 3. — P. 215-224.
[17] Benthem J. van. Language in Action: Categories, Lambdas and Dynamic Logic. — Amsterdam etc.: North-Holland, 1991. — X, 350 p. — (Studies in Logic and the Foundations of Mathematics; Vol. 130).
на сложно устроенной частичной полугруппе (в частности, в этой частичной полугруппе любой элемент представим в виде произведения других элементов бесконечным числом способов, в то время как в свободной полугруппе это не так).
В данной диссертации дан положительный ответ на вопрос о полноте исчисления Ламбека относительно L-моделей. Более того, доказано, что исчисление Ламбека полно относительно класса всех L-моделей на двухбуквенном алфавите, т. е. для каждого невыводимого утверждения А —> В, где А а В — типы исчисления Ламбека, найдётся некоторая интерпретирующая функция v, ставящая в соответствие примитивным типам множества слов в двухбуквенном алфавите, такая что v(A) % v(B).
Во многих работах изучается также другой частный случай моделей исчисления Ламбека на полугруппах с делением — реляционные модели (см. [18, 19]). Мы рассматриваем бинарные отношения как множества упорядоченных пар. Композицией (или произведением) бинарных отношений А и В называется бинарное отношение {{r,t) j (r,s) Є Л и (s,t) В для некоторого $}. Пусть S — строгий частичный порядок на некотором множестве. Множество всех подмножеств S с определёнными на нём операцией композиции и отношением С образует полугруппу с делением. Интерпретация исчисления Ламбека в любой такой полугруппе называется реляционной моделью исчисления Ламбека или R-моделью.
С. Микулаш доказал в 1992 году (см. [20]), что исчисление Ламбека полно относительно реляционных моделей. Возник вопрос
[18] Benthem J. van. Semantic parallels in natural language and computation. — Amsterdam: Institute for Logic, Language and Computation, University of Amsterdam, 1988. — 45 p. — (ILLC Prepublication Series; LP-88-06),
[19] Orlowska E. Relational interpretation of modal logics // Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic. — 1988. — Vol. 17, no. 1. — P. 2-14.
[20] Mikulas Sz. The Completeness of the Lambek Calculus with respect to Relational Semantics. — Amsterdam: Institute for Logic, Language and Computation, University of Amsterdam, 1992. — 21 p. — (ILLC Prepublication Series; LP-92-03).
об усилении этого результата путём указания какого-нибудь конкретного простого отношения строгого частичного порядка, относительно R-моделей на котором исчисление Ламбека было бы полно. В данной диссертации доказано, что в качестве такого отношения подходит обычный строгий линейный порядок на целых числах.
Операции умножения и делений, обладающие свойствами, описываемыми исчислением Ламбека, встречаются в различных областях алгебры. Например, на множестве всех двусторонних идеалов произвольного ассоциативного кольца R можно рассмотреть операции , \ и / (обычно вместо \ и / пишут ' . и .'), определённые следующим образом (см. [21]):
А»В состоит из всех конечных сумм YJa,b;, где а,- Є Л и 6; Є В;
=1 А\В=і{г Є R\ArCB};
А/В ^ {г R | гВ С А}.
Легко проверить, что исчисление Ламбека корректно относительно интерпретаций на множестве двусторонних идеалов ассоциативного кольца, если умножению, левому делению и правому делению синтаксических типов исчисления Ламбека поставить в соответствие указанные операции над двусторонними идеалами.
Аналогичные операции на различных решётках с делением рассматриваются в монографии [22], где Г. Биркгоф приводит ряд утверждений, фактически являющихся теоремами исчисления Ламбека.
[21] Lambek J. Lectures on Rings and Modules. — Waltham, Massachusetts, etc.: Blaisdell, 1966. — Русский перевод: Ламбек И. Кольца и модули / Пер. с англ. А. В. Михалёва. — М.: Мир, 1971. — 280 с.
[22] Birkhoff G. Lattice Theory. — Providence, Rhode Island, 1967. — Русский перевод: Биркгоф Г. Теория решёток / Пер. с англ. В. Н. Салия. — М.: Наука, 1984. — 568 с.
Цель работы — доказать гипотезу о полноте исчисления Ламбека относительно языковых моделей (высказанную в восьмидесятых годах Зелонкой, Бушковским, ван Бентхемом и другими) и полноту этого исчисления относительно реляционных моделей на множестве целых чисел с его естественным порядком.
Методы исследования. В диссертации использованы теоретико-доказательственные методы (устранение сечения в секвенциальных исчислениях) и комбинаторные методы.
Научная новизна и практическая ценность. Все результаты диссертации являются новыми.
Доказано, что для любого алфавита, содержащего не менее двух символов, в исчислении Ламбека выводимы те и только те утверждения, которые истинны во всех языковых моделях над этим алфавитом.
Доказано, что в исчислении Ламбека выводимы те и только те утверждения, которые истинны во всех реляционных моделях исчисления Ламбека, в которых синтаксическим типам ставятся в соответствие подмножества обычного строгого порядка на целых числах.
Работа носит теоретический характер. Её методы и результаты могут быть полезны специалистам Московского, государственного университета им. М. В. Ломоносова, Санкт-Петербургского государственного университета, Новосибирского государственного университета, Красноярского государственного университета, Тверского государственного университета, Математического института им. В. А. Стеклова РАН, Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН.
Апробация работы. Основные результаты, полученные в диссертации, докладывались на общемосковском научно-исследовательском семинаре по математической логике (руководители семинара — чл.-корр. РАН С. й. Адян, проф. В. А. Успенский), на семинаре «Логические проблемы информатики» (руководитель семинара — проф. С. Н. Артёмов), на заседании Московского математического общества и на международных конференциях в России, Швейцарии, Франции, Израиле и Испании.
Публикации. Результаты диссертации опубликованы в 11 работах, перечисленных в конце автореферата.
Структура и объем работы. Диссертация состоит из введения и 10 глав. Текст диссертации изложен на 165 страницах. Список литературы содержит 58 наименований.