math_logic_lectures (2)

Сокращенная ДНФ

Грань называется максимальной относительно , если не существует такой грани ′ , что ′ .

Коньюнкция , соответствующая максимальной грани

называется простой импликантой.

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

R .

Алгоритм построения

Берем любую КНФ функции (например совершенную), и раскрываем все скобки. После этого удаляем все нулевые, поглощаемые и дублирующие члены, т.е. выполняем преобразования вида 1 2 1 = 1 и 1 1 = 1. В результате придем к сокращенной ДНФ.

Леонид

Шалагинов

Нормальные

формы

Полнота и замкнутость

Минимизация

ДНФ

Пример

Рассмотрим функцию = (1010111100010101), построим ее сокращенную ДНФ:

СДНФ: ( )( )( )( )()( )( ).

Раскроем скобки и произведем сокращение: .

Отметим соответствующие грани на кубе:

Леонид

Шалагинов

Нормальные

формы

Полнота и замкнутость

Минимизация

ДНФ

Метод минимизирующих карт

Рассмотрим построение сокращенной ДНФ той же функции методом минимизирующих карт:

Леонид

Шалагинов

Нормальные

формы

Полнота и замкнутость

Минимизация

ДНФ

Пример

Рассмотрим функцию = (0011010110101100), построим для нее минимизирующую карту:

Леонид

Шалагинов

Нормальные

формы

Полнота и замкнутость

Минимизация

ДНФ

Теперь построим сокращенную ДНФ:

Тупиковые ДНФ

Покрытие множества максимальными гранями, из которого нельзя удалить ни одну грань, называется неприводимым.

ДНФ, соответствующая неприводимому покрытию, называется

тупиковой.

Рассмотрим несколько тупиковых ДНФ функции:

Леонид

Шалагинов

Нормальные

формы

Полнота и замкнутость

Минимизация

ДНФ

ДНФ Квайна

Максимальная грань называется ядровой, если она содержит вершину, которая не лежит ни в какой другой грани.

Совокупность ядровых граней называется ядром.

Ядро множества входит в любое покрытие этого множества максимальными гранями.

Очевидно, что грань, которая не является ядровой и целиком покрывается ядром, не лежит ни в каком неприводимом покрытии.

ДНФ, соответствующая покрытию всеми гранями, которые не покрываются ядром, называется ДНФ Квайна (RКв).

Леонид

Шалагинов

Нормальные

формы

Полнота и замкнутость

Минимизация

ДНФ

Пример

		Леонид
		Шалагинов
	Рассмотрим функцию = (0011000110101100) и построим для	Нормальные
	нее минимизирующую карту:
		формы
		Полнота и
		замкнутость
		Минимизация
		ДНФ

Красным выделены точки, лежащие только в одной грани. Очевидно, грани, содержащие эти точки и образуют ядро. Этим граням соответствуют коньюнкции , , . Легко увидеть, что остальные грани целиком покрываются ядром, поэтому ДНФ Квайна будет дизъюнкцией импликант, соответствующих ядровым граням.

RКв = .

ДНФ типа Σ

ДНФ, соответствующая покрытию множества совокупностью граней, каждая из которых входит хотя бы в одно неприводимое покрытие называется ДНФ типа (RΣ ).

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

Пусть и 0 какая-то максимальная грань, содержащая

. Точка называется регулярной (относительно 0 ), если найдется 0 , такая что .

Грань, все точки которой регулярны относительно нее, называется регулярной гранью.

Теорема Журавлева

Леонид

Шалагинов

Нормальные

формы

Полнота и замкнутость

Минимизация

ДНФ

Для того чтобы простая импликанта 0 не входила в ДНФ типа необходимо и достаточно, чтобы максимальная грань0 была регулярной.

Пример

Рассмотрим функцию = (1011000110111101), построим минимизирующую карту

красным выделена регулярная грань. Поэтому ДНФ типа будет следующая: .

Леонид

Шалагинов

Нормальные

формы

Полнота и замкнутость

Минимизация

ДНФ

ДНФ Квайна и Σ

Леонид

Шалагинов

Теорема о соотношении ДНФ Квайна и ДНФ типа Σ Нормальные

формы

(RКв) ≥ (RΣ ).

Полнота и замкнутость

Пример:

Рассмотрим функцию = (11101010010010101010000010100000), посмотрим на расположение граней:

Минимизация

ДНФ

В дальнейшем нужно применить алгоритм построения наименьшего покрытия.