Какой буквой обозначаются действительные числа. Обозначение, запись и изображение числовых множеств

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

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

Натуральные числа образовались с развитием счета, а рациональные с потребностью управлять частями целого, то вещественные числа (действительные) используются для измерений непрерывных величин. Т.о., расширение запаса чисел, которые рассматриваются, привело к множеству вещественных чисел, которое кроме рациональных чисел состоит из других элементов, называемых иррациональные числа .

Множество действительных чисел (обозначается R ) - это множества рациональных и иррациональных чисел собранные вместе.

Действительные числа делят на рациональные и иррациональные .

Множество вещественных чисел обозначают и зачастую называют вещественной или числовой прямой . Вещественные числа состоят из простых объектов: целых и рациональных чисел .

Число, которое возможно записать как отношение, где m - целое число, а n - натуральное число, является рациональным числом .

Всякое рациональное число легко представить как конечную дробь либо бесконечную периодическую десятичную дробь.

Пример ,

Бесконечная десятичная дробь , это десятичная дробь, у которой после запятой есть бесконечное число цифр.

Числа, которые нельзя представить в виде , являются иррациональными числами .

Пример:

Всякое иррациональное число легко представить как бесконечную непериодическую десятичную дробь.

Пример ,

Рациональные и иррациональные числа создают множество действительных чисел. Всем действительным числам соответствует одна точка координатной прямой, которая называется числовая прямая .

Для числовых множеств используются обозначения:

• N - множество натуральных чисел;
• Z - множество целых чисел;
• Q - множество рациональных чисел;
• R - множество действительных чисел.

Теория бесконечных десятичных дробей.

Вещественное число определяется как бесконечная десятичная дробь , т.е.:

±a 0 ,a 1 a 2 …a n …

где ± есть один из символов + или −, знак числа,

a 0 — целое положительное число,

a 1 ,a 2 ,…a n ,… — последовательность десятичных знаков, т.е. элементов числового множества {0,1,…9}.

Бесконечную десятичную дробь можно объяснить как число, которое на числовой прямой находится между рациональными точками типа:

±a 0 ,a 1 a 2 …a n и ±(a 0 ,a 1 a 2 …a n +10 −n) для всех n=0,1,2,…

Сравнение вещественных чисел как бесконечных десятичных дробей происходит поразрядно. Например , предположим даны 2 положительны числа:

α =+a 0 ,a 1 a 2 …a n …

β =+b 0 ,b 1 b 2 …b n …

Если a 0 0, то α<β ; если a 0 >b 0 то α>β . Когда a 0 =b 0 переходим к сравнению следующего разряда. И т.д. Когда α≠β , значит после конечного количества шагов встретится первый разряд n , такой что a n ≠b n . Если a n n , то α<β ; если a n >b n то α>β .

Но при этом нудно обратить внимание на то, что число a 0 ,a 1 a 2 …a n (9)=a 0 ,a 1 a 2 …a n +10 −n . Поэтому если запись одного из сравниваемых чисел, начиная с некоторого разряда это периодическая десятичная дробь, у которой в периоде стоит 9, то её нужно заменить на эквивалентную запись, с нулем в периоде.

Арифметические операции с бесконечными десятичными дробями это непрерывное продолжение соответствующих операций с рациональными числами. Например , суммой вещественных чисел α и β является вещественное число α+β , которое удовлетворяет таким условиям:

∀ a′,a′′,b′,b′′ ∈ Q(a′ ⩽ α ⩽ a′′) ∧ (b′ ⩽ β ⩽ b′′) ⇒ (a′+b′ ⩽ α + β ⩽ a′′+b′′)

Аналогично определяет операция умножения бесконечных десятичных дробей.

Число - абстракция, используемая для количественной характеристики объектов. Числа возникли еще в первобытном обществе в связи с потребностью людей считать предметы. С течением времени по мере развития науки число превратилось в важнейшее математическое понятие.

Для решения задач и доказательства различных теорем необходимо понимать, какие бывают виды чисел. Основные виды чисел включают в себя: натуральные числа, целые числа, рациональные числа, действительные числа.

Натуральные числа – это числа, получаемые при естественном счёте предметов, а вернее при их нумерации («первый», «второй», «третий»...). Множество натуральных чисел обозначается латинской буквой N (можно запомнить, опираясь на английское слово natural). Можно сказать, что N ={1,2,3,....}

Целые числа – это числа из множества {0, 1, -1, 2, -2, ....}. Это множество состоит из трех частей – натуральные числа, отрицательные целые числа (противоположные натуральным числам) и число 0 (нуль). Целые числа обозначаются латинской буквой Z . Можно сказать, чтоZ ={1,2,3,....}.

Рациональные числа – это числа, представимые в виде дроби, где m - целое число, а n - натуральное число. Для обозначения рациональных чисел используется латинская буква Q . Все натуральные и целые числа – рациональные.

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

1. Системы счисления.

Система счисления – способ наименования и записи чисел. В зависимости от способа изображения чисел разделяется на позиционные-десятичная и непозиционные-римская.

В ПК используют 2ичную, 8ричную и 16ричную системы счисления.

Отличия:запись числа в 16ной системе счисленич по сравнению с другой записью значительно короче, т.е. требует меньшего количества разрядности.

В позиционной системе счисления каждая цифра сохраняет свое постоянное значение независимо от занимаемой позиции в числе. В позиционной системе счисления каждая цифра определяет не только свое значение, но зависит от того положения, которое она занимает в числе. Каждая система счисления характеризуется основанием. Основание- это количество различных цифр, которые используются для записи чисел в данной системе счисления. Основание показывает во сколько раз изменяется значение одной и той же цифры при переходе на соседнюю позицию. В компьютере используется 2-система счисления. Основанием системы может быть любое число. Арифметические дей-ия над числами в любой позиции выполняются по правилам аналогичным 10 системе счисления. Для 2 системы счисления используется двоичная арифметика, которая реализуется в компьютере для выполнения арифметических вычислений.

