Построение сокращенной днф в классе дизъюнктивных нормальных форм
Этот метод не отличается большой эффективностью, но он прост для изложения и не требует введения дополнительных понятий.
Пусть булева функция задана таблицей истинности или СДНФ.
Минимизирующая карта булевой функции представляет собой квадратную матрицу 2nґ2n, где n – число переменных. Первые столбцы отводят для аргументов, дальнейшие – для их всевозможных конъюнкций по 2, по 3 и т. д. сомножителей, предпоследний - для конъюнкции всех аргументов, последний – для значений функции.
Шаг 1. Столбцы для аргументов, как обычно в таблицах истинности, заполняются всевозможными наборами 0 и 1. В столбцах для конъюнкций проставляются десятичные значения двоичных чисел, соответствующих наборам значений аргументов. Последний столбец заполняется соответственно значению функции.
Далее работа чередуется по строкам, по столбцам.
Шаг 2. Вычеркиваются строки, в которых функция обращается в нуль.
Шаг 3. В каждом столбце из сохранившихся чисел вычеркивают те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге.
Шаг 4. В сохранившихся строках выбирают «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводят их кружочками.
Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркивают все, кроме одного.
Шаг 6. С помощью оставшихся обведенных чисел образуют конъюнкции. Для этого переводят каждое число в двоичную систему. Переменную, которой соответствует 1, берут сомножителем без отрицания, которой соответствует 0 – с отрицанием.
Шаг 8. Составляют дизъюнкцию полученных конъюнкций. В результате получаем сокращенную ДНФ функции.
Пример 36.
Построить сокращенную ДНФ для функции f=11100101.
предыдущаяследующая