БУЛЕВЫ ФУНКЦИИ (2). Булевы функции

• Название: Булевы функции
• Дата: 18.05.2023
• Размер: 2.35 Mb.
• Имя файла: БУЛЕВЫ ФУНКЦИИ (2).docx
• Тип: Документы; #1140335
• страница: 6 из 7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	0	0	0	0	0	1	1	1	1
	1	0	1	1	0	1	1	1	0
	0	0	1	1	1	1	1	0	0
	1	0	0	1	1	0	1	1	0
	0	1	0	0	1	1	1	0	1

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


Минимизация булевых функции в базисе Пирса

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

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

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

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

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

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

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

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

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

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

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

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

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

ВАЖНО! При минимизации в базисах Шеффера и Пирса действуют два дополнительных правила:

Если контур занимает половину таблицы, то над аналитическим описанием этого контура ставится дополнительное отрицание;

Если в таблице только один контур, то над ним также следует поставить дополнительное отрицание.

Естественно, если в таблице только один контур, и он занимает половину таблицы, то над ним ставятся два дополнительных отрицания.


Пример: минимизировать в базисе Пирса функции:

	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1
	0	1	0	1	1	1	0	1
	1	0	1	0	1	0	1	0
	0	0	0	0	0	1	0	1
	1	0	0	0	0	1	0	1

, , , .

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

Для минимизации булевых функций большого числа аргументов могут быть использованы различные методы: метод неопределенных коэффициентов, метод минимизирующих карт, метод Квайна – Мак-Класки и т.д. Многие из методов страдают громоздкостью записи при их использования, некоторые работают только с полностью определенными булевыми функциями, а большинство методов позволяет получить только минимальные дизъюнктивные нормальные формы.

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

В начале рассмотрим получение МДНФ.
Минимизация булевых функций методом подбора

кратчайших претендентов.
При использовании метода булева функция представляется матрицей наборов аргументов, на которых функция равна единице (матрица единиц) и матрицей наборов, на которых функция равна нулю (матрица нулей). Под претендентом будем понимать в зависимости от требуемой формы представления функции произведение, сумму, функцию Шеффера, либо функцию Пирса над аргументами, взятые с отрицанием, либо без него. При получении МДНФ претендент – произведение аргументов. При получении МКНФ претендент – сумма аргументов, при минимизации в базисах Шеффера и Пирса – претендент операция И-НЕ и ИЛИ-НЕ над аргументами.

Число аргументов претендента будем называть длиной претендента.

Рассмотрим метод получения МДНФ методом подбора кратчайших произведений.

Пример. Задана не полностью определенная булева функция



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

- не подходит, поскольку оно равно 1 не только на 0100 матрицы единиц, но и на наборах 0101, 0110, 0111 матрицы нулей;

- не подходит, поскольку равно 1 на всех наборах матрицы нулей;

-не подходит, т.к. равно 1 на наборах 0101, 1101 матрицы нулей;

- не подходит, т.к. равно 1 на наборе 0110;

-не подходит, т.к. равно 1 на наборе 0101, 0110, 0111;

- не подходит, т.к. равно 1 на наборе 0101;

- не подходит, т.к. равно 1 на наборе 0110;

- не подходит, т.к. равно 1 на наборах 0101 и 1101;

- не подходит, т.к. равно 1 на наборе 0110;

-подходит, поскольку не равно 1 ни на одном наборе матрицы нулей и покрывает наборы 0100, 0000 матрицы единиц.

Вписываем в МДНФ и удаляем наборы 0100 и 0000 из матрицы единиц:



,

Выписываем набор 0001 матрицы единиц и аналогично ищем кратчайшее произведение равное единице на этом наборе:

- не подходит, поскольку дает значение 1 наборам 0101, 0110, 0111 матрицы нулей;

-подходит, поскольку не равно 1 ни на одном наборе матрицы нулей и покрывает наборы 0001, 1001 матрицы единиц. Вписываем в МДНФ и удаляем наборы 0001 и 1001 в матрице единиц: ,


, .

Выписываем набор 1110 и, поочередно рассматривая претенденты , находим кратчайшее произведение равное 1 на наборах 1110 и 1100 и равное нулю на всех наборах матрицы нулей. Вычеркиваем наборы 1110 и 1100 из матрицы единиц. Поскольку матрица единиц пуста – минимизация закончена. МДНФ имеет вид: .

Замечание: если искать покрытие матрицы единиц функцией Шеффера с минимальным числом аргументов, то получим минимальную форму в базисе Шеффера. Естественно, что следует учитывать особенности этой функции:

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

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

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

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

1) Задать длину претендента ;

2) Рассматривая матрицу нулей сформировать очередь всех допустимых претендентов длины ;

3) Если очередь пуста, принять и перейти к пункту 2, иначе – к пункту 4;

4) Взять первого допустимого претендента из очереди и проверить покрывает ли он хотя бы один набор в матрице единиц. Если – нет, то допустимый претендент удалить из очереди и перейти к пункту 3, если – да, то перейти к пункту 5.

5) Включить допустимый претендент в формулу, представляющую собой сумму претендентов;

6) Исключить наборы, покрываемые претендентом из матрицы единиц;

7) Исключить претендент из очереди;

8) Если матрица единиц не пуста, то перейти к пункту 3, иначе – конец.

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

Очередь состоит только из одного допустимого претендента , который равен нулю на всех наборах матрицы нулей. Этот претендент покрывает

наборы 0000, 0001,1001 матрицы единиц, поэтому он входит в формулу

. Матрица единиц после удаления этих наборов примет вид:



, .

Поскольку после удаления очередь пуста, формируем очередь допустимых претендентов, зависящих от двух аргументов: .

Допустимые претенденты не покрывают ни одного набора матрицы единиц и удаляются. Допустимый претендент покрывает наборы 1110 и 1100 матрицы единиц, поэтому он вписывается в формулу, а наборы 1110 и 1100 исключаются из матрицы единиц: ,



, .

Допустимые претенденты не покрывают набора 0101 и исключаются. Допустимый претендент покрывает набор 0101, следовательно, он входит в формулу: . Поскольку матрица единиц после удаления набора 0100 пуста – минимизация закончена.