Вычислительные системы, сети и телекоммуникации. Бильчинская С.Г. - 13 стр.

Синтез комбинационных устройств

Канонические формы представления логических функций
Синтез логического устройства распадается на два основных этапа:
1. Логическую функцию необходимо представить в виде логического
   выражения с использованием некоторого базиса (И, ИЛИ, НЕ);
2. Минимизация логического выражения.
      Приняты две исходные канонические формы представления функций:
• Совершенная дизъюнктивная нормальная форма (СДНФ);
• Совершенная конъюнктивная нормальная форма (СКНФ).
Совершенная дизъюнктивная нормальная форма.
Дизъюнктивная нормальная форма (ДНФ) - форма представления функции,
при которой логическое выражение функции строится в виде дизъюнкции ряда
членов, каждый из которых является простой конъюнкцией аргументов или их
инверсий.
Пример: f ( x1 , x2 , x3 ) = x1 ∨ x2 ⋅ x3 ∨ x1 ⋅ x2 x3 ∨ x2 ⋅ x3
Если в каждом члене ДНФ представлены все аргументы (или их инверсии)
функции, то такая форма называется СДНФ.
Правило записи СДНФ функции, заданной таблицей истинности.
Необходимо записать столько членов в виде конъюнкций всех аргументов,
сколько единиц содержит функция в таблице. Каждая конъюнкция должна
соответствовать определенному набору значений аргументов, обращающему
функцию в единицу, и если в этом наборе значение аргумента равно нулю, то в
конъюнкцию входит инверсия данного аргумента.
      Если исходная функция задана в табличной форме, то СДНФ может
быть получена непосредственно.
                                  x1         0 0 0 0 1 1 1 1
                                  x2         0 0 1 1 0 0 1 1
                                  x3         0 1 0 1 0 1 0 1
                          f ( x1 , x2 , x3 ) 0 0 1 1 0 1 0 1
f ( x1 , x2 , x3 ) = x1 ⋅ x2 ⋅ x3 ∨ x1 ⋅ x2 ⋅ x3 ∨ x1 ⋅ x2 ⋅ x3 ∨ x1 ⋅ x2 ⋅ x3 (*)
Совершенная конъюнктивная нормальная форма
     Конъюнктивная нормальная форма (КНФ) - форма представления
функции, при которой логическое выражение функции строится в виде
конъюнкции ряда членов, каждый из которых является простой дизъюнкции
аргументов или их инверсий.
Пример: f ( x1 , x2 , x3 ) = ( x1 ∨ x2 ∨ x3 ) ⋅ ( x2 ∨ x3 ) ⋅ ( x1 ∨ x2 ∨ x3 )
Если в каждом члене КНФ представлены все аргументы (или их инверсии)
функции, то такая форма называется СКНФ.
Правило записи СКНФ функции, заданной таблицей истинности.
Необходимо записать столько конъюнктивных членов, представляющих собой
дизъюнкции всех аргументов, при скольких наборах значений аргументов
функция равна нулю, и если в наборе значение аргумента равно единице, то в

                                                                                     13