Аннотация:
Рассматривается представление предикатов над конечным множеством в виде обобщенных конъюнктивных нормальных форм (ОКНФ). Найдены свойства ОКНФ предикатов, которые сохраняет некоторая функция большинства. Такие предикаты названы обобщенно биюнктивными. На основе полученных свойств предложены более быстрые полиномиальные алгоритмы решения задачи обобщенной выполнимости в случае, когда сохраняет все исходные предикаты некоторая функция большинства.
Ключевые слова:предикат над конечным множеством, функция над конечным множеством, функция большинства (мажоритантная функция), биюнктивный предикат, конъюнктивная нормальная форма, задача обобщенной выполнимости (удовлетворения ограничений), полиномиальная задача.
УДК:519.716
Статья поступила: 10.10.2017 Переработанный вариант поступил: 16.11.2017
Полный текст:
PDF файл (477 kB)