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

.3.9. Построить конечную полную систему тождеств для класса формул над базисом B, если1) B = {xy, x ⊕ y, 1};2) B = {xy, x ∨ y, 0, 1}.3.10. Функцией Линдона (см. [11]) назовем функцию ϕ(x1 , x2 ) из 7значной логики, задаваемую таблицей 1.x1 \ x2012345600000000100000002010005630500056406000565000000060000000Табл. 1.Будем обозначать функцию Линдона ϕ(x1 , x2 ) = x1 · x2 = x1 x2 .1) Доказать, что для функции Линдона справедливы тождестваA1 ) (y · y) · x = y · y, A2 ) x · (y · y) = y · y, A3 ) x1 (x2 x3 ) = y · y;Bm ) ((.

. . ((x1 x2 )x3 ) . . .)xm )x1 = y · y при m = 1, 2, . . .;Cm ) ((. . . ((x1 x2 )x3 ) . . .)xm )x2 = ((. . . (x1 x2 )x3 ) . . .)xm при m = 2, 3, . . . .2) Вывести с помощью тождеств A1 и A2 тождество x · x = y · y.3) Доказать, что с помощью тождеств A1 − A3 , Bm (m = 1, 2, . . .),Cm (m = 2, 3, . . .) любую формулу в базисе из одной функции Линдона можно преобразовать либо в формулу x · x, либо в формулу вида(. .

. ((xi1 xi2 )xi3 ) . . .)xim , где все переменные различны.4) Пусть для функции Линдона справедливо тождество(. . . ((xi1 xi2 )xi3 ) . . .)xim = (. . . ((xj1 xj2 )xj3 ) . . .)xjn ,где все переменные в левой части различны и все переменные в правойчасти различны. Доказать, что m = n и xik = xjk для всех k.5) Доказать, что система всех тождеств A1 − A3 , Bm (m = 1, 2, . . .),Cm (m = 2, 3, . .

.) является полной системой тождеств для формул вбазисе, состоящем только из одной функции Линдона.Будем говорить, что формула Φ = xi1 · xi2 · . . . · xim с правильнойрасстановкой скобок обладает свойством C n , еслиа) она содержит только переменные x1 , x2 , . . . , xn ,б) не имеет подформул вида u · u и u(vw),в) между первым вхождением переменной xi1 и вторым ее вхождением(если оно есть) встречаются все переменные x1 , x2 , . . . , xn , отличные отxi1 .6) Какие из левых и правых частей тождеств A1 − A3 , Bm (m =1, 2, . . .), Cm (m = 2, 3, . .

.) обладают свойством C n ?7) Пусть формула Φ2 получена из формулы Φ1 при помощи тождествA1 − A3 , Bm и Cm , где m < n. Доказать, что если формула Φ1 обладаетсвойством C n , то и формула Φ2 обладает свойством C n .8) Доказать, что при n ≥ 2 эквивалентность Bn нельзя получить спомощью тождеств A1 − A3 , Bm (m < n), Cm (m < n).9) Доказать, что для формул в базисе из одной функции Линдона несуществует конечной полной системы тождеств.3.11.

Решить уравнения (u · v — функция Линдона аргументов u и v):1) (x · y) · z = x · (y · z);2) x · y = y · x;3) (y · x) · y = (x · y) · x;4) x · y = z · x.§ 4. Эквивалентные преобразования контактных схемДве контактные схемы с одинаковым числом m полюсов называютсяэквивалентными, если их полюса можно так занумеровать v1 , . . . , vn иu1 , .

