Дискретно-непрерывная математика (стр. 2 )

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

Модуль 1.

Введение в алгебры

Микромодуль 1.

Основные понятия арифметики

1.1. Операции и их свойства

Определение. Операцией над множеством S называется функция f: Sn→S, n N.

В этом определении есть два важных момента, которые заслуживают особого вспоминания. Во-первых, раз операция является функцией, то результат применения операции однозначно определен. Поэтому данный упорядоченный набор из п элементов S функция f переводит только в один элемент S. Во-вторых, поскольку область значений операции лежит в S, на которое операция действует, будем говорить, что операция замкнута на S,

Говорят, что операция Sn→S имеет порядок г. Ограничимся рассмотрением ситуаций, когда порядок равен 1 или 2. В этом случае операции называют монадическими (или унарными) и диадическими (или бинарными) соответственно. Элементы набора из п элементов в области определения называют операндами. Операции обычно обозначают символами, которые называют операторами. В случае унарных операций обычно символ оператора ставят перед операндом.

Наиболее простым примером является операция изменения знака на R. В предположении, что операция сложения уже определена, -х определяет операцию x у: х+у =0 (х отображается в у: х+у=0).

Определение. Бинарные операции обозначают одним из трех способов. В первом случае оператор ставится между операндами (infix), во второму — перед операндами (prefix) и в третьему — после операндов (postfix).

Пример 1.

а+b infix,

+ab prefix,

аb+ postfix.

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

Согласно большинству математических текстов, кроме некоторых работ по алгебре и формальной логике, мы будем использовать обозначение infix. Другие обозначения имеют то преимущество, что не требуют скобок при определении порядка вычислений сложных выражений, и это делает их особенно удобными для автоматической обработки. Можно проверить соответствие между следующими парами выражений, которые записаны в формах infix и postfix соответственно:

а) a+b• c+(d+e• (f+g),

аbс• + defg+• ++;

б) (a+b)• c+d+e• f+g,

ab+с• d+ef• +g+;

в) a+(b• (c+d)+e)• f+g,

abed+ e+f +g+.

Пример 2. Рассмотрим алгебраическое выражение

а + b • с + (d + е • (f + g))

и его представление на рис. 1.1, корое называют деревом.

Рис. 1.1

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

α← b • с, β← а + α, γ ← f + g,

δ ← е • γ, π←d + δ, ρ← β + π.

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

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

Вычисление значения выражения в форме postfix осуществляется следующим образом:

Аналогично в форме prefix вычисления осуществляются следующим образом:

«Переходы» по дереву показаны на рис. 1.2, а (форма prefix), на рис. 1.2,b (форма postfix) и на рис. 1.2, c (форма infix) со скобками:

((a + (b• c)) + (d + (e• (g + g)))).

Рис. 1.2

К этим вопросам мы возвратим позднее.

Мы уже знакомые со многими бинарными операциями, например с арифметическими операциями +, •, —, / и операциями над множествами — объединением ( ) и пересечение ( ).

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

Пример 3. Пусть операция определена на множестве {a, b, с} при помощи таблицы

	а b c
a b c	a a b b a c a b b

Следовательно,

а b = а,

b b = a,

с b= b, ...

Такие символы, как © и ®, будут использоваться для обозначения разных операций, которые будут вво

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

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

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

Определение. Говорят, что бинарная операция на множестве А коммутативна, если

а b=b а для всех a, b А.

Следовательно, обычная операция сложения на Z коммутативна, а вычитание — нет.

Определение. Говорят, что операция на множестве А ассоциативна, если

(а b) с = а (b с) для всех a, b,c A.

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

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