Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
ігїіг
I
__________I
Рис. 7
Рис. 8
номером 7*. Тогда фигура 23 называется логической сетью, полученной путем расщепления выхода /. Входами 23 являются все входы 2', выходами — все выходы логической сети 2' с номерами 1, ..., / — І, 7 + 1, .р и еще два Хі я. выхода, возникших из выхода с номером /
сети 2\ Следовательно, 23 имеет п входов и р + 1 выход.
[Ц
?
I ~ 1г
%
Рис. 9
Рис. 10
3°. Пусть заданы алфавиты переменных X = СсЛ и 2 = иЛ*). Рассмотрим логическую сеть 2, имеющую к входов и р выходов.
Схемой из функциональных элементов называется логическая сеть, входам и выходам которой приписаны раз-
*) Здесь символ {хЛ обозначает множество веех ад, где индекс 1 пробегает натуральный ряд (или его подмножество).
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 339
личные буквы х^, ,Яц и соответственно из
алфавитов X и Ъ (см. рис. 9). Полученную таким образом схему будем обозначать через ?.
^ (Л'11Т * « *1 •• ?! 21р)*
Приведем примеры схем.
1, Пусть множество Р состоит из трех элементов (см. рис. 10).
Тогда фигура Г), изображенная на рис. 11, будет схемой, так как она может быть построена с иснользовани-
Рис. 11
г/
Рис. 12
ем ? при помощи операций Г-ПГ. Этапы этого построения изображены в табл. 1.
2. Фигура 22, изображенная на рис. 12, будет также схемой (см. табл. 2).
В дальнейшем мы встретимся с примерами схем, у которых вход является одновременно и выходом и у которых возможно несколько выходов.
II эт ап. Определение функционирования схемы.
4°. Пусть ?(#], Хп\ гр)—схема из функцио-
нальных элементов*). Сопоставим ей систему уравнений
*) Без ограничения общности можно считать, что номера переменных образуют начальные отрезки натурального ряда.
22*
S40 ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Таблица 1
Логическая сеть Способ получения Логическая сеть Способ получения
ТВ !!1 'Ы V Порутся две тривиальные логические сети (Синие иидунции) В il производит раз- ВСТВЛСRUG ВЫХОДОВ 1 и 2. Операция III (2 раза) К выходам (i, 2) ц (3, 4) сети IV подключают элементы <&- Операция II (2 раза) ИГ 1 i t1 L*' г* 1 1- J fi 3 * il Й 1 T *t К I применяется операция I К выходам 2 и 3 сети III подключают эло-моптьГ Операция II (2 раза) К выходам 1, 2 сети V подключают элемопт V-Операция 11
(функций) алгебры логики
?2| = /1 (^11 • • ч ^я) |
? ?' * • « • »
*Р = Л>(Я1, Я»),
называемую также проводимостью данной схемы. Для этого каждому элементу из множества F ставится в соответствие логический оператор ..., ...), имею-
щий и,-мест и задаваемый булевой функцией /? (у„ ..., упд). Далее по индукции определяется проводимость схемы.
а) Базис индукции. Схема 2 — тривиальная схема (см. рис. 13). В этом случае уравнение имеет вид
г1 — хи
и проводимость есть тождественная функция,
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 34j
Таблица 2
Логпческал сеть Способ получения Логическая сеть Способ получения
fill t 1 S 4 1fM \ i г г a »n * & г г Верутся четыре тривиальные логические сети К выходам (2, 3) сети II подключают элемент Операция II К выходам (1, 2) в (3, 4) сети IV под ключают элементы V- Операция 11 (2 раза) ЦП! 1 г з 4- 1! /г «5 4 Я, Д, V % К I применяется операция I (3 раза) В III производит разветвление выхода 2. Операция III К выходам (1, 2) сетиУ подключают элемент &• Операция 11
б) Индуктивный переход. Пусть 2' и 2" — две схемы, сети которых не пересекаются и входам и
Рис. 13
''ПЧ
___1 1
Lp*1
...Т
p+q
Рис. 14
выходам которых приписаны, соответственно, различные буквы (см. рис. 14). Пусть также схемам
2 (яд, ..жп; гр), 2 (^«+1» •..( *Тп^т1 %т+и ? • м 3р+«)
342 Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ соответствуют системы уравнений
• ? •> З'п) » /р+|(^пЦ| • • •?» Я-п+тп) «
(*) (**)'
= /р (Я|, ., Хп)» — /р+5(а’п+1, .. •, #щ.»л).
I. Схеме 21 (я,, ^„+га; Zp+q)t являющейся объ-
единением двух данных схем, поставим в соответствие систему уравнений, представляющую собой объединение уравнений (*) и (**):
^1 :Я= /1 (*^15 • *4 Х1< 1 * *•» Я'ИЕт)»
гр ) #?г> ?Тм-Т!» * ••» ^и+Я1)!
2р+1 ” /р+1 (>^1» ? **1
%Р+Ч ” /р + е (*^3 » • ? *т З'П} ^тг+ш).
Здесь /1( не зависят существенно от перемепных
2цц, • • ч -З^п+тп, а /р4-1' * • 'з /р+9 переменных Х%} * . тп
и
/1 8=3 /г* **ч/р=/р 1 /р+1“/в+11 • * • ? /р+д “ /р+з-
II. Пусть схема 1 ^2 (*^11 ? * * !
®1У »»•* г/х*-1» ^-И» * "1 ®>п.—1> г;л ^+11 ? »ч 2Р1 гр-н)
получена из схемы
2 (з^1, ..хп, ^р)
путем присоеднпепия К выходам г-;, ...,2;Л1 (щ < р)'
элемента Г<, н полученному новому выходу приписана буква гр+1. Тогда сопоставим этой схеме систему уравнений, получающуюся из (*) вычеркиванием }и ,..3 ]П{ строчек с добавлением строки
гр+1 ~ 1\ (/?! (ХИ • • •] Хп), • , f}n {Х1} . . ?„)).
ГЛ. 2. СППТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 343
Получим
— /1 (^1, . .Хц),
2;!-1 “ /ц-1 (^1» * • ч *?»)»
2;1 + 1 ~ /ц + 1 (“Е’1> ? ? ? 1 %Ч ) 1
2Л13-1 (л’|* . .т,(),
2Д(г-+1= +1 (‘т1’ 1 ?. 1 ет,,),
Z|} = /р (л1!, . . .,
2р+1 — /* (/ц (ли • ? ? ^ 'Ь ? ? *1/;л (^и • • •» ег«)}*
III. Пусть схема ^3(2*!, хп; ги . гр, гР+}) получена из схемы'2'(#1, ..., хп; г1г ..гр) расщеплением выхода с номером / на два выхода, и полученным выходам приписаны соответственно буквы z} и гРы. Тогда этой схеме поставим в соответствие систему уравнений
