![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Минимизация булевых функций в классе ДНФ
Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза. Пример 6.1. Формула Формула φ(x 1, x 2, …, xn) называется импликантой формулы ψ(x 1, x 2, …, xn), если φ — элементарное произведение и φ ∧ ψ ~ φ , т. е. для соответствующих формулам φ и ψ функций Дизъюнкция всех простых импликант данной формулы (функции) называется сокращенной ДНФ . Теорема 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), и требуемая импликанта имеет вид ![]() Определение простых импликант функции сводится к нахождению всех k -кубов, которые не содержатся в кубах более высокого порядка. После нахождения простых импликант задача построения минимальной ДНФ сводится к изучению матрицы Квайна. При наглядном размещении простых импликант в карте Карно удается непосредственно находить минимальную ДНФ, выбирая те простые импликанты, которые покрывают все единицы и имеют наименьшее возможное число вхождений переменных. Так, минимальной ДНФ для функции, изображенной на рис. 6.8, является формула Рис. 6.8 Логические сети Читайте также:
![]() |
Последнее изменение этой страницы: 2016-03-16; Просмотров: 1339; Нарушение авторского права страницы