Минимизация функции методом Квайна

Максимальный интервал I_a, который не содержится ни в каком другом интервале I_a Ë I_к

где I_к - все интервалы функции, кроме I_a.

Рассмотрим функцию, заданную в СНФК:

N	Ki	F

 

В левой части двоичный эквивалент конституент,а в правой присутствует ли она в функциональном представлении или нет.

Кроме интервалов,представленные конституентами выделим другие интервалы более крупные.

 

001 0х1

011 х11

100 1х0 - максимальные интервалы относительно конституент.

110 11х

 

Лемма.

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

Доказательство:

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

М = А + В = А + В

В – максимальный интервал

В Ì В - не максимальный интервал

Вычеркиванием терма – получим максимальный интервал.

Тупиковой формой –называется нормальная форма Кантора, из которой не может быть вычеркнут ни один терм без изменения представления функции.

Минимальной формой – называется тупиковаяформа, минимальной сложности

Выражения для максимальных интервалов называются простыми импликантами.

ТЕОРЕМА.

Все тупиковые,а следовательно и минимальные формы содержатся в объединении всех простых импликант.

Доказательство:

Из определения следует,что если вНФК присутствует неминимальный интервал,то она не является тупиковой и не является минимальной.

Следовательно, тупиковой и минимальной формой есть объединение некоторых простых импликант из множества всех простых импликант.

Согласно вышеуказанной теореме 1-й шаг метода Квайна состоит в выделении простых импликант функции и составлении таблицы.

Строки соответствуют простым импликантам.

Столбцы – конституентам функции.

 

0х1
х11
1х0
11х

Если конституента содержится соответственном максимальном интервале, то в клетке ставится 1, если нет, то клетка остаётся пустой.

2-й шаг

Состоит в том, что из множества простых импликант составляются всевозможные подмножества, обладающие свойствами:

1. Элементы подмножества суммарно покрывают все конституенты функции.

2. При вычеркивании любого элемента подмножества свойство 1 не выполняется.

Подмножество, удовлетворяющее свойствам называется минимальными покрытиями таблицы Квайна.

 

ТЕОРЕМА

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

Доказательство:

Необходимость следует из того, что тупиковые и минимальные формы есть объединение простых импликант. Достаточность следует из того, что не возможно вычеркнуть простую импликанту, а следовательно любой первичный термин, без нарушения покрытия всех конституент функции.