Крах алгоритмической проблематики теории соответствия?
Article Sidebar
Опубликован:
16.01.2007
Main Article Content
Аннотация
Рассматриваются три ключевые проблемы теории соответствия: если дана модальная пропозициональная формула и формула первого порядка, определить, эквивалентны ли они в шкадах Крипке (проблема соответствия); если дана модальная пропозициональная формула, определить, существует ли формула первого порядка, эквивалентная ей в шкалах Крипке (проблема определимости первого порядка модальных пропозициональных формул), если дана формула первого порядка, определить, существует модальная пропозициональная формула, которая эквивалентна ей в шкалах Крипке (проблема модальной определимости формул первого порядка). Для всех этих задач были даны краткие доказательства алгоритмической неразрешимости.
Скачивания
Данные скачивания пока не доступны.
Article Details
Как цитировать
Чагров А., Чагрова Л. Крах алгоритмической проблематики теории соответствия? // Логические исследования / Logical Investigations. 2007. Т. 13. C. 248-272.
Выпуск
Раздел
Статьи
Литература
Мальцев А.И., Алгоритмы и рекурсивные функции. М.: Наука, 1986.
Фейс Р. Модальная логика. М.: Наука, 1974.
Чагров А.В. Неразрешимые свойства расширений логики доказуемости // Алгебра и логика. 1990. Т. 29. N 3. С. 350-367.
Чагров А.В. Неразрешимые свойства расширений логики доказуемости. II // Алгебра и логика. 1990. Т. 29. N 5. С. 613-623.
Чагров А.В. Алгоритмическая проблема аксиоматизации табличной нормальной модальной логики // Логические исследования. Вып 9. М.: Наука, 2002. C. 251-263.
Чагрова Л.А. О проблеме определимости пропозициональных формул интуиционистской логики формулами классической логики первого порядка. Калинин: КГУ, 1989. (Диссертация на соискание ученой степени кандидата физико-математических наук, защищенная в Институте математики с вычислительным центром АН МССР, Кишинев.)
van Benthem J.A.F.K. Modal Logic and Classical Logic. Bibliopolis, Napoli, 1983.
van Benthem J.A.F.K. Correspondence Theory // D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd Edition, Vol. 3. Kluwer Academic Publishers, 2001. P. 325-408.
Chagrov A.V., Chagrova L.A. Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames // Studia Logica. 1995. Vol. 55. No. 3. P. 421-448.
Chagrov A.V., Chagrova L.A. The Truth About Algorithmic Problems in Correspondence Theory // Advances in Modal Logic. Vol. 6. College Publications, 2006. P. 121-138.
Chagrov A., Zakharyashchev M. The undecidability of the disjunction property of propositional logics and other related problems // Journal of Symbolic Logic. 1993. Vol. 58. P. 967-1002.
Chagrov A., Zakharyashchev M. Modal Logic. Oxford University Press, 1997.
Chagrova L.A. An undecidable problem in correspondence theory // Journal of Symbolic Logic. 1991. Vol. 56. P. 1261-1272.
Isard S. A finitely axiomatizable undecidable extension of К // Theoria. 1977. Vol. 43. P. 195-202.
Kripke S. Semantical analysis of modal logic, Part I // Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik. 1963. Bd. 9. S. 67-96.
Zakharyaschev M., Wolter F. and Chagrov A. Advanced Modal Logic // D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd Edition. Vol. 3. Kluwer Academic Publishers, 2001. P. 83-266.
Фейс Р. Модальная логика. М.: Наука, 1974.
Чагров А.В. Неразрешимые свойства расширений логики доказуемости // Алгебра и логика. 1990. Т. 29. N 3. С. 350-367.
Чагров А.В. Неразрешимые свойства расширений логики доказуемости. II // Алгебра и логика. 1990. Т. 29. N 5. С. 613-623.
Чагров А.В. Алгоритмическая проблема аксиоматизации табличной нормальной модальной логики // Логические исследования. Вып 9. М.: Наука, 2002. C. 251-263.
Чагрова Л.А. О проблеме определимости пропозициональных формул интуиционистской логики формулами классической логики первого порядка. Калинин: КГУ, 1989. (Диссертация на соискание ученой степени кандидата физико-математических наук, защищенная в Институте математики с вычислительным центром АН МССР, Кишинев.)
van Benthem J.A.F.K. Modal Logic and Classical Logic. Bibliopolis, Napoli, 1983.
van Benthem J.A.F.K. Correspondence Theory // D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd Edition, Vol. 3. Kluwer Academic Publishers, 2001. P. 325-408.
Chagrov A.V., Chagrova L.A. Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames // Studia Logica. 1995. Vol. 55. No. 3. P. 421-448.
Chagrov A.V., Chagrova L.A. The Truth About Algorithmic Problems in Correspondence Theory // Advances in Modal Logic. Vol. 6. College Publications, 2006. P. 121-138.
Chagrov A., Zakharyashchev M. The undecidability of the disjunction property of propositional logics and other related problems // Journal of Symbolic Logic. 1993. Vol. 58. P. 967-1002.
Chagrov A., Zakharyashchev M. Modal Logic. Oxford University Press, 1997.
Chagrova L.A. An undecidable problem in correspondence theory // Journal of Symbolic Logic. 1991. Vol. 56. P. 1261-1272.
Isard S. A finitely axiomatizable undecidable extension of К // Theoria. 1977. Vol. 43. P. 195-202.
Kripke S. Semantical analysis of modal logic, Part I // Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik. 1963. Bd. 9. S. 67-96.
Zakharyaschev M., Wolter F. and Chagrov A. Advanced Modal Logic // D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd Edition. Vol. 3. Kluwer Academic Publishers, 2001. P. 83-266.