Изменения
→Доказательство 0-1 принципа
{{ Определение
| definition =
Функция <tex> f: A \rightarrow B </tex> называется '''монотонной''', если <tex> \forall a_1, a_2 \in A : a_1 \le leqslant a_2 \Rightarrow f(a_1) \le leqslant f(a_2) </tex>
}}
Пусть <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 leqslant a_2 </tex>. Тогда <tex> f(\min(a_1, a_2)) = f(a_1) </tex>. Также, по монотонности, <tex> f(a_1) \le leqslant f(a_2) </tex>. Тогда <tex> \min(f(a_1), f(a_2)) = f(a_1) </tex>. То есть,
<tex> f(\min(a_1, a_2)) = \min(f(a_1), f(a_2)) = f(a_1) </tex>. Такие же рассуждения можно провести для случая <tex> a_2 < a_1 </tex>.
| statement = Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая
| proof =
Рассмотрим сеть <tex> N </tex>, сортирующую в возрастающем порядке: <tex> a_0 \le leqslant a_1 \le leqslant \dots \le leqslant a_{n-1} </tex>.
Предположим, что есть последовательность <tex> a </tex>, которую сеть <tex> N </tex> не сортирует. Тогда после пропуска <tex> a </tex> через сеть <tex> N </tex>, получим последовательность <tex> b </tex>, в которой найдется индекс <tex> i </tex> такой, что <tex> b_i > b_{i + 1} </tex>.
