Уникальный 1-в-3 сидел

Question

Предположим, у меня есть формула CNF с пунктами размера 2 и 3. Он имеет уникальное удовлетворение.

Я знаю значение каждого бита уникального назначения, поскольку он был сделан из бинарной схемы умножения, где я умножую два числа простых чисел A и B, что A * B= S где S - это полупроизводитель. Я добавил условия, которые a!= 1, b!= 1 и a <= b, затем добавляли значение s к формуле Убедитесь, что назначение уникально. Единственный способ удовлетворить формулу - поставить значения A и B в правильном порядке на входных битах.

Количество истинных литералов в каждом пункте либо 1, 2 или 3. Поскольку я знаю значение каждого бита, я могу точно сказать, какие литералы верны в каждом пункте, и считают их. Например, я знаю, какие пункты удовлетворены ровно 1 буквальной. И эта буквальная логически является частью уникального решения.

Мой вопрос простой: если я удаляю все пункты с более чем 1 истинным литералом, обязательно будет обязательно будет уникальным?

Другими словами, если я хотел записать доказательство разрешения (вероятно, экспоненциально долго), чтобы продемонстрировать, что решение уникальна (другое решение, в CO-NP), могу ли я записать его, используя только предложения с 1 Истинный буквальный?

Интуитивно, я так думаю, но я не могу защитить мою точку зрения, даже когда думаешь о эквиваленте 2SAT.

Answer 1

Рассмотрим следующие CNF: $$ (A \ lor \ lnot b) \ land (\ lnot \ lor b) \ land (a \ lor b). $$ Он имеет уникальное удовлетворяющее задание, $ a= b=Top $ , который удовлетворяет последнему пункту дважды.Однако, если вы удалите последний пункт, то вы получите еще одно удовлетворение, $ a= b=bot $ .