Страница публикации
О преобразованиях Цейтина в логических уравнениях
Авторы: Семёнов А.А.
Журнал: Прикладная дискретная математика
Том:
Номер: 4 (6)
Год: 2009
Отчётный год: 2009
Издательство:
Местоположение издательства:
URL:
Аннотация: В статье сообщается о применении преобразований Цейтина в различных областях пропозициональной логики, связанных с решением систем логических уравнений. Показывается, что преобразования Цейтина не изменяют числа решений системы логических уравнений, и строится биекция между множествами решений системы и результата её преобразований по Цейтину. Приводятся некоторые результаты по применению преобразований Цейтина к построению оценок сложности систем пропозиционального вывода. С использованием преобразований Цейтина строятся простейшие доказательства NP-полноты проблемы совместности системы логических уравнений степени 2 и #Р-полноты проблемы подсчёта числа выполняющих наборов для хорновской КНФ. С использованием преобразований Цейтина показывается также, что ROBDD-граф для булевой функции в хорновской КНФ или в КНФ с двухбуквенными дизъюнктами нельзя построить за полиномиальное время, если Р ≠ NP.
Индексируется WOS: 0
Индексируется Scopus: 0
Индексируется РИНЦ: 1
Публикация в печати: 0
Добавил в систему: