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

. . , 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).

.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.