Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Нахождение минимальной ДНФ с помощью карт Карно
Этот метод используется для формул с малым числом переменных. Карта Карно для функции n переменных содержит 2 n ячеек, каждая из которых соответствует одной из 2 n возможных комбинаций значений n булевых переменных x 1, x 2, …, xn. Две соседние ячейки отличаются значением только одной переменной. В случае функции трех переменных карту Карно можно представить в следующем виде:
В случае четырех переменных карта Карно имеет следующий вид: Булева функция может быть представлена на карте Карно выделением на карте ячеек, соответствующих наборам, на которых функция принимает значение 1. В этих ячейках будем писать 1. Незаполненные ячейки соответствуют нулям функции. Пример 3.14. Заполним карту Карно для функции
2 k соседних ячеек, содержащие единицы, называются покрытием в том случае, если они расположены в виде прямоугольника или квадрата. При этом считается, что ячейки на противоположных концах строки или столбца являются соседними, как будто карта расположена на торе. Каждое покрытие соответствует импликанте. Покрытие, состоящее из двух ячеек, соответствует произведению всех переменных кроме одной, значением которой отличаются эти ячейки. Покрытие из четырех ячеек соответствует произведению, в котором отсутствуют две переменные и т.д. Чем больше ячеек в покрытии, тем проще импликанта. Для получения простой импликанты выбирается покрытие наибольшего размера. Для построения минимальной ДНФ по карте Карно следуют двум правилам. 1. Выбирают покрытия наибольшего размера, содержащие ячейки, которые не могут быть ни в каком другом покрытии. 2. Для оставшихся ячеек выбирают покрытие наибольшего размера. Пример 3.15. Найдем минимальную ДНФ для функции. = Выпишем двоичные номера всех K1: 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1011, 1111.
Построим карту Карно и покроем все единицы на карте Карно покрытиями наибольшего размера.
Порядок построения минимальной ДНФ будет таким: - Выбираем покрытие наибольшего размера для ячейки, соответствующей x 1 x 2 x 3 x 4. Это будет импликанта x 3 x 4. - Выбираем покрытие для ячейки . Это будет импликанта . - Выбираем покрытие для ячейки . Это будет импликанта . Больше непокрытых ячеек не осталось, следовательно, минимальная ДНФ имеет вид .
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-01-20; просмотров: 408; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.218.254.122 (0.004 с.) |