dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 102
Текст из файла (страница 102)
Как и в предыдущем случае, обращаемся к индуктивной гипотезе, утверждающей, что существуют формулы F1 и F2, которые обладают следующимисвойствами.1.Подстановка для формулы E1 (E2) удовлетворяет E1 (E2) тогда и только тогда, когдаона может быть расширена до подстановки, удовлетворяющей формуле F1 (F2).2.Переменные в формулах F1 и F2 различны, за исключением присутствующих в E.3.Формулы F1 и F2 находятся в КНФ.Для того чтобы построить искомую формулу F, мы не можем просто объединить F1и F2 логическим ИЛИ, так как полученная в результате формула не будет находиться вКНФ. Однако можно использовать более сложную конструкцию, которая учитывает,что важно сохранить выполнимость формул, а не их эквивалентность. Предположим, чтоF1 = g1 ∧ g2 ∧ … ∧ gp и F2 = h1 ∧ h2 ∧ … ∧ hq, где символы g и h обозначают дизъюнкты.Введем новую переменную y и определимF = (y + g1) ∧ (y + g2) ∧ … ∧ (y + gp) ∧ ( y + h1) ∧ ( y + h2) ∧ … ∧ ( y + hq).Мы должны доказать, что подстановка T удовлетворяет E тогда и только тогда, когда Tможет быть расширена до подстановки S, удовлетворяющей F.(Необходимость) Пусть подстановка T удовлетворяет E.
Как и в варианте 1, обозначим через T1 (T2) сужение T на переменные E1 (E2). Поскольку E = E1 ∨ E2, то T удовлетворяет E1 или E2. Предположим, что E1 истинна при T. Тогда подстановку T1, представляющую собой сужение T на переменные E1, можно расширить до подстановки S1, длякоторой истинна F1.
Расширение S подстановки T, для которого истинна определеннаявыше формула F, построим следующим образом.1.S(x) = S1(x) для всех переменных x из F1.2.S(y) = 0. Этим выбором всем дизъюнктам F, полученным из F2, придается значение“истина”.3.Для всех переменных x из F2, отсутствующих в F1, S(x) может принимать значения 0или 1 произвольно.4По правилу 1 подстановка S делает истинными все дизъюнкты, полученные из дизъюнктов g, а по правилу 2 — все дизъюнкты, полученные из дизъюнктов h. Поэтому подстановка S удовлетворяет формуле F.4В силу п.
2 не обязательно даже, чтобы S(x) = T(x) при тех x, для которых T(x) определено. —Прим. ред.452Стр. 452ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛЕсли подстановка T не удовлетворяет E1, но удовлетворяет E2, то расширение строится аналогично, за исключением того, что S(y) = 1 в правиле 2. Подстановка S(x) согласуется с S2(x) на переменных, на которых определена S2(x), а значения переменных, присутствующих только в S1, в подстановке S произвольны. Приходим к выводу, что и вэтом случае F истинна при S.(Достаточность) Предположим, что подстановка T для E расширена до подстановкиS для F, и F истинна при S.
В зависимости от значения переменной y возможны два случая. Пусть S(y) = 0. Тогда все дизъюнкты, полученные из дизъюнктов h, истинны. Однако y ложно в дизъюнктах вида (y + gi), получаемых из gi. Это значит, что S придает значение “истина” самим gi, так что F1 истинна при подстановке S.Более строго, пусть S1 — сужение S на переменные F1. Тогда F1 истинна при S1. Поскольку S1 — это расширение подстановки T1, являющейся сужением T на переменныеE1, то согласно гипотезе индукции E1 должна быть истинной при подстановке T1. Но F1истинна при T1, поэтому формула E, представляющая собой E1 ∨ E2, должна быть истинной при T.Остается рассмотреть случай S(y) = 1, аналогичный предыдущему, и это предоставляется читателю. Итак, E истинна при T, если только F истинна при S.Теперь нужно показать, что время, необходимое для построения F по E, не превышает квадрата n — длины E. Независимо от возможного случая, обе процедуры — разбиение E на E1 и E2 и построение формулы F по F1 и F2 — занимают время, линейно зависящее от размера E.
Пусть dn — верхняя граница времени, необходимого для построенияформул E1 и E2 по E, вместе со временем, затрачиваемым на построение формулы F поF1 и F2, в любом из вариантов 1 и 2. Тогда T(n) — время, необходимое для построения Fпо E, длина которой n, описывается следующим рекуррентным соотношением.T(1) = T(2) ≤ e, где e — некоторая константа.T(n) ≤ dn + c max0<i<n–1 (T(i) + T(n – 1 – i)) для n ≥ 3.Константу c еще предстоит определить так, чтобы T(n) ≤ cn2. Базисное правило для T(1)и T(2) говорит о том, что если E — одиночный символ или пара символов, то рекурсияне нужна, поскольку E может быть только одиночным литералом, и весь процесс занимает некоторое время e. В рекурсивном правиле используется тот факт, что E составленаиз подформул E1 и E2, связанных оператором ∧ или ∨, и, если E1 имеет длину i, то E2имеет длину n – i – 1.
Более того, весь процесс построения F по E состоит из двух простых шагов — замены E формулами E1 и E2 и замены F1 и F2 формулой F, — которые,как мы знаем, занимают время, не превышающее dn, плюс два рекурсивных преобразования E1 в F1 и E2 в F2.Докажем индукцией по n, что существует такая константа c, при которой T(n) ≤ cn2для всех n > 0.Базис.
Для n = 1 нам нужно просто выбрать c не меньше, чем e.10.3. ÎÃÐÀÍÈ×ÅÍÍÀß ÏÐÎÁËÅÌÀ ÂÛÏÎËÍÈÌÎÑÒÈСтр. 453453Индукция. Допустим, что утверждение справедливо для длин, которые меньше n.Тогда T(i) ≤ ci2 и T(n – i – 1) ≤ c(n – i – 1)2. Таким образом,T(i) + T(n – i – 1) ≤ n2 – 2i(n – i) – 2(n – i) + 1(10.1)Поскольку n ≥ 3 и 0 < i < n – 1, то 2i(n – i) не меньше n, а 2(n – i) не меньше 2.Поэтому для любого i в допустимых пределах правая часть (10.1) меньше n2 – n.
ТогдаT(n) ≤ dn + cn2 – cn согласно рекурсивному правилу из определения T(n). Выбирая c ≥ d,можно сделать вывод, что неравенство T(n) ≤ cn2 справедливо для n, и завершитьиндукцию. Таким образом, конструкция F из E занимает время O(n2). Пример 10.14. Покажем, как конструкция теоремы 10.13 применяется к простой формулеE = x y + x (y + z). Разбор данной формулы представлен на рис. 10.7. К каждому узлу приписано выражение в КНФ, которое построено по выражению, представленному этим узлом.ИЛИИИИЛИРис.
10.7. Приведение булевой формулы к КНФЛистья соответствуют литералам, и КНФ для каждого литерала — это дизъюнкт, состоящий из одного такого литерала. Например, лист с меткой y связан с КНФ ( y ).Скобки тут не обязательны, но мы ставим их в КНФ, подчеркивая, что речь идет о произведении дизъюнктов.Для узла с меткой И соответствующая КНФ получается как произведение (И) всехдизъюнктов двух подформул.
Поэтому, например, с узлом, соответствующим выражению x (y + z), связана КНФ в виде произведения одного дизъюнкта ( x ), соответствующего x , и двух дизъюнктов (v + y)( v + z), соответствующих y + z.55В данном конкретном случае, когда подформула y + z уже является дизъюнктом, можно невыполнять общее построение дизъюнкта для логического ИЛИ формул, а взять (y + z) в качестве произведения дизъюнктов, эквивалентного y + z. Однако здесь мы строго придерживаемсяобщих правил.454Стр.
454ÃËÀÂÀ 10. ÒÐÓÄÍÎÐÅØÀÅÌÛÅ ÏÐÎÁËÅÌÛДля узла с меткой ИЛИ нужно ввести новую переменную. Добавляем ее во все дизъюнкты левого операнда и ее отрицание во все дизъюнкты правого операнда. Рассмотрим,например, корневой узел на рис. 10.7. Он представляет собой логическое ИЛИ формулx y и x (y + z), для которых соответствующие КНФ были определены как (x)( y ) и( x )(v + y)( v + z), соответственно. Вводим новую переменную u, добавляя ее в дизъюнкты первой группы, а ее отрицание — в дизъюнкты второй группы.
В результате получаем формулуF = (u + x)(u + y )( u + x )( u + v + y)( u + v + z)В теореме 10.13 говорится, что всякую подстановку T, удовлетворяющую E, можнорасширить до подстановки S, удовлетворяющей F. Например, E истинна при подстановке T(x) = 0, T(y) = 1 и T(z) = 1. Можно расширить T до подстановки S, добавляя значенияS(u) = 1 и S(v) = 0 к требуемым S(x) = 0, S(y) = 1 и S(z) = 1, которые берутся из T.
Нетрудно убедиться, что F истинна при S.Заметим, что, выбирая S, мы были вынуждены выбрать S(u) = 1, так как подстановкаT делает истинной только вторую часть E — x (y + z). Поэтому для того, чтобы истинными были дизъюнкты (u + x)(u + y ) из первой части E, необходимо S(u) = 1. Но значение для v можно выбрать любым, так как в соответствии с T в подформуле y + z истинныоба операнда логического ИЛИ. 10.3.4. NP-ïîëíîòà ïðîáëåìû 3-âûïîëíèìîñòèПокажем, что проблема выполнимости NP-полна даже для более узкого класса булевых формул.
Напомним, что проблема 3ВЫП (3-выполнимости) состоит в следующем.• Дана булева формула E, представляющая собой произведение дизъюнктов, каждый из которых есть сумма трех различных литералов. Выполнима ли E?Несмотря на то что формулы вида 3-КНФ — лишь небольшая часть КНФ-формул, ихсложности достаточно, чтобы проверка их выполнимости была NP-полной проблемой.Это показывает следующая теорема.Теорема 10.15. Проблема 3ВЫП NP-полна.Доказательство. Очевидно, что 3ВЫП принадлежит NP, поскольку ВЫП принадлежит NP. Для доказательства NP-полноты сведем ВКНФ к 3ВЫП следующим образом. Вданной КНФ E = e1 ∧ e2 ∧ L ∧ ek каждый дизъюнкт ei заменяется, как описано ниже, исоздается новая формула F.
Время, необходимое для построения F, линейно зависит отдлины E, и, как мы увидим, подстановка удовлетворяет формуле E тогда и только тогда,когда ее можно расширить до подстановки, удовлетворяющей F.10.3. ÎÃÐÀÍÈ×ÅÍÍÀß ÏÐÎÁËÅÌÀ ÂÛÏÎËÍÈÌÎÑÒÈСтр. 455455Если ei — одиночный литерал, скажем, (x)6, то вводятся две новые переменные u и v,и (x) заменяется произведением четырех дизъюнктов1.(x + u + v)(x + u + v )(x + u + v)(x + u + v ).Поскольку здесь присутствуют все возможные комбинации из u и v, то все четыредизъюнкта истинны только тогда, когда x истинна. Таким образом, все подстановки,удовлетворяющие E, и только они, могут быть расширены до подстановки, удовлетворяющей F.2. Предположим, что ei есть сумма двух литералов — (x + y). Вводится новая переменная z, и ei заменяется произведением двух дизъюнктов (x + y + z)(x + y + z ).
Как и вслучае 1, оба дизъюнкта истинны одновременно только тогда, когда истинна (x + y).3.Если дизъюнкт ei есть сумма трех литералов, то он уже имеет вид, требуемый 3-КНФ,и остается в создаваемой формуле F.4.Предположим, что ei = (x1 + x2 + L + xm) при некотором m ≥ 4. Вводятся новые переменные y1, y2, …, ym–3, и ei заменяется произведением дизъюнктов(x1 + x2 + y1)(x3 + y 1 + y2)(x4 + y 2 + y3)L(xm–2 + ym–4+ ym–3)(xm–1 + xm + ym–3).(10.2)Подстановка T, удовлетворяющая E, должна делать истинным хотя бы один из литералов в ei, скажем xj (напомним, что xj может быть либо переменной, либо ее отрицанием). Тогда, если придать переменным y1, y2, …, yj–1 значение “ложь”, а yj, yj+1, …,ym–3 — “истина”, то все дизъюнкты в (10.2) будут истинными.
Таким образом, Tможно расширить до подстановки, удовлетворяющей всем этим дизъюнктам. Наоборот, если при подстановке T все x имеют значение “ложь”, то T невозможно расширить так, чтобы формула (10.2) была истинной. Причина в том, что дизъюнктовm – 2, а каждый y, которых всего m – 3, может сделать истинным лишь один дизъюнкт, независимо от того, имеет ли он значение “истина” или “ложь”.Таким образом, мы показали, как свести любой экземпляр E проблемы ВКНФ к экземпляру F проблемы 3ВЫП, выполнимому тогда и только тогда, когда выполнима формула E. Построение, очевидно, требует времени, которое линейно зависит от длины E,так как ни в одном из рассмотренных выше четырех случаев длина дизъюнкта не увеличивается более, чем в 32/3 раза (соотношение числа символов в случае 1). Кроме того,символы, необходимые для построения формулы F, легко найти за время, пропорциональное числу этих символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
