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

Минимизация логических функций необходима для упрощения сложных выражений этих самых функций, например, сложные логические функции могут отображаться в две-три и более строк (допустим, на листе формата А4). Понятно, что сразу приступать к схемной реализации таких функций по большому счету тупо. Минимизировать логические функции можно с помощью всяких правил и законов алгебры логики (про это здесь), можно с помощью так называемых карт Карно. Представление функций с помощью карт Карно очень удобно, когда число переменных невелико (меньше или равно 6). По сути карта Карно - это табличка, которая содержит 2ⁿ клеток, где n - число переменных (n=1, 2, 3 ... n). К каждой клетке содержится логическое произведение переменных или их инверсий. Одни перемнные располагаются по горизонтали, другие - по вертикали. Изображаться карты Карно могут по-разному. Например, так:

x3x4	x1x2
	00	01	10	11
00
01
10
11

Или так:

Что касается первой таблички, первый знак (0 или 1) относится к первому символу (x₁ или x₃). Второй знак, соответственно, ко второму символу. Т. е., если в самой нижней правой ячейке стоит 1, то функция записывается x₂x₄. Во втором варианте вертикальные и горизонтальные черточки напротив ячеек означают, что переменная перекрывает эти ячейки, т. е. x₁ перекрывает две верхние стрроки, x₂ - два верхних столбца и т. п. И так, и так правильно, но лично мне более предпочтителен второй вариант.

Заполняются карты Карно следующим образом. Допустим есть некая функция из четырех переменных. Карта Карно будет содержать 16 клеток (2⁴ = 16). Функция вот такая:

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

Как это все делается? Посмотрите, вторая сверху слева ячейка, в ней стоит 1 и этой единице соответствует первое слагаемое в формуле. Единица стоит именно там, поскольку в этой ячейке перекрываются все переменные. Стоит уйти на ячейку влево, вправо, вверх, вниз и одна из переменных уже перекрывать ее не будет. Если одна из переменных с инверсией, что характерно для второго слагаемого, единица ставится с учетом не перекрытия ячейки этой переменной, т. е. для второго слагаемого x₁ с инверсией и единица стоит в третьей (сверху) строке третьего столбца. Для четвертого слагаемого с инверсией переменные x₂ и x₄. Поэтому единица стоит в последней строке (второй столбец). Так проставляются все единицы. В пустых ячейках по идее стоят нули (не показаны для наглядности). Подытожим, если пременная без инверсии, ей соответствует 1, если с инверсией - 0. Суть ясна?

После проставления всех единиц начинается объединение ячеек, в которых стоят эти самые единицы. Объединяются клетки по следующим правилам: число объединяемых клеток 2, 4, 8, 16, 32 и т. д., т. е. 2ⁿ, объединять надо как можно больше клеток, а самих объединений должно быть как можно меньше. На рисунке ниже показано, как это делается:

Для тех, кто не понял, единицы в количестве три, пять, шесть, семь, девять, десять и т. п. не объединяются. Если единицы стоят буквой "Т", "Г" и пр., то они также не объединяются.

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

Вот так. Было 5 слагаемых, осталось 2. Такую функцию уже намного легче реализовать. Такая форма записи функции называется совершенной дизъюнктивной нормальной формой (СДНФ). Дизъюнктивная нормальная форма (ДНФ) - это такая форма представления функции, при которой логические выражения функции строятся в виде дизъюнктивного ряда членов, каждый из которых является простой конъюнкцией аргументов. На простом языке, ДНФ - это форма записи функции в виде логической суммы слагаемых, каждое из которых является логическим произведением переменных. Если в каждом члене ДНФ представлены все аргументы или их инверсии, такая форма записи называется совершенной (СДНФ). Существует также конъюнктивная нормальная форма (КНФ) - форма представления функции в виде конъюнкции (логического умножения) ряда членов, каждый из которых является простой дизъюнкцией (логическим сложением) аргументов. Если в каждом члене КНФ представлены все аргументы или их инверсии, то такая форма называется совершенной (СКНФ).