Главная > Логические методы анализа и синтеза схем
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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-9. ПРЕОБРАЗОВАНИЯ И МИНИМИЗАЦИЯ В БАЗИСЕ, СОСТОЯЩЕМ ИЗ ФУНКЦИИ ВЕББА ИЛИ ИЗ ФУНКЦИИ ШЕФФЕРА

Ранее было показано, чт.о функции Вебба и Шеффера образуют базисы, состоящие только из одной функции. Будем называть такие базисы монофункциональными.

В последнее время возник большой интерес к монофункциональным базисам. Поэтому рассмотрим их более подробно. В § 1-2 и 1-5 были введены двухместные функции Вебба и Шеффера. По аналогии с ними введем с помощью таблицы -местные функции Вебба и Шеффера:

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

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

По аналогии с (1-20) можно написать следующие соотношения:

При раскрытии скобок аналогично соотношениям (1-21) получим:

Заметим, что если или равны единице, то эти соотношения выразятся несколько иначе. Например, при

Наконец, приведем соотношения, показывающие связь между многоместными функциями Вебба и Шеффера:

Эти соотношения аналогичны соотношениям (1-22) и формулам де Моргана.

Справедливость всех вышеприведенных соотношений можно установить при помощи таблиц функций.

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

Рассмотрим равенство (1-25) из § 1-7. Из (1-25) легко получить:

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

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

Если обращается в нуль только на одном наборе, то в правой части (2-24) останется только один инвертированный операнд. Если же обращается в единицу только на одном наборе, отрицание в правой части соотношения (2-25) исчезает.

Для получения аналогичных нормальных форм в базисе Шеффера можно использовать (1-28) и характеристические функции нуля.

Перейдем теперь к аналитическому выражению характеристических функций единицы в базисе Вебба. В § 1-7 было получено выражение

Если применить последнее из соотношений (2-20), то

и мы можем написать, что

и получить выражение для характеристической функции единицы:

при условии, что

Теперь мы можем сформулировать алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе -местной функции Вебба вида, например, (2-24):

К Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль.

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

3. Все полученные выражения характеристических функций объединяются местной операцией Вебба, где — количество нулей заданной функции.

Пример 2-20. Построить совершенную нормальную форму вида (2-24) для следующей таблично заданной функции:

В соответствии с алгоритмом получаем:

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

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

Все определения из § 2-1 имеют свои аналоги для рассматриваемого базиса. Совершенной нормальной формой в дальнейшем будем считать выражение (2-24), операнды которого будут иметь наибольший возможный для данной функции ранг. Определение минимальной нормальной формы вполне аналогично определению 2-13.

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

Инверсанта и функции характеризуется тем, что всегда из следует Очевидно, что все из (2-24) являются инверсантами заданной функции Отметим, что тоже является инверсантой функции

По аналогии с классическим базисом будем говорить, что выражение в базисе Вебба, операндами которого являются все простые инверсанты заданной функции, является сокращенной нормальной формой функции. Минимальная нормальная форма будет получаться из сокращенной выбрасыванием некоторых инверсантов. Определение тупиковой формы в рассматриваемом базисе формулируется по аналогии с определением 2-11 из того же § 2-1.

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

Через будем обозначать выражение, которое описывает -местную операцию Вебба над операндами.

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

Другими словами,

где — произвольные термы и

Чтобы доказать справедливость леммы, рассмотрим все возможные случаи, полагая

1. Для все Но тогда и и в согласии с четвертым тождеством (2-20) обе стороны равенства (2-27) превращаются в

2. Среди имеется хотя бы одна единица. Но тогда и и в согласии с третьим тождеством из (2-20) обе стороны равенства (2-27) обращаются в нуль.

Введем теперь операции следующих типов: склеивания

неполного склеивания

(2-29) и поглощения

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

Для двухместного случая аналоги операций склеивания и поглощения имеют вид:

и

Справедливость всех этих соотношений легко доказать, используя лемму и два последних соотношения

Рассмотрим теперь аналоги методов минимизации, рассмотренных нами для базиса конъюнкция, дизъюнкция, отрицание.

Метод неопределенных коэффициентов

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

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

Пример 2-21. Найти минимальную нормальную форму для функции из примера (2-20).

Переходя к системе уравнений с неопределенными коэффициентами для данной функции, получаем:

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

Как следует из этой системы, Наиболее экономное решение для двух оставшихся уравнений

Окончательно

Метод Квайна

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

Пример 2-22. Найти минимальную нормальную форму для следующей совершенной нормальной формы функции:

Минитермы третьего ранга

Используем соотношение (2-29) и производим все. возможные неполные екленвания между этими минитермамн. Минитермы, которые участвовали хотя бы в одном склеивании, от.мечаем звездочкой, так как они в дальнейшем будут поглощены мннитермом второго ранга, являющимся результатом склеивания на основании соотношения (2-30). Получим минитермы второго ранга

В результате склеивания между первым и последним минитермом получится вырожденный минитерм, который инвертируется. Тот же самый результат получится из склеивания третьего и четвертого минитермов. Не будет поглощаться только второй минитерм.

Минитермы первого ранга

Удаляя из нормальной формы все поглощающиеся пнверсанты, получаем сокращенную нормальную форму, содержащую только простые инверсанты:

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

Метод Мак-Класки

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

Пример 2-23. Найти минимальную нормальную форму функции, принимающей значение нуль на наборах с номерами 0, 2, 4, 6, 8, 10, 12, 13, 14.

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

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

По неотмеченным наборам строится сокращенная нормальная форма, учитывая что нулю в наборе соответствует а единице —

Как и в предыдущем примере, единственная переменная вырожденного минитерма инвертируется.

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

Отметим, что минимальная ДНФ этой же функции более сложна:

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

От этой сложности на одну букву. Этот результат говорит еще раз о тесной связи этих базисов между собой. Метод перехода, предложенный Е. И. Пупыревым, указан в литературе, приведенной в конце книги.

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