. . , un , что для любых i, j функции проводимости fij между vi и vj впервой схеме и gij между ui и uj во второй схеме совпадают.Тождеством для контактных схем называется пара эквивалентныхконтактных схем, соединенных знаком ←→.Если задано некоторое тождество, то считается, что заданы такжевсе тождества, которые получаются из данных с помощью следующихопераций:1) одинаковая перенумерация полюсов в обеих частях тождества;2) переименование одинаковых переменных в произвольные одинаковые переменные (в частности, разные переменные можно переименовывать в одинаковые);3) замена всюду x → x̄, x̄ → x.Подмножество Σ1 , состоящее из некоторых вершин и контактов схемыΣ, называется подсхемой схемы Σ, если в Σ1 некоторое (может бытьпустое) подмножество вершин считается полюсами и при этом:1) если вершина из Σ1 является полюсом в Σ, то она является полюсоми в Σ1 ;2) если вершина из Σ1 инцидентна контакту из Σ \ Σ1 , то она являетсяполюсом в Σ1 .Применение тождества к контактной схеме Σ состоит в выделениив Σ подсхемы, совпадающей с одной частью тождества, и замене этойподсхемы на схему из другой части того же тождества с сохранениемнумерации полюсов.Система тождеств для контактных схем называется полной, если длялюбых двух эквивалентных контактных схем одну в другую можно преобразовать, применяя тождества из данной системы.Основной назовем следующую систему тождеств (в тождествах t3 и t5допускается совпадение полюсов):t1 :t2 :t3 :t4 :•←→∅x1x2•12x1x̄1•112←→12x2•1 x2•x̄1←→2x1 2x1x1t5 :x1•12x2x2←→←→x1 2131 x123x1(m)t6•x2:←→•1xm1...•Теорема 4.1 (В.

Л. Мурский [11]). Бесконечная система тождеств t1– t5 , tm6 , m = 1, 2, . . ., является полной.(m)4.1. При помощи эквивалентных преобразований t1 − t5 , t6 (m =1, 2, . . .) доказать эквивалентность схем:•x1)←→11x2)x←→12•x12xx←→3)1122xx4)1 xx•y•y2 ←→x1x←→5)1x•y221•y2yx6)x←→1•122ȳxx7)1 x̄•x8)2 ←→y1y2•1•xyy←→1 xy2yy•33yx9)2z1 xz•xy1 y2x̄y2 ←→1 x̄yx•z•xx̄←→x̄22312)1x̄yx•z•3x2←→•1 x̄z•y11)y←→x1•x•110)221y••yzz2Цепочку I контактов xσ1 1 , xσ2 2 , .

. . , xσnn , соединяющих полюса k и j, бу-дем изображать какI12Звездой с центром в полюсе 1 назовем контактную схему вида2Ip1I II ...3p−1Пусть переменные x1 , x2 , . . . , xn фиксированы, а число j в двоичнойсистеме записывается как σ1 σ2 . . . σn . Тогда контактом с пометкой Ij будем обозначать цепочку из n последовательно соединенных контактовxσ1 1 , xσ2 2 , . . . , xσnn .Рассмотрим систему обобщенных тождеств:TI :TII :←→•∅II˜←→1212•I0TIII :1I1 I2n −1 ←→...22n...122nTIV :•xx←→1..

I1.1 x2I0•ITV :2I2n −1•I1I2 ←→1 I233II←→TV I :1122I•TV II :I←→112TV III : pI2I1I II ...3p←→1IIp−1I3...p−1IITIX : 1I2 ←→31 II234.2. Вывести из основной системы тождеств обобщенные тождестваTI – TIX .Каноническойконтактнойсхемойдлябулевойфункции f (x1 , . . . , xn ), отличной от константы 0, назовем двухполюсную контактную схему, состоящую из цепочек, соединяющих полюса и неимеющих общих вершин, кроме полюсов, и соответствующих всем конъюнкциям совершенной дизъюнктивной нормальной формы функции f .Для константы 0 канонической контактной схемой назовем контактнуюсхему, состоящую из двух изолированных полюсов.

Канонической многополюсной контактной схемой назовем объединение непересекающихсяпо внутренним вершинам двухполюсных канонических контактных схем,построенных для каждой пары полюсов.Привести контактную схему к каноническому виду можно при помощиследующего алгоритма [11].1. Каждый контакт исходной контактной схемы заменяем на двухполюсную подсхему в соответствии с тождеством TIV .2. Рассматриваем произвольную вершину исходной контактной схемы,не являющуюся полюсом.1) Применяя тождество TV III для каждой звезды с центром в этойвершине добиваемся того, чтобы из рассматриваемой вершины исходилитолько различные цепочки контактов.2) По тождеству TIII рассматриваемую вершину вместе со всеми цепочками контактов, исходящими из нее, удаляем.Повторяя пп. 1) и 2) для каждой вершины, не являющейся полюсом, получим контактную схему, в которой цепочки контактов соединяюттолько полюса.3.

