В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786), страница 3
Текст из файла (страница 3)
2.13, По КНФ К, являющейся входом для язык» ВЫП, построят" граф С и число й, являющиеся входом для задачи КЛИКА: 1) А = (У! Ч 22 Ч хз)(22 Ч хЗНх! Чхз); 2) А = х1(хг Ч хз)(х! Ч хз Ч х4)УЗ,' 3) К = (Х1 ч хг ч хзИУЗ ч хз)(х1 ч Уз); 4) К =хз(х1 чх4)(х! чУЗ)(хзчхг); 5) К вЂ” (х! ч хг ч У4)(хз ч хз)(х1 ч х2 ч х4); 6) К (Х1 Ч Уз)(хг Ч хз Ч х4)(хг Ч х4)(х1 ч Х4) !) К = (х! ч Уг ч хз) (22 ч Уз ч Х4)(У! ч х4) (хг ч хз) 8) А = (х! ч хг ч хзНхг ч х4) (х! ч х4)хз.
2.14. По КНФ К, являющейся входом для задачи ВЫП, построить граф С и число 1, являющиеся входом задачи ВЕРШИННОЕ ПОКРЫТИЕ; 1) К -' (Х! Ч Х2 Ч ХЗ)(Х! Ч Хг)(Х1 Ч Уг)! 2) А — (х! Ч х2 хз)(х! Ч У2 Ч х3)(х1 Ч Уз)! 3) К = (Х! Ч Х2 ЧХЗ)(хг ЧХЗ ЧХ4)(У1 Ч Х4)! 4) К = (х, ч 2.4 ч Уг)(х! ч Уз)(хз ч х2ч хз); 5) к = (хг чУзих! чхз чх4)х4(х! чхг); 6) К (х! Ч хгИхз Ч хгих! Ч хг Ч х4)! у) К (у! ч 22 чхз)(х! ч у4 чхз)(у1 чхз чуз)', 8) К (х2 Ч хз)(х1 Ч х2 Ч х4)(хУ! Ч хг Ч х4). 2.15.
Граф С и число ! являются входом задачи ВЕРШИННОЕ ПОКРЫТИЕ. Построить вход задачи ПОКРЫТИЕ МНОЖЕСТВ, соответствующий паре (С, !): 1) ! =2,С: 2) ! =З,С 3) (=З,С: 14 4)(=3,6: 2.16. Данный вход задачи КЛИКА преобразовать ио входы задач ВЕРШИННОЕ ПОКРЫТПЕ н ПОКРЫТИЕ Л(НОЖЕСТВАМИ: 1) 1 = 4. С: (2 17) Доказать ХР-полноту задач 1 — 8 из введении к параграфу. 2.18. Доказать, что следующие задачи яалщотся ХР-полными; ) Т11""х ® сушествование набора, обращающего дНФ в ноль; 11 2) существование набора, обращающего ДНФ в ноль при условии, что каждое слагаемое этой ДНФ содержит не более 4 букв.
гтэ) 2.19. Выделить среди перечисленных задач полиномиально решаемые я ХР-полные (при условии Р ф ХР): '. 1) существование двух противогкщожных наборов, на которых ДНФ обращается в единицу; 2) суцккч воиаиие двух противоположных наборов, на которых ДНФ обращается в ноль; 3) существование набора, на котором полипом Жегалкина обращается в ноль; (4))существование набора, на котором заданные полиномы Жегалкина (количество которых заранее неизвестно) сшновременно обращаются в ноль; 5) существование эйлерова цикла в графе (эйлероным циклом назы- вается цикл, проходящий по всем ребрам графа, причем по каждому в точности один раэ); 6) существование гамильтонова цикла в графе (гамильтоновым цик- лом называется простой цикл, проходящий через все вершины графа); ~ 7у раскраска вершин графа в два цвета (граф можно раскрасить в два цвета, если каждой его вершине можно приписать цвет таким образом, что смежным вершинам приписаны разные цвета); 8) раскраска вершин гиперграфа в дна цвета (гиперграфом называет- ся пара < 1г, Е >, где Р— конечное множество вершин, Е, Е С 2з— множество ребер; гиперграф можно раскрасить в два цвета, если каж- дой его вершине можно припясать цвет таким образом, что любое ребро будет содержать по меньшей мере две вершины, окрашенные в разные цвета).
2.20. Выяснить, какие из перечисленных задач являются полиноми- ально решаемыми, какие — ХР-полными: 1) распознавание нелинейности булевой функции, если Я функция залаяв таблицей своих значений, (б), Функция задана формулой, , ~'в) функция задана в виде ДНФ, . г) функция задана в виде сокращенной ДНФ, д) функция задана в виде полннома Жегалкина; 2) распознавание пемонотопностп булевой функции, если а) функции задана таблицей своих значений, ;б)~функция задана формулой, н) функция задана в виде ДНФ, г) функция задана в виде сокращенной ДНФ, ,д) функция задана в впдс полянома Жегалкина; 3) распознавание несамодвойствсяностп функции, если а) функция задши таблицей своих значений, б) функция задана формулой, гв) функция задана в виде ДНФ, гв и Рис.
2 Рис. 1 Рис. 4. Рис. 5 Рис. 3 Рис. 7. Рис. 8 Рис. б Рис. 9. зз г) фуикция зацаиа в виде совершеииой ДНФ, Я~ Функция задала в виде полииома Жегалкииа; 4) существововвиие в графе й-клики (Л-кликой иазываетси подграф, являющийся полиым графом с Й вершииами), если ;"ау число к заранее взвеспю, 6) число к подастся ва вход МТ вместе с графом; 2.21. Доказать полииомиальиую зквивалеитиость задач Х з и бг, если 1) бг = ВЫП. Ег = 4-ВЫП; 2) бз =- РАСКРАСКА ГРАФА В 2 ЦВЕТА: Ьг = УМНОЖЕНИЕ ДВО- ИЧНЫХ ЧИСЕЛ. Часть 2.
Эквивалентные преобразования $3. Эквивалеитиые преобразовиия формул Две формулы алгебры логики ивзываются зкеиеалегепнмми„если оии реализуют равные функции алгебры логики. Тозсдеспгеам в алгебре логики иазывается равенство, в левой и правой частях которого стоят эквивалеитиые функции. Справедливы, в частиости, следующие тождества:: (1) хз Ч хг = хгйхг (2) х~йхг = хт Ч хг (3) 2 = х (4) (хг Ч хг)йхз = (х~йхз) Ч (хзйхз) (5) х1йхг = хгйх1 (б) (х~йхг)йхз = х|й(хгйхз) (7) хйх = х (3) (хзйхз)йхг = х1йзч (9) (х1йХз) Ч хг =- хг (10) х1Чхг "хгЧх1 (П) (х1 Ч х )йзг = (12) (х~ Чхг) Чхз = х~ Ч(хгЧхз) (13) хЧх = х (14) х~йХ1 = хгййг.
Если в тождество А = В вместо одинаковых переменных всюду под- ставить произвольиые одинаковые формулы, то снова получится тожде- сгво А' =- В', Примеиить тождество А = В к формуле С вЂ” зто значат выделить в формуле С подформулу, полностью совпадакицую с А' (иля В') и заменить в С зту подформулу иа В' (соответствеиио, иа А'). Вместо й мы обычно будем использовать или вообще этот знак будем опускать. 3.1.
Используя только тождество (6), вывести тождества 1)(хз хг) (хз хз) = ((хг хг) хз) хз,. 2) хг ((хг.хз) х4) = ((хз ' тг) 'хз) хз, 3) хз (хг (хз х4)) = ((хз . хг) хз) хз', 4) (х1' (хз 'хз)) (х4 'хз) = (((х\ 'хг) 'хз) 'хз) ' хз~ 5) хг'Ихг хз) (х4 зз)) =(((хз ° хг) ° хз) хз) хз. 3.2. Пусть формулы Е! и Ег получены из любыми правильными расстановками скобок тождество (б), можно вывести тождество Г! Замечание. Результат задачи 3.2 для ко ц аналогичный результат для дизъюнкции (см. тождество (12)) позволяет записывать длинные конъюнкции и дизъюнкции без скобок, В следующих задачах порядок действий определяется либо скобками, либо соглашением о том, что конъюнкция выполняется раньше дизъюнкции, а отрицание применяется к той формуле, над которой оно стоит.
З.З. С помощью тождеств (1)-(14) преобразовать в совершенную дизьюпктивную нормальную форму от переменных х, р, г или в формулу ХВгх следующие формулы: 1) хр; 2) Х7 р (хг Ч р); 3) хт 4) хр Ч рг Ч х Ч г; 5) хр ч рг( 6)*р * рр*; 9).р р"**: ' 6) хрчргх; 9) (г: Чр)(рчр)(2чх); 10) х ч р 4 р 7 2 '4 2 '4 х; И) 2 Ррчх рчг. 3.4. Доказать, что с помощью тождеств (1)-(14) любую формулу алгебры логики в базисе (Ч, Вг,-), содержащую любое подмножество из переменных х), хг,...,х„, можно преобразовать в совершенную днзьюнктивную нормальную форму от всех переменных хм хе...,, х„или в формулу х)Вгх!.
Система тождеств в заданном базисе называется полно(1, если для любых двух эквивалентных формул С и Р в этом базисе С можно преобразовать в Р, применяя только тождества данной системы. 3.5. Доказать, что система тождеств (1)-(14) является полной для формул в базисе (Ч, 32, — ). 3.6. Доказать, что система тождеств алгебры логики ( )-( ) гики (2)-(9) является полной для формул в базисе (Ч, Й.
— 1. й (1)-(14) выяснить, если 3) Г х7рчрчгч»ЧХ, Ег=х.ргчх.р72; 4) Е~ =хрчргЧ гх, Гг = (х Чр)(рЧг)(гЧх); 5) Е'! = хр7 хг, Гг = (/г Ч 2) (х Ч р) Ч р 7 г) ° рг; б) У'! = хрг'/хрт, Гг = (хчр)Х7Ч(рч2)ргч(ХЧ2)(хчг); 7) Е! = (х Ч р)г Ч (х Ч р)г, Гг = х Ч р г Ч хр ° 2; 8) Р! = хр Ч гй, Рг = (2 Ч р) (р Ч и); 9)у =*р *6' р,у -рр( ) (*рр).
У*У~ 94) 9 9) 99) У, = ~~~, У, - 29ь У ррр; 11) Р! =г'4р Ч гЧиЧхрги, Гг =Хрги Ч(х Чр)г Ч и, 12) Г! = Ур ° уй Ч (х Ч р)(г Ч и), Гг = Х ° рги Ч р ° ги Ч уа, 3.8. Построить эквивалентные преобразования при помощи тождеств (Ц-(14) для формул Г! и Гг, где: 1) г! =хЧр2чрг, Гг=(хчрчг)'(х ЧрЧхЧ»/; 2) Г! = (хр)/2)(й)/р) Чх (р Ч2 Ч ((х'/3)р)), гг = (х Ч Р)(г Ч х) Ч (Р Ч 2)(Й Ч Р) Ч хР» (х' Ч Р); 6)У,=~(* У)9(*ррр.).(9 „*-)),У,=-УР ГЯУРУ; 4) Г! = х ч р» ч»р, Гг = (х ч р') х ч ч х ч р (х ч г); 5) Е! = ((хЧр) (хЧр)) хрЧ(хр хр)чх ° р, Гг = х7р; б) г! = 2»чхрчхг, гг = (рг) (хч р); У)У,=((69 ГР) ( 99)) (~(*УР ( Р)(9 Р)),У,-Н; В) Г! = хр \(хрг Ч х)/2), Х~ = рхг (х Ч р); 9) У, = ( Р (9 9)) (Р Р *), У, = (, Р Р)(* ~9 Р »( Р р У ); 10) Г! = х ((р ч 2) (г ч р)), Гг .= (хр ч 22) ° (гр !/ Хг); 11) Е! =х(рЧ 2)(рЧВ), Гг = хрг Чхр ° х; 12) Г! = (х'Ч 2) . ~(х Ч р) (х Ч 2), Гг = р Ч г Ч хг; 13)Г)=х (р г)чр»,Гг=хрчг ° (х ° р)Чхр 14) Г! = ((хр ч хр) ч х ч р)((х ч р) ч (х ч р)) .
(х ч р), à — ур 15) Р! = ((х чу)2 чхр) (хчрг. (хгч р)) чхрг, Гг =(~учхг). (ргч 22) (г'Ч р Ч г) Чхрг. Аналогично тому, как это указано выше, определяются понятия тождества и полной системы тождеств для формул над любым базисом в алгебре логики или в /с-значной логике (/2 ) 3).. 3.9. Построить конечную полную систему тождеств для класса фор мул иад базисам В, сели 1) В = (ху,хну, Ц; 2) В = (ху, х Ч у. О, 1).
3.10. функц»»ей Линдона (см. [11!) назовел» функцию р(х»,хз) из 7- значной логики, задаваемую таблицей 1. Табл. 1. Будем обозначать функцию Линдона»э(х», хз) = х» хз = х»хз. Ц Доказать, что для функции Линдона справедливы тождества А») (у у) . х = у. у, Аз) х (у у) = у у, Аз) х»(хзхз) = у. у; Вт) ((... ((х»хз)хз)...)худ)х» = у у при т = 1, 2,, ..; Ст) (( .. ((х»хз)хз). ° .)хт)хз = ((.. ° (х»хз)хз) )хщ»»рн т = 2,3,.... 2) Вывести с помощью тождеств А» н Аз тождество х х = у у.
3) Доказать, что с помощью тождеств А» — Аз, В ( =,,...), А — А В (тп =12..., С (т = 2, 3,...) любую формулу в базисе из одной функции Линдона люжно преобразовать либо в формулу х х, либо в формулу аида (... ((хих»,)х»,)...)х», где все переменные различны. 4) Пусть для функции Линдона справедливо тождество (... ((хих„)х;,)...)х; = (... ((х,х,)х;)...)х „, где все переменные в левой части различны р » и все пе еменные в правой части различны. Доказать, что т = а и х;„= хз, дл я всех Й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
