Математические заметки
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Матем. заметки:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Математические заметки, 2005, том 77, выпуск 2, страницы 291–302
DOI: https://doi.org/10.4213/mzm2481 (Mi mzm2481) 		 
Финитные задачи и логика слабого закона исключенного третьего

А. В. Чернов

Московский государственный университет им. М. В. Ломоносова
PDF полного текста (220 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/mzm2481
Аннотация: Определяется новая характеристика пропозициональной формулы как операции над финитными задачами – мощность достаточного множества решений (ДМР). Доказывается, что если формула выводима в логике слабого закона исключенного третьего, то мощность ДМР ограничена константой, зависящей только от числа переменных; в противном случае достижимая мощность ДМР близка (больше корня некоторой степени) к тривиальной верхней оценке на нее. Это утверждение является аналогом ранее опубликованного результата автора об алгоритмической сложности множеств, полученных как значения пропозициональных формул. Также введено понятие колмогоровской сложности финитной задачи и получены аналогичные результаты.
Библиография: 11 названий.
Поступило: 12.11.2003
Англоязычная версия:
Mathematical Notes, 2005, Volume 77, Issue 2, Pages 263–272
DOI: https://doi.org/10.1007/s11006-005-0025-z
Реферативные базы данных:
УДК: 510.52
Образец цитирования: А. В. Чернов, “Финитные задачи и логика слабого закона исключенного третьего”, Матем. заметки, 77:2 (2005), 291–302; Math. Notes, 77:2 (2005), 263–272
Цитирование в формате AMSBIB
\RBibitem{Che05}
\by А.~В.~Чернов
\paper Финитные задачи и логика слабого закона исключенного третьего
\jour Матем. заметки
\yr 2005
\vol 77
\issue 2
\pages 291--302
\mathnet{http://mi.mathnet.ru/mzm2481}
\crossref{https://doi.org/10.4213/mzm2481}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2157096}
\zmath{https://zbmath.org/?q=an:1074.03005}
\elib{https://elibrary.ru/item.asp?id=14466483}
\transl
\jour Math. Notes
\yr 2005
\vol 77
\issue 2
\pages 263--272
\crossref{https://doi.org/10.1007/s11006-005-0025-z}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000227418800025}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-20144362969}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mzm2481
  • https://doi.org/10.4213/mzm2481
  • https://www.mathnet.ru/rus/mzm/v77/i2/p291
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Математические заметки Mathematical Notes
    Статистика просмотров:
    Страница аннотации:533
    PDF полного текста:228
    Список литературы:70
    Первая страница:2
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024