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

Одна и та же логическая функция может быть записана различным образом. Например, функция F( , ) может быть записана следующими эквивалентными выражениями:

F ( , ) = + + (1)

F ( , ) = + + (2)

F ( , ) = ( + ). (3)

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

Элементарной называется конъюнкция, в которую входят только переменные и их отрицания.

Например: ; ; ; ; .

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

Например: + ; + ; + + .

В элементарные конъюнкции (дизъюнкции) не могут входить одинаковые переменные, а также переменные с их отрицаниями. Такие дизъюнкции (конъюнкции) должны преобразовываться. При этом они упрощаются, а также превращаются в 0 или 1.

Например: = ; =0; + + = ; + =1.

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

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

Функции выражений (1) и (2) записаны также в ДНФ.

Конъюнктивной нормальной формой (КНФ) называется такая форма, в которой функция представляется в виде конъюнкции элементарных дизъюнкций, например: F = ( + ) ( + + ).

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

F= + + (5)

F= + . (6)

Поэтому среди нормальных форм выделяются такие, в которых функции записываются единственным образом. Их называют совершенными. Применяются совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы (СДНФ и СКНФ). Формы СДНФ и СКНФ имеют две отличительные особенности:

· все элементарные конъюнкции и дизъюнкции имеют одинаковый ранг;

· в элементарные конъюнкции (дизъюнкции) входят все те переменные или их отрицания, от которых зависит функция.

Функция (5) содержит конъюнкции одинакового ранга, но записана в ДНФ, а не в СДНФ. Это объясняется тем, что элементарные конъюнкции не содержат всех тех переменных или их отрицаний, от которых зависит функция.

Функция F( , , ) = + + + записана в СДНФ.

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

1. Правило записи СДНФ функции по таблице истинности:

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

Например, логическая функция задана таблицей истинности, представленной на рис. 9а. Для наборов 3, 5, 6, 7 записываем конъюнкции через пробел: , , , .

В пробелы ставим знак дизъюнкции и получаем функцию в СДНФ, т.е.: F( , , ) = + + + .

а) б)

			F

			F

Рис. 9. Таблицы истинности логических функций

Для задания функции не обязательно всегда вычерчивать таблицу истинности. Можно указать, что функция F( , , ) равна единице, например, на наборах 3, 5, 6, 7.

2. Правило записи СКНФ функции по таблице истинности:

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

Например, пусть логическая функция задана прежней таблицей истинности, представленной на рис. 9а. Для наборов 0, 1, 2, 4 записываем элементарные дизъюнкции:

( + + ) ( + + ) ( + + ) ( + + ).

Дизъюнкции соединяем знаками конъюнкции и получаем функцию в СКНФ:

F( , , )=( + + )( + + )( + + )( + + ).

При построении ЭВМ широко используются компоненты, работа которых описывается функциями, представленными в дизъюнктивных формах. Поэтому целесообразно в дальнейшем рассматривать эти формы логических функций.