Метод Карно (диаграммы Вейча)

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

Карты Карно (их разновидностью являются карты Вейча, которые строятся как развертки куба на плоскости), являются графическим представлением таблиц истинности. Поэтому они строятся или по таблице истинности анализируемой функции, или же по ее СНДФ.

Напомним, что каждая строка таблицы истинности, для которой функция равна единице, соответствует конкретному минтерму функции, представленной в СНДФ. Строка, для которой функция равна нулю является определенным макстермом функции, представленной в СНКФ.

Карта Карно представляет собой прямоугольник, разбитый на квадраты, число которых равно общему числу наборов для данной функции n переменных, т.е. оно равно 2n. Так, для функции четырех переменных квадратов будет 16, для пяти переменных - 32 и т.д. Каждый квадрат соответствует определенному набору или терму, причем наборы располагаются так, чтобы соседние наборы или термы, как по горизонтали, так и по вертикали, отличались бы только значением одной переменной: в одном квадрате она с инверсией, а в другом, соседнем - без. Функцию в СНДФ наносят на карту, отмечая, например, знаком 1 квадраты, соответствующие тем наборам, на которых функция равна единице, т.е. в СНДФ функции есть соответствующий минтерм. Остальные квадраты отмечаются знаком 0. Иногда в углу квадрата ставят номер набора. Такой способ используется, если функция задана числовым образом, но он неудо-бен для процедуры минимизации.

Рассмотрим примеры построения карт Карно по таблицам истинности для 2-х, 3-х и 4-х переменных.

1) Логическая функция двух переменных, где а) - таблица истинности; а б) - карта Карно.

Карту Карно для функции, например, четырех переменных A, B, C, D можно представить и таким образом:

№26. Сформулировать правила минимизации логических функций, заданных в виде карт Вейча

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

1. Добавим к данной функции слагаемое х, • х2 • х3, которое уже есть в данной функции, используя правило 3 (см. рис. 3.26):

2. Применим метод склеивания (теорема 11, рис. 3.26)
одинаково подчеркнутых элементарных конъюнкций

3. Применим метод склеивания для двух последних
элементарных конъюнкций

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

№27 Изложить алгоритмы получения МДНФ и МКНФ функций с помощью карт Карно.

Метод Квайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.^[1][2][3]
Преобразование функции можно разделить на два этапа:

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: