Пред.
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) легко получить:
если выбрать характеристические функции единицы для множества
Если использовать характеристические функции единицы для множества
Если Для получения аналогичных нормальных форм в базисе Шеффера можно использовать (1-28) и характеристические функции нуля. Перейдем теперь к аналитическому выражению характеристических функций единицы в базисе Вебба. В § 1-7 было получено выражение
Если применить последнее из соотношений (2-20), то
и мы можем написать, что
и получить выражение для характеристической функции единицы:
при условии, что
Теперь мы можем сформулировать алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы в базисе К Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль. 2. Выписать термы типа (2-26), соответствующие этим наборам аргументов. При этом, если аргумент 3. Все полученные выражения характеристических функций объединяются местной операцией Вебба, где Пример 2-20. Построить совершенную нормальную форму вида (2-24) для следующей таблично заданной функции:
В соответствии с алгоритмом получаем:
Перейдем теперь к проблеме минимизации в монофункциональных базисах. Существует,два подхода проблеме минимизации: либо по аналогии с минимизацией в классе ДНФ строится специальный метод минимизации для монофункционального базиса, либо минимизация производится в классе ДНФ, а затем строится специальный метод перехода от базиса конъюнкция, дизъюнкция, отрицание к монофункциональному базису. Рассмотрим сначала первый подход на примере минимизации в базисе, состоящем из функции Вебба. Все определения из § 2-1 имеют свои аналоги для рассматриваемого базиса. Совершенной нормальной формой в дальнейшем будем считать выражение (2-24), операнды которого будут иметь наибольший возможный для данной функции ранг. Определение минимальной нормальной формы вполне аналогично определению 2-13. Понятиям интервал и максимальный интервал из геометрической интерпретации области определения функции алгебры логики соответствовали понятия импликанта и простая импликанта при минимизации в классе ДНФ. В базисе Вебба соответствующие понятия будем называть инверсантой и простой инверсаной. Инверсанта и функции По аналогии с классическим базисом будем говорить, что выражение в базисе Вебба, операндами которого являются все простые инверсанты заданной функции, является сокращенной нормальной формой функции. Минимальная нормальная форма будет получаться из сокращенной выбрасыванием некоторых инверсантов. Определение тупиковой формы в рассматриваемом базисе формулируется по аналогии с определением 2-11 из того же § 2-1. Прежде чем перейти к рассмотрению применения в базисе Вебба некоторых известных из классического базиса методов минимизации, рассмотрим эквивалентные преобразования, приводящие к операциям склеивания и поглощения в алгебре Вебба. Через Лемма. Если Другими словами,
где Чтобы доказать справедливость леммы, рассмотрим все возможные случаи, полагая 1. Для 2. Среди Введем теперь операции следующих типов: склеивания
неполного склеивания
(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 |
Оглавление
|