Сложение двоичных чисел:0+0=1;0+1=1;1+0=1;1+1=10

Вычитание:0-0=0;1-0=1;1-1=0;10-1=1

Умножение:0*0=0;0*1=0;1*0=0;1*1=1

В компьютере широко применяется 8 система счисления и 16 система счисления. Они используются для сокращения записи двоичных чисел

2. Понятие множества.

Понятие «множество» является фундаментальным понятием математики и не имеет определения. Природа порождения любого множества разнообразна, в частности, окружающие предметы, живая природа и др.

Определение 1 : Объекты, из которых образовано множество, называются элементами данного множества . Для обозначения множества используют заглавные буквы латинского алфавита: например X, Y, Z, а в фигурных скобках через запятую выписывают его элементы строчными буквами, например: {x,y,z}.

Пример обозначения множества и его элементов:

X = {x 1 , x 2 ,…, x n } – множество, состоящее из n элементов. Если элемент x принадлежит множеству X, то следует записать: xÎX, иначе элемент x не принадлежит множеству X, что записывается: xÏX. Элементами абстрактного множества могут быть, например, числа, функции, буквы, фигуры и т.д. В математике в любом разделе используется понятие множества. В частности, можно привести некоторые конкретные множества вещественных чисел. Множество вещественных чисел х, удовлетворяющих неравенствам:

· а ≤ x ≤ b называется сегментом и обозначается ;

· а ≤ x < b или а < x ≤ b называется полусегментом и обозначается: ;

· а < x < b называется интервалом и обозначается (a,b).

Определение 2 : Множество, имеющее конечное число элементов, называется конечным. Пример. X = {x 1 , x 2 , x 3 }.

Определение 3 : Множество называется бесконечным , если оно состоит из бесконечного числа элементов. Например, множество всех вещественных чисел бесконечно. Пример записи. X = {x 1 , x 2 , ...}.

Определение 4 : Множество, в котором нет ни одного элемента, называют пустым множеством и обозначают символом Æ.

Характеристикой множества является понятие мощности. Мощность – это количество его элементов. Множество Y={y 1 , y 2 ,...} имеет ту же мощность, что и множество X={x 1 , x 2 ,...}, если существует взаимно однозначное соответствие y= f(x) между элементами этих множеств. Такие множества имеют одинаковую мощность или равномощны. Пустое множество имеет нулевую мощность.

3. Способы задания множеств.

Считают, что множество задано своими элементами, т.е. множество задано, если о любом объекте можно сказать: принадлежит он этому множеству или не принадлежит. Задавать множество можно следующими способами:

1) Если множество конечно, то его можно задать перечислением всех его элементов. Так, если множество А состоит из элементов 2, 5, 7, 12 , то пишут А = {2, 5, 7, 12}. Количество элементовмножества А равно 4 , пишут n(А) = 4.

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

2) Множество можно задать указанием характеристического свойства его элементов. Характеристическое свойство – это такое свойство, которым обладает каждый элемент, принадлежащий множеству, и не обладает ни один элемент, не принадлежащий ему. Рассмотрим, например, множество Х двузначных чисел: свойство, которым обладает каждый элемент данного множества, – «быть двузначным числом». Это характеристическое свойство дает возможность решать о том, принадлежит какой-либо объект множеству Х или не принадлежит. Например, число 45 содержится в данном множестве, т.к. оно двузначное, а число 4 множеству Х не принадлежит, т.к. оно однозначное и не является двузначным. Случается, что одно и то же множество можно задать, указав различные характеристические свойства его элементов. Например, множество квадратов можно задать как множество прямоугольников с равными сторонами и как множество ромбов с прямым углом.

В тех случаях, когда характеристическое свойство элементов множества можно представить в символической форме, возможна соответствующая запись. Если множество В состоит из всех натуральных чисел, меньших 10, то пишут В = {x N| x <10}.

Второй способ – более общий и позволяет задавать как конечные, так и бесконечные множества.

4. Числовые множества.

Числовое - множество, элементами которых являются числа. Числовые множества задаются на оси действительных чисел R. На этой оси выбирают масштаб и указывают начало отсчета и направление. Наиболее распространенные числовые множества:

· - множество натуральных чисел;

· - множество целых чисел;

· - множество рациональных или дробных чисел;

· - множество действительных чисел.

5. Мощность множества. Приведите примеры конечных и бесконечных множеств.

Множества называются равномощными, эквивалентными, если между ними есть взаимно - однозначное или одно-однозначное соответствие, то есть такое попарное соответствие. когда каждому элементу одного множества сопоставляется один-единственный элемент другого множества и наоборот, при этом различным элементам одного множества сопоставляются различные элементы другого.

Например, возьмём группу студентов из тридцати человек и выдадим экзаменационные билеты по одному билету каждому студенту из стопки, содержащей тридцать билетов, такое попарное соответствие из 30 студентов и 30 билетов будет одно-однозначным.

Два множества, равномощные с одним и тем же третьим множеством, равномощны. Если множества M и N равномощны, то и множества всех подмножеств каждого из этих множеств M и N , также равномощны.

Под подмножеством данного множества понимается такое множество, каждый элемент которого является элементом данного множества. Так множество легковых автомобилей и множество грузовых автомобилей будут подмножествами множества автомобилей.

