Изменения

Перейти к: навигация, поиск

0-1 принцип

6 байт добавлено, 18:26, 31 мая 2012
м
Доказательство 0-1 принципа
{{Лемма
| statement =
Пусть <tex> f: A \rightarrow B </tex> - монотонная. Тогда <tex> \forall a_1, a_2 \in A: f(\min(a_1, a_2)) = \min(f(a_1), f(a_2)) </tex>.
| proof =
Не теряя общности, предположим что <tex> a_1 \le a_2 </tex>. Тогда <tex> f(\min(a_1, a_2)) = f(a_1) </tex>. Также, по монотонности, <tex> f(a_1) \le f(a_2) </tex>. Тогда <tex> \min(f(a_1), f(a_2)) = f(a_1) </tex>. То есть,
1, x \ge b_i
\end{cases}
</tex> . Очевидно, она монотонная. Заметим, что <tex> f(b_i) = 1 </tex>, а <tex> f(b_{i + 1}) = 0 </tex>, то есть <tex> f(b) </tex>, или <tex> f(N(a)) </tex> - не отсортирована. Так как <tex> f </tex> и <tex> N </tex> коммутируют, <tex> N(f(a)) </tex> - также не отсортирована. Но по предположению теоремы, все последовательности из нулей и единиц сеть сортировать умеет, то есть такой последовательности <tex> a </tex> не найдется, то есть сеть компараторов является сортирующей.
}}
222
правки

Навигация