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

Пусть n – число элементов множества Ω. Занумеруем варианты числами от 1 до n, и будем обозначать варианты их номерами, полагая, что Ω={1, 2, …, n}.

С учетом предыдущего функцию выбора C можно считать отображением множества {0,1}ⁿ в себя, C:{0,1}ⁿ→{0,1}ⁿ. Так как C(X)⊂X для любого предъявления X, то С(ξ)≤ξ для любого ξ∈{0,1}ⁿ. Обратно, всякая функция C:{0,1}ⁿ→{0,1}ⁿ, С(ξ)≤ξ, является функцией выбора.

Для ξ = (ξ₁,ξ₂,…,ξ_n)∈{0,1}ⁿ пусть C(ξ) = ((C₁(ξ),C₂(ξ), …, C_n(ξ)).

Тогда C_i(ξ)=1 означает, что вариант i попадет в число выбранных из предъявления с характеристическим вектором ξ. Для всех векторов ξ с ξ_i=0 значение C_i(ξ) постоянно и равно 0. Поэтому, по теореме о разложении булевой функции по аргументу, функция C_i(ξ), i=1,2,…,n, имеет вид

C_i(ξ) = ξ_i⋅f_i(ξ),

где

f₁(ξ)=C₁(1,ξ₂,…,ξ_n), f₂(ξ)=C₂(ξ₁,1,…,ξ_n), …, f_n(ξ)=C_n(ξ₁,ξ₂,…,1).

Таким образом, каждой функции выбора C отвечает набор функций f=(f₁,f₂,…,f_n), про который говорят, что он дает логическое представление функции выбора C. Обратно, произвольный набор булевых функций f=(f₁, f₂,…,f_n), в котором функция f_i(ξ) не зависит от ξ_i, i=1,2,…n, однозначно определяет функцию выбора C, для которой составляет ее логическое представление. Логическое представление f=(f₁, f₂,…,f_n) можно рассматривать как отображение :{0,1}ⁿ→{0,1}^т, полагая

f(ξ)=(f₁(ξ),f₂(ξ),…,f_n(ξ)).

Пример.Пусть Ω={1,2,3,4}. Будем считать, что варианты занумерованы в порядке убывания их привлекательности для потребителя: вариант с меньшим номером лучше (предпочтительнее) варианта с большим номером. Выбор осуществляется в соответствии со следующими правилами:

1) потребитель никогда не отказывается от выбора и никогда не выбирает более двух вариантов;

2) при предъявлении двух или трех вариантов потребитель отбрасывает худший вариант.

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

Дадим явные аналитические выражения для функций C_i. Легко видеть, что

f₁(ξ)=1; C₁(ξ)=ξ₁ 1.

Функция f₂(ξ)=C₂(ξ₁,1,ξ₃,ξ₄) принимает значение 0 только на одном наборе (1,1,0,0); имеем:

f₂(ξ) = ξ₁’∨ξ₃∨ξ₄; C₂(ξ)= ξ₂ (ξ₁’∨ξ₃∨ξ₄).

Функция f₃(ξ)=C₃(ξ₁,ξ₂,1,ξ₄) принимает значение 1 на четырех наборах (0,0,1,0), (0,0,1,1), (0,1,1,1), (1,0,1,1). Записав ее в виде ДНФ, получаем:

f₃(ξ) = ξ₁’ξ₂’∨ξ₁’ξ₂ξ₄∨ξ₁ξ₂’ξ₄; C₃(ξ)= ξ₃(ξ₁’ξ₂’∨ξ₁’ξ₂ξ₄∨ξ₁ξ₂’ξ₄).

Функция f₄(ξ)=C₄(ξ₁,ξ₂,ξ₃,1) принимает значение 1 только на одном наборе (0,0,0,1); имеем:

f₄(ξ) = ξ₁’∨ξ₂’∨ξ₃’; C₄(ξ)= ξ₄ (ξ₁’∨ξ₂’∨ξ₃’).

Теорема.Общее число различных функций выбора на множестве вариантов из n элементов равно ()nn122−.

Доказательство. Соответствие функций выбора и их логических представлений

C ↔ f = (f₁,f₂,…,f_n)

является взаимно однозначным. Теперь доказываемое утверждение следует из того, что каждое логическое представление является набором из n булевых функций от n–1 переменной, а общее число булевых функций от n–1 переменной равно 2.􀀀 12−n