Конъюнктивную нормальную форму можно получить и другим путем. Для этого используются рассуждения и методы, дуальные рассмотренным по отношению к дизъюнктивным нормальным формам. На многомерном кубе ищется покрытие множества вершин для нулевых значений функции, а на карте Карно - покрытие нулевых клеток. Рассматриваемый пример иллюстрируется на рис. 221, а и б. Соответствующая конъюнктивная нормальная форма y = (x1 ∨ x2)(x̅1 ∨ x̅2 ∨ x3) реализуется соответствующей схемой. Комплекс кубов этой функции и его дополнение имеют вид:
; 
,
а их покрытия
; 
.
Покрытию С соответствует дизъюнктивная нормальная форма для отрицания функции y̅ = x1x2x̅3 ∨ x̅1x̅2, откуда можно получить приведенное выше выражение функции в конъюнктивной нормальной форме.
10. Многовыходные схемы. Схемы, реализующие несколько функций, можно представить как простое объединение схем, реализующих
- 547 -
каждую функцию отдельно. Но такой путь, как правило, является неэкономичным. Часто бывает целесообразно преобразовать совокупность данных функций к такому виду, чтобы реализующие их схемы содержали общие части, а схема с многими выходами представляла собой единое целое.
Задача сводится к выбору для каждой функции такого покрытия, которое включало бы возможно большее число s-кубов, содержащихся в покрытиях других функций. Этому требованию удовлетворяют, например, покрытия для трех функций, которому соответствует трехвыходная схема. Если бы для функции y3 было выбрано другое покрытие, то схема получилась бы менее экономичной.
В этом параграфе описаны различные методы представления булевых функций применительно к задаче минимизации. При небольшом числе переменных эта задача обозрима, и ее можно решить простым перебором различных вариантов. Для функции многих переменных разработаны формальные методы минимизации, которые рассматриваются в следующем параграфе.
5. Минимизация булевых функций
1. Постановка задачи. Минимизация схемы в булевом базисе сводится к поиску минимальной дизъюнктивной формы, которой соответствует минимальное покрытие. Общее число букв, входящих в нормальную форму, выражается ценой покрытия 
, где qs - число s-кубов, образующих покрытие даннойфункции от n переменных. Используются и другие определения цены покрытия, например с’ = с + q, где q - общее число всех кубов покрытия. Во всех случаях минимальное покрытие характеризуется наименьшим значением его цены.
Обычно задача минимизации решается в два шага. Сначала ищут сокращенное покрытие, которое включает все s-кубы максимальной размерности, но не содержит ни одного куба, покрывающегося каким-либо кубом этого покрытия. Соответствующую дизъюнктивную нормальную форму называют сокращенной, а ее минитермы - простыми импликантами. Для данной функции сокращенное покрытие является единственным, но оно может быть избыточным вследствие того, что некоторые из кубов покрываются совокупностями других кубов.
На втором шаге осуществляется переходот сокращенной к тупиковым дизъюнктивным' нормальным формам, из которых выбираются минимальные формы. Тупиковые формы образуются путем исключения из сокращенного покрытия всех избыточных кубов, без которых оставшаяся совокупность кубов еще образует покрытие данной функции, но при дальнейшем исключении любого из кубов она уже не покрывает множества всех вершин, соответствующих единичным значениям функции, т. е. перестает быть покрытием.
Куб сокращенного покрытия, который покрывает вершины данной функции, не покрываемые никакими другими кубами, не может оказаться избыточным и всегда войдет в минимальное покрытие. Такой куб, как и соответствующая ему импликанта, называют экстремалью (существенной импликантой), а покрываемые им вершины—отмеченными вершинами. Множество экстремалей