Монотонная формула CNF с m членами на n переменных ( ) - это формула вида , где каждый является ИЛИ некоторого подмножества переменных и находятся в диапазоне от до . f ( x 1 , … , x n ) = ⋀ C i C i x 1 , … , x n i 1 м
Например, - это монотонная формула CNF с 2 членами на 4 переменных.
Я ищу самую короткую формулу (не обязательно монотонную, не обязательно CNF, подойдет любая формула!) Для того же набора переменных, который представляет ту же функцию, что и заданная монотонная формула CNF для n переменных с n членами. (Обратите внимание, что количество терминов и переменных одинаково.)
Одним из очевидных способов построения формулы является расширение данного определения CNF, которое даст нам формулу размера . (Давайте определим размер формулы как длину формулы, когда она записана в виде строки.) Я хочу знать, является ли это наиболее эффективной общей конструкцией или существует ли для каждого n-членного монотонного CNF формула? размером .o ( n 2 )
Я просто хочу знать, возможно ли это, меня не очень интересует алгоритм. Если это невозможно, функция, которая служит контрпримером, была бы великолепна. Указатели на то, где я могу найти ответ в литературе, также приветствуются.
РЕДАКТИРОВАТЬ: я добавляю пример, чтобы сделать яснее.
Скажем, входная формула имеет вид . Это монотонная формула CNF. Более короткая формула , которая представляет собой ту же самую функцию , состоит в следующем: х 1 ∨ ( х 2 ∧ х 3 ∧ ... ∧ х п ) .
источник
Учтите, что для любого CNF вы можете вычислить множество простых импликатов (из которых любой минимум должен быть подмножеством), взяв замыкание в соответствии с разрешением и применив исключение из подсчета.
Однако в случае любого монотонного CNF закрытие разрешения F равно F (поскольку отрицательных литералов нет, разрешение невозможно). Следовательно, минимальный CNF - это множество простых импликатов, и это именно та формула, которую вы уже имеете.F F F
Конечно, я предполагаю, что вы не хотите вводить новые переменные.
Если вы хотите убедиться, что у вас есть какая-то формула, которая имеет терминов, то, как вы предлагаете, единственный способ получить это - расширить некоторые пункты, добавив отсутствующие переменные. Любой такой CNF должен иметь одинаковое количество литералов (размер, который, как я полагаю, вы полагаете) для фиксированных f и n .N е N
источник