В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики, страница 3

Найти размер максимальной клики графа G:1) G - граф на рис. 2;2) G - граф на рис. 5;3) G - граф на рис. 8;4) G - граф на рис. 9.2.6. Найти минимальное вершинное покрытие графа G:1) G - граф на рис. 1;2) G - граф на рис. 2;3) G - граф на рис. 3;4) G - граф на рис.

6.2.7. 1. Доказать полиномиальную решаемость задачи 2-ВЫП.2. Продемонстрировать работу полиномиального алгоритма для задачи 2-ВЫП на примере входа K, если:1) K = (x1 ∨ x2 )(x̄2 ∨ x3 )(x̄2 ∨ x1 )(x̄1 ∨ x̄3 )x4 (x4 ∨ x5 )(x1 ∨ x3 )(x3 ∨ x̄1 );2) K = (x̄1 ∨ x4 )x1 (x2 ∨ x̄3 )(x5 ∨ x̄2 )(x̄2 ∨ x3 )x4 (x̄2 ∨ x̄5 )(x2 ∨ x̄6 ).2.8.

Продемонстрировать работу жадного алгоритма для задачи поиска минимального остовного дерева на примере входа G:G:2.9. Доказать, что следующие задачи принадлежат классу NP.1) Задача L1:Вход: граф G = (V, E), число k.Вопрос: есть ли в графе G простой цикл длины k?Доказать, что L1 ∈ NP.2) Задача L2:Вход: граф G = (V, E), число k.Вопрос: есть ли в графе G вершина степени k?Доказать, что L2 ∈ NP.3) Задача L3:Вход: матрица M из 0 и 1 размера n × m, число k.Вопрос: есть ли покрытие матрицы M мощности k (множество строкматрицы M называется ее покрытием, если в образованной ими подматрице нет нулевых столбцов)?Доказать, что L3 ∈ NP.4) Задача L4:Вход: матрица M из 0 и 1 размера n × m без совпадающих столбцов,число k.Вопрос: есть ли тест для матрицы M длины k (множество строк матрицы M называется тестом, если в образованной ими подматрице всестолбцы различны; длиной теста называется число строк в нем)?Доказать, что L4 ∈ NP.2.10.

Построить преобразование входа задачи L1 во вход задачи L2 ,доказывающее полиномиальную сводимость языка L1 к языку L2 :1) L1 есть ВЫП, L2 есть 0-1 ЦЛП;2) L1 есть ВЫП, L2 есть 3-ВЫП;3) L1 есть КЛИКА, L2 есть ВЕРШИННОЕ ПОКРЫТИЕ;4) L1 есть ВЕРШИННОЕ ПОКРЫТИЕ, L2 есть ПОКРЫТИЕ МНОЖЕСТВ.2.11. Данный вход K задачи ВЫП преобразовать во вход K 0 задачи3-ВЫП:1) K = (x1 ∨ x2 ∨ x3 ∨ x4 )(x̄1 ∨ x2 ∨ x̄3 ∨ x̄4 )(x̄2 ∨ x̄3 ∨ x4 );2) K = (x3 ∨ x̄1 ∨x2 ∨ x̄5 ∨ x̄4 )x̄2 (x̄2 ∨x1 ∨x5 ∨ x̄3 )(x3 ∨x4 )(x1 ∨ x̄3 ∨x4 ∨x5 ).2.12. По КНФ K построить 0-1 матрицу A и вектор b, являющиесявходом задачи 0-1 ЦЛП, соответствующим КНФ K:1) K = (x̄1 ∨ x̄2 )(x̄1 ∨ x̄3 );2) K = (x̄1 ∨ x̄2 ∨ x3 )(x1 ∨ x̄3 );3) K = (x̄1 ∨ x2 ∨ x̄3 )(x1 ∨ x̄2 ∨ x̄4 );4) K = (x1 ∨ x̄2 ∨ x3 )(x̄1 ∨ x2 ∨ x̄3 );5) K = (x̄1 ∨ x2 ∨ x̄3 ∨ x3 )(x1 ∨ x̄2 )(x̄2 ∨ x3 );6) K = (x1 ∨ x̄2 ∨ x3 )(x̄1 ∨ x̄2 )(x1 ∨ x̄3 );7) K = (x̄1 ∨ x2 ∨ x3 )(x̄1 ∨ x3 )(x̄2 ∨ x4 );8) K = (x1 ∨ x2 ∨ x̄4 )(x̄1 ∨ x3 )(x̄2 ∨ x̄4 ).2.13.

По КНФ K, являющейся входом для языка ВЫП, построитьграф G и число k, являющиеся входом для задачи КЛИКА:1) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x3 )(x1 ∨ x3 );2) K = x1 (x2 ∨ x3 )(x1 ∨ x3 ∨ x4 )x2 ;3) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x3 )(x1 ∨ x3 );4) K = x3 (x1 ∨ x4 )(x1 ∨ x2 )(x4 ∨ x2 );5) K = (x1 ∨ x2 ∨ x4 )(x3 ∨ x4 )(x1 ∨ x2 ∨ x4 );6) K = (x1 ∨ x3 )(x2 ∨ x3 ∨ x4 )(x2 ∨ x4 )(x1 ∨ x4 );7) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x3 ∨ x4 )(x1 ∨ x4 )(x2 ∨ x3 );8) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x4 )(x1 ∨ x4 )x5 .2.14. По КНФ K, являющейся входом для задачи ВЫП, построитьграф G и число l, являющиеся входом задачи ВЕРШИННОЕ ПОКРЫТИЕ:1) K = (x1 ∨ x2 ∨ x3 )(x1 ∨ x2 )(x1 ∨ x2 );2) K = (x1 ∨ x2 ∨ x3 )(x1 ∨ x2 ∨ x3 )(x1 ∨ x3 );3) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x3 ∨ x4 )(x1 ∨ x4 );4) K = (x1 ∨ x4 ∨ x2 )(x1 ∨ x3 )(x4 ∨ x2 ∨ x3 );5) K = (x2 ∨ x3 )(x1 ∨ x3 ∨ x4 )x4 (x1 ∨ x2 );6) K = (x1 ∨ x2 )(x3 ∨ x5 )(x1 ∨ x2 ∨ x4 );7) K = (x1 ∨ x2 ∨ x3 )(x1 ∨ x4 ∨ x5 )(x1 ∨ x3 ∨ x5 );8) K = (x2 ∨ x3 )(x1 ∨ x2 ∨ x4 )(x1 ∨ x2 ∨ x4 ).2.15.

Граф G и число l являются входом задачи ВЕРШИННОЕ ПОКРЫТИЕ. Построить вход задачи ПОКРЫТИЕ МНОЖЕСТВ, соответствующий паре (G, l):1) l = 2, G:2) l = 3, G:3) l = 3, G:4) l = 3, G:2.16. Данный вход задачи КЛИКА преобразовать во входы задачВЕРШИННОЕ ПОКРЫТИЕ и ПОКРЫТИЕ МНОЖЕСТВАМИ:1) k = 4, G:2) k = 4, G:2.17. Доказать NP-полноту задач 1 – 8 из введения к параграфу.2.18. Доказать, что следующие задачи являются NP-полными:1) существование набора, обращающего ДНФ в ноль;2) существование набора, обращающего ДНФ в ноль при условии, чтокаждое слагаемое этой ДНФ содержит не более 4 букв.2.19.

