Простая индукция
Cтраница 1
 |
Структура данных для цепочек. [1] |
Простая индукция по числу прохождений внешнего цикла в программе на рис. 3.2 показывает, что после i прохождений список ОЧЕРЕДЬ содержит цепочки длины, не меньшей / max-i 1, и они расположены в соответствии с их компонентами с номерами от / тах-i 1 до / тах. Поэтому рассматриваемый алгоритм лексикографически упорядочивает свой вход. [2]
Простая индукция показывает теперь, что алгебра X кофибрантна. [3]
Простой индукцией по длине формулы можно показать, что определения ограниченной и неограниченной переменных в формуле непротиворечивы. [4]
Поясним эту концепцию в терминах простой индукции над целыми числами, которая, вероятно, давно знакома большинству читателей. [5]
Очевидно, что теорема 2 с помощью простой индукции непосредственно распространяется на любое число слагаемых. [6]
Пункт ( g) дает обещанное выше обобщение простой индукции. Если 5 - множество положительных целых чисел, то мы получаем простейший случай математической индукции, разобранный в тексте. Заметим, что требуется доказывать утверждения Р ( 1), так как Р ( у) обязательно справедливо ( тривиальным образом) для всех таких у. Мы видим, что во многих случаях доказательство утверждения Р ( 1) упрощается. [7]
Как только что упоминалось, расширение теоремы ЗЗС с двух матроидов до k матроидов осуществляется простой индукцией. [8]
Применяя этот метод к матрицам порядка п 2, разбитым на четыре 2k - l x 2k - l - блока и используя простую индукцию по &, нетрудно показать, что их можно перемножить, применив 7k умножений и 6 ( 7 - 4) сложений. Пусть теперь п - любое произвольно большое натуральное число. [9]
Ясно, что при доказательстве аддитивности можно ограничиться случаем, когда Е состоит из двух элементов, поскольку к общему случаю легко перейти простой индукцией. [10]
Допустим А ( 0) & Vx [ Vy ( у х э А ( у)) э А ( х) ], выведем Vy ( у х э А ( у)) простой индукцией по х и затем получим А ( х) с помощью V-удал. [11]
Надо доказать, что разбиение л грубо, насколько возможно. Простая индукция по числу блоков, разбиваемых в строках 9, 10, показывает, что каждое такое разбиение, сделанное алгоритмом, необходимо для совместимости. Оставляем эту индукцию в качестве упражнения. [12]
Другими словами, если обе функциональные зависимости, из которых составляется данная сложная функция, непрерывны, то и сама эта сложная функция непрерывна. Эта теорема простой индукцией легко распространяется на случай сложных функций, определяемых с помощью трех и более звеньев: если в каждом звене зависимость непрерывна, то и получаемая сложная функция будет непрерывной. Было бы очень тяжелой задачей в каждом таком случае особо доказывать непрерывность встретившейся нам комбинации элементарных функций. [13]
При доказательстве какой-либо теоремы Т ( у) по индукции может оказаться, что случай Т ( у) этой теоремы зависит не только от непосредственно предшествующего случая Т у), но и от одного или нескольких предыдущих случаев. Ее можно свести к простой индукции, если доказать сначала путем простой индукцаи лемму ( s) s vT ( s), после чего теорема получается подстановкой sy ( ср. [14]
С другой стороны, ясно, что MT [ ( w) есть 0 и, следовательно, эта сумма прямая, что и доказывает нашу теорему. Отметим, что это доказательство с заменой простой индукции трансфинитной остается справедливым и в бесконечном случае. [15]
Страницы: 1 2