Мощность множества действительных чисел, называют мощностью континуума и обозначают буквой «алеф» א . Наименьшей бесконечной областью является мощность множества натуральных чисел. Мощность множества всех натуральных чисел принято обозначать (алеф-нуль) .

Часто мощности называют кардинальными числами. Это понятие введено немецким математиком Г. Кантором. Если множества обозначают символическими буквами M, N , то кардинальные числа обозначают через m, n . Г.Кантор доказал, что множество всех подмножеств данного множества М имеет мощность большую, чем само множество М.

Множество, равномощное множеству всех натуральных чисел, называется счетным множеством.

6. Подмножества указанного множества.

Если из нашего множества выбрать несколько элементов и сгруппировать их отдельно – то это будет подмножество нашего множества. Комбинаций, из которых можно получить подмножество много, количество комбинаций лишь зависит от количества элементов в исходном множестве.

Пусть у нас есть два множества А и Б. Если каждый элемент множества Б является элементом множества А, то множество Б называется подмножеством А. Обозначается: Б ⊂ А. Пример.

Сколько существует подмножеств множества А=1;2;3.

Решение. Подмножества состоя из элементов нашего множества. Тогда у нас существует 4 варианта по количеству элементов в подмножестве:

Подмножество может состоять из 1 элемента, из 2, 3 элементов и может быть пустым. Давайте последовательно запишем наши элементы.

Подмножество из 1 элемента: 1,2,3

Подмножество из 2 элементов:1,2,1,3,2,3.

Подмножество из 3 элементов:1;2;3

Не забудем, что пустое множество так же является подмножеством нашего множества. Тогда получаем, что у нас есть 3+3+1+1=8 подмножеств.

7. Операции над множествами.

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

Объединением (соединением) множеств А и В называется множество (символически оно обозначается через ), состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А или В . В форме от х объединение множеств записывается так

Запись читается: «объединение А и В » или «А , объединенное с В ».

Операции над множествами наглядно изображают графически с помощью кругов Эйлера (иногда используют термин «диаграммы Венна-Эйлера»). Если все элементы множества А будут сосредоточены в пределах круга А , а элементы множества В – в пределах круга В , тооперацию объединения с помощью кругов Эйлера можно представить в следующем виде

Пример 1 . Объединением множества А = {0, 2, 4, 6, 8} четных цифр и множества В = {1, 3, 5, 7, 9} нечетных цифр является множество = ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} всех цифр десятичной системы счисления.

8. Графическое изображение множеств. Диаграммы Эйлера-Венна.

Диаграммы Эйлера-Венна – геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U , а внутри его – кругов (или каких-нибудь других замкнутых фигур), представляющих множества. Фигуры должны пересекаться в наиболее общем случае, требуемом в задаче, и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.

Операции над множествами рассматриваются для получения новых множеств из уже существующих.

Определение. Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис. 1):

Определение. Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат одновременно как множеству А, так и множеству В (рис. 2):

Определение. Разностью множеств А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 3):

Определение. Симметрической разностью множеств А и В называется множество элементов этих множеств, которые принадлежат либо только множеству А, либо только множеству В (рис. 4):

Декартовым (или прямым) произведением множеств A и B называется такое результирующее множество пар вида (x ,y ) , построенных таким образом, что первый элемент из множества A , а второй элемент пары - из множества B . Общепринятое обозначение:

A ×B ={(x ,y )|x ∈A ,y ∈B }

Произведения трёх и более множеств можно построить следующим образом:

A ×B ×C ={(x ,y ,z )|x ∈A ,y ∈B ,z ∈C }

Произведения вида A ×A ,A ×A ×A ,A ×A ×A ×A и т.д. принято записывать в виде степени: A 2 ,A 3 ,A 4 (основание степени - множество-множитель, показатель - количество произведений). Читают такую запись как «декартов квадрат» (куб и т.д.). Существуют и другие варианты чтения для основных множеств. К примеру, R n принято читать как «эр энное».

Свойства

Рассмотрим несколько свойств декартова произведения:

1. Если A ,B - конечные множества, то A ×B - конечное. И наоборот, если одно из множеств-сомножителей бесконечное, то и результат их произведения - бесконечное множество.

2. Количество элементов в декартовом произведении равно произведению чисел элементов множеств-сомножителей (в случае их конечности, разумеется): |A ×B |=|A |⋅|B | .

3. A np ≠(A n ) p - в первом случае целесообразно рассмотреть результат декартова произведения как матрицу размеров 1×np , во втором же - как матрицу размеров n ×p .

4. Коммутативный закон не выполняется, т.к. пары элементов результата декартова произведения упорядочены: A ×B ≠B ×A .

5. Ассоциативный закон не выполняется: (A ×B )×C ≠A ×(B ×C ) .

6. Имеет место дистрибутивность относительно основных операциях на множествах: (A ∗B )×C =(A ×C )∗(B ×C ),∗∈{∩,∪,∖}

10. Понятие высказывания. Элементарные и составные высказывания.

Высказывание - это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно (И-1) или ложно (Л-0), но не то и другое одновременно.

Например, «Сегодня идет дождь», «Иванов выполнил лабораторную работу №2 по физике».

Если у нас имеется несколько исходных высказываний, то из них при помощи логических союзов или частиц мы можем образовывать новые высказывания, истинностное значение которых зависит только от истинностных значений исходных высказываний и от конкретных союзов и частиц, которые участвуют в построении нового высказывания. Слова и выражения «и», «или», «не», «если... , то», «поэтому», «тогда и только тогда» являются примерами таких союзов. Исходные высказывания называются простыми , а построенные из них с помощью тех или иных логических союзов новые высказывания - составными . Разумеется, слово «простые» никак не связано с сутью или структурой исходных высказываний, которые сами могут быть весьма сложными. В данном контексте слово «простой» является синонимом слова «исход-ный». Важно то, что значения истинности простых высказываний предполагаются известными или заданными; в любом случае они никак не обсуждаются.

