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

 

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

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

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) одни и те же клетки могут входить в разные области, т.е. области могут пересекаться.

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

3) допускается сворачивание карты в цилиндр как по горизонтальной, так и по вертикальной оси с объединением противоположных граней

Карты.

Например, карту, размеченную следующим образом, следует свернуть сна-

х х х чала по вертикальной оси, что даёт две области

по две клетки каждая. Затем свернуть карту по

горизонтальной оси, в результате чего получает-

ся область, состоящая из четырёх клеток;

х х х 4) при участии всех отмеченных клеток в

х х процедуре формирования областей следует

Стремиться к минимальному числу областей, поскольку только тогда число членов минимизированной функции будет

Минимальным.

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