Дискретная математика. Кулаков Ю.В - 24 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Конъюнкция, соответствующая максимальному единичному интервалу булевой функции, называ-
ется простой импликантой этой функции.
Дизъюнкция простых импликант называется сокращенной ДНФ булевой функции.
При определении максимальных интервалов множество интервалов, соответствующих вершинам
гиперкуба, разбивают на пояса, причем некоторый i-й пояс содержит интервалы, отвечающие наборам с
i единицами в каждом. Тогда выделение максимальных интервалов сводится к попарному сравнению
элементов только соседних поясов. Каждая пара элементов соседних поясов, отличающихся друг от
друга только в одном разряде, образует новый интервал. Если построенные интервалы не являются мак-
симальными, то процесс выделения максимальных интервалов продолжают.
Результаты выделения максимальных интервалов для рассматриваемого примера приведены на рис.
15.
В данном случае множество максимальных интервалов {−00, 1−0, 11−, −11} содержит четыре мак-
симальных интервала, каждый из которых образует гиперкуб размерности 1 (ребро).
Сокращенная ДНФ рассматриваемой функции f (x
1
, x
2
, x
3
) имеет вид:
f
с
(x
1
, x
2
, x
3
) =
32213132
xxxxxxxx ∨∨∨ .
Получением сокращенной ДНФ булевой функции заканчивается первый этап метода.
Тупиковой ДНФ булевой функции f (x
1
, x
2
, ..., x
n
) называется такая ДНФ этой функции, которая при
вычеркивании хотя бы одного первичного терма не определяет f. Минимальная ДНФ булевой функции f
(x
1
, x
2
, ..., x
n
) является тупиковой.
Построение тупиковых ДНФ булевой функции сводится к покрытию столбцов строками в двумер-
ной таблице. Покрытием столбцов строками в двумерной таблице называется такое множество строк,
при котором для каждого столбца найдется хотя бы одна строка, на пересечении с которой этот столбец
имеет единицу, причем при вычеркивании хотя бы одного элемента из этого множества строк указанное
свойство не выполняется.
2 Построение и покрытие таблицы Квайна.
Таблица Квайна – двумерная таблица, каждой строке которой взаимно однозначно соответствует
максимальный единичный интервал, столбцу – конституента, а на пересечении i-й строки и j-го столбца
ставится единица, если j-я конституента входит в i-й интервал; в противном случае клетка (i, j) не заполня-
ется или в ней ставится ноль. Для рассматриваемого примера таблица Квайна представлена табл. 6.
Таблица 6
Конституента
Максимальные еди-
ничные интерва-
лы
000 100 110 011 111
a
–00 1 1 0 0 0
b
1–0 0 1 1 0 0
c
11– 0 0 1 0 1
d
–11 0 0 0 1 1
Максимальный единичный интервал называется обязательным, если найдется конституента, при-
надлежащая ему и только ему. Множество обязательных интервалов образует ядро покрытия. В данном
случае ядром покрытия является множество {–00, –11}, которое покрывает первый, второй, четвертый и
пятый столбцы.
Минимальная ДНФ выбирается из тупиковых ДНФ, соответствующих покрытиям таблицы Квайна.
Покрытия таблицы Квайна определяются путем преобразования некоторой мультипликативно-
аддитивной формы в аддитивно-мультипликативную. В рассматриваемом примере обозначим строки
000
100
110
011
111
−00
1
−0
11
−
−11
Ри

Страницы