Хотя высказывание типа «Сегодня не четверг» не составлено из двух различных простых высказываний, для единообразия конструкции оно также рассматривается как составное, по-скольку его истинностное значение определяется истинностным значением другого высказыва-ния «Сегодня четверг»

Пример 2. Cледующие высказывания рассматриваются как составные:

Я читаю «Московский комсомолец» и я читаю «Коммерсант».

Если он сказал это, значит, это верно.

Солнце не является звездой.

Если будет солнечно и температура превысит 25 0 , я приеду поездом или автомобилем

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

11. Операции над высказываниями.

1. Операция отрицания.

Отрицанием высказывания А (читается «не А », «неверно, что А »), которое истинно, когда А ложно и ложно, когда А – истинно.

Отрицающие друг друга высказывания А и называются противоположными.

2. Операция конъюнкции .

Конъюнкцией высказываний А и В называется высказывание, обозначаемое А В (читается «А и В »), истинные значения которого определяются в том и только том случае, когда оба высказывания А и В истинны.

Конъюнкцию высказываний называют логическим произведением и часто обозначают АВ.

Пусть дано высказывание А – «в марте температура воздуха от 0 С до +7 С » и высказывание В – «в Витебске идет дождь». Тогда А В будет следующей: «в марте температура воздуха от 0 С до +7 С и в Витебске идет дождь». Данная конъюнкция будет истинной, если будут высказывания А и В истинными. Если же окажется, что температура была меньше 0 С или в Витебске не было дождя, то А В будет ложной.

3 . Операция дизъюнкции .

Дизъюнкцией высказываний А и В называется высказывание А В (А или В ), которое истинно тогда и только тогда, когда хотя бы одно из высказываний истинно и ложно – когда оба высказывания ложны.

Дизъюнкцию высказываний называют также логической суммой А+В.

Высказывание «4<5 или 4=5 » является истинным. Так как высказывание «4<5 » – истинное, а высказывание «4=5 » – ложное, то А В представляет собой истинное высказывание «4 5 ».

4 . Операция импликации .

Импликацией высказываний А и В называется высказывание А В («если А , то В », «из А следует В »), значение которого ложно тогда и только тогда, когда А истинно, а В ложно.

В импликации А В высказывание А называют основанием, или посылкой, а высказывание В – следствием, или заключением.

12. Таблицы истинности высказываний.

Таблица истинности - это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию и значениями функции.

Таблицы истинности применяются для:

Вычисления истинности сложных высказываний;

Установления эквивалентности высказываний;

Определения тавтологий.

Числа разделяются на классы. Целые положительные числа - N = {1, 2, 3, … } - составляют множество натуральных чисел. Зачастую и 0 считают натуральным числом.

Множество целых чисел Z включает в себя все натуральные числа, число 0 и все натуральные числа, взятые со знаком минус: Z = {0, 1, -1, 2, -2, …}.

Каждое рациональное число x можно задать парой целых чисел (m, n), где m является числителем, n - знаменателем числа: x = m/n. Эквивалентным представлением рационального числа является его задание в виде числа, записанного в позиционной десятичной системе счисления, где дробная часть числа может быть конечной или бесконечной периодической дробью. Например, число x = 1/3 = 0,(3) представляется бесконечной периодической дробью.

Числа, задаваемые бесконечными непериодическими дробями, называются иррациональными числами . Таковыми являются, например, все числа вида vp, где p - простое число. Иррациональными являются известные всем числа и e.

Объединение множеств целых, рациональных и иррациональных чисел составляет множество вещественных чисел. Геометрическим образом множества вещественных чисел является прямая линия - вещественная ось, где каждой точке оси соответствует некоторое вещественное число, так что вещественные числа плотно и непрерывно заполняют всю вещественную ось.

Плоскость представляет геометрический образ множества комплексных чисел, где вводятся уже две оси - вещественная и мнимая. Каждое комплексное число, задаваемое парой вещественных чисел, представимо в виде: x = a+b*i, где a и b - вещественные числа, которые можно рассматривать как декартовы координаты числа на плоскости.

Делители и множители

Рассмотрим сейчас классификацию, которая делит множество натуральных чисел на два подмножества - простых и составных чисел. В основе этой классификации лежит понятие делимости натуральных чисел. Если n делится нацело на d, то говорят, что d "делит" n, и записывают это в виде: . Заметьте, это определение, возможно, не соответствует интуитивному пониманию: d "делит" n, если n делится на d, а не наоборот. Число d называется делителем числа n. У каждого числа n есть два тривиальных делителя - 1 и n. Делители, отличные от тривиальных, называются множителями числа n. Число n называется простым, если у него нет делителей, отличных от тривиальных. Простые числа делятся только на 1 и сами на себя. Числа, у которых есть множители, называются составными. Число 1 является особым числом, поскольку не относится ни к простым, ни к составным числам. Отрицательные числа также не относятся ни к простым, ни к составным, но всегда можно рассматривать модуль числа и относить его к простым или составным числам.

Любое составное число N можно представить в виде произведения его множителей: . Это представление не единственно, например 96 = 8*12 = 2*3*16. Однако для каждого составного числа N существует единственное представление в виде произведения степеней простых чисел: , где - простые числа и . Это представление называется разложением числа N на простые множители. Например .

