3.Метод Квайна.

Данный метод минимизации основан на применении свойства идемпотентности, поглощения и склеивания.

Рассмотрим этот метод на примере. Пусть заданы номера наборов из 4-х переменных, на которых функция равна единице : f(2,5,6,7,10,12,13,14) = 1. Необходимо составить СДНФ:

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

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

abcd
	1V	0	1V	0	1V	0	0	1V
	0	1V	0	1V	0	0	0	0
	0	1	0	0	0	0	1	0
	0	0	1	1	0	0	0	0
	0	0	0	0	0	1V	1V	0
	0	0	0	0	0	1	0	1

Выбранные ячейки отметим знаком «V». На последнем этапе минимизации получаем ДНФ:

Отметим, что в общем случае решений может быть несколько.

4.Метод Карно.

тот метод минимизации функции производится посредством таблицы, которая называется картой Карно. Карта Карно – это таблица, содержащая 2ⁿ ячеек. Каждой ячейке соответствует определенный набор переменных и указывается какое значение на этом наборе принимает функция. Причем соседние ячейки отличаются значением только одной переменной, что позволяет минимизировать ДНФ, используя закон склеивания, объединяя ячейки по 2ⁿ в прямоугольники, которые называются контурами. Соседними являются крайние верхние и крайние слева и справа. Необходимо стремиться к тому, чтобы контуры содержали как можно больше ячеек. А количество контуров должно быть минимально возможным. При создании контуров одну и туже ячейку (конъюнкцию) можно включать в несколько контуров в соответствии закона идемпотентности. Каждому контуру соответствует конъюнкция. При соединении двух ячеек исключается одна переменная, четырех – две, восьми – три и т.д. При объединении ячеек исключаются, согласно закона склеивания, переменные, которые входят в конъюнкции с разными значениями. Покажем карты Карно для функций от двух, трех и четырех переменных:

0 0	01
10	11

000	010	011	001
100	110	111	101

0000	0010	0011	0001
0100	0110	0111	0101
1100	1110	1111	1101
1000	1010	1011	1001

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