Полные системы булевых функций (стр. 5 из 6)

.

Решение. Отметим на модели куба элементарные конъюнкции: первой конъюнкции соответствует вершина 6, второй – вершина 5, третьей – вершина 8, четвертой – вершина 2 (рис 8). Таким образом, множество N_f –построено. Ни одна грань не отмечена полностью, поэтому переходим к шагу 4 алгоритма.

Рис. 8

Вершины 5 и 6 принадлежат одному ребру

, вершины 6 и 8 – ребру , следовательно, минимизированная форма имеет вид:

.

Пример 16. Минимизировать функцию f(X₁,X₂,X₃), заданную табл. 5.

Таблица 5

Х1	1	1	1	0	1	0	0	0
Х2	1	1	0	1	0	1	0	0
Х3	1	0	1	1	0	0	1	0
f(X1,X2,X3)	1	1	1	1	1	1	0	0

Решение. Построим модель куба, соответствующего этой функции (рис.9).

Рис. 9

Грани (1, 2, 3, 4) соответствует X₂, грани (2, 4, 6, 8) – Х₁, следовательно, минимизированная форма имеет вид

.

Отметим, что при n = 3 геометрический метод минимизации булевых функций аналогичен минимизации с помощью прямоугольной таблицы, называемой, минимизирующей картой (картой Карно).

6. Минимизация булевой функции с помощью карты Карно

Карта Карно представляет собой таблицу для задания логических функций в СДНФ. Например, для функции, заданной табл. 5, карта Карно представлена в табл. 6.

Расположение клеток в таблице позволяет легко определить склеивающиеся между собой члены, так как каждой клетке карты Карно соответствует вершина куба. Допускающие склеивание конституенты располагаются в соседних ячейках по строкам и столбцам, или в виде квадратов и им соответствует одна импликанта, ранг которой меньше, чем ранги склеиваемых конституент. Заметим, что соседними считаются не только рядом стоящие ячейки, но и ячейки, находящиеся на противоположных концах любого столбца и любой строки.

Таблица 6

Так, склеивая конституенты, расположенные во второй и третьей строках табл. 6, получаем импликанту – – X₂, а конституентам двух последних строк соответствует импликанта Х₁ – –. Следовательно, минимальная форма заданной булевой функции имеет вид (см. пример 16)

.

Пример 17. Минимизировать с помощью карты Карно функцию f(X₁, Х₂, Χ₃), заданную табл. 4.

Решение. Построим для

минимизирующую карту (табл. 7)

Таблица 7

Объединим соседние клетки, соответствующие единичным значениям функции f, в максимальные интервалы, как показано в табл. 7. Сопоставим каждому максимальному интервалу импликанты Χ₁ и

. Следовательно, минимальная форма имеет вид:

.

Пример 18. Минимизировать булеву функцию

.

Решение. Используя таблицы истинности, построим для заданной функции f карту Карно (табл. 8).

Объединим соседние клетки, соответствующие единичному значению функции, в максимальные интервалы, как показано в табл. 8. Следовательно, минимальная форма данной функции имеет вид

Таблица 8

.

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

Пример 19. Пусть функция f(X₁, X₂, Х₃, Х₄) задана та6л. 9. Построить сокращенную ДНФ.

Решение. Максимальные интервалы, соединяющие клетки, соответствующие единичным значениям функции f, выбираются так, как показано в табл. 9. Сопоставляя им простые импликанты, получим сокращенную ДΗΦ.

Таблица 9

7. Построение оптимальных контактно-релейных схем

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

1. По заданной схеме составить соответствующую ей булеву функцию.

2. Привести эту функцию к ДНФ.

3. Минимизировать записанную в ДНФ булеву функцию одним из описанных выше способов

4. Построить релейно-контактную схему, соответствующую минимальной ДНФ.

Приведем примеры.

Пример 20. Построить оптимальную релейно-контактную схему, эквивалентную схеме на рис. l0.

Решение.

1. Составим по этой схеме булеву функцию

.

2. Эта функция записана в ДНФ, поэтому предварительных ее преобразований не требуется.

3. Склеиваем первый член с третьим:

.

4. Строим релейно-контактную схему, соответствующую полученной функции:

В упрощенной схеме вместо 9 контактов используются только 5.

Пример 21. Построить оптимальную релейно-контактную схему, эквивалентную схеме на рис. 12.

Решение.

1. Заданной схеме соответствует булева функция

.

2. Представим эту функцию в ДНФ

.

3. Склеивая второй член с четвертым, а затем проводя операцию поглощения, получим

.

4. Строим оптимальную релейно-контактную схему (рис. 13).

Упражнения

1. Минимизировать с помощью карт Карно следующие булевы функции:

а)

;

б)

;

в)

;

г)

;

д)

;

е)

.

2. Минимизировать булевы функции методом Квайна:

а)

;

б)

;

в)

;

г)

.

3. Построить для булевой функции

модель куба и минимизировать её. Функция f задана табл. 10, 11, 12.

Таблица 10

X1	X2	X3	f(X1,X2,X3)
0	0	0	1
0	0	1	0
0	1	0	1
1	0	0	0
0	1	1	1
1	0	1	1
1	1	0	0
1	1	1	1

Таблица 11