Построение минимальных нормальных форм по картам Карно

Каждой клетке карты Карно n-местной переключательной функции, со-

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

вить в соответствие элементарную конъюнкцию n-го ранга.

Дизъюнкция по-лученных ЭК - есть СДНФ функции. Две ЭК в СДНФ, отличающиеся одной

буквой (Axi, A~xi), соответствуют паре соседних клеток КК по вертикали

или горизонтали либо симметрично расположенных по вертикали или гори-

зонтали.

Данная пара клеток, в свою очередь, соответствует двоичным

наборам, отличающимся значением лишь одной переменной, то есть отлич-

ным в одном разряде.

В СДНФ конъюнкции Axi и A~xi могут быть склеены по букве xi:

Axi\/A~xi=A. В силу этого паре соседних клеток КК можно поставить в

соответствие ЭК (n-1)-го ранга. При этом в ЭК (n-1)-го ранга будет от-

сутствовать переменная, значение которой различно в соответствующих

двоичных наборах.

Например, клетке 0001 в карте соответствует ЭК ~x1~x2~x3x4, смеж-

ной с ней клетке 0011 - ~x1~x2~x3x4. Паре указанных клеток можно пос-

тавить в соответствие ЭК ~x1~x2x4=~x1~x2~x3x4 \/ ~x1~x2~x3x4 (интервал

00z1). Паре клеток 1001 и 1011 соответствует ЭК ~x2x4=~x1~x2x4 \/

x1~x2x4 (интервал 10z1). Этим двум парам клеток, симметрично располо-

женным на карте, можно поставить в соответствие ЭК ~x2x4=~x1~x2x4 \/

x1~x2x4 (интервал z0z1). Нетрудно увидеть, что каждая из четырех кле-

ток имеет две смежные клетки из этой области.

Рассуждая по индукции, назовем ОБЛАСТЬЮ СМЕЖНЫХ КЛЕТОК совокуп-

ность из 2^k клеток (k in {0,1,...,n}), каждая из которых имеет k

смежных с ней клеток из этой области. Каждой области можно поставить в

соответствие ЭК.

ПРАВИЛО ПОКРЫТИЯ 1. Любой смежной области из 2^k клеток можно пос-

тавить в соответствие элементарную конъюнкцию (n-k)-го ранга, состоя-

щую из переменных, которые имеют постоянное значение во всех единичных

наборах, соответствующих клеткам области. Причем переменная xi включа-

ется в ЭК в прямом виде, если эта переменная имеет значение 1 на всех

клетках области. Соответственно переменная xi включается в ЭК в ин-

версном виде, если эта переменная имеет значение 0 на всех клетках об-

ласти. "Покрытая" область на карте обводится контуром. Дизъюнкция ЭК,

совместно покрывающих все клетки карты, заполненные единицами, есть

одна из ДНФ переключательной функции.

Цель минимизации формулы ПФ по карте Карно - "покрыть" все клетки,

содержащие единицы, наименьшим числом ЭК наименьшего ранга, т.е. наи-

меньшим числом контуров, каждый из которых охватывает как можно боль-

шую область смежных клеток, "покрыть" все клетки, содержащие единицы.

Дизъюнкция полученных ЭК есть одна из тупиковых (возможно минимальная)

ДНФ функции.

### y=K0 \/ K1 \/ K2 \/ K5 \/ K7 \/ K8 \/ K10 \/ K14 \/ K15

n=4 --------------------- x3

--------------------- x4

00 01 11 10

+----------+----------+----------+----------+

00| 1 | 1 | 0 | 1 |

| 0| 1| 3| 2|

+----------+----------+----------+----------|

| 01| 0 | 1 | 1 | 0 |

| | 4| 5| 7| 6|

| +----------+----------+----------+----------|

| | 11| 0 | 0 | 1 | 1 |

| | | 12| 13| 15| 14|

| +----------+----------+----------+----------|

| 10| 1 | 0 | 0 | 1 |

| | 8| 9| 11| 10|

+----------+----------+----------+----------+

x1 x2

Минимальное покрытие: Области(наборы) Интервалы Конъюнкции

(0,2,8,10) z0z0(7) ~x2~x4

(1,5) 0z01(2) ~x1~x3x4

(15,14) 111z(6) x1x2x3

--------------------------------

ТДНФ 1 (5,7) 01z1(3) ~x1x2x4

ТДНФ 2 (7,15) z111(5) x2x3x4

Рассмотрим особенности построения минимальных КНФ по картам Карно.

Учитывая свойство двойственности ДНФ и КНФ функции, по карте Карно

можно построить тупиковую (возможно минимальную) КНФ.

ПРАВИЛО ПОКРЫТИЯ 2. Любой смежной области из 2^k клеток, заполнен-

ных нулями, можно поставить в соответствие элементарную дизъюнкцию

(n-k)-го ранга, состоящую из переменных, которые имеют постоянное зна-

чение во всех нулевых наборах, соответствующих клеткам области, причем

переменная xi входит в ЭД в прямом виде, если эта переменная имеет

значение 0 на всех клетках области. Соответственно переменная xi вхо-

дит в ЭД в инверсном виде, если она имеет значение 1 на всех клетках

области. Конъюнкция минимального числа ЭД, совместно покрывающих все

клетки карты, заполненные нулями, есть одна из тупиковых (возможно ми-

нимальных) КНФ переключательной функции.

### y=K0 \/ K1 \/ K2 \/ K5 \/ K7 \/ K8 \/ K10 \/ K14 \/ K15

y=D3 * D4 * D6 * D9 * D11 * D12 * D13

n=4 --------------------- x3

--------------------- x4

00 01 11 10

+----------+----------+----------+----------+

00| 1 | 1 | 0 | 1 |

| 0| 1| 3| 2|

+----------+----------+----------+----------|

| 01| 0 | 1 | 1 | 0 |

| | 4| 5| 7| 6|

| +----------+----------+----------+----------|

| | 11| 0 | 0 | 1 | 1 |

| | | 12| 13| 15| 14|

| +----------+----------+----------+----------|

| 10| 1 | 0 | 0 | 1 |

| | 8| 9| 11| 10|

+----------+----------+----------+----------+

x1 x2

Минимальное покрытие: Области(наборы) Интервалы Дизъюнкции

(3,11) z011 (x2\/~x3\/~x4)

(4,6) 01z0 (x1\/~x2\/ x4)

(4,12) z100 (~x2\/ x3\/ x4)

(13,9) 1z01 (~x1\/ x3\/~x4)

51. Специальные разложения ПФ.

Преобразование КНФ в СКНФ.

Схематично основную идею преобразования можно представить так:

X Ú Y ≡ X Ú Y Ú 0 ≡ X Ú Y Ú Z×Z ≡ (X Ú Y Ú Z)×(X Ú Y Ú Z)

Преобразование ДНФ в СДНФ.

Схематично основную идею преобразования можно представить так:

X×Y ≡ X×Y×1 ≡ X×Y×(Z Ú Z) ≡ X×Y×Z Ú X×Y×Z