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

Некоторые функции от трех переменных.

Функция - сумма по модулю 2 и исключающее ИЛИ являются эквивалентными только для двух аргументов.

_n

Общее разнообразие функций от n аргументов равно 2²

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

Пример:

f³(x)=x₁Åx₂Åx₃=

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

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

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

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

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

Примеры конъюнктивных термов:

_ _

x₁, x₂, x₁x₃, x₂x₄x₅ (терм)

___ _

x₁x₂, x₁x₂x₃ (не терм)

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

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

Каноническая нормальная форма.

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

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

Пример: _ _

n=4 x₁x₂x₃x₄ (1010)=1

_ _ _

x₁Úx₂Úx₃Úx₄=0

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

Пример получения канонических форм:

y=x₁Åx₂

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

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

_ _

y=x₁x₂Úx₁x₂

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

_ _

y=(x₁Úx₂)(x₁Úx₂)

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

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

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

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

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

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

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

Пояснение: при составлении конституент единицы (нуля) используют следующее правило:

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

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

_ _ _ _ _ _ _ _ _ _

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

6) Принципиально существует другой способ получения ККНФ:

а) составляется КДНФ, но не для самой, а для ее отрицания.

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

_ _ _ = ------------ ----- ---- _ _

y=x₁x₂Úx₁x₂, y=y=x₁x₂Úx₁x₂=x₁x₂ x₁x₂=( x₁Úx₂)(x₁Úx₂)