Минимизация функций алгебры логики

Идемпотентность

Дистрибутивность

Коммутативность

Свойства алгебры Жегалкина

x Å y = y Å x

x & y = y & x

x & (y Å z)= x & y Å z & x

x Å x = 0

x Å 0 = x

x & x = x

Для алгебры Жегалкина характерно

= x Å 1

x Ú y = x & y Å x Å y

Определение. Формула, имеющая вид полинома со сложением по модулю 2 называется полиномом Жегалкина для функции алгебры логики.

Замечание. От булевой формулы всегда можно перейти к полиному Жегалкина.

Работа автомата может быть полностью описана с помощью следующей системы функций алгебры логики [7]:

y₁= f₁ (x₁... x_n)

y₂= f₂ (x₁... x_n)

...

y_m= f_m (x₁... x_n)

Здесь Pi = (X1, X2,...,Xn); Qj = (y1, y2,...,ym) - соответственно входное и выходное слово. Работа автомата может быть задана либо в виде конечных таблиц, либо в виде аналитической записи функций f_i.

Проблема полноты системы функций эквивалентна проблеме выбора стандартного набора элементов, из которого будет строиться автомат, при этом все функции f_i должны быть выражены через базисные функции. Уменьшение числа функций в базисе приводит к уменьшению стандартных элементов, на которых строится схема, однако, при этом увеличивается общее число элементов схемы. Возникает задача о “простейшем” представлении логических функций через систему базисных функций. Для этого используют методы минимизации:

n метод вынесения за скобки;

n метод неопределенных коэффициентов;

n метод с использованием карт Карно;

n метод Мак - Класки;

n метод Блэка.

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

Для работы с картой необходимо по таблице истинности составить СДНФ, затем для каждой элементарной конъюнкции проставить 1 в соответствующие клетки карты. Затем единицы объединяются таким образом, чтобы минимизировалось число логических сложений, умножений или отрицаний, что важно для экономного конструирования ЭВМ.

Для двух переменных: Для трех переменных:

a a

c

b

b

Для четырех переменных:

a

c

cd

d

b

Пример. Для логической функции заданной таблицей

x1	x2	x3	f

построить карту Карно и на ее основе минимизировать функцию.

Решение. Построим карту согласно описанным выше правилам.

x₁

1 1 f = x1 v x2 & x3

x_{2 1 1 1}

x₃

Рассмотрим пример представления простейшей функции картой Карно

a

c 1 1

c 1 1 d

f = b

1 1 d

1 1

b

Рассмотрим построение логической схемы для функции вида:

f1 = V2 & V4 v V3 & ØV1 & ØV2 v ØV3 & ØV4 & V1.

V1

V2

V3

V4

& & & & &

& &

&

&

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