Александр Казанский - Дискретная математика. Краткий курс. Учебное пособие

5) P 1 = А С ∩ В С ∩ С и Р 2 = В ∩ С С, здесь две переменные В и С имеют дополнения и поэтому P 1 и Р 2 не имеют соседства.

6) P 1 = А С ∩ В С ∩ С и Р 2 = В С ∩ С , здесь нет переменой без дополнения и с дополнением и поэтому P 1 и Р 2 также не имеют соседства.

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

Алгоритм 1.3для нахождения простых импликантов (метод соседства).

Пусть имеется исходное выражение алгебры множеств Е , представленное в нормальной форме.

Шаг 1. Используя закон поглощения, удалим произведение Pi , которое включается в себя произведение Pj .

Шаг 2. Если имеются два соседних произведения Pi и Pj , то добавим к Е соседство S , которое они определяют.

Шаг 3. Повторяем шаг 1 и шаг 2, пока они могут быть применены.

Теорема 1.4. Когда метод соседства прекращает работу, тогда выражение Е представляет собой объединение простых импликантов.

Пример 1.10

Найти все простые импликанты для выражения Е

Е = ( А ∩ В С ∩ С С) ∪ ( А С ∩ В С ∩ С С) ∪ ( A C ∩ С ) ∪ ( А С ∩ В С ∩ С ) ∪ ∪ ( А ∩ В ∩ С )

(удалено А С ∩ В С ∩ С , поглощаемое A C ∩ С )

= ( А ∩ В С ∩ С С) ∪ ( А С ∩ В С ∩ С С) ∪ ( A C ∩ С ) ∪ ( А ∩ В ∩ С )

(для соседних произведений ( А ∩ В С ∩ С С) и ( А С ∩ В С ∩ С С) добавлено ( В С ∩ С С))

= ( В С ∩ С С) ∪ ( А ∩ В С ∩ С С) ∪ ( А С ∩ В С ∩ С С) ∪ ( A C ∩ С ) ∪ ∪ ( А ∩ В ∩ С )

(удалены ( А ∩ В С ∩ С С) и ( А С ∩ В С ∩ С С) поглощаемые ( В С ∩ С С))

= ( В С ∩ С С) ∪ ( A C ∩ С ) ∪ ( А ∩ В ∩ С )

(для соседних произведений ( В С ∩ С С) и ( A C ∩ С ) добавлено ( A C ∩ В С))

= ( A C ∩ В С) ∪ ( В С ∩ С С) ∪ ( A C ∩ С )

(для соседних произведений ( A C ∩ С ) и ( А ∩ В ∩ С ) добавлено ( В ∩ С ))

= ( A C ∩ В С) ∪ ( В С ∩ С С) ∪ ( A C ∩ С ) ∪ ( А ∩ В ∩ С ) ∪ ( В ∩ С )

(удалено ( А ∩ В ∩ С ), поглощаемое ( В ∩ С ))

= ( A C ∩ В С) ∪ ( В С ∩ С С) ∪ ( A C ∩ С ) ∪ ( В ∩ С ).

Поскольку ни одного нового импликанта образовать нельзя, алгоритм прекращает свою работу и Е представлено в виде объединения четырех простых импликантов

E = ( A C ∩ В С), ( В С ∩ С С), ( A C ∩ С ) и ( В ∩ С ).

Хотя метод соседства и дает все простые импликанты, он не отвечает на вопрос, как для данного выражения выглядит эквивалентная ему минимальная форма и тем более сколько для него имеется эквивалентных минимальных форм. Чтобы найти минимальную форму, применим следующий алгоритм.

Алгоритм 1.4для нахождения минимальной формы в выражении, представляющем собой объединение простых импликантов.

Пусть имеется исходное выражение алгебры множеств Е , представленное в нормальной форме в виде объединения всех простых импликантов Е .

Шаг 1. Представим каждый простой импликант в виде объединения фундаментальных произведений (используя алгоритм преобразования выражения к полной нормальной форме объединения пересечений).

Шаг 2. Последовательно удалим из Е каждый такой имликант, все фундаментальные произведения которого имеются среди фундаментальных произведений остающегося выражения.

Пример 1.11. Применим этот алгоритм для выражения, полученного в примере 1.10:

Е = ( A C ∩ В С) ∪ ( В С ∩ С С) ∪ ( A C ∩ С ) ∪ ( В ∩ С ).

Выразим каждый простой импликант в виде объединения фундаментальных произведений:

A C ∩ В С = ( А С ∩ В С ∩ С ) ∪ ( А С ∩ В С ∩ С С),

В С ∩ С С = ( А С ∩ В С ∩ С С) ∪ ( А ∩ В С ∩ С С),

A C ∩ С = ( А С ∩ В ∩ С ) ∪ ( А С ∩ В С ∩ С ),

В ∩ С = ( А ∩ В ∩ С ) ∪ ( А С ∩ В ∩ С ).

Удалим импликант A C ∩ В С, поскольку его фундаментальное произведение ( А С ∩ В С ∩ С ) входит в выражение для третьего импликанта, а ( А С ∩ В С ∩ С С) входит в выражение для второго импликанта. Из оставшихся трех импликантов ни один этим свойством не обладает, поэтому алгоритм прекращает свою работу и минимальная форма для Е выглядит следующим образом:

Е = ( В С ∩ С С) ∪ ( A C ∩ С ) ∪ ( В ∩ С ).

Заметим также, что метод соседних произведений можно использовать и при эквивалентных преобразованиях выражений, чтобы уменьшить число произведений, входящих в упрощаемый многочлен. Это можно сделать при помощи следующих правил, называемых правилами соседства:

( А ∩ В ) ∪ ( А С ∩ С ) ∪ ( В ∩ С ) = ( А ∩ В ) ∪ ( А С ∩ С ),

( А ∪ В ) ∩ ( А С ∪ С ) ∩ ( В ∪ С ) = ( А ∪ В ) ∩ ( А С ∪ С ).

Доказательство этих правил, использующее граф, рассмотрено далее.

Многочлену в полной нормальной форм можно взаимно однозначно поставит в соответствие неориентированный двудольный граф. Как следует из параграфа 1.13, каждое множество имеет единственную полную нормальную форму объединения пересечений, а также единственную полную нормальную форму пресечения объединений. Отсюда следует, что каждому множеству можно поставить в соответствие единственный граф, задаваемый полной нормальной формой объединения пересечений, и единственный граф, задаваемый полной нормальной формой пересечения объединений. Заметим, что существуют множества, для которых эти графы могут быть изоморфны. Из сказанного также следует, что имеются задачи, связанные с множествами, которые можно решить методами теории графов.

Сначала необходимо определить понятие смежных произведений. Оно основано на той же идее, которая используется при введении понятия соседства в параграфе 1.14. Два фундаментальных произведения Pi и Pj называются смежными, если они состоят из тех же самых переменных и различаются точно в одном литерале. Другими словами, имеется какая-то переменная, которая в одно из этих фундаментальных произведений входит без дополнения, а в другое с дополнением. В частности, объединение двух смежных фундаментальных произведений представляет собой произведение, в котором на один литерал меньше.