Формы логических функций

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

Дизъюнктивная нормальная форма (ДНФ) логической функции представляет собой дизъюнкцию элементарных конъюнкций. Элементарная конъюнкция – это конъюнкция переменных или их отрицаний. Например, F(х₁, х₂, х₃) = х₁ х₂ Ú х₁ х₃ Ú х₂ х₃ – функция, записанная в ДНФ.

Аналогично определяется конъюнктивная нормальная форма. Конъюнктивная нормальная форма (КНФ) логической функции представляет собой конъюнкцию элементарных дизъюнкций. Элементарная дизъюнкция – это дизъюнкция переменных или их отрицаний.

Например, F(х₁, х₂, х₃) = (х₁ Ú х₂) (х₁ Ú х₃) (х₁Ú х₂ Úх₃).

Совершенная дизъюнктивная нормальная форма (СДНФ) – это ДНФ, каждая конъюнкция которой содержит все переменные в прямом или инверсном виде.

Например, F(х₁, х₂, х₃) = х₁ х₂ х₃Ú х₁ х₂ х₃ Ú х₁ х₂ х₃.

Аналогично определяется совершенная конъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма(СКНФ) – это КНФ, каждая дизъюнкция которой содержит все переменные в прямом или инверсном виде.

Например, F(х₁, х₂, х₃) = (х₁ & х₂Ú х₃) (х₁ Ú х₂ Ú х₃) (х₁Ú х₂ Úх₃).

Любая логическая функция имеет только одну совершенную ДНФ или КНФ. Совершенные формы логической функции могут быть записаны по таблице истинности.

При записи СДНФ по таблице истинности каждому набору значений переменных, на котором функция равна 1, соответствует конъюнкция всех переменных функции. Если значение переменной в наборе равно 1, то переменная входит в конъюнкцию в прямом виде, иначе – в инверсном. Дизъюнкция всех полученных конъюнкций образует СДНФ.

При записи СКНФ каждому набору значений переменных, на котором функция равна 0, соответствует дизъюнкция всех переменных функции. Если значение переменной в наборе равно 0, то переменная входит в дизъюнкцию в прямом виде, иначе – в инверсном. Конъюнкция всех полученных дизъюнкций образует СКНФ.

Пример. Пусть логическая функция трех переменных описана следующей таблицей истинности (таблица 2.3).

Таблица 2.3.

Значения переменных	Значения функции
a	b	c	F(abc)

Тогда функция будет записана в СДНФ в следующим виде:

СКНФ этой функции будет иметь следующий вид:

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

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