Если и , то d является общим делителем чисел m и n. Среди всех общих делителей можно выделить наибольший общий делитель, обозначаемый как НОД(m,n). Если НОД(m,n) = 1, то числа m и n называются взаимно простыми. Простые числа взаимно просты, так что НОД(q,p) =1, если q и p - простые числа.

Если и , то A является общим кратным чисел m и n. Среди всех общих кратных можно выделить наименьшее общее кратное, обозначаемое как НОК(m,n). Если НОК(m,n) = m*n, то числа m и n являются взаимно простыми. НОК(q, p) =q*p, если q и p - простые числа.

Если через и обозначить множества всех простых множителей чисел m и n, то

Если получено разложение чисел m и n на простые множители, то, используя приведенные соотношения, нетрудно вычислить НОД(m,n) и НОК(m,n). Существуют и более эффективные алгоритмы, не требующие разложения числа на множители.

Алгоритм Эвклида

Эффективный алгоритм вычисления НОД(m,n) предложен еще Эвклидом. Он основывается на следующих свойствах НОД(m,n), доказательство которых предоставляется читателю:

Если , то по третьему свойству его можно уменьшить на величину n. Если же , то по второму свойству аргументы можно поменять местами и вновь придти к ранее рассмотренному случаю. Когда же в результате этих преобразований значения аргументов сравняются, то решение будет найдено. Поэтому можно предложить следующую схему:

while(m != n) { if(m < n) swap(m,n); m = m - n; } return(m);

Здесь процедура swap выполняет обмен значениями аргументов.

Если немного подумать, то становится ясно, что вовсе не обязательно обмениваться значениями - достаточно на каждом шаге цикла изменять аргумент с максимальным значением. В результате приходим к схеме:

while(m != n) { if(m > n) m = m - n; else n = n - m; } return(m);

Если еще немного подумать, то можно улучшить и эту схему, перейдя к циклу с тождественно истинным условием:

while(true) { if(m > n) m = m - n; else if (n > m) n = n - m; else return(m); }

Последняя схема хороша тем, что в ней отчетливо видна необходимость доказательства завершаемости этого цикла. Доказать завершаемость цикла нетрудно, используя понятие варианта цикла . Для данного цикла вариантом может служить целочисленная функция - max(m,n) , которая уменьшается на каждом шаге, оставаясь всегда положительной.

Достоинством данной версии алгоритма Эвклида является и то, что на каждом шаге используется элементарная и быстрая операция над целыми числами - вычитание. Если допустить операцию вычисления остатка при делении нацело, то число шагов цикла можно существенно уменьшить. Справедливо следующее свойство:

Это приводит к следующей схеме:

int temp; if(n>m) temp = m; m = n; n = temp; //swap(m,n) while(m != n) { temp = m; m = n; n = temp%n; }

Если немного подумать, то становится ясно, что вовсе не обязательно выполнять проверку перед началом цикла. Это приводит к более простой схеме вычисления НОД, применяемой обычно на практике:

int temp; while(m != n) { temp = m; m = n; n = temp%n; }

Для вычисления НОК(m, n) можно воспользоваться следующим соотношением:

А можно ли вычислить НОК(m, n), не используя операций умножения и деления? Оказывается, можно одновременно с вычислением НОД(m,n) вычислять и НОК(m,n). Вот соответствующая схема:

int x = v = m, y = u = n,; while(x != y) { if(x > y){ x = x - y; v = v + u;} else {y = y - x; u = u + v;} } НОД = (x + y)/2; НОК = (u+v)/2;

Доказательство того, что эта схема корректно вычисляет НОД, следует из ранее приведенных свойств НОД. Менее очевидна корректность вычисления НОК. Для доказательства заметьте, что инвариантом цикла является следующее выражение:

Это соотношение выполняется после инициализации переменных до начала выполнения цикла. По завершении цикла, когда x и y становятся равными НОД, из истинности инварианта следует корректность схемы. Нетрудно проверить, что операторы тела цикла оставляют утверждение истинным. Детали доказательства оставляются читателям.

Понятие НОД и НОК можно расширить, определив их для всех целых чисел. Справедливы следующие соотношения:

Расширенный алгоритм Эвклида

Иногда полезно представлять НОД(m,n) в виде линейной комбинации m и n:

В частности, вычисление коэффициентов a и b необходимо в алгоритме RSA - шифрования с открытым ключом. Приведу схему алгоритма, позволяющую вычислить тройку - d, a, b - наибольший общий делитель и коэффициенты разложения. Алгоритм удобно реализовать в виде рекурсивной процедуры

ExtendedEuclid(int m, int n, ref int d, ref int a, ref int b),

которая по заданным входным аргументам m и n вычисляет значения аргументов d, a, b. Нерекурсивная ветвь этой процедуры соответствует случаю n = 0, возвращая в качестве результата значения: d = m, a = 1, b = 0. Рекурсивная ветвь вызывает

ExtendedEuclid(n, m % n, ref d, ref a, ref b)

и затем изменяет полученные в результате вызова значения a и b следующим образом:

Доказательство корректности этого алгоритма построить нетрудно. Для нерекурсивной ветви корректность очевидна, а для рекурсивной ветви нетрудно показать, что из истинности результата, возвращаемого при рекурсивном вызове, следует его истинность для входных аргументов после пересчета значений a и b.

Как работает эта процедура? Вначале происходит рекурсивный спуск, пока n не станет равно нулю.

В этот момент впервые будет вычислено значение d и значения параметров a и b. После этого начнется подъем и будут перевычисляться параметры a и b.

Задачи

