О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 7
Текст из файла (страница 7)
(x1 &x2 ) = (x2 &x1 ).2◦ . (x1 ∨ x2 ) = (x2 ∨ x1 ).3◦ . ((x1 &x2 )&x3 ) = (x1 &(x2 &x3 )).4◦ . ((x1 ∨ x2 ) ∨ x3 ) = (x1 ∨ (x2 ∨ x3 )).5◦ . ((x1 ∨ x2 )&x3 ) = ((x1 &x3 ) ∨ (x2 &x3 )).6◦ . (x1 &x1 ) = x1 .7◦ . (x1 ∨ x1 ) = x1 .8◦ . (x1 ) = x1 .9◦ . (x1 ∨ x2 ) = (x1 &x2 ).10◦ . (x1 &x2 ) = (x1 ∨ x2 ).11◦ . (x1 &x1 ) = 0.12◦ . (x1 ∨ x1 ) = 1.13◦ . (x1 &1) = x1 .14◦ . (x1 ∨ 1) = 1.15◦ .
(x1 &0) = 0.16◦ . (x1 ∨ 0) = x1 .17◦ . 0 = 1.18◦ . 1 = 0.Каждое правило считаем схемой правила, т. е. имеем в виду, чтовместо любой из переменных можно подставить формулу. Обозначимсистему правил 1◦ – 18◦ через ∆.Пусть все переменные формулы F содержатся в некотором множестве X. Тогда формула F̂ — каноническая для F относительно X,если выполнена одна из возможностей: 1) F̂ реализует нуль; 2) F̂ есть37содержащая все переменные из X ДНФ (определенная однозначно сточностью до ассоциативности и коммутативности) ненулевой функции, реализуемой формулой F .Лемма 5. Если все переменные формулы F содержатся в множестве X, тогда F относительно X можно преобразовать в каноническую формулу F̂ при помощи правил системы ∆.Доказательство. Разберем все возможные ситуации, возникающие впроцессе преобразования формулы F .1) Перенесем все отрицания со скобок на переменные по правилам9◦ и 10◦ .2) Уничтожим двойные отрицания с помощью правила 8◦ .3) Уничтожим отрицания над константами с помощью правил 17◦и 18◦ .4) Раскроем скобки, применив, по возможности правило 5◦ , и получим представление A1 ∨ · · · ∨ As .5) Уничтожим пары вида xi &xi с помощью правил 1◦ , 3◦ и 11◦ .6) Уничтожим по правилу 15◦ конъюнкции, содержащие нуль.7) Уничтожим по правилу 16◦ конъюнкции в виде нуля, и если врезультате этого получим нуль, то каноническая формула получена.8) Уничтожим единицы в конъюнкциях согласно правилу 13◦ .9) Уничтожим повторяющиеся множители согласно правилу 6◦ .10) Если необходимо, дополним конъюнкции до полной длины:пусть, к примеру, конъюнкция K не содержит переменной xi ∈ X, тогда13◦12◦5◦K −−−→ K&1 −−−→ K&(xi ∨ xi ) −−−→ (K&xi ) ∨ (K&xi ).Аналогично поступим для других переменных, пока не будет достигнута необходимая длина конъюнкции.11) Наконец, руководствуясь правилом 7◦ , уничтожим повторяющиеся конюнкции.
В результате получим каноническую формулу. Леммадоказана.Теорема 7. Система правил ∆ является полной.Доказательство. Пусть F1 и F2 — эквивалентные формулы, т. е. реализующие с точностью до несущественной переменной одну и ту жефункцию f , соответственно X1 и X2 — множествавсех переменныхSформул F1 и F2 . Построим множество X = X1 X2 . Преобразуем согласно лемме 5 формулы F1 и F2 в канонические F̂1 и F̂2 относительно38❡✟x✟❡✟ S1❍x❍❍❡❡✟x✟❡✟ S2 x❍x❍❍❡Рис. 14X. Но по определению формулы F̂1 и F̂2 совпадают либо как нулевые,либо как совершенные ДНФ функции f , поэтому формулу F1 можнопреобразовать в F2 и наоборот.
Теорема доказана.Заметим, что в k–значной логике существуют конечные системыфункций, для которых не существует полной системы эквивалентных преобразований. Однако для полной конечной системы функцийполная система эквивалентных преобразований существует всегда.Рассмотрим теперь случай контактных схем.
Будем называть двеконтакные схемы эквивалентными, если количества их полюсов совпадают, между полюсами одной схемы и полюсами другой схемы существует взаимно–однозначное соответствие и функции проводимостисовпадают для соответствующих пар полюсов. Например, схемы S1 иS2 на рис.
14 эквивалентны.Определим подсхему контактной схемы как некоторое подмножество контактов контактной схемы. При этом полюсами подсхемы будут:1) все полюсы контактной схемы, принадлежащие данной подсхеме; 2)вершины общие для контактов из подсхемы и контактов не из подсхемы; 3) возможно, некоторые другие вершины. Так, если существуетконтактная схема, содержащая подсхему S с полюсами α, β и γ, то призамене S на эквивалентную ей схему S ′ (α′ , β ′ , γ ′ ) получится контактнаясхема эквивалентная исходной.Рассмотрим правила преобразования эквивалентных подсхем.1◦ . Изолированная вершина может быть как добавлена в схему, таки удалена из схемы.2◦ .
См. рис. 15. Средняя вершина, заметим, не полюс подсхемы поопределению.112 12❡ x1 r x2 ❡ ∼ ❡ x2 r x1 ❡❡ x1Рис. 152 1r x1 ❡ ∼ ❡Рис. 16392❡3◦ . См. рис. 16.4◦ . См. рис. 17.1x1❡21 ✟1✟✟❍❍❍2❡❡x2❡∼xr❍✟x1❍❍r✟✟x2Рис. 175◦ . См.рис. 18. Это так называемое схемное правило. Здесь возможно отождествление некоторых полюсов.x1✟ ❡2x1✟ ❡2✟✟✟✟❡❡∼x11 ❍x❍1❡1❍ ❡33Рис. 186◦m . См. рис. 19. Возможность устранения циклов. Здесь внутренниевершины цикла не соединяются с какими–либо другими вершинами.❡1x1✟ ❍ xm❍❍rr✟✟x2xm−1r❍❍x3❍···❡1∼Рис.
19Указанные переменные можно заменить на любые другие переменные (или их отрицания) вне зависимости от того, входятони в контактную схему или нет. Обозначим систему правилγm = {1◦ , 2◦ , 3◦ , 4◦ , 5◦ , 6◦1 , . . . , 6◦m }.Выведем некоторые следствия из системы γm .7◦ . См. рис. 20. Правый конец контакта в данном случае являетсявременным полюсом“. Определение полюсов подсхемы это допускает.”1❡ x1 r∼Рис. 20Вывод правила представлен на рис.
21.401❡60❡ x1 r ∼150❡ x1 r ∼x160❡ x1 r ∼2x11❡Рис. 218◦ . См. рис. 22.12 1❡ x1 r x1 ❡ ∼ ❡2x1❡Рис. 22Вывод правила представлен на рис. 23.x170❡ x1 ❡ ∼✟r✟✟05❡ x1 r x1 ❡ ∼❡ x1 ❡Рис. 239◦ . См. рис. 24.x2✟1 x1✟❡r✟❍❡2r x2 ❡21✟1✟✟x∼ ❡❍❍x2❍ ❡3x❍1 ❍rx2❡3Рис. 24Вывод правила представлен на рис. 25.x2✟ ❡ 04x❡ 1 r✟✟∼❍❍x❍ ❡2r❡ 0x✟x✟1 ✟❍ x225❍✟✟❡❍r✟∼✟❍❍✟❍❍ ❡ 50x❍1 ❍r✟ x2x2r x2x✟1✟✟❡❍x❍1 ❍rx2❡x2 ✟✟ 20r✟∼❍❍x2 ❍ ❡r x2 ❡x✟1✟✟❡❍x❍❡1 ❍rx2Рис. 259◦m .
См. рис. 26. Это своего рода обобщение правила 9◦ .1 x1❡r x2···❡2xm✟✟xm−1 ✟r❍∼❍❍ ❡xm3r x21✟1✟✟x❡❍❍x1 ❍rx2· · · xm−1 r xm ❡2r❡··· xxm 3m−1Рис. 26Один шаг вывода правила представлен на рис. 27. Далее повторяется аналогичная последовательность действий.41❡ x1 r20∼ ❡ x1 r❡xm✟✟ 90✟r❍∼❍x❍ ❡···❡ x1 rmxxm✟ r m−1 ❡ 09✟✟r∼❍❍xm❍ r❡xm−1···rxm−1✟✟✟r❍❍❍ rxm−1···❡ x1 r···xm ❡xmrxm−2✟✟r ✟❍❍❍rxm−2❡20∼xm rxm−1 ❡xmr❡xm−1Рис. 27Рассмотрим теперь обобщения правил 1◦ – 6◦ на случай цепей Iвида xσ1 1 xσ2 2 · · · xσnn .I. Удаление и добавление изолированной вершины. Это правилонеизменно переносится на случай цепей.II. Эквивалентность цепей I и I˜ с теми же, но расставленными вдругом порядке контактами.III. См.
рис. 28. Здесь I1 , I2 , . . . , I2n — всевозможные n–контактныецепи, выходящие из вершины, не являющейся полюсом.❡r✂❅✂ I2 ❅ I2n✂❅❅❡❡✂✂12I1···∼❡❡12···❡2n2nРис. 28Докажем правило III индукцией по n. При n = 1 имеем в точностиправило 3◦ . Предположим, что III справедливо для цепей длины n − 1,и покажем, что оно справедливо также для цепей длины n.r✟❍I1′ ✟✟ ✁I2′ ❍❍ I2′ n−1✟✁❍❍❍r✟r✟r✁❅❅❅❡❡ ❅ ❡ ❡ ❅ ❡ ··· ❡ ❅12 342n − 1 2nРис. 29σσn−1 σnn−1 σnxn ,xn и xσ1 1 · · · xn−1Все цепи сгруппируем парами вида xσ1 1 · · · xn−1◦и к каждой такой паре применим правило 9n . В результате получитсясхема, общий вид которой представлен на рис.
29. Использовав теперьправило 3◦ и предположение индукции, получим требуемое. Заметим,что некоторые из полюсов 1, 2, . . . , 2n могут совпадать.42IV. Пустьx1 =_(σ2 ,...,σn )I1′ , I2′ , . . . , I2′ n−1x1 xσ2 2 · · · xσnn ,и— цепи, соответствующие этим конъюнкциям, тогдаимеет место правило, представленное на рис. 30.121❡ x1 ❡ ∼ ❡I1′.. I ′ ❡2. 2I2′ n−1Рис. 30Докажем правило IV так же индукцией по n. Случай n = 2 есть вточности правило 4◦ . Предположим, что правило справедливо для n−1,и покажем, что оно справедливо также для n. В схеме для n−1 заменимσn−1каждый контакт xn−1по правилу 4◦ , полагая вместо переменной x2переменную xn .
С полученными в результате цепями поступим так,как изображено на рис. 31.❡ x1 r···90n∼σn−1 rxn−1n0✟❍x❍❍❡2✟r ✟∼❍❍✟σn−1❍r✟✟xn−1xnx1✟r···✟✟❡❍❍x1❍r···❡ x1 rσx n−1r n−1···r xn ❡σn−1xn ✟r❍ xn−10✟❍n❍❡9r✟∼❍❍✟✟σxn ❍r✟ x n−1n−1rr❡σn−1xnxn−1Рис. 31Далее используем предположение индукции.xx1✟r 2✟❡✟❍❍x1❍rx2···r xn ❡···rxn❡50∼xx1✟r 2✟❡✟x1rx2···r xn ❡···rxn❡20∼xx1✟r 2✟❡✟x2rx1···r xn ❡···rxnРис. 32V. Схемное правило полностью аналогичное 5◦ с той лишь разницей, что вместо контакта x1 рассматривается цепь I.
Вывод этого правила состоит в последовательном применении ряда эквивалентностей,схожих с изображенной на рис. 32.VI. Удаление цепи, являющейся циклом.43❡Теорема 8. Любые две эквивалентные контактные схемы, все переменные которых содержатся в множестве {x1 , . . . , xn }, можно преобразовать друг в друга с помощью правил системы γn .Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
