Числовое представление Булевых функций

Разнообразие двоичных алгебр

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

В принципе любую из базовых функций можно отождествить соответствующей операцией и на основе совокупности этих операций построить двоичные алгебры, отличные от Булевой. К наиболее распространенным двоичным алгебрам относятся: алгебра Жигалкина (Å, &); алгебра Вебба (Пирса) (¯); алгебра Шеффера ( | ). В каждой из этих алгебр действуют собственные законы. Естественно существуют взаимно однозначные переходы от операций одного базиса к операциям другого.

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

f³(x)= (0,2,6,7) - от этой числовой формы легко перейти к КДНФ путем замены каждого из наборов в перечислении конституенты единицы.

_ _ _ _ _ _ _ _ _ _ _

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

f³(x)= &(1,3,4,5)

_ _ _ _ _ _

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