• 49. Даны m и n - натуральные числа. Вычислите НОД(m, n). При вычислениях не используйте операций умножения и деления.
• 50. Даны m и n - натуральные числа. Вычислите НОК(m, n).
• 51. Даны m и n - натуральные числа. Вычислите НОК(m, n). При вычислениях не используйте операций умножения и деления.
• 52. Даны m и n - целые числа. Вычислите НОД(m, n). При вычислениях не используйте операций умножения и деления.
• 53. Даны m и n - целые числа. Вычислите НОК(m, n). При вычислениях не используйте операций умножения и деления.
• 54. Даны m и n - целые числа. Вычислите НОД(m, n). При вычислениях используйте операцию взятия остатка от деления нацело.
• 55. Даны m и n - целые числа. Вычислите НОК(m, n). При вычислениях используйте операцию взятия остатка от деления нацело.
• 56. Даны m и n - целые числа. Вычислите тройку чисел - (d, a, b), используя расширенный алгоритм Эвклида.
• 57. Даны m и n - натуральные числа. Представьте НОД(m, n) в виде линейной комбинации m и n.
• 58. Даны m и n - целые числа. Представьте НОД(m, n) в виде линейной комбинации m и n.
• 59. Даны m и n - целые числа. Проверьте, являются ли числа m и n взаимно простыми.

Простые числа

Среди четных чисел есть только одно простое число - это 2. Простых нечетных чисел сколь угодно много. Нетрудно доказать, что число , где - подряд идущие простые числа, является простым. Так что, если построено простых чисел, то можно построить еще одно простое число , большее . Отсюда следует, что множество простых чисел неограниченно. Пример: число N = 2*3*5*7 + 1 = 211 является простым числом.

Решето Эратосфена

Как определить, что число N является простым? Если допустима операция N % m, дающая остаток от деления числа N на число m, то простейший алгоритм состоит в проверке того, что остаток не равен нулю при делении числа N на все числа m, меньшие N. Очевидным улучшением этого алгоритма является сокращение диапазона проверки - достаточно рассматривать числа m в диапазоне .

Еще в 3-м веке до н.э. греческий математик Эратосфен предложил алгоритм нахождения простых чисел в диапазоне , не требующий операций деления. Этот алгоритм получил название "Решето Эратосфена". В компьютерном варианте идею этого алгоритма можно описать следующим образом. Построим массив Numbers, элементы которого содержат подряд идущие нечетные числа, начиная с 3. Вначале все числа этого массива считаются невычеркнутыми. Занесем первое невычеркнутое число из этого массива в массив SimpleNumbers - и это будет первое нечетное простое число (3). Затем выполним просеивание, проходя по массиву Numbers с шагом, равным найденному простому числу, вычеркивая все попадающиеся при этом проходе числа. При первом проходе будет вычеркнуто число 3 и все числа, кратные 3. На следующем проходе в таблицу простых чисел будет занесено следующее простое число 5, а из массива Numbers будут вычеркнуты числа, кратные 5. Процесс повторяется, пока не будут вычеркнуты все числа в массиве Numbers. В результате массив SimpleNumbers будет содержать таблицу первых простых чисел, меньших N.

Этот алгоритм хорош для нахождения сравнительно небольших простых чисел. Но если потребуется найти простое число с двадцатью значащими цифрами, то памяти компьютера уже не хватит для хранения соответствующих массивов. Замечу, что в современных алгоритмах шифрования используются простые числа, содержащие несколько сотен цифр.

Плотность простых чисел

Мы показали, что число простых чисел неограниченно. Понятно, что их меньше, чем нечетных чисел, но насколько меньше? Какова плотность простых чисел? Пусть - это функция, возвращающая число простых чисел, меньших n. Точно задать эту функцию не удается, но для нее есть хорошая оценка. Справедлива следующая теорема:

Функция асимптотически сверху приближается к своему пределу, так что оценка дает слегка заниженные значения. Эту оценку можно использовать в алгоритме решета Эратосфена для выбора размерности массива SimpleNumbers, когда задана размерность массива Numbers, и, наоборот, при заданной размерности таблицы простых чисел можно выбрать подходящую размерность для массива Numbers.

Табличный алгоритм определения простоты чисел

Если хранить таблицу простых чисел SimpleNumbers, в которой наибольшее простое число равно M, то достаточно просто определить, является ли число N, меньшее , простым. Если N меньше M, то достаточно проверить, находится ли число N в таблице SimpleNumbers. Если N больше M, то достаточно проверить, делится ли число N на числа из таблицы SimpleNumbers, не превосходящие значения vN. Понятно, что если у числа N нет простых множителей, меньших vN, то число N является простым.

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

Тривиальный алгоритм

Если N - нечетное число, то проверить, что оно является простым, можно на основе определения простоты числа. При этом не требуется никакой памяти для хранения таблиц чисел, - но, как всегда, выигрывая в памяти, мы проигрываем во времени. Действительно, достаточно проверить, делится ли нацело число N на подряд идущие нечетные числа в диапазоне . Если у числа N есть хоть один множитель, то оно составное, иначе - простое.

Все рассмотренные алгоритмы перестают эффективно работать, когда числа выходят за пределы разрядной сетки компьютера, отведенной для представления чисел, так что если возникает необходимость работы с целыми числами, выходящими за пределы диапазона System.Int64, то задача определения простоты такого числа становится совсем не простой. Существуют некоторые рецепты, позволяющие определить, что число является составным. Вспомним хотя бы известные со школьных времен алгоритмы. Если последняя цифра числа делится на 2, то и число делится на 2. Если две последние цифры числа делятся на 4, то и число делится на 4. Если сумма цифр делится на 3 (на 9), то и число делится на 3 (на 9). Если последняя цифра равна 0 или 5, то число делится на 5. Математики затратили много усилий, доказывая, что то или иное число является (или не является) простым числом. Сейчас есть особые приемы, позволяющие доказать, что числа некоторого вида являются простыми. Наиболее подходящими кандидатами на простоту являются числа вида , где p - это простое число. Например, доказано, что число , имеющее более 6000 цифр, является простым, но нельзя сказать, какие простые числа являются ближайшими соседями этого числа.

