Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 103
Текст из файла (страница 103)
-(Ем Р) =о -(Е) ы -(Р). Это правило — один из законов Де Моргана — позволяет спустить оператор — под оператор м. Отметим, что в виде побочного эффекта ж ме- няется на и. 2. - (Е ы Р) '=ь ~(Е) еч ~(Р). Другой "закон Де Моргана" позволяет спустить — под опе- ратор ы, изменяемый на л. 3. — ( — (Е)) =о Е.
Этот закон двойного отрицания уничтожает пару операторов -ч при- меняемых к одной формуле. Пример 1011. Рассмотрим формулу Е=- (( (х +у))(х+у)). Заметим, что в ней перемешаны оба используемых обозначения. Оператор — использован явно, когда формула, отрицание которой берется, состоит более чем из одной переменной.
На рис. 10.6 показано, как формула переписывается шаг за шагом до тех пор, пока отрицания — не ста- нут составляющими литералов. Рис.!06. Спуск отрицаний вниз по дереву формулы тат чтобы они встречались только в литералах Заключительная формула эквивалентна исходной и состоит из логических связок И и ИЛИ литералов. Ее можно упростить до формулы х ь у, но это упрощение несушествен- ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ но для нашего утверждения о том, что формулу можно переписать так, чтобы оператор— присутствовал только в литералах.
бЗ Теорема 10.12. Всякая булева формула Е эквивалентна формуле Р; в которой отрица- ния присутствуют только в литералах, т.е. применяются непосредственно к переменным. более того, длина Е линейно зависит от количества символов в Е, и Е можно построить но Е за полиномиальное время. Доказательство. Используем индукцию по числу операторов (л, м и — ) в Е. Покажем, что существует эквивалентная формула Е, в которой — присутствует только в литералах, Кроме того, если Е содержит и > 1 операторов, то Е содержит не более 2п — 1 операторов. Поскольку формуле Е достаточно одной пары скобок для каждого оператора, а число переменных в ней не может превышать числа операторов больше, чем на единицу, то приходим к выводу, что длина Е линейно пропорциональна длине Е.
Более важно, как мы увидим, что время построения Е пропорционально ее длине и, следовательно, — длине Е. Базис. Если Е содержит один оператор, то она должна иметь вид — х, х му или х жу, где х ну — переменные. В каждом из этих случаев формула уже имеет требуемый вид, поэтому Е= Е. Отметим, что, поскольку и Е, и Е содержат по одному оператору, то соотношение "число операторов в Е не превышает числа операторов в Е, умноженного на два, минус один" выполняется. Индукции.
Предположим, что утверждение справедливо для всех формул, число операторов в которых меньше, чем в Е. Если верхний оператор в Š— не —; то формула должна иметь вид Е, м Е, нли Е, ж Ез, В любом из этих случаев гипотеза индукции применима к формулам Е, и Е„и согласно ей существуют эквивалентные формулы — Е, и Ел соответственно, — в которых — встречается только в литералах. Тогда Е= Е, м Р; нли Е= (Е,) л (Ез) служат подходящими эквивалентами для Е, Пусть Е~ и Е, содержат соответственно а и Ь операторов. Тогда Е содержит а + Ь + 1 операторов. Согласно гипотезе индукции Е~ и Р; содержат соответственно 2а — ! и 2Ь вЂ” 1 операторов.
Таким образом, Е содержит не более, чем 2а426-1 операторов, что не превосходит 2(а + Ь + 1) — 1, или числа операторов в Е, умноженного на два, минус 1. Рассмотрим теперь случай, когда Е имеет вид —,Еь В зависимости от верхнего оператора в формуле Е, возможны три варианта. Заметим, что Е, содержит хотя бы один оператор, иначе Š— формула из базиса.
1. Е,= Еь Тогда согласно закону двойного отрицания формула Е= (Ез) эквивалентна Е,. Гипотеза индукции применима, так как в Ез содержится меньше операторов, чем в Е. Можно найти формулу Р; эквивалентную Е,, в которой отрицания встречаются только в литералах. Формула Е годится и для Е. Поскольку число операторов в Е не превышает числа операторов в Е,, умноженного на два, минус 1, то оно, конечно же, не превышает числа операторов в Е, умноженного на два, минус 1. 10.3. ОГРАНИЧЕННАЯ ПРОБЛЕМА ВЫПОЛНИМОСТИ 449 2. Е,=ЕгчЕь Согласно закону Де Моргана формула Е=-(Е2мЕ,) эквивалентна (-(Ее)) л (-(Ез)). Обе формулы - (Е,) и — (Е,) содержат меныпе операторов, чем Е, Поэтому согласно гипотезе индукции существуют эквивалентные им формулы Е~ и Ел в которых отрицания встречаются только в литералах.
Тогда эквивалентом Е служит формула Е = (Р;) л (Р;), Кроме того, мы утверждаем, что число операторов в Е не слишком велико. Пусть Е, и Е, содержат соответственно а и Ь операторов. Тогда в Е содержится а+ Ь+ 2 операторов. Поскольку в формулах — (Е,) и (Е,) соответственно а+ 1 и Ь+ 1 операторов, и формулы Г, и Ез построены по этим формулам, то согласно гипотезе индукции в Ез и Е; не больше, чем 2(а+ 1) — 1 и 2(Ь + 1) — 1 операторов соответственно. Таким образом„Е содержит не более 2а+ 2Ь+ 3 операторов, а это и есть число операторов в Е, умноженное на два, минус ! .
3. Еу = Е2 л Еь Обоснование этой части, использующее второй закон Де Моргана„аналогично пункту 2. Описания алгоритмов Формально время работы алгоритма сведения есть время, необходимое для выполнения его на одноленточной машине Тьюринга, однако такие алгоритмы слишком сложны. Мы знаем, что множества проблем, которые можно решить за полиномиальное время на обычных компьютерах, многоленточных и одноленточных МТ, совпадают, хотя степени полиномов при этом могут различаться. Таким образом, описывая некоторые по-настоящему сложные алгоритмы, требующие сведения одной ХР-полной проблемы к другой, примем соглашение, что время сведения будет ограничено временем работы его эффективной реализации на обычном компьютере.
Это избавит нас от подробностей обработки лент и позволи~ выделить по-настоящему важные ал- горитмические идеи. 10.3.3. |з|Р-полнота проблемы ВКНФ Теперь нам необходимо привести к КНФ формулу Е, которая состоит из логических И и ИЛИ литералов. Как уже упоминалось, чтобы за полиномиальное время создать по Е формулу Е; выполнимую тогда и только тогда, когда выполнима Е, нужно отказаться от преобразования, сохраняющего эквивалентность формул, и ввести в Е новые переменные, отсутствующие в Е. Используем этот прием в доказательстве теоремы об ХР-полноте проблемы ВКНФ, а затем приведем пример его применения.
Теорема 10.13. Проблема ВКНФ ХР-полна. Доказательство. Покажем, как свести ВЪ|П к ВКНФ за полиномиальное время. Вначале с помощью метода, описанного в теореме 10,12, преобразуем данный экземпляр ВЫП в формулу Е, содержащую ~ только в литералах. Затем покажем, как за полиноми- ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ 450 аяьное время преобразовать Е в КНФ-формулу Е, выполнимую тогда и только тогда, когда выполнима Е. Формула Е строится индуктивно по длине Е, а ее конкретные свойства — это даже больше, чем нам нужно. Точнее, индукцией по числу вхождений символов а Е("длине") докажем следующее утверждение. ° Пусть Š— булева формула длины и, в которой — встречается только в литералах.
Тогда существуют константа с и формула Е, удовлетворяющие утверждениям: а) Е находится в КНФ, и содержит не более и дизъюнктов; б) Е можно построить по Е за время, не превышаюшее с~Е~; в) подстановка Т для Е делает Е истинной тогда и только тогда, когда сушествует расширение Е подстановки Т, удовлетворяюгцее формуле Е. Базис. Если Е состоит нз одного или двух символов, то оно — литерал. Литерал является дизъюнктом, поэтому Е уже находится в КНФ. Иидукция. Предположим, что всякую формулу, более короткую, чем Е, можно преобразовать в произведение дизъюнктов, и для формулы длиной и это преобразование занимает время не более си .
В зависимости от верхнего оператора Е возможны два варианта. Вариант!. Е= Е, л Е,. Согласно гипотезе индукции существуют формулы Е~ и Ел которые выводятся из Е, и Е,, соответственно, и находятся в КНФ. Все подстановки, удовлетворяющие Еь и только они, могут быть расширены до подстановок, удовлетворяющих Еь То же самое верно для Е, и Еь Не теряя обшности, можно предполагатгь что переменные в Е, и Еэ различны, за исключением переменных, присутствующих в Е, т.е. вводимые в Е, и/нли Е переменные выбираются различными.
Рассмотрим Е.= Е, л Еэ. Очевидно, что формула Е, л Е, находится в КНФ, если в КНФ ваходятся Е, и Е,. Нам нужно показать, что подстановку Т для формулы Е можно расширить до подстановки, удовлетворяюшей Е, тогда и только тогда, когда Тудовлетворяет Е. (Доставочность) Пусть Т удовлетворяет Е. Пусть Т, и Т.
— сужения подстановки Т, применяемые ~олько к переменным формул Е~ и Ел соответственно. Тогда согласно индуктивной гипотезе Т~ и Т, могут быть расширены до подстановок Е, и эл удовлетворяюших Е, и Е, соответственно. Пусть Š— подстановка, согласованная с Е, и Еи т.е. приписывает переменным те же значения, что Е, и Еэ. Заметим, что лишь переменные из Е присутствуют и в Еь и в Рь поэтому подстановки Е, и Яэ согласованы на переменных, яа которых обе они определены, и построить Е всегда возможно.
Но тогда Е есть расширение Т, удовлетворяющее Е. (Необходимость) Наоборот, пусть подстановка Т имеет расширение Е, удовлетворяющее Е. Пусть Т, ГТэ) — сужение Т на переменные Е, (Е,). Сужение Е на переменные Е, (Еэ) обозначим через Е, (о ). Тогда Е, — это расширение Т„а Š— расширение Т.. Поскольку Е есть логическое И формул Е, и Еи Е, должна удовлетворять формуле Еь а Я, — формуле Е,. Согласно гипотезе индукции Т, (Тэ) должна удовлетворять Е, (Еэ). Поэтому Тудовлетворяет Е. 10.3. ОГРАНИЧЕННАЯ ПРОБЛЕМА ВЫПОЛНИМОСТИ 451 Вариант 2.
Е = Ез м Е,. Как и в предыдущем случае, обращаемся к индуктивной гипотезе, утверждаюгдей, что существуют формулы Г, н Гь которые обладают следуюшими свойствами. 1. Подстановка для формулы Е, (Е,) удовлетворяет Ез (Е,) тогда и только тогда, когда она может быть расширена до подстановки, удовлетворяющей формуле Г, (Г,). 2.
Переменные в формулах Гз и Гх различны, за исключением присутствующих в Е. 3. Формулы Г, и Г, находятся в КНФ. Для того чтобы построить искомую формулу Г, мы не мажем просто объединить Г, и Гх логическим ИЛИ, так как полученная в результате формула не будет находиться в КНФ. Однако можно использовать более сложную конструкцию, которая учитывает, что важно сохранить выполнимость формул, а не их эквивалентность. Предположим, что Гз = из ж дхл ... жир и Гз= Ь, ж )зхж ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
