Пример 1. Найти минимальную дизъюнктивную форму функции, заданной таблицей истинности (табл. 3).

Таблица 3

Таблица истинности функции Y=f(X₁,X₂,X₃)

X1	Х2	Х3	Y
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Эта функция интересна тем, что имеет несколько минимальных форм. По данным таблицы запишем аналитическое выражение:

Штриховыми линиями в этом выражении отмечены пары конъюнкций, к которым можно применить операцию склеивания типа . Особенно это видно при использовании диаграммы Вейча, в которой “склеиваемые” конъюнкции находятся по соседству друг с другом. Диаграмма Вейча просто по-другому интерпретирует таблицу истинности (табл. 4).

Таблица 4.

Диаграмма Вейча функции Y

 

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

В результате применения операций склеивания и поглощения можно получить другое аналитическое выражение:

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

Из приведенных зависимостей видно, что только функции у1 и у4 являются минимальными формами функций, так как они содержат наименьшее число конъюнкций и имеют минимальный ранг этих конъюнкций.

Минимизация “вручную” возможна только для функций, зависящих от 4-5 переменных, так как трудоемкость переборов растет в квадратичной зависимости от числа переменных. Применение мощных ЭВМ для этих Целей позволяет расширить границы до п= 12-15. Если при этом учесть, что функции могут быть частично определены (значения функций на некоторых наборах переменных можно определять произвольно), а также что иногда приходится решать задачи совместной минимизации систем ЛФ, то минимизация ЛФ становится сложной инженерной, практической и научной проблемой.

4.Техническая интерпретация логических функций

По логическим выражениям проектируются схемы ЭВМ. При этом следует придерживаться следующей последовательности действий.

1. Словесное описание работы схемы.

2. Формализация словесного описания.

3. Запись функций в дизъюнктивной (конъюнктивной) совершенной нормальной форме по таблицам истинности.

4. Минимизация логических зависимостей с целью их упрощения.

5. Представление полученных выражений в выбранном логически полном базисе элементарных функций.

6. Построение схемы устройства.

7. Проверка работоспособности полученной схемы. Покажем взаимосвязь перечисленных этапов на примере.

Пример 2. Спроектировать схему, фиксирующую появление “неправильной” тетрады в двоично-десятичном представлении чисел.

1. Каждая тетрада двоично-десятичного представления числа содержит десятичные цифры 0-9, что соответствует двоичным числам 0000-1001. Значения тетрады, соответствующие двоичным числам 1010-1111 (шестнадцатеричные цифры A-F), не должны появляться при представлении десятичных чисел.

2. Составим таблицу истинности функции (табл. 8), которая принимает значения, равные единице, при появлении “неправильных” тетрад. Разряды тетрады обозначим переменнымих, у, z, u.

Т а б л и ц а 5

Таблица истинности функции F

3. Исходная совершенная дизъюнктивная нормальная форма записывается

4. Эта форма функции допускает упрощение, что видно по диаграмме Вейча (табл. 9). Этот же результат может быть получен аналитически.

Т а б л и ц а 6

Диаграмма Вейча для функции F

5. Минимальная форма функции F в логически полном базисе {&, v,  } будет иметь вид:

Для представления этой же схемы в другом полном базисе, например {&}, воспользуемся правилом де Моргана:

6. По полученным зависимостям можно построить схемы фиксации “неправильных” тетрад (рис.2).

7. Проверить работоспособность построенных схем можно путем задания различных комбинаций переменных х, у, z, и и определения реакции на выходе схемы F.

Рис. 2. Схема фиксации неправильных тетрад: а - схема в базисе (, &, V), б - схема в базисе (&).

Пример 3.

Спроектировать схему устройства для обработки результатов решения студентами задач №1 и №2. При этом результатом будем считать решение одной из задач (минимальный результат) или решение двух задач.

1. Обозначим функцию решения y=f(x₁;x₂) и представим структуру разрабатываемого устройства:

y=f(x₁;x₂)

X₁

Y

X₂

1. Составим таблицу истинности для поставленной задачи.

X1	X2	Y
0	0	0
0	1	1
1	0	1
1	1	1

1. Запишем аналитическое выражение для функции Y в совершенной дизъюнктивной нормальной форме (СДНФ) по условию задачи:

Y= ⌐x₁ x₂ Vx₁⌐x₂ Vx₁x₂

1. Выполним минимизацию, используя закон склеивания для элементов 2 и 3. В результате имеем

Y =x₁x₂Vx₁

На втором шаге минимизации используем закон свёртки. В результате имеем

Y=x₂Vx₁

Полученная функция минимальна и реализуется в виде простой схемы «ИЛИ» (логического сложения).

X₁

X₂

ИЛИ

Y