Выбор подмножества импликант с минимальным числом букв

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

В табл. 2.1 колонки с номерами 1, 6, 12, 14 и 15 имеют единст- венный крестик. Соответствующие этим крестикам импликанты отмечены в табл. 2.1 символом «Ö». Этим же символом отмечены внизу табл. 2.1 все колонки, перекрытые выбранными импликанта- ми.

После этого найдем импликанты, перекрывающие остальные колонки. В рассматриваемом примере такой выбор осуществляется тривиально, так как неотмеченными остаются колонки 10, 11, ко-

торые перекрываются одной импликантой ABD F 1 F 3. Данная им-

пликанта и перекрываемые ею колонки отмечены в табл. 2.1 сим- волом «*».

Набор отмеченных простых импликант, перекрывающих совме- стно все колонки импликантной матрицы, будет полным подмно- жеством дизъюнктивных членов заданной совокупности логиче- ских функций.

 

Таблица 2.1

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

Импликанта

Конституента

ABCD

ABCD

ABCD

ABCD

ABCD

ABCD

ABCD

ABCD

ABCD

ABCD

ABCD

F 1

F 1

F 1

F 1

F 1

F 2

F 1

F 2

F 3

F 1

F 3

F 2

F 3

F 3

F 3

F 3

ABCD F 1 F 2 F 3

+

+

+

Ö ABC F 2 F 3

+

+

+

+

* ABD F 1 F 3

+

+

+

+

Ö BCD F 1 F 2

+

+

+

+

Ö BD F 3

+

+

+

+

AB F 3

+

+

+

+

Ö BD F 1

+

+

+

+

CD F 1

+

+

+

+

AD F 1

+

+

+

+

Ö

Ö

Ö

Ö

Ö

Ö

Ö

Ö

Ö

*

*

Ö

Ö

Ö

Ö

Ö

Запись логических функций в ДНФ

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

F 1 (A, B, C, D) = BD Ú BCD Ú ABD,⎫

⎪

F 2(A, B, C, D) = BCD Ú ABC, ⎬

⎭

F 3(A, B, C, D) = BD Ú ABD. ⎪

(2.7)

На рис. 2.6 приведена реализация системы функций (2.7) на эле- ментах И-НЕ.

Рис. 2.6. Реализация многовыходной комбинационной схемы