рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Рекурсия

Рекурсия - раздел Компьютеры, Фундаментальная и компьютерная алгебра От Аксиом N1-N3 До Знакомых Всем С Начальной Школы Операций Сложения И Умноже...

От аксиом N1-N3 до знакомых всем с начальной школы операций сложения и умножения натуральных чисел, сравнения натуральных чисел между собой и свойств вида "от перемены мест слагаемых сумма не изменится" большая дистанция. Зачастую доказательство таких утверждений есть формальные проверки с многократным использованием метода математической индукции. Принципиальный момент – рекурсивные определения сложения и затем умножения натуральных чисел. В общем виде рекурсия -- это метод построения или вычисления, когда каждый следующий объект строится (вычисляется) на основе предыдущих. Абстрактно рекурсия в простейшем виде описывается отображением F:M → M и начальным значением . Далее объект вычисляется как в предположении, что уже известен.

Метод математической индукции показывает, что тогда мы получаем отображение или последовательность объектов из множества M. Сама формула называется рекуррентной и ее использование возможно лишь, если явно задано начальный объект .

Определим сложение посредством рекуррентной формулы m+(n+1):=(m+n)+1. Например,

 

Умножение определяется явным заданием формулы умножения на единицу: m⋅ 1:=m, а также рекуррентной формулы m⋅ (n+1):=m⋅ n+m. В частности, единица есть нейтральный элемент операции умножения. Далее доказываются фундаментальные свойства операций сложения и умножения

Ассоциативность: для любых чисел выполняются равенства

 

 

 

Здесь специально вместо выражения "для любых натуральных чисел" употребляется выражение "для любых чисел"; эти фундаментальные свойства верны для всех чисел.

Докажем, например, ассоциативность сложения индукцией по k. Для k=1 получаем формулу (m+n)+1=m+(n+1). Это равенство справедливо для всех натуральных чисел m и n по определению сложения. Допустим теперь, что равенство (m+n)+k=m+(n+k) для некоторого k и при любых m и n установлено и теперь нам надо проверить аналогично равенство для k+1:

 

Здесь во втором равенстве использовано предположение индукции, а в остальных использовано определение сложения. Ассоциативность сложения доказана в силу принципа математической индукции (см. аксиому N3). Аналогично проверяются остальные свойства сложения и умножения.

Присоединим к множеству натуральных чисел элемент ноль 0, обладающий свойствами

 

для любого n∈ ℕ . Получаем множество всех целых неотрицательных целых чисел, для которых перечисленные выше свойства ассоциативности, коммутативности и дистрибутивности сохраняются.

– Конец работы –

Эта тема принадлежит разделу:

Фундаментальная и компьютерная алгебра

Введение... Курс Фундаментальная и компьютерная алгебра предназначен для студентов специальностей Математика Прикладная...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Рекурсия

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Н.И.Дубровин
Спасское Городище 2012 Оглавление Введение. 4 Список обозначений и терминов. 5 1 Немного о БЕЙСИКе. 6 2 Наивная теория множеств. 9

Немного о БЕЙСИКе
  В математике имеют дело с такими объектами как числа разной природы (натуральные, целые, рациональные, действительные, комплексные), многочлены одной и нескольких переменных, матриц

Наивная теория множеств.
  Математический текст состоит из определений и утверждений. Некоторые утверждения в зависимости от важности и отношения к другим утверждениям называются одним из следующих терминов:

Декартовы произведения
Упорядоченная пара, или просто пара элементов это одна из фундаментальных конструкций в математики. Представлять её можно как полочку с двумя местами -- первым и вторым. Очень часто в математике не

