В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786), страница 4
Текст из файла (страница 4)
5) Доказать, что система всех тождеств А» — Аз, В ( В (т = 1,2,."), Ст (т = 2,3.....) является полной системой тождеств для формул в базисе, состоящем только из одной функции Линдона х с правильной Будем говорить, что формула Ф = хи х;,, х„р расстановкой скобок обладает свойством С", если а) она содержит только переменные х», хз,..., х„, б) не имеет подформул вида и ° и н и(ии»), в) меЖду первым вхождением переменной хя и вторым ее вхождением (если оно есть) встречаются все переменные х», хз,..., хэн отличные от х„.
6) Какие из левых и правых частей тождеств А» — Аз, В (га = 1,2,...), С,„(т = 2,3,,) обладают свойством С"? 7) Пусть формула Фз получена нз формулы Ф» при помощи тождеств А» — Аз, В и С, где т < и. Доказать, что если формула Ф» обладает свойством С", то и формула Фз обладает свойством С". 8) Доказать, что при и > 2 эквивалентность В„нельзя получить с помощью тождеств А» — Аз, В (т < и), С (т < п). 9) Доказать, что лля формул в базисе из одной функции Линдона не существует конечной полной системы тождеств.
3.11. Решить уравнения (и и — функция Линдона аргументов и и и): 1) ( у) = х .(у ); 2) х . у = у . х; 3) (у х) у = (х у) х; 4)х-у=з х. 4. Эквивалентные преобразования контактных схем Две контактные схемы с одинаковым числом т полюсов называются экеивалентанълми, если их полюса можно так занумеровать и»,..., и„и и»,..., и„, что для любых», » функции проводимости (»1 между и» и и в первой схеме и до между и, и и, во второй схеме совпадают.
Тождеством для контактных схем называется пара эквивалентных контактных схем, соединенных знаком» вЂ” >. Если задано некоторое тождество, то считается, что заданы также все тождества, которые получаются из данных с помощью следующих операций: 1) одинаковая перенумерацня полюсов в обеих частях тождества; 2) переименование одинаковых переменных в произвольные одинаковые переменные (в частности, разные переменные можно переименовывать в одинаковые); 3) замена всюду х -л й,х -л х. 4 — + О 1 22: 1) О Х 4-4 О 1 1 ° 4 — + й4 гз: 1 2 4 — Ф О О 1 2 хт 1 2 х Ч22 1 ~~ ~ 2 Π— — О 4 — 22 хт 1 2 24 Подмножество Ем состоящее из нскОторых вершин и конты4тов схем в схемы Е, называется нодсте24оо схемы Е, если в Е4 некоторое (может быть пустое) годмножесгво вершин считается полюсами и при этом: 1) если вершина из Ег является полюсом в Е, то она является полюсом и вЕ4, 2) если вершина нз Ег инц44дентна контакту из Е 1ЕН то она является полюсом в Ен Применение тождества к контактной схеме Е состоит в выделении в Е подсхемы, совпадающей с одной частью тождества, и замене этой подсхсмы на схему из другой части того же тождества с сохранением нумерации полюсов.
Система тождеств для контактных схем называется полной, если для любых двух эквивалентных контактных схем одну в другую можно преобразовать. применяя тождества из данной системы. Осноекоо назовем следующую систему тождеств (в тождествах 44 и $4 допускается совпадение полюсов): 1 2 1 2 Я4 иг 2 4 2 1 2 Хг Х! 3 3 Теорема 4.1 (В. Л.
Мурский [11]). Бесконечная система тождеств 44 — йн 24', гл = 1, 2, „является полной. 4.1. При помощи эквивалентных преобразований 24 — 44224 (гп = Ь22) 1, 2,...) доказать эквивалентность схем: йй 1 - 2-*- -"- 1 2 1 2 3) 4 — + Π— — О х 5) 1 2 1 2 х Тгк. Π— -О» — + 1 2 1 »» » — + О 1 1 3 Р ты»» »'р схемой для булевой конгпактной Канонической 1 т»г 1 1 2 1 1 2 3 3 1 1 т„: » — + О- О 1 2 р-1 р-1 1 1 т,:1 г 11 3 3 4.2.
Вывести нз основной системы тождеств обобщ обоб енные тождества т,-т„. функции дх»,...,х„), отличной от конопаты О, назовем двухполюо. иую контактную схемч, состоящую из цепочек, соединяющих полюса и не имеющих общих вор»пин, кроме полюсов, и соответствующих всем коньюнкциям совершенной дизьюнктивной нормальной формы функции 1, Для константы 0 канонической контактной схемой назовем контактную схему, состоящую из двух изолированных полюсов, Канонической многопалюснсй контактной схемой назовем объединение непересекающихся по внутренним вершинам двухполюсных канонических контактных схем, построенных для каждой пары полюсов. Привести контактную схему к каноническому виду можно прн помощи следующего алгоритма ~П!. 1. Каждый контакт исходной контактной схемы заменяем на двухполюсную подсхему в соответствии с тождеством Т»ю 2. Рассматриваем произвольну»о вершину исходной контактной схемы, ие являющуюся пол»осам.
1) Применяя тождество Там» для каждой звезды с центром в втой вершине добиваемся того, чтобы из рассматриваемой вершины исходили только различные цепочки контактов. 2) По тождеству Тпц рассматриваемую вершину вместе со всеми цепочками контактов, исходящими нз нее, удаляем. Повторяя пп. 1) и 2) для каждой вершины, не являющейсн полюсом, получим контактную схему, в которой цепочки контактов соединяют только полюса, 3, В случае, если контактная схема имеет более двух полюсов, выполняем транзитивное замыкание по тождеству Т»х.
4. Повторяющиеся цепочки контактов, соединяющие одну и ту же пару полюсов, вычеркиваем по тождеству Тгл 4.3. Привести к каноническому виду следующие контактные схемы: ~з)) р 1 Р х 3 х 1 2 1) о— 1 2 2 о— 1 2 2 х У г) 1 х г зе 4.4. 1) Выяснить, эквивалентны ли данные контактные схемы, приводя каждую из них к каноническому виду." 4.б. 1) Пусть Š— контактная схема, зависящая от переменньгх хм .,х„, и а = (ам....а„) — вектор нз О н 1. Пусть В(Е,сг) — число простых циклов (без повторения вершин) в контак состоящих из некоторых контактов вида х,,...,х„, и пу ~, ~В(Е, ).
Доказать, что если контактная схема Е' от переменных х(,, х» по" лучена из контактной схемы Е от переменных хм,х» в Резу в ез льтате применения любого из тождеств 1( — гм то В(Е) = В(Е'), а если в ре- зультате применения тождества Юе( ), т < и, то В(Е) — В(Е') делится на 2»-т 2) Основываясь на утверждении п. 1) доказать, что контактную схему нельзя преобразовать в контактную схему У прн помон(н то)кдеств Ф( — (м (е (1) (2) (а+2) 3) Основываясь на утверждении и. 1) доказать, что тождество (е~ не выводится из тождеств (( — Ц, (е,..., (е (1) (») 4) Доказать, что из множестватождеств 82 — (м(е (пт = 1,2,...) наль(ю) зя выделить конечной полной системы тождеств для контактных схем. б) Доказать, что в классе всех контактных схем не существует конечной полной системы тождеств. Чисть 3.
Надежность и контроль управляющих систем Для управляющей системы (схемы) без памяти, функционирование которой описывается дискретной функцией илн в общем случае, функпией, может быть сформулирована следующая модель (см, (б, 12)), в рамках которой обычно рассматриваются вопросы ее надежности. Предполагается, что имеется некоторый "внешний" источник неисправностей (источиик помех', П, под действием которого рассматриваемая схема Е может переходить в одно из своих "неисправных состояний" (схем), определяемых этим источникохь Пчсть схеме Е = Е('), реализующей (вектор-) функцию Г = г = (Л,...,1 ) от входных переменных (о Й) ()) х = (хь....т„), п источнику неисправностей И соответствуют "неисправные" состояния (схемы) Е(г),,Е('), где схема Е('), г = 2,...,(, реа.
изует функцию г = ((г,..., („, ) от переменных х. При этом все состояния (как исправное Е = Е('), так и неисправные Е(г),.... Е(')) разбиваются на классы (функционально) неотличимых состояний, то есп классы эквивалентности по отношению равенства реализуемых функций, и рассматриваются далее с точностью до неотличимости. В дальнейшем., говоря о неналежной схеме Е, будем иметь в виду указанную выше модель )г( = (Е, И) и (или) соответствующее ей множество схем вместе с теми функциями, которые они реализуют. З 5. Задача контроля управляющих систем. Тесты для таблиц Рассмотрим математическую модель задачи контроля управляющих систем, связанную с понятием теста для таблицы.
Для целых чисел а и 6, где а < 6, через (а, 6") будем обозначать множество целых чисел отрезка (а,6), то есть множество целых ( таких, что а < г < 6. Для множестваА и натуральных и.т через А' будемобозначать множество матриц с п строками, тл столбцами и элементами из А. При этом будем считать, что А"', то есть т-я декартова степень множества А, совпадает с А'"'.
Для матрицы М из множества А" ее подматрицу, расположеннуго в строках с номерами из множества 1 и в столбцах с номерами из множества,7, где 1 С '11, п'( и д С 11, т), будем обозначать через М < 1, 1 >. При этом подматрипу вида М < 1, 11 т1 > (М < 11,п~(. «>) будем обозначать через М < 1 > (соответственно М(/)), Матрица М называезся приведенной, если все ее столбцы различны.
Пусть М = (Е, И) — указанная выше модель ненадежной схемы Е с состояниями Е = Е('), Е(з),..., Е(') и функциями Р = Р('), Р( ),..., у'(г) (г) от переменных х = (хь..., х„), Пусть, далее, функции Г, Г,..., Р' (1) (2) (й определены на множестве наборов ЛГ = (А,..., «1р) и принимают значения из множества (наборов) А = (оь..., о,).
Сопоставим рассматриваемой задаче контроля матрицу М, М Е Ар', где м < г, ) >= г («)(о,) для всех г, г е '11, р(, и у, у е (1,11). Заметим, что если М(1) = МЦ), то состояния с номерами г и у невозможно отличить друг от друга на основе данных наборов. В таких случаях все состояния, как правило, разбиваются на классы эквивалентности по отношению неотличимости, а задача контроля ставится и решается для этих классов. Заметим также, что каждому классу неотличимости состояний соответствует группа одинаковых столбцов матрицы М, а задаче контроля для этих классов — приведенная матрица М', множество столбцов которой совпадает с множеством различных столбцов матрицы ЛХ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
