Алгебраические системы — страница 5

  • Просмотров 8633
  • Скачиваний 1024
  • Размер файла 1780
    Кб

 удовлетворяет условиям аксиомы индукции. Т.к. - истина, то . Если , то - истина и по второму условию теоремы индук­ции - истина. Поэтому . Множество  удовлетворяет условиям аксиомы индукции. Поэтому . Обозначение. Множество целых чисел  состоит из натуральных чисел, нуля и чи­сел противоположных натуральным. Для   обозначим  . Теорема 2. (обобщение принципа полной математической индук­ции). Пусть - одноместный

предикат на , где , который удовлетворяет условиям: 1. - истина. 2.  (- истина ®- истина). Тогда предикат  тождественно истинен на . Теорема 3. (сильная форма принципа полной математической ин­дукции). Пусть - одноместный предикат на , который удовлетво­ряет условиям: 1. - истина. 2.  (- истины® - истина). Тогда предикат  тождественно истинен на . Теорема 4. (обобщение сильной формы принципа полной математической индукции).

Пусть - одноместный предикат на , где , который удовлетворяет условиям: 1. - истина. 2.  (- истины ® - истина). Тогда предикат  тождественно истинен на . Числа Фибоначчи Определение. Числа Фибоначчи , для , определяются рекуррентно (1)   , ; (2)   для всех . Из определения чисел Фибоначчи следует, что , , , , , , , , , , . Для вычисления чисел Фибоначчи справедлива следующая формула Бине (3)  , . Из (1) и (2) следует, что индукционное

предположение, при доказа­тельстве формулы Бине, должно предполагать справедливость (3) для  и , и значит, начальные условия должны требовать выполнение (3) для  и .  Поэтому доказательство формулы Бине может проводиться по следующей теореме математической индукции. Теорема 5. Пусть - одноместный предикат на , который удовлетворяет условиям: 1. - истины. 2.  (- истины ® - истина). Тогда предикат  тождественно истинен на .

  Проведём доказательство формулы Бине по теореме 5. Для  и  равенство (3) принимает вид , . Очевидно, что эти равенства верны. Предположим, что равенство (3) истинно для чисел  и . Тогда из (2) следует, что . После простых преобразований правой части получим, что   По индукции формула Бине доказана. Теорема 6. Пусть - одноместный предикат на , который удовлетво­ряет условиям: 1. - истина. 2.  (- истины ® - истина). Тогда

предикат  тождественно истинен на .   п.3. Основное свойство ассоциативных операций. Теорема. Если бинарная операция  на множестве  ассоциативна, то   при любой расстановке скобок, задаю­щих порядок выполнения операций  в произведении  значения произведений будут одинаковыми, то есть значение произведения не зави­сит от способа расстановки скобок. Доказательство. Проводится индукцией по . Проверим