Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции 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. Карта строится в виде матрицы размера 2nkна 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, …, δnk), и требуемая импликанта имеет вид — переменная, соответствующая значению δj.

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

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

Рис. 6.8

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






Читайте также:

  1. Алгоритмы записи произвольной функции, заданной в таблице в виде с помощью элементарных функций.
  2. Анатомо-морфологическая база высших психических функций.
  3. В зависимости от расположения верхних передних зубов при II классе аномалии Э. Энгль выделил два подкласса.
  4. Взаимосвязь общих и конкретных функций менеджмента
  5. Возрастные изменения психических функций человека в трудоспособном периоде онтогенеза
  6. ВОПРОС 11. Характеристика основных функций социАЛЬНО-культурной деятельности
  7. Вычисление выражений с использованием стандартных функций
  8. Гуморальная регуляция висцеральных функций.
  9. Дифференциальное исчисление функций нескольких переменных
  10. Дуги механизмов определяют способы реализации функций
  11. Зависимость уровня осуществления функций защиты от количества расходуемых ресурсов.
  12. Изменение стоимости объекта при придании добавочных функций


Последнее изменение этой страницы: 2016-03-16; Просмотров: 197; Нарушение авторского права страницы


lektsia.com 2007 - 2017 год. Все права принадлежат их авторам! (0.088 с.) Главная | Обратная связь