Приведение произвольных нормальных форм Булевой функции к каноническим

Преобразование произвольной аналитической формы Булевой функции в нормальную

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

Пример:

_ _ _ _ _ _

y=f⁴(x)=(x₁x₂Úx₂x₃)(x₁|x₄)=(x₁x₂Úx₂x₃)(x₁x₄)=(x₁x₂Úx₂x₃)(x₁Úx₄)=

_ _ _ _ _ _ _ _ _ _

=x₁x₂Úx₁x₂x₄Úx₁x₂x₃Úx₂x₃x₄₌x₁x₂Úx₁x₂x₃Úx₂x₃x₄=x₁(x₂Úx₂x₃)Úx₂x₃x₄=

_ _ _ _

=x₁(x₂Úx₃) Úx₂x₃x₄=x₁x₂Úx₁x₃Úx₂x₃x₄ (КДНФ)

Замечания:

1) В общем случае любая Булева функция может иметь несколько КДНФ, отличающихся либо количеством термов, либо количеством букв в этих термах.

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

3) По сравнению со схемой, построенной по ДНФ, схема, построенная по скобочной форме (*), является более предпочтительной т.к. при одном и том же числе логических элементов (И, ИЛИ) содержат меньшее число входов (9 вместо 10).

Задача преобразования нормальной формы Булевой функции в скобочной форме называют задачей фактеризации.

4) Сущность конструктивного подхода при получении ДНФ состоит в следуюшем:

а) преобразование операций не-Булевого базиса к операциям Булевого базиса (см. последние строки таблицы)

б) снятие отрицаний над выражениями с применением законов двойственности

в) раскрытие скобок с применением дистрибутивного закона

г) упрощения выражения с применением закона поглощения

Для приведения произвольной ДНФ к КНФ необходимо использовать правило дизъюнктивного развертывания применительно к каждому из неполных конъюнктивных термов.

_ _

P=P(x_iÚx_i)=Px_iÚPx_i, где P-неполный конъюнктивный терм (ранг этого терма

меньше n), а x_i - недостающий в терме аргумент.

Пример:

_ _ _ _ _ _ _ _ _ _

y=x₁Úx₂x₃(ДНФ)=x₁(x₂Úx₂)(x₃Úx₃) Úx₂x₃(x₁Úx₁)=x₁x₂x₃Ú x₁x₂x₃Ú

_ _ _ _ _ _ _ _ _

Úx₁x₂x₃Úx₁x₂x₃Ú x₁x₂x₃Ú x₁x₂x₃ (КДНФ)

Замечание:

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

y= (0,1,2,3,5)=f³

Преобразование КНФ к ККНФ реализуется путем применения правила конъюнктивного развертывания к каждому неполному дизъюнктивному терму.

_ _

P=PÚx_ix_i=(PÚx_i)(PÚx_i)

_ _ _ _ _ _ _ _ _ _

y=x₁Úx₂x₃(ДНФ)=(x₁Úx₂)(x₁Úx₃)(КНФ)=(x₁Úx₂Úx₃x₃)(x₁Úx₃Úx₂x₂)=

_ _ _ _ _ _ _ _

=(x₁Úx₂Úx₃)(x₁Úx₂Úx₃)(x₁Úx₂Úx₃)(x₁Úx₂Úx₃)(ККНФ)

y= (4,6,7)