Выделить среди перечисленных задач полиномиально решаемыеи NP-полные (при условии P 6= NP):1) существование двух противоположных наборов, на которых ДНФобращается в единицу;2) существование двух противоположных наборов, на которых ДНФобращается в ноль;3) существование набора, на котором полином Жегалкина обращаетсяв ноль;4) существование набора, на котором заданные полиномы Жегалкина(количество которых заранее неизвестно) одновременно обращаются вноль;5) существование эйлерова цикла в графе (эйлеровым циклом называется цикл, проходящий по всем ребрам графа, причем по каждому вточности один раз);6) существование гамильтонова цикла в графе (гамильтоновым циклом называется простой цикл, проходящий через все вершины графа);7) раскраска вершин графа в два цвета (граф можно раскрасить в двацвета, если каждой его вершине можно приписать цвет таким образом,что смежным вершинам приписаны разные цвета);8) раскраска вершин гиперграфа в два цвета (гиперграфом называется пара < V, E >, где V — конечное множество вершин, E, E ⊆ 2V —множество ребер; гиперграф можно раскрасить в два цвета, если каждой его вершине можно приписать цвет таким образом, что любое ребробудет содержать по меньшей мере две вершины, окрашенные в разныецвета).2.20.

Выяснить, какие из перечисленных задач являются полиномиально решаемыми, какие — NP-полными:1) распознавание нелинейности булевой функции, еслиа) функция задана таблицей своих значений,б) функция задана формулой,в) функция задана в виде ДНФ,г) функция задана в виде сокращенной ДНФ,д) функция задана в виде полинома Жегалкина;2) распознавание немонотонности булевой функции, еслиа) функция задана таблицей своих значений,б) функция задана формулой,в) функция задана в виде ДНФ,г) функция задана в виде сокращенной ДНФ,д) функция задана в виде полинома Жегалкина;3) распознавание несамодвойственности функции, еслиа) функция задана таблицей своих значений,б) функция задана формулой,в) функция задана в виде ДНФ,г) функция задана в виде совершенной ДНФ,д) функция задана в виде полинома Жегалкина;4) существовование в графе k-клики (k-кликой называется подграф,являющийся полным графом с k вершинами), еслиа) число k заранее известно,б) число k подается на вход МТ вместе с графом;2.21.

Доказать полиномиальную эквивалентность задач L1 и L2 , если1) L1 = ВЫП, L2 = 4-ВЫП;2) L1 = РАСКРАСКА ГРАФА В 2 ЦВЕТА; L2 = УМНОЖЕНИЕ ДВОИЧНЫХ ЧИСЕЛ.••••••••••••••••••••••••••Рис. 1.Рис. 2.••••••••••••••Рис. 4.••••••Рис. 3.•••••••Рис. 6.Рис. 5.••••• • • • •• • • • •Рис. 9.•Рис. 8.••••Рис. 7.•••Часть 2. Эквивалентные преобразования§ 3. Эквивалентные преобразовния формулДве формулы алгебры логики называются эквивалентными, если ониреализуют равные функции алгебры логики.Тождеством в алгебре логики называется равенство, в левой и правойчастях которого стоят эквивалентные функции.Справедливы, в частности, следующие тождества:(1) x1 ∨ x2 = x̄1 &x̄2(2) x1 &x2 = x̄1 ∨ x̄2¯=x(3) x̄(4) (x1 ∨ x2 )&x3 = (x1 &x3 ) ∨ (x2 &x3 )(5) x1 &x2 = x2 &x1(6) (x1 &x2 )&x3 = x1 &(x2 &x3 )(7) x&x = x(8) (x1 &x̄1 )&x2 = x1 &x̄1(9) (x1 &x̄1 ) ∨ x2 = x2(10) x1 ∨ x2 = x2 ∨ x1(11) (x1 ∨ x̄1 )&x2 = x2(12) (x1 ∨ x2 ) ∨ x3 = x1 ∨ (x2 ∨ x3 )(13) x ∨ x = x(14) x1 &x̄1 = x2 &x̄2 .Если в тождество A = B вместо одинаковых переменных всюду подставить произвольные одинаковые формулы, то снова получится тождество A0 = B 0 .

