Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

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

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




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

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

Для ξ = (ξ12,…,ξn)∈{0,1}n пусть C(ξ) = ((C1(ξ),C2(ξ), …, Cn(ξ)).

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

Ci(ξ) = ξi⋅fi(ξ),

где

f1(ξ)=C1(1,ξ2,…,ξn), f2(ξ)=C21,1,…,ξn), …, fn(ξ)=Cn12,…,1).

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

f(ξ)=(f1(ξ),f2(ξ),…,fn(ξ)).

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

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

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

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

Функция выбора задается следующей таблицей: ξ C(ξ) ξ C(ξ)
       
       
       
       
       
       
       
       

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

f1(ξ)=1; C1(ξ)=ξ1 1.

Функция f2(ξ)=C21,1,ξ34) принимает значение 0 только на одном наборе (1,1,0,0); имеем:

f2(ξ) = ξ1’∨ξ3∨ξ4; C2(ξ)= ξ2 1’∨ξ3∨ξ4).

Функция f3(ξ)=C312,1,ξ4) принимает значение 1 на четырех наборах (0,0,1,0), (0,0,1,1), (0,1,1,1), (1,0,1,1). Записав ее в виде ДНФ, получаем:

f3(ξ) = ξ1’ξ2’∨ξ1’ξ2ξ4∨ξ1ξ2’ξ4; C3(ξ)= ξ31’ξ2’∨ξ1’ξ2ξ4∨ξ1ξ2’ξ4).

Функция f4(ξ)=C4123,1) принимает значение 1 только на одном наборе (0,0,0,1); имеем:

f4(ξ) = ξ1’∨ξ2’∨ξ3’; C4(ξ)= ξ4 1’∨ξ2’∨ξ3’).

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

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

C ↔ f = (f1,f2,…,fn)

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






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных