В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786), страница 8
Текст из файла (страница 8)
этой схемы представлен на рис. 35. ~~зрю~~~ фу~ни~~,~ и корректирую~ в' Докажите что если для натурально„ тельных /с, йм ", /с. иьгесг место Ранено во Ф, +... Ь"У) <5"(У)+" +Е'у), 7 16 Покажпте что в случае размыкания дчя величин введенных в зздаче 7.15, справедливы неравенства: а) 6(р+ 1) < 58(х1 Е хз 9 хз) < 6(р + 1) + 2((р+ 1) пюб 2), б) 6(р+ 1) < И(Я(хьхз,хз)) < 6(р+ 1) + ((р+ 1) шоб 2), где озз(хмхз,хз) = хгхзхз ъ хгхзхз чх!хзхз. 7,17. Пусть Š— корректирующая один обрыв КС, в которой можно выделить з пар вершин (все вершины различны) таких, что по анализу проводимостей между этими парами вершин можно обнаружить любой единичный обрыв контакта.
Показать, что схему Е можно преобразовать в корректирующую один обрыв КС Е' такую, что любой единичный об- рыв контакта в ней может быть обнаружен по анализу проводимосгей между двумя вершинами схемы. Ответы, указания и решения К параграфу 1. 1.1. 1) Ла: 2) да; 3) нет; 4) нет. 1.2. 1) Нет. Прпмер: (х), 2) Нет. Пример: (О, 1, х»). 1.3. Ла. 1.4.
6) Нет, так как, яапркмер, Функция /(х,у) = х ч у явля и, . ри добавлении в нее Фиктивной переменной г посимметрпческой, но при д лучастся несимметрнческая функция д(х, у. х) = х У у. 7) Да. 1.6. «сть»» и»»»~ ° ° ° ~ »1»+1 > 0 /(х ... х х +») — произвольная функция яз »;»(и+ 1), Из разложения /(х ....х„х, »)=х„е»/(х»,...,х»,1)л«2»+»/(х»,...,х„.О) ,» х»~ - х» х»'» = »+ ф ' полностью определяется парой своих подфунк. следует, что «рункщщ / полност пий /(хм...,х„,1) и /(х»...., „, .1) /( ....
х О). Поскольку последние также принадлежат классу Я, имеем »«1(п+ 1)~ < ~фп)~ . Отсюда ~4»»« ~в«««»г«»~ г. гж Из (4) вытекает невозрастание последовательности гл«Д(п) ~. Покажем, что она ограничена. Если Я не пусто, то 1 = л/1 < »Я(л)) < 4»ДРг(п)~ = л/2г" = 2. (3) Следовательно, предел последовательносг -",/»ф )» и *л,/»флЯ существует и за ключен в сегменте (1, 2]. 1.7. В самом деле, при некотором фиксирова сван нем гп существует Ф . ( ',...
) к Я. Так как последовательносгь '" ~фп)~ не Функция д(х»,..., х,„) возрастает, то з"ЯЯ~ < 4 Я(~д)! < (2г 1)г < 2, »-«»» х Ф нкций, завися- 1,8. 2) Воспользоваться тем, что число монотонных фу о ит п(»""). щих от переменных х», хг...., х„, нс превосходит 3) 1/2. Нижняя оценка Ц(п)~. Выберем линейную функцию 1 в »,» ных наборов длины равной х» «Т» ". «Т» х». Пусгь В" — множество двоичны 1пп Яфю)! = 2»~г Тем самым построен инвариантный класс Я с характеристикой «т = 1/2.
1.12. 1. а) 7/(М) = (х). Указание. Воспользуйтесь доказательством леммы о немонотонной функции. б) б»(Л) есть множество всех попарно неконгрузнтных нщ»инейных функций переменных х, у. Указание. Воспользуйтесь доказательством леммы о нелинейной функции. в) У(»;1) есть множество всех функций, существенно зависящих ровно от Й+ 1 переменных. г) УЯ) = (ху,х у у,х). 2. Класс квазис»»л»л»сгр»»чсск»»х функций. Указание.
Каждая функция д,(х»,хг...., х„) = х»хг .. х»Чхг .. х„является порождающим элементом данного класса (есть и другис). 4. Верхпяи оценка очевидна, Получим нижнюю. Пусть О„ — минимальный инвариантный класс, содержащий функциюд»(х»,хп. х») = х»хг . х»ух»хг .х„, Все классы Я„попар»»о различные. Пусть, далее, а = О,а»аг...
— бесконечная двоичная дробь. Полож»»л» б»» = () »:» =» Легко видеть, что О» есть инвариантный класс и при а» »4 аг имеем: »»»»«»1 Я»г Нижняя оценка доказана. Отсюда К параграфу 2, (» хг «»)(1»л«хгчх4)(х»л»хгл»гг)(»гчхгчх«)(хгл«хгчх4). и с нечетным числом координат, ра нь,„1 Ч ство ~аборощ обращающих функцию / в и Ф"'~ = 2" ' Ср~ди Функций д(х„) Р „„' О из 2 функ»»»»й попарно отличающихс сне В ', ЯснО, что число фущ«цнй»»»» (3) Равно 2г" . Отсюда 2'" <»фп)~ ВеРхнЯЯ оценка ~9(п) ~. пРи фиксиРованной ФУнкцин ~ = хч»п...
а» х; имеется не более 2г < 2г" различных функций / Е»'„г(п). Ч»»ело линейных Функций, зависящих от переменныхх»,...,х„, равно 2»+», Позтому )фп)! < 2»+'2г" . Такпм образом 2г <»Гг(п)! < 2»+»2г"-' еи à — О ~ 5=~-'; и, „иомиально решаелзые, 2), 4), 6), 8) — 1(Р- 2.19. 1), 3). 5), ) - полииол г) д1. 2) а) г) д) 3) а) г), д), 4) а) — полино К параграфу 3.
3'1' 4)(х!цх"'гзВ'(т4 хз = !. 2 ° В' ' ) ((~! ~2)'хзйхз'хз) = (((х! хз).х 3.2. Указание. Докажите ш Д - те индукцисй поп, что выражение х! хз...,х„ тановкой скобок можно с помощью тождества с любой правильной расстановк ... ((х ° х ) хз) ... ° х„! х„см.4.1 ) 4) дите к виду хх, остальные к совершенной З.З. Указание. 2) и 4) првведите зъюл! нй!Рл фр "Ч ) = ху (хууу) =' хухХЧхуу) =' ххЧуу й хй ) ч (хчг)уг = гхуч гху ч хуг чгуг = ху»ч 5) гу ч уг = (г ч у)ху (х Чху.)Ч хуя Ч хуг = ху»Ч хуг Ч хуг, хуг Ч ху Ч »у. — (хуг хуг 3.5. Сл!. задачу 4.4, (21 = (21 = (з! 3.6.
Выведем (1) используя (2)-(9); х! хз = х! Ч хз = х! хз = Выведем (10), используя (2)-(9): х! Чхз — — х! Чхз = х! 22 = хз х! = (з! хз Чх! = хз Чх!. Указание. Для вывода (11), (12) и (13) сводите, используя (2)-(3), дизъюнкцию к к н ю к конъюнкции и обратно и нспользу ( ), ( ( ) соответственно. Для вывода (14) используйте (8) и (5). 3.7, Указание: при помощи тождеств (1)-(14) при д ве итс обе формулы к совершенной д.и.ф. Ответ: 1), 3), б)-11) — да; 2), 4), 5) — нел: 3.8.
Указание: при помощи тождеств (1)-(14) обе фоРмУлы можно привести к совершенной д.н.ф. по шую юбу(о 3.9. 1) Указание: постройте систему тождеств, по позволяющую лю У(о ить в полипом Жегал- формулу нед бззисом В = (ху,х Ю у, Ц переводить кина. 2) Например: тождества (4)-(7), (10), (12), (13) вместе с тождествами 030 0 13г1 = 1, хЗ»0 = О, хл»1 =х,ОЧО = О, 1Ч1 = 1, хЧО = х, хЧ1=1 3.10. 2) Указание, Докажите индукцией по и, что выражение х! .
,х с любой правильной расстановкой скобок можно с помощью Хз ' ° ° ° э цеста А,, В, С преобразовать в выражение (...Их!.хг) хз) х„,) х„(см.4.1) К параграфу 4. 4.2. Указание. Ты: использУйте тождество Зз. Многократно используйте тождества зз и зз 3) Многократно используйте тождества зз и зг и затем З~ . 4) Используйте тождества Зз и Зз.
4.4. 1) Нет; 2) да. К параграфу 5. 5.1. 1) 2; 2) 3; 3) 2; 4) 3; 5) 2; 6) 3. 5.2. 1) и; 2) и — 1; 3) и — 1, 4) и. 5.3. Указание. Два столбца матрицы М различаются в У-й строке тогда и только тогда, когда 2-я строка матрицы М(21 покрывает сумму по модулю 2 этих столбцов. 5.5. 1), 4), 5), 7) — Да. 2), 3), 6), 8), 9) — Вообще говоря, нет. 5.6. Пусть А и  — тупиковые тесты матрицы М с т строками. Тогда ни одно нз вклзочений А с В, В с А не имеет места. Отсюда вытекает, что число тупиковых тестов не превосходит максимального числа попарно нссравннмых наборов в В, а значит; не превосходит величины Я) б 7. Число матриц размерности й хи с попарно различными столбцами равно 2"(гл — 1) ...
(2! — и+ 1). Число матриц размерности гп х и, у которых х строк с фиксированными номерами заданы, равно 2"( ~!. б 8. 1) (1,2), (1,4), (2,3), (3,4); 2) (1,2,3), (1,2,4), (1,3,4); 5) (1 г, з), (1, г 5), (г, з, 4), (1, 4, 5), (з, 4, 5); 6) (1, г, з), (2, 3, 5), (3, 4, 5).
5.9. Указание. Нижняя оценка доказывается от противного из предположения о существовании теста длины меньшей, чем (1о82 и) . Для доказательства верхней оценки изучите число классов эквивалентности, на которые все и столбцов матрицы тупикового теста разбиваются ее первыми 1 строками (( Е (1,..., и — 1)), достижимость нижней (верхней) границы доказывает матрица из задачи 5.2.1 (соответственно 5.2.2 при 9=0).
02 Рцте матрицу М, доказывайте от про!г) 5.10. Нет. Указание. тинного. трите лгатрцпУ Мйй и оцените с„„чц 5.11. Указание. Рассмотр в тех ее строках, к ° х, которые связаны с тестом, Рицы М а,г,г ~ ]2 +11 5.12. Пусть Т, Т С !1, гл — тес столбцов матрицы М которые обр множество пол!еров тех стол л .омс ом г, ! = ..... Б, цз условия задачц Пусть дале г 6 Ул для которых столбец М(Т, ') — множество тех чисел !', ! !, д. вно одну слинигт. Так как в каждой строке подмагри М(Т 4+~(]у~] ]4) ~ ]Т], и, следовате Т С, л пруя последние неравенства по всем г, г = 1, „,, матрице М(Т) число столбцов, содержащих одну единицу, не опыте, * б льше, чем ]Т], получим: ]Т] > 2л — э ' ] к"'р ~~(1,01» И,оо) (пу, И101), (по», И101), (пй, в а) и б) совпадают: ИООО), (001), (010», ИООО), уно) (01о) (п1)) Иооо), (1оо), (п1)Э, И001), (010), (,,')' (( 01' (100) '(,01», И01о), (101), (пу, И1оо) ..
(101) (и'». '101)) „) И101», Иоп). (по»; б) Иоп), (101», И1о1), (по», Иоп), 64 гг еть! пунктов а) и б) совпадают: ИООО), (00 ) (» И ( О ) (110» ((000) (001), (п1», И001) (по) (п1» 65. Стветы гунктов а) и б) совпадают: И000), (1 ), (» ( (101),(п1». И010) (100),(п1» И010) (101) (п1» И001) (010), (п1», И001) (010) (100» т; ИООО». 6.7.
(1тветы пунктов а) и б) совпадают: „ 6'6',) И010) (пн» И100), (по», И010), (100), (и»'» ((( 0,) (роо) '(101» И010) (100), (по», Ио1о), (100), (п1» Ио'0) (' ' ' (по», И1оо), (1о1), (по». 6.9. Указание. Доказательства проводятся от противного. 6.10. 1) Указание. Найдите т групп по (и — ) овлетворяюшую (после инедцничныс обрывы которых дают матрицу, удое Р Н Тоноян 1191) Рассмотри вертирования) условиям задачи 5.12; 2) (Р. Н. Тоноян [ ]).
мых следуюгццми словате в!Ри л > 2т ноже во н боРОВ. ПОРождаел ь!х сл дУ г в! т п-вв-г вг вв1т-вг 1вв(01]г вво мидлиныпв алфавите (0,1): 0" 1 0 ', 1 0 ', '[ О' [01]"О" ", 0" "~[01]" "1" (э! = 0; —, — 1.т О т- 1 эг = 1; л — 2т, эл = Т;т — 7). 6.11. л+ 1. 6.12. 1) 2. 2) Указание. Используйте метод дихотомии, т.
е. д схемы на две части. 6.13. а) 2" ', б) 2" ', в) 2", 6,14. Указание. Расслютрите наборы единичной сферы и ее центр. достижимость оценки проиллюстрируйте на схеме, построенной по методу каскадов. 6.15, (Х. А. Мадатян [14]). Указание. Докажите, что среди неисправных схем найдутся схемы, реализующие обе константы, а также схемы, реализующие или х",хг* х,',", или х,'НхггЧ '!тх в для любого набора (оно'г,...,с г) 6.16. 1) Указание. Рассмотрите изолированный блок этой схемы. 2) а) 2 при четных л, 3 прп нечетных и; б) 4; в) 6 при четных л, 7 при нечетных л.
3) (Р. Н, Тоноян [18]). Указание. Используйте метод дихотомии. Длина теста нс более, чем на константу, отличается от кгйгл. 4) а) (Р. Н. Топоян [18]). Указание, Используйте метод дихотомии, б) Указание. Используйте метод деления схемы на 4 части. 6.17. (Н. П. Редькин [6]). Указание. Рассмотрите КС, реелизуюшую функцию Дхг,..., х„) и построенную по формуле (Ку(хгЧ х!)) (Ру(х! у й!)), где Ку и Ру — конъюнктивная и дизъюнктивнал совершенные нормальные формы функции у. 6.18. 1) а) ИОО), (01), (П», число тестов — 2; б) И001), (010), (ОП), (ПО), (П1» (порядок псрслгснных — х, у, !7'), число тестов — 12. 2) И001), (ОП), (ПО» (порядок переменных — х, у, д').
3) И 1000), (0001), (ОПО» (порядок переменных — а, Ь, х, у). 4) ИОООО), (ОП1). (ПП». 6.19. 2) Указание. Рассмотрите схему на рис. 25 и заметьте, что неисправность типа 0 на выходе третьего слева инвертора в нижнем ряду инверторов обнаруживается лишь на наборе (0001), нс входящем в тест из задачи 6.18.4. 6 20. (Н. П. Редькин [6]).
Указание, Искомая схема строится по индукции из блоков, каждый блок подобен схеме на рис. 22 а) без выхода и!. Тест из четырех наборов: (0,0,0,...,0), (1,0,0,...,0), (0,1,1,...,1), (1,1,1,,Ц, 6.21. 1) Введем обозначение: 01 11 11 01 ОО 11 11 01 00 01 М = 11 01 ОО 01 П 01 00 01 11 11 00 01 11 11 01 11 11 11 01 00 а теста Т размером 5 х 2п при этом будет иметь вид Т = (4РММ Му), где матрица М' получается из матрицы М выбрасы; нужного количества первых столбцов (порядок переменных— . х, о ). Указание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
