Пусть А1, ,Аn – набор множеств, называемых образующими или порождающими, а s1 sn некоторая последовательность нулей и единиц, тогда

Пусть А₁,…,А_n – набор множеств, называемых образующими или порождающими, а s₁…s_n некоторая последовательность нулей и единиц, тогда

Множество называется первичным термом. Пересечение первичных термов называется элементарным пересечением.

Если элементарное пересечение имеет вид:

то оно называется конституэнтой. Конституэнта отличается от остальных элементарных пересечений тем, что 1) она содержит ровно n членов (n- число образующих множеств) 2) каждое образующее множество либо само входит в конституэнту, либо входит его дополнение.

Любая конституэнта определяется последовательностью . Эта последовательность задает некоторое число, в двоичной форме записи. Например, если число образующих равно n=4, а конституэнту определяет последовательность 0101, то эту последовательность можно считать записью число в двоичной системе исчисления, переводим его в десятичную систему 0101₂=5₁₀.

Итак, если известно количество образующих множеств, то любую конституэнту можно задать числом. Так, например число 5, в системе 4 порождающих множеств задает конституэнту 5₁₀=101₂=0101

`A<sub>1</sub>ÇA<sub>2</sub>Ç`A₃ÇA₄, а в системе 3 порождает A₁Ç`A₂ÇA₃

Если множество ВÎÌ(А₁…А_n) записано в виде объединения элементарных пересечений, то говорят, что оно представлено в нормальной форме Кантора (НФК). Точнее в нормальной дизъюнктивной форме Кантора.

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

Если множество В записано в виде объединения конституэнт, то говорят, что В представлено в совершенной нормальной форме Кантора (СНФК).

Теорема (о представление множества в СНФК)

Пусть дана алгебра множеств, порожденная множествами А₁,…,А_т, тогда любое множество этой алгебры можно представить в СНФК.

Представление множества в СНФК не будет оптимальным, очень часто множество можно представить более короткой формулой. Но, оказалось, что СНФК легко находится. А дальше ее можно упростить. Но в реальных задачах приходиться работать с формулами содержащими не 3-4 переменные, а десятки и сотни переменных. В случае большого числа переменных упрощение или минимизация формул оказывается довольно трудоемкой работой. Существует много алгоритмов минимизации СНФК. Один из них мы рассмотрим сейчас.

Определение.

НФК называется минимальной, если она содержит минимальное количество термов, т.е. с помощью законов булевой алгебры нельзя преобразовать ее в НФК с меньшим количеством термов.

Алгоритм, который мы рассмотрим, называется алгоритмом Квайна.

На первом этапе алгоритма Квайна находится сокращенная НФК исходного множества.

Для «механизации» этой работы используется следующий алгоритм.

1. Конституэнты задающие исходное множество записываются в виде последовательностей нулей и единиц.

2. Получившееся множество последовательностей нулей и единиц разбивается на слои, следующим образом:
в нулевой слой попадает одна последовательность, состоящая из нулей; во первый слой попадают последовательности содержащие 1 единицу; во второй слой последовательности содержащие две единицы, и т.д.

3. Выполняются все операции склеивания. (ĀÇВÈАÇВ=В)Нетрудно заметить, что операцию склеивания можно применить только к конституэнтам, расположенным в соседних слоях. Разбиение всех конституэнт на слои уменьшает сложность алгоритма.

Импликантой мы будем называть элементарное пересечение, которое либо является конституэнтой, входящей в СНФК исходного множества, либо получено в результате склеивания при выполнения шага 3.

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

Сокращенная НФК – это объединение всех простых импликант.

Пример. Пусть А=Ā₁Ç Ā₂Ç Ā₃È А₁Ç Ā₂Ç Ā₃È А₁Ç А₂Ç Ā₃ÈĀ₁Ç А₂Ç А₃È А₁Ç А₂Ç А₃

Например:0-пояс -000

1-пояс -100

2-пояс -110, 011

3-пояс -111

Сокращенная НФК множества А имеет вид:

А= Ā₂Ç Ā₃È А₁Ç Ā₃È А₁Ç А₂ È А₂Ç А₃

На этом закончился первый этап метода Квайна.

СОКРАЩЕННАЯ НФК в общем случае избыточна, некоторые из составляющих ее простых импликант могут быть исключены при сохранении эквивалентности формулы. ТУПИКОВАЯ НФК - это НФК, из которой нельзя исключить ни одной простой импликанты без потери эквивалентности формулы. МИНИМАЛЬНАЯ НФК - это тупиковая НФК, содержащая минимальное число букв среди возможных НФК.

На втором этапе находится минимальная НФК.

Для дальнейшей работы нам потребуется несколько определений

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

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

Второй этап

Построение и покрытие таблицы Квайна.

Таблица Квайна – двумерная таблица каждой строке которой взаимно – однозначно соответствует простая импликанта, столбцу- конституэнта, а на пересечении i-й строки и j-ого столбца находится единица, если j–я конституэнта участвовала в получении i–й простой импликанты; в противном случаи клетку (i, j) не заполняют или ставят в ней 0.

Строим таблицу Квайна для рассматриваемого нами примера: 4 интер., 5 конституэнт.

Таблица Квайна

Максим интервал
-00
1-0
11-
-11

Сначала находим ядро покрытия.

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

У нас ядро {-00, -11}. Ядро покрывает 1, 2, 4, 5 столбцы.

Образуем покрытие.

Для образования покрытия можно взять 2 или 3-ю строку. В результате получаем 2 покрытия.

1) {-00, -11, 1-0(добавляем к ядру 2-ю строку)}

2) {-00, -11, 11-(добавляем к ядру 3-ю строку)}

Каждое из них минимально имеет сложность 6.

А= Ā₂Ç Ā₃È А₁Ç Ā₃ È А₂Ç А₃

А= Ā₂Ç Ā₃È А₁Ç А₂ È А₂Ç А₃

Полученные пересечения порождают 2-покрытия: {-00, 1-0, -11}, {-00, 11-, -11}

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

Скобочная форма Кантора – выражение, определяющее множество М, в котором кроме первичных термов и знаков Ç,È,` есть скобки –(,).

Минимальная НФК находится в результате перебора всех покрытий.

Дата добавления: 2015-11-04