Задачи

Проекты

• 67. Построить класс "Температура", позволяющий задавать температуру в разных единицах измерения. Построить Windows-проект, поддерживающий интерфейс для работы с классом.
• 68. Построить класс "Расстояния", позволяющий использовать разные системы мер. Построить Windows-проект, поддерживающий интерфейс для работы с классом.
• 69. Построить класс "Простые числа". Построить Windows-проект, поддерживающий интерфейс для работы с классом.
• 70. Построить класс "Системы счисления". Построить Windows-калькулятор, поддерживающий вычисления в заданной системе счисления.
• 71. Построить класс "Рациональные числа". Построить Windows-калькулятор, поддерживающий вычисления с этими числами.
• 72. Построить класс "Комплексные числа". Построить Windows-калькулятор, поддерживающий вычисления с этими числами.

Натуральные числа - это те числа, с которых когда-то всё началось. И сегодня это первые числа, с которыми встречается в своей жизни человек, когда в детстве учится считать на пальцах или счетных палочках.

Определение: натуральными называют числа, которые используют для счета предметов (1, 2, 3, 4, 5, ...) [Число 0 не является натуральным. Оно и в истории математики имеет свою отдельную историю и появилось много позже натуральных чисел.]

Множество всех натуральных чисел (1, 2, 3, 4, 5, ...) обозначают буквой N.

Целые числа

Научившись считать, следующее, что мы делаем - это учимся производить над числами арифметические действия. Обычно сначала (на счетных палочках) учатся выполнять сложение и вычитание.

Со сложением всё понятно: сложив любые два натуральных числа, в результате всегда получим тоже натуральное число. А вот в вычитании обнаруживаем, что из меньшего отнять большее так, чтобы в результате получилось натуральное число, мы не можем. (3 − 5 = чему?) Здесь возникает идея отрицательных чисел. (Отрицательные числа уже не являются натуральными)

На этапе возникновения отрицательных чисел (а они появились позже дробных) существовали и их противники, считавшие их бессмыслицей. (Три предмета можно показать на пальцах, десять можно показать, тысячу предметов можно представить по аналогии. А что такое "минус три мешка"? — В то время числа хоть уже и использовались сами по себе, в отрыве от конкретных предметов, количество которых они обозначают, всё ещё были в сознании людей гораздо ближе к этим конкретным предметам, чем сегодня.) Но, как и возражения, так и основной аргумент в пользу отрицательных чисел, пришел из практики: отрицательные числа позволяли удобно вести счет долгам. 3 − 5 = −2 — у меня было 3 монеты, я потратила 5. Значит, у меня не просто закончились монеты, но и 2 монеты я кому-то должна. Если верну одну, долг изменится −2+1=−1, но тоже может быть представлен отрицательным числом.

В итоге, отрицательные числа появились в математике, и теперь у нас есть бесконечное количество натуральных чисел (1, 2, 3, 4, ...) и есть такое же количество им противоположных (−1, −2, −3, −4, ...). Добавим к ним ещё 0. И множество всех этих чисел будем называть целыми.

Определение: Натуральные числа, им противоположные и нуль составляют множество целых чисел. Оно обозначается буквой Z.

Любые два целых числа можно вычесть друг из друга или сложить и получить в результате целое число.

Идея сложения целых чисел уже предполагает возможность умножения, как просто более быстрого способа выполнения сложения. Если у нас есть 7 мешков по 6 килограмм, мы можем складывать 6+6+6+6+6+6+6 (семь раз прибавлять к текущей сумме по 6), а можем просто помнить, что такая операция всегда будет давать в результате 42. Как и сложение шести семерок 7+7+7+7+7+7 тоже всегда будет давать 42.

Результаты операции сложения определенного числа самого с собой определенное количество раз для всех пар чисел от 2 до 9 выписываются и составляют таблицу умножения. Для умножения целых чисел больше 9 придумывается правило умножения в столбик. (Которое распространяется и на десятичные дроби, и которое будет рассматриваться в одной из следующих статей.) При умножении любых двух целых чисел друг на друга всегда получим в результате целое число.

Рациональные числа

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

Когда у нас было 7 мешков по 6 килограмм, с помощью умножения мы легко посчитали, что общий вес содержимого мешков составляет 42 килограмма. Представим себе, что мы высыпали всё содержимое всех мешков в одну общую кучу массой 42 килограмма. А потом передумали, и захотели распределить содержимое обратно по 7 мешкам. Сколько килограмм при этом попадет в один мешок, если будем распределять поровну? – Очевидно, что 6.

А если захотим распределить 42 килограмма по 6 мешкам? Тут мы подумаем о том, что те же общие 42 килограмма могли бы получиться, если бы мы высыпали в кучу 6 мешков по 7 килограмм. И значит при делении 42 килограмм на 6 мешков поровну получим в одном мешке по 7 килограмм.

А если разделить 42 килограмма поровну по 3 мешкам? И здесь тоже мы начинаем подбирать такое число, которое при умножении на 3 дало бы 42. Для «табличных» значений, как в случае 6 ·7=42 => 42:6=7, мы выполняем операцию деления, просто вспоминая таблицу умножения. Для более сложных случаев используется деление в столбик, которое будет рассмотрено в одной из следующих статей. В случае 3 и 42 можно «подбором» вспомнить, что 3 ·14 = 42. Значит, 42:3=14. В каждом мешке будет по 14 килограмм.

