Получение минимальных конъюнктивных нормальных

форм с помощью диаграмм Вейча.

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

При минимизации следует руководствоваться следующими правилами:

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

2) В клетки таблицы заносятся значения булевой функции. При поиске клеточки таблицы аргумент набора равный 0 берется без отрицания, а равный 1 – с отрицанием. В найденную клетку записывают значение функции.

3) Обводят контурами все нули с соблюдением следующих правил:

- контур должен быть прямоугольным;

- внутри контура не должно быть единиц;

- при обводке следует получить минимальное число контуров максимальной площади;

- число нулей в контуре должно быть равно степени числа 2 (1, 2, 4, 8, 16,…);

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

- при обводке следует учитывать, что самая верхняя и самая нижняя строки таблицы являются соседними. Соседними являются также крайний левый и крайний правый столбцы.

- количество контуров должно быть как можно меньше, а площадь контуров – как можно больше.

4) Записывают минимальное выражение как конъюнкцию логических сумм, которые описывают контура таблицы. Для поиска логического выражения для контура выясняют от каких аргументов он зависит. Если все нули контура приписаны к аргументу , то в логическое произведение этот аргумент входит. Если все нули контура помечены инверсией аргумента, то в произведение вписывается . Если в контуре есть 0, помеченные и 0, помеченные , то в описание контура этот аргумент не входит.

Пример: минимизировать не полностью определенную булеву функцию, заданную таблицей.

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