Изменения

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

Теорема Хватала

744 байта добавлено, 07:03, 20 ноября 2011
Нет описания правки
|statement=
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.
|proof=
# Пусть <tex> d'_k > k </tex>. <tex> (\mbox{false} \rightarrow \mbox{true}) = (\mbox{false} \rightarrow \mbox{true}) = \mbox{true}. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
# Пусть <tex> d'_k \leq k, \mbox{ } d'_{n - k} \geq d_{n - k} \geq n - k </tex>. <tex> (\mbox{true} \rightarrow \mbox{true}) = \mbox{true} </tex>. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
Значит, импликация <tex> (*) </tex> выполняется и для последовательности <tex> d' </tex>, q.e.d.
}}
272
правки

Навигация