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

Начнем с некоторых общих замечаний относительно монотонных булевых функций.

Булева функция f(ξ₁,ξ₂,…,ξ_n) называется монотонной по первому аргументу, если f(0,ξ₂,…,ξ_n)≤f(1,ξ₂,…,ξ_n) для любого вектора (ξ₁,ξ₂,…,ξ_n), и антимонотонной по первому аргументу, если выполняется противоположное неравенство. Аналогично определяется монотонность и антимонотонность по остальным аргументам. Функция f(ξ₁,ξ₂,…,ξ_n) антимонотонна по ξ₁ в том и только том случае, когда функция f(ξ₁’,ξ₂,…,ξ_n) монотонна по ξ₁. Функция f(ξ₁,ξ₂,…,ξ_n) монотонна, если она монотонна по всем своим аргументам.

Если функция f(ξ₁,ξ₂,…,ξ_n) монотонна по ξ₁, она допускает следующее разложение по переменной ξ₁.

f(ξ₁,ξ₂,…,ξ_n)= f(0,ξ₂,…,ξ_n) ∨ f(1,ξ₂,…,ξ_n)ξ₁.

В справедливости этого тождества несложно убедиться непосредственно, подставив ξ₁=0 и ξ₁=1:

f(0,ξ₂,…,ξ_n)= f(0,ξ₂,…,ξ_n) ∨ f(1,ξ₂,…,ξ_n)⋅0;

f(1,ξ₂,…,ξ_n)= f(0,ξ₂,…,ξ_n) ∨ f(1,ξ₂,…,ξ_n)⋅1

(второе верно в силу монотонности, поскольку f(0,ξ₂,…,ξ_n) ≤ f(1,ξ₂,…,ξ_n)).

Если функция f(ξ₁,ξ₂,…,ξ_n) монотонна еще и по переменной ξ₂, то разложение можно продолжить. В случае, когда функция f(ξ₁,ξ₂,…,ξ_n) монотонна по всем аргументам, последовательно применяя указанное разложение, мы придем к ДНФ функции f(ξ₁,ξ₂,…,ξ_n), не содержащей отрицаний переменной. Если функция f(ξ₁,ξ₂,…,ξ_n) по некоторым переменным монотонна, а по некоторым антимонотонна, ее можно представить в виде ДНФ, в которую первые переменные входят без отрицания, а вторые – только с отрицанием.

В качестве примера рассмотрим так называемы пороговые функции, которые определяются условиями вида

f(ξ₁,ξ₂,…,ξ_n) = 1⇔ k₁ξ₁+k₂ξ₂+…+k_nξ_n ≥ s,

где k₁, k₂, …, k_n, s – действительные коэффициенты. Пороговая функция монотонна по тем переменным, которые входят в сумму с положительным коэффициентом и антимонотонна по тем переменным, которые входят в сумму с отрицательным коэффициентом.

Пример.Пусть f(ξ₁,ξ₂,ξ₃) определяется условием

f(ξ₁,ξ₂,ξ₃)=1 ⇔ 3ξ₁−5ξ₂+ξ₃≥−1.

Тогда

f(ξ₁,ξ₂,ξ₃)= ξ₁ξ₃∨ξ₂’.

Чтобы получить эту формулу, можно выписать СДНФ и провести в ней сокращения, используя законы поглощения.􀀀

Рассмотрим теперь турнирный выбор. Для множества участников (игроков) Ω={1,2,…n} задана турнирная таблица T=(t_ij), в которой клетка t_ij содержит 2, если i победил j; 0, если j победил i; 1, если i и j сыграли вничью. Все клетки t_ii содержат единицы.

Пусть X – некоторое множество участников турнира. По определению турнирного выбора из X отбираются победители, то есть игроки, набравшие максимальное число во встречах с игроками из X. Для i∈X обозначим через l_i(X) разность между числом побед и числом поражений игрока i во встречах с игроками из X. Ясно, что победителями являются те игроки, для которых l_i(X) принимает наибольшее значение. Таким образом,

i∈C(X) ⇔ ∀j∈X l_i(X)≥l_j(X).

Пусть ξ = (ξ₁,ξ₂,…,ξ_n) характеристический вектор множества X и (C₁(ξ),C₂(ξ),…,C_n(ξ)) – характеристический вектор C(X). Для i∈X имеем

l_i(X) = ξ₁⋅(t_i1−1) + ξ₂⋅(t_i2−1) +…+ ξ_n⋅(t_in−1).

Обозначим через g_ij(ξ) пороговую функцию, определенную условием

g_ij(ξ)=1 ⇔ l_i(X)− l_j(X) ≥0,

(результат i не хуже, чем результат j).

Тогда условие попадания в число победителей можно переписать так:

C_i(ξ)=1 ⇔ ξ_i=1 ∧ (ξ_j=0 ∨ l_i(X)− l_j(X) ≥0)

или

C_i(ξ)=ξ_i⋅(ξ₁’ ∨ g_i1(ξ))(ξ₂’ ∨ g_i2(ξ))⋅… (ξ_n’ ∨ g_in(ξ)).

Следовательно, логическое представление функции выбора задается функциями

f_i(ξ)=(ξ₁’ ∨ g_i1(ξ))(ξ₂’ ∨ g_i2(ξ))⋅… (ξ_n’ ∨ g_in(ξ)), i=1,2,…,n,

при том, что ξ_i=1.

Пример. Рассмотрим турнир с пятью участниками:

Имеем

l₁(ξ) = −ξ₂+ξ₃+ξ₄; l₂(ξ) = ξ₁+ξ₄; l₃(ξ) = −ξ₁−ξ₄+ξ₅;

l₄(ξ) = −ξ₁−ξ₂+ξ₃; l₅(ξ) = −ξ₃.

Проведем расчеты для участника 1:

g₁₁(ξ)=1;

g₁₂(ξ)=1 ⇔ −ξ₁−ξ₂+ξ₃≥0; g₁₂(ξ)=ξ₁’∨ξ₂’;

g₁₃(ξ)=1 ⇔ ξ₁−ξ₂+ξ₃+2ξ₄−ξ₅≥0;

g₁₃(ξ)=ξ₁ξ₂’∨ξ₁ξ₃ ∨ξ₁ξ₅’∨ξ₂’∨ξ₄∨ξ₅’;

g₁₄(ξ)=1 ⇔ξ₁+2ξ₂+ξ₄≥0; g₁₄(ξ)=1;

g₁₅(ξ)=1 ⇔ −ξ₂+2ξ₃+ξ₄≥0; g₁₅(ξ)=ξ₂’∨ξ₃∨ξ₄.

Отсюда

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

Раскрыв скобки и проведя упрощения, получаем:

f₁(ξ)=ξ₂’,

откуда

C₁(ξ)=ξ₁ξ₂’.

Это позволяет сделать вывод, что, участник 1 окажется победителем в любом предъявлении, в которое входит он сам, а участник 2 не входит.

Аналогичным образом можно рассчитать остальные четыре компоненты функции выбора.􀀀