Минимизация функций. Метод минимизации по картам Карно

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

Дизъюнктивные нормальные формы

Введём понятие степени булевой переменной. Будем считать, что x ¹= x, x⁰ =` x.

Из определения следует, что х ^a=1, если х = a, и х^a =0, если х ¹ a. В справедливости этого можно убедиться простым перебором значений.

Конъюнкция x1 ^a1 x2 ^a2 ...xn ^an называется элементарной, если в ней каждая переменная встречается не более одного раза.

Рангом элементарной конъюнкции называется число букв, образующих эту конъюнкцию.

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

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

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

Дизъюнктивная нормальная форма, содержащая наименьшее число букв x_i ^{a i} по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется минимальной ДНФ (МДНФ).

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

Любую функцию можно представить в виде СДНФи это представление единственно, так как оно однозначно сопоставляется таблице истинности функции.

Пример. Найдём разложение функции f =(a Å b)® ` ac по переменной а:
F=a×f(a=1) Ú `a×f (a=0) =a ×((1 Å b) ® 0)Ú `a× ((0 Å b)® c) =a× (`b®0)Ú` a (b®c). Здесь мы учли, что (1Å х)= `х, (0 Å х)= х. Если ещё учесть, что (х®0) =`х, что следует из таблицы истинности импликации, то получим окончательную формулу для функции f = a×b Ú` a× (b®c).

Таблица 1.5
х	у	х®у

Пример. Представим функцию импликации в виде СДНФ, для чего запишем её табличное представление (табл.1.5). Здесь в множестве Т 1 три набора 000, 001 и 111, поэтому в СДНФ будет три конъюнкции х ® у =` х ×` у Ú` х × у Ú х×у

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

Любая функция алгебры логики может быть записана в виде СДНФ. То, что запись в СДНФ часто является неэкономной, видно из примера.

Пример 1. Пусть задана СДНФ

` x <sub>2</sub> (x <sub>1</sub>, x <sub>2</sub>, x <sub>3</sub>)= x <sub>1</sub> x <sub>2</sub> x <sub>3</sub>Ú x <sub>1</sub> x <sub>2</sub>` x ₃ Ú x ₁` x <sub>2</sub> x <sub>3</sub>Ú x <sub>1</sub>` x ₂` x <sub>3</sub> Ú` x ₁ x ₂ x ₃.

Преобразуем эту СДНФ. Добавим еще один конъюнктивный член x₁x₂x₃. Это добавление не меняет данной функции, так как x Ú x = x,

f (x ₁, x ₂, x ₃)= x ₁ x ₂ x ₃Ú x ₁ x ₂` x <sub>3</sub>Ú x <sub>1</sub>` x ₂ x ₃Ú x ₁` x <sub>2</sub>` x ₃Ú x ₁ x ₂ x ₃Ú` x ₁ x ₂ x ₃.

Преобразуем это выражение, используя равенства: a ` b Ú ab = a (операция склеивания) и a × b Ú a = a, a × b Ú` a = b Ú` a (операция поглощения).

Получим:

f (x ₁, x ₂, x ₃)= x ₁ x ₂(x ₃Ú` x <sub>3</sub>)Ú x <sub>1</sub>` x ₂(x ₃Ú` x <sub>3</sub>)Ú x <sub>2</sub> x <sub>3</sub>(x <sub>1</sub>Ú` x ₁)= x ₁ x ₂Ú x ₁` x ₂Ú x ₂ x ₃.

Аналогично предыдущему делаем дальнейшие преобразования:

f (x ₁, x ₂,х₃)= x ₁(x ₂Ú` x ₂)Ú x ₂ x ₃= x ₁Ú x ₂ x ₃.

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

Данный метод минимизации применим для функций с числом переменных не более 6 и удобен для ручной минимизации, когда человек видит те комбинации, которые можно объединить вместе. Рассмотрим его на конкретном примере.

Пример 2. Рассмотрим функцию

f ₁(x ₁, x ₂, x ₃)= x ₁ x ₂ x ₃Ú x ₁ x ₂` x <sub>3</sub>Ú x <sub>1</sub>` x ₂ x ₃Ú x ₁` x <sub>2</sub>` x ₃Ú` x ₁ x ₂ x ₃.

Множество переменных разобьем на две группы. Одной группе сопоставим строки таблицы, второй — столбцы, так чтобы каждой клетке соответствовала комбинация переменных из этих групп. Карта Карно для нее имеет вид табл. 1.6.

Таблица 1.6
x1x2/x3
00
01		15
11	12	11
10	14	13

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

Для нашего случая 0 0 ® 0 1®1 1 ®10 (при каждом последующем переходе изменяется только подчеркнутый символ). Аналогично именуются столбцы таблицы.

Заполнение карты производится по таблице соответствия исходной функции. В примере конъюнкции x₁x₂x₃ соответствует клетка 11/1, а x₁x₂`x₃ клетка 11/0 и т.д. В данной таблице каждая единица имеет порядковый индекс, который соответствует порядковому номеру данной компоненты в исходной функции (расстановка этих индексов совершенно не обязательна и здесь приведена для лучшего понимания).

Для минимизации необходимо попарно “склеить” рядом стоящие единицы, имеющие хотя бы одну общую компоненту. При этом надо стремиться “склеить” в один набор как можно больше клеток. В данном примере мы можем “склеить” 11,12,13,14 вместе. Это запишется как x₁, так как содержимое всех этих клеток зависит только от x₁ и не меняется при изменении x₂ или x₃. На следующем шаге склеим 11 и 15. В результате получим x₂x₃. Рассуждения аналогичны: при изменении x₁ изменения ячеек с 11 и 15 не происходит.

Результирующей минимальной записью исходной функции будет

f(x₁,x₂,x₃)=x₁Úx₂x₃.

Пример 3. Минимизируем функцию пяти переменных:

f ₂(x ₁, x ₂, x ₃, x 4, x 5)= x ₁` x <sub>2</sub>` x ₃` x 4Ú x <sub>1</sub>` x ₂` x <sub>3</sub> x 4Ú` x ₁ x ₂ x ₃ x 4Ú` x <sub>2</sub> x <sub>1</sub>` x 5.

Карта Карно для нее приведена в табл.1.7.

Таблица 1.7

x 4 x 5 \x 1 x 2 x 3
							14	11,4
								11
			13					12
			13				14	12,4

Если в конъюнкции переменная не присутствует, то 1 ставится во все клетки, удовлетворяющие присутствующим переменным. Так, например, первой конъюнкции соответствует две клетки: 100/00 и 100/01.

Минимизация приводит к формуле

f ₂(x ₁, x ₂, x ₃, x ₄, x ₅)= x ₁` x <sub>2</sub>` x ₃Ú` x <sub>1</sub> x <sub>2</sub> x <sub>3</sub> x <sub>4</sub>Ú` x ₂ x ₁` x ₅.

Пример 4. Рассмотрим функцию

f ₃(x ₁, x ₂, x ₃)= x ₁ x ₂` x <sub>3</sub>Ú x <sub>1</sub>` x ₂ x ₃Ú x ₁` x <sub>2</sub>` x ₃Ú` x <sub>1</sub> x <sub>2</sub> x <sub>3</sub>Ú` x ₁ x ₂` x <sub>3</sub>Ú` x ₁` x ₂ x ₃.

Таблица 1.8
x 1 x 2/ x 3

По карте Карно табл.1.8 видно, что для данной функции существует две минимальных формы:

f (x ₁, x ₂, x ₃)=` x <sub>1</sub> x <sub>3</sub>Ú x <sub>2</sub>` x ₃Ú x ₁` x ₂,

f (x ₁, x ₂, x ₃)=` x <sub>1</sub> x <sub>2</sub>Ú` x ₂ x ₃Ú x ₁` x ₃.

Дата добавления: 2014-01-07