Реализация функций Алгебры логики (ФАЛ) на элементах ЭВМ. Способы задания функций. Переход от одних способов задания ФАЛ к другим.Минимизация Методом Квайна Мак-Класски.

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

Функция а/л может быть представлена в виде логического элемента, имеющего N входов и от 1 до N выходов. Первые, обозначающие аргументы функции (входы), имеют название «входного алгоритма». Возможное количество входных комбинаций описывается как «2^N».

Реализация комбинационных схем с помощью функций а/л:

1. Задать функцию, которую хотим реализовать (в виде функций а/л)

2. провести минимизацию функции, используя один из методов (графический – карты карно (диаграммы вейча) или способ квайна-мак-класски)

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

4. Нарисовать схему

Способы представления функций а/л:

А) Табличный способ (таблица истинности).

Функция отображения входных значений на выходные.

С таблицы истинности обычно начинается проектирование устройста.

Б) Запись в виде формулы, используя базисы логической функции.

Базис – совокупность элементарных логических функций, с помощью которой можно выразить любую логическую функцию.

Базисы:

А) И, ИЛИ, НЕ

Б) Штрих Шеффера (И-НЕ)

В) Стрелка Пирса (ИЛИ-НЕ)

Существует 2 формы записи:

а) СДНФ (в ней функция представлена как дизъюнкция элементарных конъюнкций, причём каждый элемент конъюнкции содержит в себе ВСЕ переменные, на которых определена эта функция)

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

Правила перехода от табличной формы к СДНФ:

В таблице истинности выбрать значения, на которых функция принимает значения «1», выписать элементарные конъюнкции, при этом если элемент присутствует как «1»-ца, то она входит в прямом виде, если как «0», то в инверсном. (для СКНФ – наоборот).

Все термы соединены дизъюнкциями.

СДНФ:

F(X1,X2,X3)= nX3X2X3 + X1nX2nX3 + X1X2nX3

СКНФ:

F(X1,X2,X3)= (X1+X2+X3) * (X1+X2+nX3) * (X1+nX2+X3) * (nX1+X2+nX3) * (nX1+nX2+nX3)

Конъюнкция – логическое умножение ( *, &, ^ )

Дизъюнкция – логическое сложение ( +, \/ («стрелка вниз»))

В) Сокращенная запись

СДНФ:

∑ (3,4,6) – там, где функция на выходе равна «1»

СКНФ:

∏ (0,1,2,5,7) - там, где функция на выходе равна «1»

Функция не определена:

X (….) – в скобках указываются номера наборов.

В случае, если необходимо записать в виде базиса не полностью определённую функцию, её доопределяю «1»-ми или «0»-ми (для СДНФ доопределяют «1»-ми, для СКНФ – «0»-ми).

__________________________________________________________________

Минимизация функций основана на правиле склеивания:

A*B + A*nB = A

Методы минимизации:

1) Квайна-Мак-Класски

2) Графический с использованием карт Карно (диаграмм Вейча).

Минимизация Методом Квайна Мак-Класски.

В данном методе расписываются все входящие в функцию элементы по мере возрастания количества «единиц» в терме.

Заметим, что если мы имеем переменную в прямом виде – она преобразуется в единицу, в инверсном – в ноль, отсутствует – в «-».

Т.е. «Х1Х2Х3nX4» равно 1110.

Пример:

f = 0001 v 0011 v 0101 v 0111 v 1110 v 1111.

Сортируем в группы (по количеству единиц в термах).

Далее члены из соседних групп склеиваются, образуя новые группы:

В данном примере также склеиваются снова элементы первой и второй группы (второй таблицы).

В итоге, у нас получилось 3 «группы», которые мы заносим в импликантную матрицу и проверяем минимизацию.

Исходя из получившихся результатов склеивания мы можем уменьшить количество импликант (в данном примере достаточно двух).

0**1 —> nX1X4;

111* —> X1X2X3.