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

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

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



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






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


Матем. заметки, 2005, том 77, выпуск 2, страницы 291–302 (Mi mz2481)  

Финитные задачи и логика слабого закона исключенного третьего

А. В. Чернов

Московский государственный университет им. М. В. Ломоносова

Аннотация: Определяется новая характеристика пропозициональной формулы как операции над финитными задачами – мощность достаточного множества решений (ДМР). Доказывается, что если формула выводима в логике слабого закона исключенного третьего, то мощность ДМР ограничена константой, зависящей только от числа переменных; в противном случае достижимая мощность ДМР близка (больше корня некоторой степени) к тривиальной верхней оценке на нее. Это утверждение является аналогом ранее опубликованного результата автора об алгоритмической сложности множеств, полученных как значения пропозициональных формул. Также введено понятие колмогоровской сложности финитной задачи и получены аналогичные результаты.
Библиография: 11 названий.

DOI: https://doi.org/10.4213/mzm2481

Полный текст: PDF файл (220 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Mathematical Notes, 2005, 77:2, 263–272

Реферативные базы данных:

УДК: 510.52
Поступило: 12.11.2003

Образец цитирования: А. В. Чернов, “Финитные задачи и логика слабого закона исключенного третьего”, Матем. заметки, 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/mz2481}
\crossref{https://doi.org/10.4213/mzm2481}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2157096}
\zmath{https://zbmath.org/?q=an:1074.03005}
\elib{http://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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000227418800025}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-20144362969}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mz2481
  • https://doi.org/10.4213/mzm2481
  • http://mi.mathnet.ru/rus/mz/v77/i2/p291

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:313
    Полный текст:64
    Литература:49
    Первая стр.:2

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019