16. Преобразование и упрощение логических выражений. Упрощение логических функций с помощью карт Карно. Частично-определенная функция и ее упрощение.

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

Наименование	Для умножения	Для сложения
Коммутативный закон	Х1Х2 = Х2Х1	Х1+Х2 = Х2+Х1
Ассоциативный закон	Х1(Х2Х3) = (Х1Х2)Х3	Х1+(Х2+Х3) = (Х1+Х2)+Х3
Дистрибутивный закон	Х1(Х2+Х3) = Х1Х2+Х1Х3
Правило повторения	ХХ = Х	Х+Х=Х
Правило отрицания
Правило двойного отрицания
Теоремы де Моргана:
Операции с 0 и 1:	Х1 = 1 Х0 = 0	Х+1 = 1 Х+0 = Х

Рассмотрим булево выражение: . Для реализации данного выражения необходимо 2 инвертора, 3 конъюнктора (И) и 1 дизъюнктор (ИЛИ). Упростим данное логическое выражение: .Таким образом, все логическое выражение сведено к логической операции ИЛИ.На практике для упрощения логических выражений, описывающих работу устройства, применяют карты Карно. Карта Карно представляет собой графическое изображение всех возможных наборов значений аргументов, каждый минтерм изображается на карте в виде клетки. Карта образуется путем такого расположения клеток, при котором минтермы, находящиеся в соседних клетках, отличаются значением одной переменной.

Карта Карно для 2-х переменных имеет вид, представленный на рисунке 1.1.а.

а)	б)	в)
Рис. 1.1 – Упрощение логического выражения с помощью карты Карно

Минимизируем исходное логическое выражение посредством применения карты Карно. Поставим 1 в карте Карно в тех клетках, которые соответствуют наборам функции, присутствующим в логическом выражении, рисунок 1.1.б.Отыскание минимальной формы сводится к максимальному склеиванию по некоторому аргументу: по В – вертикаль и по А – горизонталь. Единицы, находящиеся в соседних клетках, объединим контурами (рисунок 1.1.в). Возможно объединение 2, 4, 8 и т.д. единиц, стоящих в соседних клетках. Кроме этого, карта Карно может быть свернута в горизонтальный или вертикальный цилиндры, или шар, что также позволяет объединить единицы, стоящие в соседних крайних клетках свернутых карт.Т.к. у нас два контура, то новое выражение будет состоять из двух членов, связанных функцией ИЛИ. Например, для нижнего контура аргумент А встречается с и В, но в соответствии с правилом булевой алгебры аргументы и В дополняют друг друга, и их можно опустить, т.е. остается только аргумент А. В результате значение функции будет также сведено к логической операции ИЛИ.

Рассмотрим пример построения карты Карно для трех переменных. Пусть дано логическое выражение:

.Карта Карно и результат минимизации представлены на рисунке 1.2.

Рассмотрим пример построения карты Карно для четырех переменных, рисунок 1.3.

Рис. 1.3 – Карта Карно для 4-х переменных

В рассмотренных примерах осуществлялась минимизация по 1, однако в некоторых случаях более удобной может оказаться минимизация по 0. Пример такого случая представлен на рисунке 1.4. Минимизация по нулям показана штрихпунктирной линией, а по единицам – сплошной.

	Минимизация по 0 и 1

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