В случае, если контактная схема имеет более двух полюсов, выполняем транзитивное замыкание по тождеству TIX .4. Повторяющиеся цепочки контактов, соединяющие одну и ту же паруполюсов, вычеркиваем по тождеству TV I .4.3. Привести к каноническому виду следующие контактные схемы:x•y1)z•z̄•x̄•1y•zx2•xzy2)1ȳ•x̄•x2z2yy3)1xȳ•34.4. 1) Выяснить, эквивалентны ли данные контактные схемы, приводя каждую из них к каноническому виду:yx1)•12zxy•1x2)2z1 zy•yx•y21 xz•z•y24.5. 1) Пусть Σ — контактная схема, зависящая от переменныхx1 , . .

. , xn , и α = (a1 , . . . , an ) — вектор из 0 и 1. Пусть R(Σ, α) — число простых циклов (без повторения вершин) в контактной схеме Σ,состоящихиз некоторых контактов вида xa11 , . . . , xann , и пусть R(Σ) =Pα∈B n R(Σ, α).Доказать, что если контактная схема Σ0 от переменных x1 , . . . , xn получена из контактной схемы Σ от переменных x1 , . .

. , xn в результатеприменения любого из тождеств t1 − t5 , то R(Σ) = R(Σ0 ), а если в ре(m)зультате применения тождества t6 , m ≤ n, то R(Σ) − R(Σ0 ) делится на2n−m .2) Основываясь на утверждении п. 1) доказать, что контактную схемуx1 x••yz2нельзя преобразовать в контактную схемуyx1•z2(1)(2)при помощи тождеств t1 − t5 , t6 , t6 .(m+1)3) Основываясь на утверждении п. 1) доказать, что тождество t6(1)(m)не выводится из тождеств t1 − t5 , t6 , .

. . , t6 .(m)4) Доказать, что из множества тождеств t1 −t5 , t6 (m = 1, 2, . . .) нельзя выделить конечной полной системы тождеств для контактных схем.5) Доказать, что в классе всех контактных схем не существует конечной полной системы тождеств.Часть 3. Надежность и контроль управляющих системДля управляющей системы (схемы) без памяти, функционированиекоторой описывается дискретной функцией или, в общем случае, векторфункцией, может быть сформулирована следующая модель (см. [6, 12]), врамках которой обычно рассматриваются вопросы ее надежности.

Предполагается, что имеется некоторый “внешний” источник неисправностей(источник помех) И, под действием которого рассматриваемая схемаΣ может переходить в одно из своих “неисправных состояний” (схем),определяемых этим источником. Пусть схеме Σ = Σ(1) , реализующей(1)(1)(вектор-) функцию F = F (1) = (f1 , . . . , fm ) от входных переменныхx = (x1 , . . . , xn ), и источнику неисправностей И соответствуют “неисправные” состояния (схемы) Σ(2) , . . . , Σ(t) , где схема Σ(i) , i = 2, . .

. , t,(i)(i)реализует функцию F (i) = (f1 , . . . , fm ) от переменных x. При этом всесостояния (как исправное Σ = Σ(1) , так и неисправные Σ(2) , . . . , Σ(t) ) разбиваются на классы (функционально) неотличимых состояний, то естьклассы эквивалентности по отношению равенства реализуемых функций, и рассматриваются далее с точностью до неотличимости. В дальнейшем, говоря о ненадежной схеме Σ, будем иметь в виду указаннуювыше модель M = (Σ, И) и (или) соответствующее ей множество схемвместе с теми функциями, которые они реализуют.§ 5.

Задача контроля управляющих систем. Тесты для таблицРассмотрим математическую модель задачи контроля управляющихсистем, связанную с понятием теста для таблицы.Для целых чисел a и b, где a ≤ b, через ba, be будем обозначать множество целых чисел отрезка [a, b], то есть множество целых i таких, чтоa ≤ i ≤ b. Для множества A и натуральных n, m через An,m будем обозначать множество матриц с n строками, m столбцами и элементами из A.При этом будем считать, что Am , то есть m-я декартова степень множества A, совпадает с A1,m . Для матрицы M из множества An,m ее подматрицу, расположенную в строках с номерами из множества I и в столбцахс номерами из множества J, где I ⊆ b1, ne и J ⊆ b1, me, будем обозначать через M < I, J >.