Минимизация булевых функций в классе ДНФ

⇐ ПредыдущаяСтр 15 из 27Следующая ⇒

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

Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза.

Пример 6.1. Формула — элементарное произведение, а формула элементарным произведением не является.

Формула φ (x 1, x 2, …, xn) называется импликантой формулы ψ (x 1, x 2, …, xn), если φ — элементарное произведение и φ ∧ ψ ~ φ , т. е. для соответствующих формулам φ и ψ функций справедливо неравенство Формула φ (x 1, x 2, …, xn) называется импликантой функции f , если φ — импликанта совершенной ДНФ, представляющей функцию f . Импликанта формулы ψ называется простой, если после отбрасывания любой литеры из φ не получается формула, являющаяся импликантой формулы ψ.

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

Теорема 6.1. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ.

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

Заметим, что представление функции в виде тупиковой ДНФ в общем случае неоднозначно.

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

Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие три операции:

— операция полного склеивания — ;

— операция неполного склеивания — ;

— операция элементарного поглощения — .

Теорема 6.2 (теорема Квайна). Если исходя из совершенной ДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант.

В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения очевидным образом можно преобразовать для нахождения минимальных конъюнктивных нормальных форм (МКНФ).

Карты Карно

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

Карта Карно для п переменных служит эффективным средством иллюстративного представления n -куба. Она содержит 2nячеек, каждая из которых соответствует одной из 2nвозможных комбинаций значений п логических переменных x 1, x 2, …, xn. Карта строится в виде матрицы размера 2n – kна 2kтак, что ее столбцы соответствуют значениям переменных x 1, x 2, …, xk, строки — значениям переменных xk + 1 , … xn, а соседние ячейки (как по вертикали, так и по горизонтали) отличаются только значением одной переменной (рис. 6.5).

Рис. 6.5

На рис. 6.6 приведены карты Карно для функций трех и четырех переменных соответственно. В этих картах все ячейки, отмеченные скобкой xi(по строке и столбцу), представляют входные комбинации с xi= 1, а в неотмеченных строках и столбцах ячейки соответствуют комбинациям с xi= 0 (см. рис. 6.6a , на котором разными способами изображена одна и та же карта). Например, на рис. 6.6а ячейка а соответствует набору 001 значений переменных x 1, x 2, x 3. Отметим, что для каждой функции может быть построено несколько различных карт. На рис. 6.6б изображены две карты Карно для функции четырех переменных. Первая карта соответствует разбиению переменных {{x l, x 2}, {x 3, x 4}}, а вторая — {{х 1}, {х 2, х 3, х 4}}.

Рис. 6.6

У каждой вершины n -куба есть ровно п смежных с ней вершин, т. е. вершин, отличающихся от нее только одной координатой. Поскольку в карте Карно каждая ячейка может иметь не более четырех ячеек, соседних по строке или столбцу, для представления точек, отличающихся только на одну координату, необходимо использовать и более удаленные ячейки. Например, точки b и c на рис. 6.6б отличаются только значением переменной x 3, т. е. являются смежными.

Булева функция может быть представлена на карте Карно выделением 1-ячеек (т. е. ячеек, в которых функция принимает значение, равное 1). Подразумевается, что необозначенные ячейки соответствуют 0-точкам.

На рис. 6.7 изображена карта, представляющая булеву функцию f (x , y , z ), для которой f (0, 0, 0) = f (1, 1, 0) = f (1, 1, 1) = f (1, 0, 1) = 0, f (0, 1, 0) = f (1, 0, 0) = f (0, 0, 1) = f (0, 1, 1) = 1.

Рис. 6.7

Для построения импликант берутся всевозможные наборы 1-ячеек, образующих вершины некоторого k -куба (т. е. 2kточек таких, что пары соседних отличаются ровно одной координатой). Совпадающие координаты образуют набор (δ 1, …, δ n – k), и требуемая импликанта имеет вид — переменная, соответствующая значению δ j.

Определение простых импликант функции сводится к нахождению всех k -кубов, которые не содержатся в кубах более высокого порядка.

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

Рис. 6.8

Логические сети

⇐ Предыдущая 10 11 12 13 141516 17 18 19 Следующая ⇒