Новые константы в предтабличных суперинтуиционистских логиках: подход П.C. Новикова
Ключевые слова:
предтабличные суперинтуиционистские логики, новые логические константы, полнота по П.С. Новикову, алгоритмическая проблема распознавания консервативности
Аннотация
П.С. Новиков в конце 50-х годов ХХ века поставил задачу о новых логических связках как экстрапонятиях для языка со стандартными логическими связками $\vee$, $\wedge$, $\rightarrow$, $\neg$. Я.С. Сметанич в своих работах привел точные формулировки подхода Новикова к понятию новых логических связок в суперинтуиционистских логиках (новая логическая связка, полнота по Новикову). В статье рассмотрена проблема П.C. Новикова применительно к новым константам в предтабличных суперинтуиционистских логиках $LC$, $L2$, $L3$: логика конечных цепей, логика корневых шкал глубины 2 (вееров), логика корневых шкал глубины 3 с наибольшим элементом (даймондов). Получено исчерпывающее описание семейства всех полных по Новикову расширений каждой из предтабличных суперинтуиционистских логик в языке с несколькими дополнительными константами: для $LC$ и $L2$ семантическое описание всех полных по Новикову расширений дано в терминах классов конечных цепей с раскраской ($LC$) и конечных вееров с раскраской ($L2$); для $L3$ подобное описание дано для случая одной константы. Установлена алгоритмическая разрешимость каждого пополнения по Новикову указанных трех суперинтуиционистских логик, а также алгоритмическая проблема распознавания консервативности расширений этих логик в языке с одной дополнительной константой.
Литература
1. Григолия Р.Ш. Свободные S4.3-алгебры с конечным числом образующих // Исследования по неклассическим логикам и формальным системам. М.: Наука, 1983. С. 281-287.
2. Ершов Ю.Л., Палютин Е.А. Математическая логика. 2-е изд. М.: Наука, 1987. 336 с.
3. Захарьящев М.В. Синтаксис и семантика суперинтуиционистских логик // Алгебра и логика. 1989. Т. 28. № 4. С. 262-282.
4. Клини С.К. Введение в метаматематику М.: Иностранная литература, 1957. 526 с.
5. Кощеева А.К. Аксиоматика полных по П.С. Новикову расширений суперинтуиционистской логики $L2$ в языке с одной дополнительной константой // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2014. № 3. С. 28-39.
6. Кощеева А.К. Новая константа в суперинтуиционистской логике $L3$ // Алгебра и логика. 2015. Т. 54. № 1. С. 34-52.
7. Кощеева А.К. Новые константы в предтабличных суперинтуиционистских логиках: дис. … канд. физ.-матем. наук / Сибирский федеральный университет. Красноярск, 2015. 84 с.
8. Кузнецов А.В. Некоторые свойства структуры многообразий псевдобулевых алгебр // XI Всесоюзный алгебраический коллоквиум. Резюме сообщ. и докл. Кишинев, 1971. С. 255-256.
9. Кузнецов А.В. О суперинтуиционистских логиках и финитной аппроксимируемости // Доклады АН СССР. 1970. Т. 195. № 5. С. 1029-1032.
10. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2004. 256 с.
11. Максимова Л.Л. Предтабличные суперинтуиционистские логики // Алгебра и логика. 1972. Т. 11. № 5. C. 558-570.
12. Максимова Л.Л., Шрайнер П.А. Алгоритмы распознавания табличности и предтабличности в расширениях интуиционистского исчисления // Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика. 2006. Т. 6. № 3. С. 49-58.
13. Новиков П.С. Конструктивная математическая логика с точки зрения классической. М.: Наука, 1977. 328 с.
14. Плиско В.Е., Хаханян В.Х. Интуиционистская логика. М.: МГУ, мех.-мат. ф-т, 2009. 159 с.
15. Расёва Е., Сикорский Р. Математика метаматематики. М.: Наука, 1972. 592 с.
16. Скворцов Д.П. Об интуиционистском исчислении высказываний с дополнительной логической связкой // Исследования по неклассическим логикам и формальным системам. М.: Наука, 1983. C. 154-173.
17. Сметанич Я.С. О полноте исчисления высказываний с дополнительной операцией от одной переменной // Труды Московского математического общества. 1960. Т. 9. С. 357-371.
18. Сметанич Я.С. Об исчислениях высказываний с дополнительной операцией // Доклады АН СССР. 1961. Т. 139. № 2. С. 309-312.
19. Чагров А.В. Неразрешимые свойства суперинтуиционистских логик // Математические вопросы кибернетики. Вып. 5: сб. статей под ред. С.В. Яблонского. М.: Физматлит, 1994. С. 62-108.
20. Эсакиа Л.Л. Алгебры Гейтинга. Тбилиси: Мецниереба, 1985. 104 с.
21. Янков В.А. Построение последовательности сильно независимых суперинтуиционистских пропозициональных исчислений // Доклады АН СССР. 1968. Т. 181. № 1. С. 33-34.
22. Яшин А.Д. Новая регулярная константа в интуиционистской логике высказываний // Сибирский математический журнал. 1996. Т. 37. № 6. С. 1413-1432.
23. Яшин А.Д. О новой константе в интуиционистской логике высказываний // Фундаментальная и прикладная математика. 1999. Т. 5. № 3. С. 903-926.
24. Яшин А.Д. Классификация полных по Новикову логик с дополнительными логическими константами // Алгебра и логика. 2003. Т. 42. № 3. С. 366-383.
25. Яшин А.Д. О новых константах в двух предтабличных суперинтуиционистских логиках // Алгебра и логика. 2011. Т. 50. № 2. С. 246-267.
26. Яшин А.Д., Кощеева А.К. Новые константы в суперинтуиционистской логике $L2$ // Математические заметки. 2013. Т. 94. № 6. С. 918-932.
27. Bezhanishvili N., de Jongh D. Intuitionistic logic. http://www.illc.uva.nl/Research/Publications/Reports/PP-2006-25.text.pdf
28. Chagrov A., Zakharyaschev M. Modal logic. Oxford: Oxford University Press, 1997. 605 р.
29. Dubashi D.P. On decidable varieties of Heyting algebras // J. Symb. Log. 1992. Vol. 57. № 3. P. 988-991.
30. Dummett M.A. A propositional calculus with denumerable matrix // J. Symb. Log. 1959. Vol. 24. № 2. Р. 97-106.
31. Dunn J.M., Meyer R.K. Algebraic completeness results for Dummet's LC and its extensions // Zeitschr. Math. Log. und Grundl. Math. 1971. Vol. 17. Р. 225-230.
32. Fitting M. Intuitionistic logic, model theory and forcing (Studies in Logic and the Foundations of Mathematics). Amsterdam-London: North-Holland Publishing Company, 1969. 191 p.
33. Gabbay D.M. On some new intuitionistic propositional connectives. I // Studia Logica. 1977. Vol. 36. № 1-2. P. 127-139.
34. Goldblatt R.I. Metamathematics of modal logics. Part I // Rep. on Math. Logic. 1976. Vol. 6. P. 41-78.
35. Goldblatt R.I. Metamathematics of modal logics. Part II // Rep. on Math. Logic. 1976. Vol. 7. P. 21-52.
36. Hosoi T. On intermediate logics. I // J. Fac. Sci. Univ. Tokyo. Sec. 1. 1967. № 14. P. 293-312.
37. Hosoi T., Ono H. The intermediate logics of the second slice // J. Fac. Sci. Univ. Tokyo. Sec. 1. 1970. № 17. P. 457-461.
38. Kirk R.E. A characterization of the classes of finite tree frames which are adequate for the intuitionistic logic // Zeitschr. Math. Log. und Grundl. Math. 1980. Vol. 26. № 6. P. 497-501.
39. Колмогоров А.Н. К толкованию интуиционистской логики / Избранные труды. Математика и механика. М.: Наука, 1985. С. 142-148.
40. Ono H. Kripke models and intermediate logics // Publs. Res. Inst. Math. Sci. Kyoto Univ. 1970. Vol. 6. № 71. P. 461-476.
41. Yashin A.D. New intuitionistic logical constants and Novikov completeness // Studia Logica. 1999. Vol. 63. № 2. P. 151-180.
42. Zakharyaschev M., Wolter F., Chagrov A. Advanced modal logic // Handbook of Philosophical Logic. Vol. 3 / Gabbay D.M., Guenthner F. Kluver Acad. Publ. 2001. P. 83-266.
2. Ершов Ю.Л., Палютин Е.А. Математическая логика. 2-е изд. М.: Наука, 1987. 336 с.
3. Захарьящев М.В. Синтаксис и семантика суперинтуиционистских логик // Алгебра и логика. 1989. Т. 28. № 4. С. 262-282.
4. Клини С.К. Введение в метаматематику М.: Иностранная литература, 1957. 526 с.
5. Кощеева А.К. Аксиоматика полных по П.С. Новикову расширений суперинтуиционистской логики $L2$ в языке с одной дополнительной константой // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2014. № 3. С. 28-39.
6. Кощеева А.К. Новая константа в суперинтуиционистской логике $L3$ // Алгебра и логика. 2015. Т. 54. № 1. С. 34-52.
7. Кощеева А.К. Новые константы в предтабличных суперинтуиционистских логиках: дис. … канд. физ.-матем. наук / Сибирский федеральный университет. Красноярск, 2015. 84 с.
8. Кузнецов А.В. Некоторые свойства структуры многообразий псевдобулевых алгебр // XI Всесоюзный алгебраический коллоквиум. Резюме сообщ. и докл. Кишинев, 1971. С. 255-256.
9. Кузнецов А.В. О суперинтуиционистских логиках и финитной аппроксимируемости // Доклады АН СССР. 1970. Т. 195. № 5. С. 1029-1032.
10. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2004. 256 с.
11. Максимова Л.Л. Предтабличные суперинтуиционистские логики // Алгебра и логика. 1972. Т. 11. № 5. C. 558-570.
12. Максимова Л.Л., Шрайнер П.А. Алгоритмы распознавания табличности и предтабличности в расширениях интуиционистского исчисления // Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика. 2006. Т. 6. № 3. С. 49-58.
13. Новиков П.С. Конструктивная математическая логика с точки зрения классической. М.: Наука, 1977. 328 с.
14. Плиско В.Е., Хаханян В.Х. Интуиционистская логика. М.: МГУ, мех.-мат. ф-т, 2009. 159 с.
15. Расёва Е., Сикорский Р. Математика метаматематики. М.: Наука, 1972. 592 с.
16. Скворцов Д.П. Об интуиционистском исчислении высказываний с дополнительной логической связкой // Исследования по неклассическим логикам и формальным системам. М.: Наука, 1983. C. 154-173.
17. Сметанич Я.С. О полноте исчисления высказываний с дополнительной операцией от одной переменной // Труды Московского математического общества. 1960. Т. 9. С. 357-371.
18. Сметанич Я.С. Об исчислениях высказываний с дополнительной операцией // Доклады АН СССР. 1961. Т. 139. № 2. С. 309-312.
19. Чагров А.В. Неразрешимые свойства суперинтуиционистских логик // Математические вопросы кибернетики. Вып. 5: сб. статей под ред. С.В. Яблонского. М.: Физматлит, 1994. С. 62-108.
20. Эсакиа Л.Л. Алгебры Гейтинга. Тбилиси: Мецниереба, 1985. 104 с.
21. Янков В.А. Построение последовательности сильно независимых суперинтуиционистских пропозициональных исчислений // Доклады АН СССР. 1968. Т. 181. № 1. С. 33-34.
22. Яшин А.Д. Новая регулярная константа в интуиционистской логике высказываний // Сибирский математический журнал. 1996. Т. 37. № 6. С. 1413-1432.
23. Яшин А.Д. О новой константе в интуиционистской логике высказываний // Фундаментальная и прикладная математика. 1999. Т. 5. № 3. С. 903-926.
24. Яшин А.Д. Классификация полных по Новикову логик с дополнительными логическими константами // Алгебра и логика. 2003. Т. 42. № 3. С. 366-383.
25. Яшин А.Д. О новых константах в двух предтабличных суперинтуиционистских логиках // Алгебра и логика. 2011. Т. 50. № 2. С. 246-267.
26. Яшин А.Д., Кощеева А.К. Новые константы в суперинтуиционистской логике $L2$ // Математические заметки. 2013. Т. 94. № 6. С. 918-932.
27. Bezhanishvili N., de Jongh D. Intuitionistic logic. http://www.illc.uva.nl/Research/Publications/Reports/PP-2006-25.text.pdf
28. Chagrov A., Zakharyaschev M. Modal logic. Oxford: Oxford University Press, 1997. 605 р.
29. Dubashi D.P. On decidable varieties of Heyting algebras // J. Symb. Log. 1992. Vol. 57. № 3. P. 988-991.
30. Dummett M.A. A propositional calculus with denumerable matrix // J. Symb. Log. 1959. Vol. 24. № 2. Р. 97-106.
31. Dunn J.M., Meyer R.K. Algebraic completeness results for Dummet's LC and its extensions // Zeitschr. Math. Log. und Grundl. Math. 1971. Vol. 17. Р. 225-230.
32. Fitting M. Intuitionistic logic, model theory and forcing (Studies in Logic and the Foundations of Mathematics). Amsterdam-London: North-Holland Publishing Company, 1969. 191 p.
33. Gabbay D.M. On some new intuitionistic propositional connectives. I // Studia Logica. 1977. Vol. 36. № 1-2. P. 127-139.
34. Goldblatt R.I. Metamathematics of modal logics. Part I // Rep. on Math. Logic. 1976. Vol. 6. P. 41-78.
35. Goldblatt R.I. Metamathematics of modal logics. Part II // Rep. on Math. Logic. 1976. Vol. 7. P. 21-52.
36. Hosoi T. On intermediate logics. I // J. Fac. Sci. Univ. Tokyo. Sec. 1. 1967. № 14. P. 293-312.
37. Hosoi T., Ono H. The intermediate logics of the second slice // J. Fac. Sci. Univ. Tokyo. Sec. 1. 1970. № 17. P. 457-461.
38. Kirk R.E. A characterization of the classes of finite tree frames which are adequate for the intuitionistic logic // Zeitschr. Math. Log. und Grundl. Math. 1980. Vol. 26. № 6. P. 497-501.
39. Колмогоров А.Н. К толкованию интуиционистской логики / Избранные труды. Математика и механика. М.: Наука, 1985. С. 142-148.
40. Ono H. Kripke models and intermediate logics // Publs. Res. Inst. Math. Sci. Kyoto Univ. 1970. Vol. 6. № 71. P. 461-476.
41. Yashin A.D. New intuitionistic logical constants and Novikov completeness // Studia Logica. 1999. Vol. 63. № 2. P. 151-180.
42. Zakharyaschev M., Wolter F., Chagrov A. Advanced modal logic // Handbook of Philosophical Logic. Vol. 3 / Gabbay D.M., Guenthner F. Kluver Acad. Publ. 2001. P. 83-266.
Поступила в редакцию
2016-02-01
Опубликована 2016-05-20
Опубликована 2016-05-20