Натуральные числа
  Числа {1,2,3,… }, которые можно получить из единицы операцией сложения, называют натуральными и обозначают ℕ. Аксиоматическое описание натуральных чисел может быть таким (см.

Порядок на множестве натуральных чисел
На множестве имеется отношение линейного порядка. Скажем, что n<m, если найдется натуральное число k такое, что n+k=m. Отношение n≤ m тогда получается из отношения строгого неравенства про

Делимость натуральных чисел
Операция деления не всегда возможна в области натуральных чисел. Это дает нам право ввести отношение делимости: скажем, что число n делит число m, если m=nk для какого-либо подходящего k∈ 

Делимость целых чисел
  Обозначим через -- кольцо целых чисел. Термин «кольцо» означает, что мы имеем дело с множеством R, на котором заданы две операции – сложение и умножение, подчиняющиеся известным пра

Алгоритм Евклида
Дана пара целых чисел (m,n). Считаем n остатком с номером 1. Первый шаг алгоритма Евклида – делим m на n с остатком, а далее делим остаток на вновь получившийся остаток, покуда этот вновь получивши

Матричная трактовка алгоритма Евклида
Придадим матричную трактовку алгоритму Евклида (о матрицах см. следующий параграф). Перепишем последовательность делений с остатком в матричном виде:   Подставляя в каждое по

Элементы логики
Математики имеют дело с объектами, такими как, например, -- числа, -- функции, -- матрицы, -- прямые на плоскости и т.д., а также имеют дело с высказываниями. Высказывание есть некоторое повествова

Высказывательные формы
Будет ли выражение высказыванием? Нет, эта запись есть высказывательная форма от одной переменной . Если вместо переменной подставлять допустимые значения, то получаем различные высказывания, котор

Матричная алгебра
  Матричная алгебра над кольцом R (R – кольцо целых чисел, поле рациональных чисел, поле вещественных чисел) – наиболее широко используемая алгебраическая система с множеством операци

Определители
Определитель квадратной матрицы A есть ее числовая характеристика, обозначаемая или . Начнем с определителей матриц малых размерностей 1,2,3: ОПРЕДЕЛЕНИЕ. Пу

Линейные преобразования плоскости
Известно, что любое преобразование плоскости ϕ, сохраняющее расстояния, есть либо параллельный перенос на вектор , либо поворот вокруг точки О на угол α, либо симметрия относительно прямо

Комплексные числа
  В этом параграфе изучается лишь одно поле -- поле комплексных чисел ℂ . С геометрической точки зрения оно представляет из себя плоскость, а с алгебраической точки зрения в это

Конструкция поля комплексных чисел.
Мы фактически уже построили поле комплексных чисел в предыдущем параграфе. В силу исключительной важности поля комплексных чисел приведем его непосредственную конструкцию. Рассмотрим пространство с

Сопряжение комплексных чисел
Поле комплексных чисел доставляет нам новое свойство -- наличие нетождественного непрерывного автоморфизма (изоморфизма на себя). Комплексное число называется сопряженным к , а отоб

Тригонометрическая форма записи комплексных чисел
Изобразим комплексное число вектором. Длина этого вектора, т.е. величина называется модулем комплексного числа и обозначается . Величину назовем нормой числа , иногда удобнее пользоваться е

Комплексная экспонента
Правило (2) параграфа дает нам право определить экспоненту чисто мнимого числа:   Действительно, таким образом определенная функция обладает следующими свойствами: &

Решение квадратных уравнений.
Линейный многочлен при всегда имеет корень . Квадратный трехчлен уже не всегда имеет корни над полем действительных чисел. Пусть – квадратный трехчлен над полем комплексных чисел ( ). Обоз

Основная теорема алгебры комплексных чисел
Поле называется алгебраически замкнутым, если любой многочлен над этим полем, не равный константе, имеет хотя бы один корень. Из теоремы Безу сразу следует, что над таким полем любой неконстантный

ТЕОРЕМА об отношении эквивалентности
Пусть “ ” – отношение эквивалентности на множестве М. Для элемента обзначим через класс эквивалентности. Тогда множество М разбивается в объединение классов эквивалентности; каждый элемент из М при

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги