1302
правки
Изменения
м
→Доказательство 0-1 принципа
{{Лемма
| statement =
Пусть <tex> f: A \rightarrow B </tex> - монотонная, а <tex> N </tex> - какая-то сеть компараторов. Тогда <tex> N </tex> и <tex> f </tex> коммутируют: , то есть <tex> N(f(a)) = f(N(a)) </tex> - другими словами, неважно, применить сначала <tex> f </tex> к <tex> a </tex> и пропустить через сеть <tex> N </tex>, или пропустить через сеть <tex> N </tex> последовательность <tex> a </tex>, а потом применить монотонную функцию <tex> f </tex>.
| proof =
Рассмотрим произвольный компаратор <tex> [i: j] </tex>, сортирующий элементы <tex> a_i </tex> и <tex> a_j </tex>. Применим его к последовательности <tex> f(a) </tex> и рассмотрим элемент с индексом <tex> i </tex>.
