(926)274-88-54
Бесплатная доставка.
Бесплатная сборка.
График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
|
|
Звоните! (926)274-88-54 Бесплатная доставка. Бесплатная сборка. |
Ассортимент тканей График работы: Ежедневно. С 8-00 до 20-00. Почта: soft_hous@mail.ru |
  
|
Читальный зал --> Программные средства foundation Графически это означает, что можно обводить прямоугольные наборы единиц {rectangular sets of Is), содержащихся в 2 клетках ( прямоугольные как в буквальном, так и в переносном смысле этого слова), распространив определение прямоугольный на случаи, когда необходимо принимать во внимание свернутость карты по краям. Литералы, которые войдут в соответствующие термы-произведения, можно непосредственно определить по карте; вопрос о каждой из переменных решается по одному из следующих правил; Если обведенная область покрывает только ту часть карты, где переменная равна О, то эта переменная входит в терм-произведение в виде дополнения. Если обведенная область покрывает только ту часть карты, где переменная равна 1, то эта переменная входит в терм-произведение непосредственно. Если в обведенную область попадают участки карты, где переменная равна О, а также участки карты, где переменная равна 1, то эта переменная отсутствует в терме-произведении. Сумма произведений для нашей функции должна состоять из термов-произведений (обведенных наборов клеток, содержащих 1), которые покрывают все единицы на карте и не содержат нулей. z\00 01 11 10 z\00 01 11 10  Ч Лхг = X Z + г Рис. 4.29. F = XYz( (а) первоначальная карта Карно; (Ь) карта Карно с обведенными термами-произведениями; (с) схема И-ИЛИ В самом последнем нашем примере логическая функция имела вид: F=Xxyz( 1,4, 5,6); карта Карно для нее представлена на рис. 4.29(a) и (Ь). Мы обвели два набора единиц: один из них охватывает четыре клетки и соответствует терму-произведению Y, а другой состоит из двух единиц и эквивалентен терму-произведению X Z. Обратите внимание на то, что во второй терм-произведение входит на Один литерал меньше, чем в соответствующий терм-произведение в нашем алгебраическом решении (X Y - Z). Включив клетку б в наибольший возможный набор единиц, мы нашли более экономичную реализацию данной логической функции. поскольку 2-входовой вентиль И, скорее всего, будет стоить дешевле, чем 3-входовой вентиль. То, что два разных терма-произведения покрывают теперь одну и ту же клетку, содержащую 1 (4-ю клетку), никак не отражается на логической функции, так как при логическом сложении 1 + 1 = 1, а не 2! Соответствующая двухуровневая схема И-ИЛИ показана на рис. 4.29(c). Другим примером может служить минимизация схемы устройства для обнаружения простых чисел, приведенная ранее нарис. 4.18; результат минимизации представлен нарис. 4.30.
F = Zn3,n2,n1,N0(1.2.3,5,7,11,13) N,N, 00 01 11 10 Ng-No Ng-Ni-No (C) N3 N, 4>v- IV N1 > > Na-No N3-N2-Ni > Рис. 4.30. Устройство для обнаружения простых чисел: (а) исходная карта Карно; (Ь) обведенные наборы единиц и соответствующие им термы-произведения; (с) минимизированная схема Теперь нам понадобится еще несколько определений, чтобы внести ясность в то, что мы делаем: Минимальная сумма {minimal sum) логической функции F(Xi,..., Хя) - это такое выражение для F вида сумма произведений , что не существует представлений F в виде суммы произведений с меньшим числом термов-произведений, а в любое другое выражение вида сумма произведений с тем же самым чис- лом термов входит, по меньшей мере, столько же литералов. Другими словами, минимальная сумма содержит наименьшее возможное число термов-произведений (равное числу вентилей на первом уровне и числу входов вентилей на втором уровне) и, кроме этого, наименьшее возможное число литералов (равное числу входов вентилей на первом уровне). Таким образом, среди трех вариантов схем для обнаружения простых чисел, только схема, приведенная нарис. 4.30 является реализацией минимальной суммы. Следующее определение точно устанавливает смысл слов влечет за собой , когда мы говорим о логических функциях: Логическая функция P(Xi,... ,Хя) влечет за собой (implies) логическую функцию F(Xi,..., Хя), если для каждой комбинации переменных, такой что Р = 1, имеет место также F = 1. Иначе это можно выразить так: если Р влечет за собой F, то F равно 1 для каждой комбинации переменных, для которой Р = 1, и, может быть, еще при каких-нибудь комбинациях. Такую связь между Р и F можно символически записать в виде Р =Ф F. Об этой связи между Р и F можно сказать также, что F включает в себя (includes) р или что F покрывает (covers) Р . Простая импликанта (prime implicant) логической функции F(Xi,..., Х ) - это нормальный терм-произведение P(Xi,...,Xn), который влечет за собой F, причем такой, что если любую переменную удалить из Р, то получающийся при этом терм-произведение уже не влечет за собой F. На языке карты Карно простая импликанта функции F представляет собой обведенный набор клеток, содержащих 1, удовлетворяющий нашим правилам обьединения, такой, что если мы попытаемся его расширить (покрыть вдвое большее число клеток), то в него обязательно попадет, по крайней мере, один 0. Теперь пришел черед самого важного; речь идет о теореме, которая устанавливает предел того, сколько труда нужно затратить на поиск минимальной суммы логической функции: Теорема о простых импликантах. Минимальная сумма является суммой простых импликант. Это означает, что при поиске минимальной суммы не нужно рассматривать термы-произведения, не являющиеся простыми импликантами. Эта теорема легко доказывается от противного. Предположим, что терм-произведение Р в минимальной сумме не является простой импликантой. Тогда, по определению простой импли-канты, из Р можно удалить какой-то литерал, если только Р не является единицей, и получить новый терм-произведение Р*, который все еще влечет за собой F. Если мы заменим Р на Р* в сумме, относительно которой мы предположили. Что она минимальна, то получающаяся в результате этого сумма будет по-прежнему равна F, но будет содержать на один литерал меньше. Поэтому исходная сумма, фигурировавшая в нашем предположении, вовсе не была минимальной. Рассмотрим в качестве другого примера минимизации функцию 4-х переменных, приведенную на рис. 4.31. В данном случае имеется две простые импликанты, и совершенно очевидно, что их обе необходимо включить в минимальную сумму, чтобы покрыть все клетки таблицы, содержащие 1. Мы не приводим принципиальную схему, поскольку теперь вы уже сами знаете, как это сделать. ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку. Звоните! Ежедневно! (926)274-88-54 Продажа и изготовление мебели. Копирование контента сайта запрещено. Авторские права защищаются адвокатской коллегией г. Москвы. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||