Главная > Логические методы анализа и синтеза схем
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

2-10. ФУНКЦИОНАЛЬНАЯ ДЕКОМПОЗИЦИЯ

С ростом числа аргументов ФАЛ быстро возрастает сложность задачи минимизации. Как показали многочисленные исследования, даже при использовании современных вычислительных машин практически оказывается возможным минимизировать функции с числом аргументов, не превосходящим 30—35. Выходом из этого положения может служить нахождение не минимальной формы данной функции переменных, а представление ее в виде

где функции зависят от меньшего числа переменных с последующей минимизацией выражений для функций .

Представление функции в виде (2-33) называется функциональной декомпозицией этой функции.

Если множества аргументов от которых зависят функции и множество не имеют общих элементов, то функциональная декомпозиция называется разделительной, или непересекающейся. Если это не так, т. е. имеется хотя бы один аргумент входящий более чем в одно подмножество то функциональная декомпозиция называется неразделительной, или пересекающейся.

Если функция представима в виде

то функциональная декомпозиция называется простой. Простая функциональная декомпозиция может быть как разделительной, так и неразделительной. Функциональную декомпозицию вида (2-33) будем называть (-кратной функциональной декомпозицией. Простая функциональная декомпозиция при этом может

быть названа однократной функциональной декомпозицией.

Примером функциональной декомпозиции может служить представление функции в виде разложения по аргументу:

которое может быть представлено в виде

где

В полученном представлении обозначим и через — через Через будем обозначать число элементов множества М. В нашем случае

Обобщим функциональную декомпозицию на случай

Значок 0 означает, что пересечение множеств пусто. Как следует из (2-34), рассматриваемый нами случай есть простая разделительная функциональная декомпозиция, отличная от тривиальной декомпозиции такого вида — разложения функции по ее аргументу. Для нахождения декомпозиции такого типа воспользуемся методом, предложенным А. Кертисом.

Пусть мы имеем функцию для которой проверяется возможность ее представления в виде (2-34) при условии, что Зададим некоторое разбиение множества аргументов функции на два ненересекающихся подмножества, содержащих каждое не менее двух аргументов.

Каждому набору из множеств и сопоставим их номера (это сопоставление описано в § 1-7). Тогда множество номеров наборов из содержит все номера от О до включительно, а множество номеров наборов из содержит все номера от 0 до включительно. Построим теперь матрицу размером Строки и столбцы этой матрицы перенумеруем соответственно от 0 до 2 1—1 и от 0 до На пересечении строки с номером и столбца с номером запишем значение исходной функции на наборе аргументов, который является композицией наборов с номерами и При получении этой декомпозиции следует учитывать истинную нумерацию аргументов в X.

Пример 2-24. Записать в матричной форме описанного вида функцию заданную следующей таблицей, при условии, что

Матрица данной функции имеет вид:

Для получения элементов этой матрицы используем таблицу задания функции с учетом принятой нумерации наборов в и . Например, элемент матрицы стоящий на пересечении второй строки и третьего столбца, есть значение исходной функцни на наборе

Будем для удобства обозначать элементы множества как а элементы множества — как При этом Каждый столбец матрицы можно рассматривать как функцию вида

где — фиксированный набор значений аргументов из , номер которого соответствует номеру данного столбца. Аналогично каждую строку матрицы можно рассматривать как функцию вида где — фиксированный набор значений аргументов из номер которого соответствует номеру данной строки. Тогда нетрудно видеть, что возможно представление исходной функции в двух следующих формах:

и

Поставим теперь задачу о нахождении условий, при которых функция допускает простую разделительную декомпозицию нетривиального типа (отличную от разложения по аргументу). Эта задача решается с помощью следующей теоремы.

Теорема 2-6. Функция алгебры логики допускает простую разделительную функциональную декомпозицию нетривиального вида тогда и только тогда, когда матрица, соответствующая заданному разбиению множества X на подмножества и содержит не более двух различных столбцов.

Докажем сначала необходимость. Пусть функцию можно представить в виде

Из (2-37) следует, что

Функция соответствует функции в нашей матрице. Но как функция алгебры логики может принимать лишь два различных значения, откуда вытекает необходимость условия, сформулированного в теореме.

Докажем теперь достаточность условий теоремы. Пусть матрица содержит не более двух различных столбцов. Покажем тогда, что исходная функция может быть представлена в виде (2-34). Так как каждый столбец есть функция вида то сопоставим два различных столбца, имеющихся по условию в матрице, произвольным образом функциям (если в матрице нет различных столбцов, то исходная функция не зависит от аргументов, входящих в множество ).

Определим теперь функцию следующим образом. Она равна нулю на всех наборах для которых имеет место равенство и равна единице для всех наборов для которых имеет место равенство Заменяя после этого на получаем:

Теорема доказана.

Эта теорема может быть обобщена на случай -кратной разделительной декомпозиции, дающей представление функции в виде

В этом случае необходимым и достаточным условием существования -кратной разделительной декомпозиции при заданном разбиении множества X на множества является условие наличия в матрице функции не более различных столбцов. Доказательство этого утверждения представляется читателю.

Отметим, что при поиске простой разделительной декомпозиции, отличной от тривиальной или разделительной (-кратной декомпозиции, необходимо просмотреть различные разбиения множества X на множества и процесс перебора таких разбиении

заканчивается либо при нахождении такого разбиения, которое удовлетворяет условиям теоремы 2-6, либо при исчерпании всех возможных способов разбиения, число которых равно

Заметим, что поиск декомпозции некоторой ФАЛ приводит в случае успеха этого поиска к построению некоторой скобочной формы представления данной функции.

Пример 2-25. Найти простую разделительную декомпозицию для функции принимающей значение 1 на наборах аргументов с номерами 0, 6, 7, 8, 13, 15, 17, 19, 22, 23, 24, 25, 27, 28. На остальных наборах функция принимает значение, равное 0.

Произведем разбиение множества X на подмножества . В соответствии с заданием функции стоонм матрицу:

Так как число различных столбцов в этой матрице больше двух, то для выбранного разбиения множества X на подмножества и простая разделительная декомпозиция невозможна. Читателю предлагается проверить, что при любом нетривиальном разбиении множества X на подмножества и (разбиение нетривиально, если для данной функции невозможно получить простую разделительную декомпозицию.

Однако возможно получить разделительную кратную декомпозицию того вида, который был рассмотрен в обобщении теоремы

2-6. Для построенной нами матрицы число различных столбцов равно четырем. Эти столбцы имеют вид:

Как следует из обобщения теоремы 2-6, возможно построение декомпозиции исходной функции в следующем виде:

Определяем для чего сопоставляем этим

функциям четыре различных столбца в том порядке, в котором очи написаны. Тогда

Отсюда

Следовательно,

Аналогично

Окончательно после упрощений получаем:

Можно рассмотреть задачу нахождения функциональной декомпозиции функции с несколько иной точки зрения. Пусть задана некоторая функция Пусть также из множества X аргументов этой функции выделено некоторое подмножество .

Будем говорить, что два набора значений переменных из множества совместимы, если , где означает множество переменных, не вошедших в , но содержащихся в X. В

протйвном случае два набора и будем называть несовместимыми. Отношение совместимости разбивает все множество наборов значений переменных из на классы, в каждый из которых попадают лишь совместимые наборы. Число таких классов зависит от вида исходной функции и выбранного множества . Обозначим его как Рассмотрим теперь функцию которая принимает различные значения на различных классах совместимости. Значения этой функции мы будем представлять двоичной записью в разрядах, где если если Каждую компоненту в этой записи будем рассматривать как функцию, определенную на множестве .

Пример 2-26. Пусть имеется функция шести переменных, принимающая значение 1 на наборах с номерами 2, 12, 17, 28, 44, 45, 50, 61, 62. В качестве множества возьмем множество -Выпишем классы совместимых наборов Для удобства запишем наборы, на которых функция по условию принимает значение 1 в двоичном виде:

Если же в качестве множества взять множество аргументов то разбиение на классы совместимых наборов будет выглядеть следующим образом:

обоих случаях функция должна принимать шесть различных значений. Эти значения кодируются тремя двоичными функциями. Есть некий произвол, состоящий в том, как кодируются шесть значений восемью комбинациями значений где -кодирующие двоичные функции.

Если выбрать кодирование, совпадающее с номером класса совместимости, то для первого рассмотренного случая получим:

(кликните для просмотра скана)

Звездочка в этой таблице стоит против тех наборов, на которых функция не определена. Эти наборы никогда не возникают, так как функция не принимает значений, равных 0 и 7. Исходная функция зависящая от шести переменных, сведена нами к функции, зависящей от пяти переменных,

что привело нас к разделительной трехкратной декомпозиции специального вида, рассмотренного в обобщении теоремы 2-6. Если теперь произвести доопределение функции в полученной таблице нулями, то мы получим следующее выражение:

Заметим, что при первом способе выбора множества X мы не получили фактически никакого уменьшения числа переменных так как вместо аргументов в ней появились аргументы

Как следует из приведенного примера, в процессе построения декомпозиции функции в двух местах возникал произвол: при кодировании значений функции и при доопределении функции Минимальность окончательного выражения тесно связана с тем выбором, который мы осуществляем на этих шагах. Полностью проблема получения минимального выражения при нахождении разделительной декомпозиции пока не имеет решения.

Мы рассмотрели лишь самый простой вид функциональной декомпозиции. В § 3-8 мы рассмотрим некоторые проблемы, связанные с неразделительной функциональной декомпозицией.

1
Оглавление
email@scask.ru