Функционально полные системы булевых функций

Аналитическое представление булевых функций.

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

Конституента 1 - функция f(x₁, x₂,... x_n) принимающая значение 1 только на единственном наборе.

Конституента 1 записывается как логическое произведение n различных булевых переменных, некоторые из них могут быть с отрицаниями. Например, х₁х₂х₃х₄ - элементарное логическое произведение, являющееся конституентой еденицы переменных х₁,х₂,х₃,х₄ принимает значение 1 на единственном наборе 1001. Понятно, что на остальных 15 наборах эта конституента единицы равна нулю.
Если вспомнить, что дизъюнкция равна 1, когда хотя бы одна из переменных принимает значение 1, то можно легко выразить любую булеву функцию как дизъюнкцию конституент единицы, соответствующих тем наборам, на которых функция равна 1. Эта форма и есть СДНФ.

Другая известная форма носит название совершенной конъюнктивной нормальной формы (СКНФ). Она строится аналогично СДНФ.

Конституента 0 -функция f(x₁, x₂,... x_n) принимающая значение 0 только на единственном наборе

Конституента нуля записывается в виде элементарной дизъюнкции всех переменных. Каждому набору соответствует своя конституента 0. Например, набору 0110 переменных х₁х₂х₃х₄ соответствует конституента нуля х₁ v х₂ v х₃ v х₄. СКНФ представляется как конъюнкция конституент нуля, соответствующих нулевым наборам функции."

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

Функционально полной системой булевых функций (ФПСБФ) называется совокупность таких булевых функций (f₁, f₂,... f_k), что произвольная булева функция f может быть записана в виде формулы через функции этой совокупности

Дата добавления: 2014-01-20