Теперь попробуем разделить 42 килограмма поровну на 5 мешков. 42:5=?
Замечаем, что 5 ·8=40 (мало), а 5·9=45 (много). То есть, ни по 8 килограмм в мешке, ни по 9 килограмм, из 5 мешков мы 42 килограмма никак не получим. При этом понятно, что в реальности разделить любое количество (крупы, например,) на 5 равных частей нам ничего не мешает.

Операция деления целых чисел друг на друга не обязательно дает в результате целое число. Так мы пришли к понятию дроби. 42:5 = 42/5 = 8 целых 2/5 (если считать в обыкновенных дробях) или 42:5=8,4 (если считать в десятичных дробях).

Обыкновенные и десятичные дроби

Можно сказать, что любая обыкновенная дробь m/n (m – любое целое, n – любое натуральное) представляет собой просто специальную форму записи результата деления числа m на число n. (m называют числителем дроби, n – знаменателем) Результат деления, например, числа 25 на число 5 тоже можно записать в виде обыкновенной дроби 25/5. Но в этом нет необходимости, так как результат деления 25 на 5 может быть записан просто целым числом 5. (И 25/5 = 5). А вот результат деления числа 25 на число 3 уже не может быть представлен целым числом, поэтому здесь и возникает необходимость использования дроби, 25:3=25/3. (Можно выделить целую часть 25/3= 8 целых 1/3. Более подробно обыкновенные дроби и операции с обыкновенными дробями будут рассмотрены в следующих статьях.)

Обыкновенные дроби хороши тем, что, чтобы представить такой дробью результат деления любых двух целых чисел, нужно просто записать делимое в числитель дроби, а делитель в знаменатель. (123:11=123/11, 67:89=67/89, 127:53=127/53, …) Затем по возможности сократить дробь и/или выделить целую часть (эти действия с обыкновенными дробями будут подробно рассмотрены в следующих статьях). Проблема в том, что производить арифметические действия (сложение, вычитание) с обыкновенными дробями уже не так удобно, как с целыми числами.

Для удобства записи (в одну строку) и для удобства вычислений (с возможностью вычислений в столбик, как для обычных целых чисел) кроме обыкновенных дробей придуманы ещё и десятичные дроби. Десятичная дробь – это специальным образом записанная обыкновенная дробь со знаменателем 10, 100, 1000 и т.п. Например, обыкновенная дробь 7/10 – это то же, что и десятичная дробь 0,7. (8/100 = 0,08; 2 целых 3/10=2,3; 7 целых 1/1000 = 7, 001). Переводу обыкновенных дробей в десятичные и наоборот будет посвящена отдельная статья. Операциям с десятичными дробями – другие статьи.

Любое целое число может быть представлено в виде обыкновенной дроби со знаменателем 1. (5=5/1; −765=−765/1).

Определение: Все числа, которые могут быть представлены в виде обыкновенной дроби, называют рациональными числами. Множество рациональных чисел обозначают буквой Q.

При делении любых двух целых чисел друг на друга (кроме случая деления на 0) всегда получим в результате рациональное число. Для обыкновенных дробей есть правила сложения, вычитания, умножения и деления, позволяющие произвести соответствующую операцию с любыми двумя дробями и получить в результате также рациональное число (дробь или целое).

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

Казалось бы, других чисел не существует, все числа рациональные. Но и это не так.

Действительные числа

Существуют такие числа, которые нельзя представить в виде дроби m/n (где m-целое, n-натуральное).

Какие же это числа? Мы ещё не рассмотрели операцию возведения в степень. Например, 4 2 =4 ·4 = 16. 5 3 =5 ·5 ·5=125. Как умножение представляет собой более удобную форму записи и вычисления сложения, так и возведение в степень – это форма записи умножения одного и того же числа самого на себя определенное количество раз.

Но теперь рассмотрим операцию, обратную возведению в степень – извлечение корня. Квадратный корень из 16 – это число, которое в квадрате даст 16, то есть число 4. Квадратный корень из 9 – это 3. А вот квадратный корень из 5 или из 2, например, не может быть представлен рациональным числом. (Доказательство этого утверждения, другие примеры иррациональных чисел и их историю можно посмотреть, например, в Википедии)

В ГИА в 9 классе есть задание на определение того, является ли число, содержащее в своей записи корень, рациональным или иррациональным. Задача заключается в том, чтобы попытаться преобразовать это число к виду, не содержащему корень (используя свойства корней). Если от корня не удается избавиться, то число иррациональное.

Другим примером иррационального числа является число π, знакомое всем из геометрии и тригонометрии.

Определение: Рациональные и иррациональные числа вместе называют действительными (или вещественными) числами. Множество всех действительных чисел обозначают буквой R.

В действительных числах, в отличии от рациональных, мы можем выразить расстояние между любыми двумя точками на прямой или на плоскости.
Если нарисовать прямую и выбрать на ней две произвольные точки или выбрать две произвольные точки на плоскости, то может так получиться, что точное расстояние между этими точками невозможно выразить рациональным числом. (Пример – гипотенуза прямоугольного треугольника с катетами 1 и 1 по теореме Пифагора будет равна корню из двух – то есть иррациональному числу. Сюда же относится точная длина диагонали тетрадной клетки (длина диагонали любого идеального квадрата с целыми сторонами).)
А в множестве действительных чисел любые расстояния на прямой, в плоскости или в пространстве могут быть выражены соответствующим действительным числом.