Краткие теоретические сведения. Дизъюнктивная нормальная форма (ДНФ) — нормальная форма, в которой булева формула имеет вид дизъюнкции нескольких конъюнкций

Дизъюнктивная нормальная форма (ДНФ) — нормальная форма, в которой булева формула имеет вид дизъюнкции нескольких конъюнкций.

Совершенная Дизъюнктивная Нормальная Форма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

- в ней нет одинаковых элементарных конъюнкций.

- в каждой конъюнкции нет одинаковых пропозициональных букв.

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

Конъюнктивная нормальная форма (КНФ) — нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнкций.

Совершенная Конъюнктивная Нормальная Форма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

- в ней нет одинаковых элементарных дизъюнкций.

- в каждой дизъюнкции нет одинаковых пропозициональных букв.

- каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

Пример нахождения СКНФ

Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности статьи Минимизация логических функций методом Куайна:

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

для функции СКНФ –

.

для функции СДНФ –

.

Запишем полное выражение СКНФ:

В дизъюнкцию записывается переменная без инверсии если она в наборе равна 0 и с инверсией если она равна 1.

При этом, полное выражение СДНФ примет вид:

Метод Куайна – способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных
Преобразование функции можно разделить на два этапа:

· на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;

· на втором этапе — переход от сокращённой формы к минимальной форме.

Рассмотрим действия на первом этапе представления функции в сокращенной форме.

Представим, что заданная функция представлена в СДНФ. Для осуществления первого этапа преобразование проходит два действия:

1. Операция склеивания;

2. Операция поглощения.

Операция склеивания сводится к нахождению пар членов, отличающихся только одним членом выражения. Результаты склеивания играет роль дополнительных членов.

Следующий шаг - операция поглощения. Она основана на равенстве. Вследствие этого действия, из логического выражения вычёркиваются все члены, поглощаемые другими переменными, результаты которых получены в операции склеивания.
Обе операции первого этапа могут выполнятся до тех пор, пока это может быть осуществимо.

Пример выполнения операции склеивания и поглощения имеет вид:

.

Члены сокращённой формы называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией – СДНФ.

Второй этап заключается в минимизации полученного выражения.

Как и на первом этапе, в полученном равенстве могут содержаться члены, устранение которых никаким образом не повлияет на конечный результат. Следующий этап минимизации – удаление таких переменных. Пример представлен в таблице 4.1

Таблица 4.1

Пример минимизации полученных выражений.

Простые импликанты	Конституенты единицы
	×	×
	×		×
			×	×
				×	×
					×	×

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

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

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

Таким образом, минимальная ДНФ будет иметь вид:

Используя полученные при минимизации выражения, построим устройство реализующее приведённую таблицу истинности.

В заключении отметим, что совершенные нормальные формы не являются самым простым способом задания переключательных функций. Как правило, они допускают преобразование с помощью правил булевой алгебры к более простому виду. Способам построения простейших представлений переключательных функций посвящен один из следующих разделов курса.

Вопросы для самопроверки:

1. Используя таблицу истинности (Таблица 3.2), минимизировать полученное выражение при помощи СДНФ.

Таблица 3.2 – таблица заданий на самостоятельную работу.

2. В пакете программ САПР, построить полученную схему устройства.

3. На примере показать принцип его работы.

Вопросы для самоконтроля.

1. Что такое Совершенная Дизъюнктивная Нормальная Форма?

2. Что такое Совершенная Конъюнктивная Нормальная Форма?

2. Приведите пример операции склеивания и поглощения.

3. Этапы преобразования функции методом Куайна?

4. Как выбираются простые импликанты?