RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2012, том 407, страницы 111–128 (Mi znsl5488)

Правило сечения в методе резолюций

В. П. Оревков

С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург, Россия

Аннотация: В работе метод резолюций расширяется новым правилом, которое аналогично правилу сечения генценовских секвенциальных исчислений. Получены верхние и нижние оценки сложности опровержений с аналогом правила сечения и без этого правила. Сложность опровержений сравнивается также со сложностью секвенциальных доказательств с сечениями по формулам, которые не содержат импликаций, конъюнкций и квантора $\exists$ и в которые отрицание может входить только непосредственно перед элементарными формулами. Библ. – 3 назв.

Ключевые слова: метод резолюций, опровержение, сечение, секвенция, верхняя оценка, нижняя оценка.

УДК: 510.635+510.57+510.635+510.57

Поступило: 16.04.2012


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2014, 199:1, 56–65

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


© МИАН, 2024