Спецкурс "Исчисление Ламбека"

М. Р. Пентус
2005/2006

Внимание! Спецкурс "Исчисление Ламбека" завершился 28 апреля 2006 г.

Краткое содержание прошедших лекций

Краткий конспект: PostScript, pdf.

        30.09.2005

1.1-1.20.  Полугруппы с делением.
Домашнее задание: 1.9, 1.13, 1.15.

        07.10.2005

2.1-2.25.  Несеквенциальное исчисление.
Домашнее задание: 2.9, 2.10, 2.20.

        14.10.2005

2.26-2.27. Теорема о полноте.
3.1-3.5.   Определение секвенциального исчисления.

        21.10.2005

3.6-3.11.  Устранимость сечения.
3.12-3.15. Эквивалентность несеквенциального и секвенциального исчислений.
Домашнее задание: 3.12.

        11.11.2005

3.17-3.21. Допустимые правила.
3.22-3.25. Двойственность.
4.1-4.3.   Исчисление Ламбека с одним примитивным типом.
4.4-4.12.  Элементарные фрагменты исчисления Ламбека.
4.17-4.27. Исчисление Ламбека с единицей.
Домашнее задание: 3.18, 4.23, 4.24.

        18.11.2005

4.13-4.16. Консервативные расширения исчисления Ламбека.
4.28-4.32. Модели на моноидах с делением.
4.33-4.39. Добавление структурных правил.
5.1-5.3.   Понятие L-модели исчисления Ламбека.
Домашнее задание: 4.5, 4.6, 4.34.

        25.11.2005

5.4-5.19.  Модели исчисления Ламбека.

        02.12.2005

5.17.      Доказательство полноты исчисления L относительно R-моделей.
Домашнее задание: доказать существование универсальной R-модели.

        09.12.2005

5.20-5.26. Модели исчисления Ламбека.
6.1-6.12.  Интерпретация в свободной группе.
6.19-6.22. Положительный счётчик.
Домашнее задание: 6.8, 6.21.

        16.12.2005

6.30-6.39. Интерполяционное свойство.

        17.02.2006

7.1-7.10.  Контекстно-свободные грамматики.
7.16-7.20. Грамматики Ламбека.

        03.03.2006

6.23-6.29. Тонкие секвенции.
6.40-6.42. Исчисление Lcut.

        17.03.2006

7.21-7.38. Построение КС-грамматики по грамматике Ламбека.
8.1-8.10.  Мультипликативная циклическая линейная логика.
8.12-8.14. Эквивалентность в циклической линейной логике.
8.30-8.32. Корректность относительно классической логики высказываний.
8.40-8.43. Интерпретация циклической линейной логики в свободной группе.
Домашнее задание: 8.9, 8.10, 8.13, 8.14.

        24.03.2006

8.11.      Устранимость сечения в циклической линейной логике.
8.19-8.23. Исчисление без правила циклической перестановки.
8.24-8.29. Инварианты в циклической линейной логике.

        31.03.2006

8.33-8.39. Доказательство консервативности циклической линейной логики
           над исчислением Ламбека с пустыми антецедентами.
Домашнее задание: 8.39.

        07.04.2006

9.1-9.21.  Определение сети доказательства.
9.22-9.27. Доказательство критерия выводимости в терминах
           сетей доказательства.
Домашнее задание: 9.27.

        14.04.2006

9.28-9.37. Облегчённые сети доказательства.
8.15-8.18. Конгруэнция.
10.1-10.9. Сети эквивалентности.
Домашнее задание: 10.7.

        21.04.2006

10.10.     Лемма о цикле, составленном из двух <-планарных множеств рёбер.

        28.04.2006

10.11-10.13. Необходимое условие эквивалентности формул
             в циклической линейной логике.

Программа спецкурса

Упорядоченные полугруппы, полугруппы с делением, синтаксическое исчисление Ламбека (используемое в математической лингвистике), секвенциальные исчисления (исчисления генценовского типа), устранимость сечения в секвенциальном исчислении Ламбека и её следствия, открытые проблемы, относящиеся к фрагментам и вариантам исчисления Ламбека, языковые и реляционные модели исчисления Ламбека, инварианты в исчислении Ламбека, грамматики Ламбека и их связь с контекстно-свободными грамматиками.

Дополнительная литература

  1. Lambek J. The mathematics of sentence structure // American Mathematical Monthly. 1958. Vol. 65, N 3. P. 154-170.
    Русский перевод: Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сборник переводов / Под ред. Ю. А. Шрейдера и др. М.: Мир, 1964. С. 47-68.
  2. Moortgat M. Categorial type logics // Handbook of Logic and Language / Editors J. van Benthem and A. ter Meulen. Eslevier/MIT Press, 1997. P. 93-177. 1997.
  3. Такеути Г. Теория доказательств. М.: Мир, 1978.

Адрес: http://lpcs.math.msu.su/~pentus/spec2005w.htm
Изменения внесены 02.05.2006.
Мати Рейнович Пентус
Телефон/факс: + 7 - 495 - 939 30 31