Применить тождество A = B к формуле C — это значитвыделить в формуле C подформулу, полностью совпадающую с A0 (илиB 0 ) и заменить в C эту подформулу на B 0 (соответственно, на A0 ).Вместо & мы обычно будем использовать · или вообще этот знак будемопускать.3.1. Используя только тождество (6), вывести тождества1)(x1 · x2 ) · (x3 · x4 ) = ((x1 · x2 ) · x3 ) · x4 ;2) x1 · ((x2 · x3 ) · x4 ) = ((x1 · x2 ) · x3 ) · x4 ;3) x1 · (x2 · (x3 · x4 )) = ((x1 · x2 ) · x3 ) · x4 ;4) (x1 · (x2 · x3 )) · (x4 · x5 ) = (((x1 · x2 ) · x3 ) · x4 ) · x5 ;5) x1 · ((x2 · x3 ) · (x4 · x5 )) = (((x1 · x2 ) · x3 ) · x4 ) · x5 .3.2. Пусть формулы F1 и F2 получены из выражения x1 · x2 · .

. . · xnлюбыми правильными расстановками скобок. Доказать, что, используятождество (6), можно вывести тождество F1 = F2 .Замечание. Результат задачи 3.2 для конъюнкции и аналогичныйрезультат для дизъюнкции (см. тождество (12)) позволяет записыватьдлинные конъюнкции и дизъюнкции без скобок. В следующих задачахпорядок действий определяется либо скобками, либо соглашением о том,что конъюнкция выполняется раньше дизъюнкции, а отрицание применяется к той формуле, над которой оно стоит.3.3. С помощью тождеств (1)-(14) преобразовать в совершенную дизъюнктивную нормальную форму от переменных x, y, z или в формулу x&x̄следующие формулы:1) xȳ;2) x ∨ y · (xz̄ ∨ y);3) x̄;4) xy ∨ ȳz ∨ x̄ ∨ z̄;5) xy ∨ yz;6) xyz ∨ x ∨ y ∨ z;7) x̄y ∨ ȳz ∨ z̄x;8) xȳ ∨ yz̄x;9) (x ∨ ȳ)(y ∨ z̄)(z ∨ x);10) x ∨ y ∨ y ∨ z ∨ z ∨ x;11) x̄ · yz ∨ x · y ∨ z.3.4.

Доказать, что с помощью тождеств (1)-(14) любую формулу алгебры логики в базисе {∨, &, −}, содержащую любое подмножество изпеременных x1 , x2 , . . . , xn , можно преобразовать в совершенную дизъюнктивную нормальную форму от всех переменных x1 , x2 , . . . , xn или вформулу x1 &x̄1 .Система тождеств в заданном базисе называется полной, если для любых двух эквивалентных формул C и D в этом базисе C можно преобразовать в D, применяя только тождества данной системы.3.5. Доказать, что система тождеств (1)-(14) является полной дляформул в базисе {∨, &, −}.3.6.

