Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №14, Москва, 2005
Авторы: Чубарян А.А.
O сложности выводов в некоторых системах классического исчисления высказываний
Аннотация:
В работе исследованы сложностные характеристики выводов в системах Фреге и в системах Фреге с правилом подстановки (единичной и мультипликативной). Для произвольной тавтологии φ введено понятие минимально-определяющей дизъюнктивной нормальной формы Ɗmin (φ) и доказано, что количество шагов кратчайшего вывода тавтологии φ в произвольной системе Фреге не превышает с • s • Ɩ , где s – некая характеристика Ɗmin (φ), Ɩ —длина формулы φ и с — некоторая константа, зависящая от выбора системы Фреге. При этом указывается, что для произвольного n можно указать последовательность формул длины n, для которых величина s имеет соответственно порядок n, n2 , n3 ,…, n[√nlogn 2] . В работе доказано также, что существует последовательность тавтологий длины n, для которых и в системах Фреге и в системах Фреге с правилом подстановки оценки количества шагов формул и общей длины выводов имеют порядок n и n2 соответственно. Доказано также, что существуют тавтологии длины n, выводимые с единичной подстановкой не менее, чем за n шагов, а с мульмультипликативной подстановкой не более, чем за log2 n шагов.
Ключевые слова:
сложностные характеристики выводов, системы Фреге, системы Фреге с правилом подстановки, определяющий конъюнкт, минимально-определяющая дизъюнктивная нормальная форма
Язык публикации: русский, страниц: 8 (с. 49-56)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Чубарян Анаит Арташесовна,  ,  Ереванский государственный университет, ф-т информатики и прикладной математики