СДНФ, либо в 0, если используется СКНФ. При этом, в случае частично определённой функции учитываются и безраз- личные наборы

Целью минимизации является переход от совершенной формы записи ФАЛ к соответствующей нормальной форме с минимальным числом членов и минимальным числом аргументов в каждом из них.

Упрощение ФАЛ с сохранением её свойств называется минимизацией.

Существует два класса методов минимизации ФАЛ: графические и алгебраические. Из графических методов наибольшее практическое применение получил метод карт Вейча-Карно.

1. Минимизация ФАЛ с помощью карт Вейча-Карно.

Карта Вейча-Карно представляет собой специальную форму таблицы истинности для двух, трёх или четырёх аргументов:

n = 2n = 3 Число клеток карты определяется числом

х₁ х₁ х₁ х₁ возможных наборов значений аргументов и

х₀ х₀ при числе аргументов n равно 2ⁿ.

х₀ х₀ Таким образом, каждая клетка карты соответ-
х₂ х₂ х₂ ствует определённому набору аргументов.

n = 4

х₁ х₁ Минимизация производится в следующей

х₀ х₃последовательности.
Отмечаются клетки карты, соответствую-

х₃ щие членам исходной функции или, иными

х₀ х₃ словами, наборам аргументов, на которых
х₂ х₂ х₂ функция обращается в 1, если используется

Отсюда следует, что размечать карту можно непосредственно по таблице истинности.

Каждая отмечаемая клетка расположена на пересечении строк и столбцов таблицы, одноимённых с аргументами соответствующего члена функции.

Например, пусть КЦУ задано таблицей истинности:

№ набора х₂ х₁ х₀ у Соответствующая ей ФАЛ будет иметь вид:

0 0 0 0 0 у_СДНФ = х₂х₁х₀ Ú х₂х₁х₀ Ú х₂х₁х₀ Ú х₂х₁х₀ Ú х₂х₁х₀ или

1 0 0 1 0 у_СКНФ = (х₂ Ú х₁ Ú х₀)(х₂ Ú х₁ Ú х₀)(х₂ Ú х₁ Ú х₀)(х₂ Ú

2 0 1 0 ~ х₁ Ú х₀).

3 0 1 1 1 Первый член функции в СДНФ и третий в СКНФ

4 1 0 0 1 соответствуют безразличному набору.

5 1 0 1 0 Представим таблицу истинности в форме карты

6 1 1 0 1 Вейча-Карно.

7 1 1 1 1 Для разметки карты переменные каждого из членов функции в совершенной форме следует рассматривать как координаты. В соответствии с этим определим клетку, соответствующую первому члену функции в СДНФ. Координата х₀ определяет нижнюю строку карты, коорди-

ната х₁ - два первых столбца, а координата х₂ - два крайних столбца. Все координаты пересекаются на единственной клетке карты - нижней левой угловой.

случай СДНФслучай СКНФ Остальные клет-

х₁ х₁ х₁ х₁ ки находятся
х₀ I х₀ I ~ аналогично не-

1 1 0 зависимо от

х₀ ~ 1 1 II х₀ 0 0 II формы предс-
тавления ФАЛ.
х₂ х₂ х₂ х₂ х₂ х₂

х₁ х₁

х₀ Далее отмеченные клетки объединяются в

х₀ замкнутые области. При этом используются

х₂ х₂ х₂ следующие правила:

1) каждая область должна представлять собой прямоугольник с числом клеток 2^k, где k = 0, 1, 2,... Т.е. область может содержать одну клетку (k = 0), две клетки (k = 1), четыре (k = 2), восемь (k = 3) и т.д. Кроме того, нельзя объединять клетки, расположенные по диагонали, а также разделённые неотмеченными клетками.

х х х Например, в область можно объединить две верхние ле-

вые клетки, но нельзя объединить нижние и крайние

х х правые.

В то же время число клеток в области должно быть максимально возможным, поскольку только тогда число аргументов в соответствующем члене минимизированной функции будет минимальным;

2) одни и те же клетки могут входить в разные области, т.е. области могут пересекаться.

Например, при следующей разметке карты х х следует сформировать две пересекающиеся области; х