Нормальные формы булевых функций

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

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

Элементарную конъюнкцию (дизъюнкцию) называют также конъюнктивным (дизъюнктивным) термом.

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

Примерами термов являются: _.  

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

Рангом терма называется количество букв входящих в него.

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

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

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

Пример 2.1. При n = 4 конъюктивный терм  принимает значение равное единице на наборе 1010, а дизъюнктивный терм  принимает значение равное нулю на наборе 1101.

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

Замечания:

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

2. С помощью канонических форм любую булеву функцию можно представить в булевом базисе.

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

4. Правило перехода от табличной формы задания булевой функции к аналитической:

а) в таблице истинности выделяются все наборы аргументов, при которых функция равна единице (нулю);

б) для каждого из этих наборов составляют конституенты единицы (нуля);

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

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

 

Пример 2.2.  Получить канонические формы для функции   y = x₁ Å x₂.

Составим таблицу истинности заданной функции:

x1	x2	y	Конституенты единицы	Конституенты нуля
0	0	0	-
0	1	1		-
1	0	1		-
1	1	0	-

КДНФ - каноническая дизъюнктивная нормальная форма:

;

ККНФ - каноническая конъюнктивная нормальная форма:

.

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

Существует другой способ получения ККНФ:

    а) составляется КДНФ, но не для самой булевой функции, а для ее отрицания;

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

 

2.4. Числовая и символическая формыпредставления

Булевых функций

 

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

Пример 2.3. Функция от трех переменных задана в числовой форме:  

От числовой формы легко перейти к КДНФ путем замены каждого из наборов в перечислении конституентой единицы.

.

Аналогично можно перейти к ККНФ:

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

Пример 2.4.  f ³(Х)=x₁Å x₂Å x₃=  - символическая форма булевой функции.

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

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

Пример 2.5. Преобразовать  аналитическое выражение заданной булевой функции к нормальной форме:

 

Замечания:

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

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

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

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

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

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

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

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

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

Приведенные рассуждения справедливы и для КНФ.

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

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

, где P - неполный конъюнктивный терм (ранг этого терма меньше n ), а x_i - недостающий в терме аргумент.

 

Пример 2.6.  Привести ДНФ заданной функции к КДНФ:

 

 

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

 - числовая форма функции.

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

 

Пример 2.7. Привести ДНФ заданной функции к ККНФ:

 

 - числовая форма функции.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: