Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 104
Текст из файла (страница 104)
ж Ья, где символы д и Ь обозначают дизъюнкты. Введем новую переменную у и определим Г = 1у ь я,) д (у ь яз) ж ... ж (у -ь я„) ж !у ь Ь,) ж ( т н Ь,) ж ... ж ( т .ь Ь ). Мы должны доказать, что подстановка Т удовлетворяет Е тогда и только тогда, когда Т может быть расширена до подстановки 5, удовлетворяющей Г. 1гтеобходииоспзь) Пусть подстановка Т удовлетворяет Е. Как и в варианте 1, обозначим через Т, (Т,) сужение Т на переменные Ез (Е,). Поскольку Е = Е, ч Еь то Т удовлетворяет Е, или Е,.
Предположим, что Ез истинна при Т. Тогда подстановку Т,, представляющую собой сужение Т на переменные Еь можно расширить до подстановки Еь для которой истинна Рн Расширение 5 подстановки Т, для которого истинна определенная выше формула Г, построим следующим образом. а1х) = Ез(х) для всех переменных х из Г,. 2. Яу) = О. Этим выбором всем дизъюнктам Г, полученным из Гз, придается значение "истина". 3. Для всех переменных х из Гь отсутствующих в Г,, 5(х) может принимать значения О или 1 произвольно. 4 По правилу! подстановка 5 делает истинными все дизъюнкты, полученные из днзьюнктов я, а по правилу 2 — все дизъюнкты, полученные из дизъюнктов Ь.
Поэтому подстановка Я удовлетворяет формуле Е'. Если подстановка Т не удовлетворяет Еи но удовлетворяет Еь то расширение строится аналогично, за исключением того, что Яу) = 1 в правиле 2. Подстановка Я(х) согласуется с Я,(х) на переменных, на которых определена Яз(х), а значения переменных, при- " Б силу п. 2 не обязательно даже, чтобы 5(х) = Дх) при тех х, лля которых Т1х) определено.— Прим. ред.
452 ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ сутствующих только в Еь в подстановке Ь' произвольны. Приходим к выводу, что и в зтом случае Е истинна при Е. (Достаеочмость) Предположим, что подстановка Т для Е расширена до подстановки з для Е, и Е истинна при Е. В зависимости от значения переменной у возможны два случая. Пусть Б(у) = О. Тогда все дизъюнкты, полученные из дизъюиктов Ь, истинны.
Однако у ложно в дизъюнктах вида (у + 3,), получаемых из 3,. Это значит, что Е придает значеиие "истина" самим дч так что Е, истинна прн подстановке Е. Более строго, пусть Е, — сужение Б на переменные Еь Тогда Е, истинна при Еь Поскольку Е, — это расширение подстановки Ть являюшейся сужением Т на переменные Еь то согласно гипотезе индукции Е, должна быть истинной при подстановке Ть Но Е истинна при Т„поэтому формула Е, представляющая собой Е, м Еь должна быть истинной при Т. Остается рассмотреть случай Яу) = 1, аналогичный предыдушему, и зто предоставляется читателю.
Итак, Е истинна при Т, если ~олько Е истинна при Е. Теперь нужно показать, что время, необходимое для построения Е по Е, не превышает квадрата п — длины Е. Независимо от возможного случая, обе процедуры — разбнеиие Е на Е> и Ез и построение формулы Е по Е, и Еу — занимают время, линейно зависящее от размера Е. Пусть ~7п — верхняя граница времени, необходимо~о для построения формул Е, и Е по Е, вместе со временем, затрачиваемым на построение формулы Е по Е~ и Еь в любом из вариантов 1 и 2.
Тогда Т(н) — время, необходимое для построения Е по Е, длина которой и, описывается следующим рекуррентным соотношением. Т(1) = Т(2) < е, где е — некоторая константа. Т(п) < дп -ь с шаха, .„, (7(1) ч 7(п — ! — 1)) для п > 3. Константу с еше предстоит определить так, чтобы 7(п) < сп . Базисное правило для Т(1) и 7(2) говорит о том, что если Š— одиночный символ или пара символов, то рекурсия ие нужна, поскольку Е может быть только одиночным литералом, и весь процесс занимает некоторое время е. В рекурсивном правиле используется тот факт, что Е составлена из подформул Е, и Е,, связанных оператором л или м, и, если Е, имеет длину Б то Е, имеет длину и-! — 1.
Более того, весь процесс построения Е по Е состоит из двух простых шагов — замены Е формулами Е, и Е, и замены Е, и Е, формулой Е, — которые, как мы знаем, занимают время, не превышаюшее Ып, плюс два рекурсивных преобразования Е, в Е, и Е, в Р> Докажем индукцией по и. что существует такая константа с, при которой 7(л) < сп~ для всех п > О. Базис. Для п =! нам нужно просто выбрать с ие меньше, чем е, Индукции. Допустим, что утверждение справедливо для длин, которые меньше ж Тогда 7(1) < с1 н Т(п — 7 — 1) < с(п — ! — ! ) .
Таким образом, Т(1) + 7(п — 7 — 1) < пз — 27(п — 7) — 2(п — 7) ч 1 (10.1) 10.3. ОГРАНИЧЕННАЯ ПРОБЛЕМА ВЫПОЛНИМОСТИ 453 Поскольку п>3 и 0 <1< и — 1, то 2((п — е) не меньше и, а 2(~ — е) не меньше 2. Поэтому для любого 1 в допустимых пределах правая часть (! О.1) меньше и — л. Тогда 2 Т(п) < е(п+ сп' — сн согласно рекурсивному правилу из определения Т(н). Выбирая с > е(, можно сделать вывод, что неравенство Т(н)<сн справедливо для и, и завершить 2 индукцию.
Таким образом, конструкция Е из Е занимает время О(н'). П Пример 10.14. Покажем, как конструкция теоремы 10.13 применяется к простой формуле Е = х у ь х (у+ -). Разбор данной формулы представлен на рис. 1О 7. К каждому узлу припи- сано выражение в КНФ, которое построено по выражению, представленному этим узлом. (и+к)(и+у)(и+те)(и+и+у)(и+Т+е) (пее) (е) Рис. /О.7. Приведение булевой формулы к КНФ Листья соответствуют литералам, и КНФ для каждого литерала — это днзъюнкт, состоящий из одного такого литерала.
Например, лист с меткой у связан с КНФ (у ), Скобки тут не обязательны, но мы ставим нх в КНФ, подчеркивая, что речь идет о про- изведении дизъюнктов. Для узла с меткой И соответствующая КНФ получается как произведение (И) всех дизъюнктов двух подформул. Поэтому, например, с узлом, соответствующим выражению х(у+ а), связана КНФ в виде произведения одного дизъюнкта (х ), соответствующего х, н двух днзъюнктов(и +у)(й-ъг), соответствующнху+ -. Для узла с меткой ИЛИ нужно ввести новую переменную.
Добавляем ее во все дизьюнкты левого операнда и ее отрицание во все днзъюнкгы правого операнда. Рассмотрим, например, корневой узел на рис. 10.7, Он представляет собой логическое ИЛИ формул хи н х(у+с), для которых соответствующие КНФ были определены как (х)(у) и 5 В ланном конкретном случае, когда полформулау+ е уже является дизъюнктом, можно не выполнять общее построение лизъюнкта лля логического ИЛИ формул, а взять (у+ е) в качестве произведения лизъюнктов, эквивалентного у+в. Олнако здесь мы строго придерживаемся общих правил.
ГЛАВА 10. ТРУДНОРЕШАЕМЫЕ ПРОБЛЕМЫ (х )(»+у)(й+ г), соответственно. Вводим новую переменную и, добавляя ее в дизъюнкты первой группы, а ее отрицание — в дизъюнкгы второй группы. В результате получаем формулу Е=(и+я)(и+ у )(й+ х)(й+ «+у)(й+ «+х) В теореме 10.13 говорится, что всякую подстановку Т, удовлетворяюшую Е, можно расширить до подстановки Я удовлетворяющей Е Например, Е истинна при подстановке Т(х) = О, Т(у) = 1 н Т(х) = !. Можно расширить Тдо подстановки 5, добавляя значения Яи) = 1 и о(г) = 0 к требуемым Е(х) = О, Яу) = 1 и 5(я) = 1, которые берутся из Т.
Нетрудно убедиться, что Е истинна прн о. Заметим, что, выбирая Я мы были вынуждены выбрать Яи) = 1, так как подстановка Т делае~ истинной только вторую часть Š— х (у+ -). Поэтому для того, чтобы истинными были дизъюнкты (и+ х)(и+ у ) из первой части Е, необходимо 5(и) = 1. Но значе- ние для» можно выбрать любым, так как в соответствии с Т в подформуле у+ = истинны оба операнда логического ИЛИ. ЕЗ 10.3.4. (к!Р-полнота проблемы 3-выполнимости Покажем, что проблема выполнимости МР-полна даже для более узкого класса булевых формул.
Напомним, что проблема ЗВЫП (3-выполнимости) состоит в следуюшем. ° Дана булеза формула Е, представляющая собой произведение дизъюнктов, каждый из которых есть сумма трех различных литералов. Выполнима ли Е? Несмотря на то что формулы вида 3-КНФ вЂ” лишь небольшая часть КНФ-формул, их сложности достаточно, чтобы проверка их выполнимости была ХР-полной проблемой. Это показывает следуюшая теорема. Теорема 10.15. Проблема ЗВЫП ХР-полна. Доказательство. Очевидно, что ЗВЫП принадлежит Лчо, поскольку ВЫП принадлежит МР.
Для доказательства ХР-полноты сведем ВКНФ к ЗВЫП следующим образом. В данной КНФ Е = е, л е, л " л ет каждый дизъюнкт е, заменяется, как описано ниже, н создается новая формула Е Время, необходимое для построения Р; линейно зависит от длины Е, и, как мы увидим, подстановка удовлетворяет формуле Е тогда и только тогда, когда ее можно расширить до подстановки, удовлетворяющей Р'.
1. Если е, — одиночный литерал, скажем, (х)', то вводятся две новые переменные и и», и (х) заменяется произведением четырех дизъюнктов (х+ и + «)(х+ и +» )(х+ и 4 1)(х + й + «). б Для улобства, говоря о литералах, считаем нх переменными без отрицания, например х. Но все наши построению остаются в силе н в том случае, когда некоторые нлн все литералы являются отрицаниями переменных, например х . 10.3. ОГРАНИЧЕННАЯ ПРОВЛЕМА ВЫПОЛНИМОСТИ 4бб Поскольку здесь присутствуют все возможные комбинации из и и г, то все четыре дизъюнкта истинны только тогда, когда х истинна. Таким образом, все подстановки, удовлетворяющие Е, и только они, могут быть расширены до подстановки, удовлетворяющей Е.
2. Предположим, что е, есть сумма двух литералов — (х ьу). Вводится новая переменная х, и е, заменяется произведением двух дизъюнктов (х+у+ г)(х+у+ х ). Как и в случае 1, оба дизъюнкта истинны одновременно только тогда, когда истинна (х + у). 3. Если дизъюнкт е, есть сумма трех литералов, то он уже имеет вид, требуемый З-КНФ, и остается в.создаваемой формуле Е. 4. Предположим, что е, =(х, +х:+" +х ) при некотором иг >4. Вводятся новые пе- ременные уь ул ...,у г, и е, заменяется произведением дизъюнктов (хг '~' хг ь уг)(хз '~" ~~ г ь у )(хз '~" у '~ уз)' '' (х ~ -г у к+у з)(х г -ьх„г у,„з). (10.2) Подстановка Т, удовлетворяющая Е, должна делать истинным хотя бы один из литералов в е„скажем х, (напомним, что х, может быть либо переменной, либо ее отрицанием).
Тогда, если придать переменным уг, у..., у,, значение "ложь", а у„у, ь ..., у, — "истина", то все дизъюнкты в (10.2) будут истинными. Таким образом, Т можно расширить до подстановки, удовлетворяющей всем этим дизъюнктам. Наоборот, если при подстановке Т все х имеют значение "ложь*', то Т невозможно расширить так, чтобы формула (10.2) была истинной. Причина в том, что дизъюнктов и — 2, а каждый у, которых всего и — 3, може~ сделать истинным лишь один дизь- юнкт, независимо от того, имеет ли он значение "истина" или "ложь". Таким образом, мы показали, как свести любой экземпляр Е проблемы ВКНФ к экземпляру Е проблемы ЗВЪ|П, выполнимому тогда и только тогда, когда выполнима формула Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
