Минимизация логических функций методом карт Вейча

Практическая работа № 7

Изучение минимизации логических функций с использованием карт Карно-Вейча

Цель: Повторитьзаконы алгебры логики;построение таблиц истинности;алгоритм нахождения СДНФ и СКНФ; научиться минимизировать логическую функции:

- методом карт Вейча;

- методом карт Карно.

Порядок выполнения

1. Изучить теоретическую часть
2. Выполнить практическое задание
3. Ответить на контрольные вопросы
4. Оформить отчет по проделанной работе

Теоретическая часть

Минимизация логических функций методом карт Вейча

Метод минимизации функции с помощью карт Вейча обеспечивает простоту получения результатов. Карта Вейча представляет собой определенную форму таблицы истинности. Таблица1 является картами Вейча для функций соответственно двух (а), трех (б), четырех (в) аргументов.

Каждая клетка карты соответствует некоторому набору значений аргументов. Этот набор аргументов определяется присвоением значения лог. 1 буквам, на пересечении строк и столбцов которых расположена клетка.

Х3

Число клеток карты равно числу всех возможных наборов значений аргументов 2ⁿ(n– число аргументов функций). В каждую из клеток карты записывается значение функции на соответствующем этой клетке наборе значений аргументов.

Правила получения МДНФ функций с помощью карт Вейча:

Все клетки, содержащие 1, объединяются в замкнутые области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2^к, где к = 0, 1, 2,... Значит, допустимое число клеток вобласти 1, 2, 4, 8,... Области могут пересекаться и одни и те же клетки могут входить в разные области. Затем проводится запись выражения МДНФ функции. Каждая из областей в МДНФ представляется членом, число букв в котором на к меньше общего числа аргументов функцииn (n-k). Каждый член МДНФ составляется лишь из тех аргументов, которые для клеток соответствующей области имеют одинаковое значение (без инверсии либо с инверсией).

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

Таким образом, при охвате клеток замкнутыми областями следует стремиться, чтобы число областей было минимальным (при этом минимальным будет число членов в МДНФ функции), а каждая область содержала возможно большее число клеток (при этом минимальным будет число букв в членах МДНФ функции).

Пример 1: Пусть функция задана таблицей истинности:

Для получения МДНФ используем карты Вейча:

		Х3						Х3

Все клетки, содержащие 1, охватываются двумя областями. В каждой из областей 2ⁿ клеток, для них n-k=3-1= 2, и эти области в МДНФ будут представлены членами, содержащими по две буквы. Первой области соответствует член (аргумент х₃ здесь не присутствует, так как для одной клетки этой области он имеет значение без инверсии, для другой – с инверсией); второй области соответствует член .

Следовательно, МДНФ функции

Пример 2:

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

Минимальная ДНФ функции

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

	1		u cmV2LnhtbFBLBQYAAAAABAAEAPMAAAD7BQAAAAA= " filled="f"> 1	1

Минимальная ДНФ функции

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

МКНФ