Преобразование не всех равных 2-Sat Pr0blem в эквивалентную 2-SAT pr0blem

Question

Я просматриваю предыдущие экзаменационные работы и сталкиваюсь с вопросом, который меня смутил.

Вопрос:

Преобразовать задачу Не-все-равные 2-SAT, заданную в пунктах {x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1} к эквивалентной проблеме 2-SAT. (Подсказка: задача 2-SAT содержит 10 пунктов).

Насколько я понимаю, это просто нахождение отрицания для каждого литерала в каждом предложении? Так, например, {x1, x2} = {-x1, -x2}, и это делается для каждого пункта? Это правильно?

Answer 1

Это правильно. В частности, заменить все пункты (x ∨ y) с (x ∨ y) ∧ (~x ∨ ~y), Это буквально говорит, что "x или y должны быть истинными, а x или y должны быть ложными", или эквивалентно "удовлетворять (x ∨ y) убедившись, что один из x а также y ложно ".

Чтобы доказать эквивалентность, давайте сначала предположим, что задача NAE 2-SAT выполнима. Пусть A будет удовлетворительным назначением и пусть {x, y} быть одним произвольным пунктом. Так как именно один из x а также y верно, это означает, что (x ∨ y) ∧ (~x ∨ ~y) правда. Следовательно, соответствующие два пункта в формуле 2-SAT выполняются. поскольку {x, y} был выбран произвольно, и мы заключаем, что A удовлетворяет всем условиям в формуле 2-SAT.

И наоборот, допустим, что NAE 2-SAT не является выполнимым. То есть для любого присвоения существует какой-то пункт {x, y} для которого x а также y либо оба истинны, либо оба ложны. Пусть A будет произвольно выбранным назначением и пусть {x, y} быть пунктом, который A не удовлетворяет (в NAE 2-SAT). поскольку x = yэто означает, что (x ∨ y) ∧ (~x ∨ ~y) ложно (потому что одна из половин соединения будет ложной). Следовательно, A не удовлетворяет формуле 2-SAT. Поскольку A был выбран произвольно, мы заключаем, что ни одно присвоение не удовлетворяет формуле 2-SAT.