Доказать, что система тождеств алгебры логики (2)-(9) являетсяполной для формул в базисе {∨, &, −}.3.7. При помощи эквивалентных преобразований (1)-(14) выяснить,являются ли формулы F1 и F2 эквивалентными, если1) F1 = x̄y ∨ ȳz ∨ z̄x, F2 = xyz ∨ x ∨ y ∨ z;2) F1 = xȳ ∨ yz̄, F2 = (x ∨ ȳ)(y ∨ z̄);3) F1 = x ∨ y ∨ y ∨ z ∨ z ∨ x, F2 = x̄ · yz ∨ x · y ∨ z;4) F1 = xȳ ∨ yz̄ ∨ zx, F2 = (x ∨ ȳ)(y ∨ z̄)(z ∨ x);5) F1 = xy ∨ x̄z, F2 = ((x ∨ z̄)(x ∨ ȳ) ∨ y ∨ z) · yz;6) F1 = xȳz ∨ x̄yz̄, F2 = (x ∨ y)xy ∨ (y ∨ z)yz ∨ (x ∨ z̄)(x̄ ∨ z);7) F1 = (x ∨ y)z ∨ (x̄ ∨ ȳ)z̄, F2 = x ∨ y · z ∨ xy · z̄;8) F1 = xȳ ∨ z ū, F2 = (x̄ ∨ y)(z̄ ∨ u);9) F1 = xȳ ∨ z ū· x̄y ∨ z̄u, F2 = x̄ȳ(z ∨ u)∨(x ∨ y)·zu∨xy(z ∨ u)(z̄ ∨ ū);10) F1 = xyz · yzu, F2 = yz ∨ x ∨ u;11) F1 = x ∨ y ∨ z ∨ u ∨ xyzu, F2 = xyzu ∨ (x ∨ y)z ∨ u;12) F1 = xy · zu ∨ (x ∨ y)(z ∨ u), F2 = x̄ · yzu ∨ ȳ · zu ∨ z̄ ū.3.8. Построить эквивалентные преобразования при помощи тождеств(1)-(14) для формул F1 и F2 , где:1) F1 = x ∨ yz ∨ ȳz̄, F2 = (x ∨ y ∨ z) · (x ∨ y ∨ x ∨ z);2) F1 = (xy ∨ z̄)(x̄ ∨ y) ∨ x̄ · (y ∨ z ∨ ((x ∨ z̄)y)),F2 = (x̄ ∨ ȳ)(z ∨ x) ∨ (ȳ ∨ z)(x̄ ∨ z̄) ∨ xȳz̄ · (x̄ ∨ ȳ);3) F1 = (x ∨ ȳ) ∨ ((x ∨ ȳ ∨ z) · (x̄ ∨ y ∨ z̄)), F2 = ȳ ∨ x ∨ z ∨ x̄y;4) F1 = x ∨ yz̄ ∨ z ȳ, F2 = (x ∨ y) · x ∨ z ∨ x ∨ y · (x ∨ z);5) F1 = ((x ∨ ȳ) · (x̄ ∨ y)) · xy ∨ (xy · xy) ∨ x̄ · ȳ, F2 = x ∨ y;6) F1 = x̄z̄ ∨ xy ∨ xz̄, F2 = (ȳz) · (x ∨ z̄);7) F1 = ((xȳ ∨ x̄y) ∨ (x ∨ y)) · ((x ∨ y) ∨ (x ∨ y)(x̄ ∨ ȳ)), F2 = xy;8) F1 = xȳ · (xȳz ∨ x̄yz̄), F2 = ȳxz · (x̄ ∨ y);9) F1 = (x ∨ (ȳ ∨ z̄)) · (y ∨ z), F2 = (x ∨ y)(z ∨ x̄ ∨ ȳ)(x ∨ y ∨ z);10) F1 = x · ((y ∨ z̄) · (z ∨ ȳ)), F2 = (xy ∨ xz) · (xy ∨ xz);11) F1 = x(y ∨ z)(ȳ ∨ z̄), F2 = xyz ∨ xy · xz;12) F1 = (x̄ ∨ z̄) · (x ∨ y) · (x ∨ z̄), F2 = ȳ ∨ z ∨ xz̄;13) F1 = x · (ȳ · z̄) ∨ yz, F2 = xy ∨ z · (x̄ · ȳ) ∨ xyz;14) F1 = ((xȳ ∨ x̄y) ∨ x ∨ y)((x ∨ y) ∨ (x ∨ y)) · (x̄ ∨ ȳ), F2 = xy;15) F1 = ((x ∨ y)z̄ ∨ x̄y) · (x̄ ∨ yz · (xz̄ ∨ y)) ∨ xȳz, F2 = (x̄ȳ ∨ xz) · (ȳz ∨x̄z̄) · (x ∨ ȳ ∨ z̄) ∨ xyz.Аналогично тому, как это указано выше, определяются понятия тождества и полной системы тождеств для формул над любым базисом валгебре логики или в k-значной логике (k ≥ 3).