Аналитические методы построения сокращенной ДНФ

Построение сокращенной ДНФ по совершенной ДНФ. Определим следующие операции над ДНФ:

1°. Склеивание: .

2°. Неполное склеивание: .

3°. Поглощение: .

Алгоритм построения сокращенной ДНФ состоит в следующем:

1. Представить заданную функцию совершенной ДНФ.

2. Проводить операции неполного склеивания до тех пор, пока это возможно.

3. Выполнить все поглощения.

Алгоритм Нельсона построения сокращенной ДНФ. Представим заданную функцию любой КНФ, например, совершенной КНФ. Затем проведем раскрытие скобок и выполним все поглощения.

Пример 4. Рассмотрим функцию, заданную табл. 1. Построим совершенную КНФ:

.

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

.

Отметим, что сокращенная ДНФ может иметь большее число членов, чем совершенная ДНФ.