|
Финитные задачи и логика слабого закона исключенного третьего
А. В. Чернов Московский государственный университет им. М. В. Ломоносова
Аннотация:
Определяется новая характеристика пропозициональной формулы как операции над финитными задачами – мощность достаточного множества решений (ДМР). Доказывается, что если формула выводима в логике слабого закона исключенного третьего, то мощность ДМР ограничена константой, зависящей только от числа переменных; в противном случае достижимая мощность ДМР близка (больше корня некоторой степени) к тривиальной верхней оценке на нее. Это утверждение является аналогом ранее опубликованного результата автора об алгоритмической сложности множеств, полученных как значения пропозициональных формул. Также введено понятие колмогоровской сложности финитной задачи и получены аналогичные результаты.
Библиография: 11 названий.
Поступило: 12.11.2003
Образец цитирования:
А. В. Чернов, “Финитные задачи и логика слабого закона исключенного третьего”, Матем. заметки, 77:2 (2005), 291–302; Math. Notes, 77:2 (2005), 263–272
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm2481https://doi.org/10.4213/mzm2481 https://www.mathnet.ru/rus/mzm/v77/i2/p291
|
Статистика просмотров: |
Страница аннотации: | 555 | PDF полного текста: | 241 | Список литературы: | 79 | Первая страница: | 2 |
|