Специальная метематика / solov.doc

Пермский Государственный Технический Университет

А. Е. СОЛОВЬЕВ

СПЕЦИАЛЬНАЯ МАТЕМАТИКА

конспект лекций

для студентов специальности АСУ

Пермь, 2001г.

Оглавление

Введение

Введение

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

Самостоятельное значение имеют математические проблемы теоретического и практического программирования.

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

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

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

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

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

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

1. Теория множеств

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

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

Теорию множеств можно подразделить на аксиоматическую и интуитивную (наивную).

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

Для интуитивного понятия множества существенны два момента, следующие из "определения":

1. Различимость элементов.

2. Возможность мыслить их как нечто единое.

Студенты образуют группу. Деревья составляют лес.

Целые числа составляют множество целых чисел.

Жители Марса - множество марсиан.

Множество, не содержащее элементов, называется пустым множеством и обозначается ∅ или {}. Обычно именно фигурные скобки используются для выделения множества (отсутствие элементов в скобках и говорит о том, что это пустое множество).

Множество, заведомо содержащее все рассматриваемые элементы, называется универсальным или универсумом - U.

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

Включать ли самого себя в множество тех, кого он обязан брить?!

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

A = {a, b, c, d} - задание множества явным перечислением элементов.

Например, гвардия = {Иванов, Петров, Сидоров}

B = {x | С(x)} - задание множества (характеристическим) свойством С(x).

Например, студенчество = {x | x - студент} - множество таких х, что х - студент.

Отношение включения ⊆ . Множество А включено в множество В (А ⊆ В) или А есть подмножество множества В, если из х ∈ А следует х ∈ В.

Например, студенческая группа ⊆ студенты данной специальности

Отношение строгого включения ⊂: Если A ⊆ B и A ≠ B , то можно написать

A ⊂ B.

Например: ∅ ⊂ множество отличников

Кстати, на что намекает это отношение?

Свойства отношения включения:

1. Рефлексивность: A ⊆ A

2. Принцип объемности: A ⊆ B и B ⊆ A следует B = A (на основе этого принципа и доказывается равенство двух множеств).

3. Транзитивность: A ⊆ B и B ⊆ C следует A ⊆ C

Полезные соотношения:

{ }= ∅ ; 1 ≠ { 1 } ; {{ 1 }} ≠ { 1 } ; { а, в } = { в, а }

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

1. Объединение множеств A и B

A ∪ B = { x | x ∈ A или x ∈ B } (или - неисключающее)

2. Пересечение множеств A и B

A ∩ B = { x | x ∈ A и x ∈ B }

3. Разность множеств A и B

A \ B = { x | x ∈ A и x ∉ B }

4. Симметрическая разность множеств A и B

A Δ B = { x | (x∈A и x∉B) или (x∉A и x∈B)}=( A \ B ) ∪ ( B \ A )

5. Дополнение множества A

A = { x | x ∉A }

Пример.

Пусть А = {1, 2, 3} и B = {3,4}, тогда

A ∪ B = {1, 2, 3, 4}

A ∩ B = {3}

A \ B = {1, 2}

A Δ B = {1, 2, 4}

А = множество чисел кроме 1, 2, 3.

1.3. Диаграммы Эйлера - Венна

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

U

II

III

I

A

B

A∪B - зоны I, II, III.

A∩B - зона III.

A\B - зона I.

A - все, кроме круга А.

AΔB - зоны I, III.

Диаграмма для общего случая c тремя множествами будет иметь вид:

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

1.4. Алгебра множеств

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

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

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

Остальные операции можно выразить через эти три.

Законы:

1. Коммутативный:

A ∪ B = B ∪ A A ∩ B = B ∩ A

2. Ассоциативный:

A ∪ (B ∪ C) = (A ∪ B) ∪ C = A ∪ B∪ C A ∩(B ∩ C) = (A ∩ B) ∩ C = A ∩ B ∩ С

3. Дистрибутивный:

A ∪ (B ∩ С)= (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ С) = (A ∩ B) ∪ (A ∩ C)

4. Поглощения:

A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A

5. Идемпотентности:

A ∪ A = A A ∩ A = A

6. Исключенного третьего: Противоречия:

A ∪A = U A ∩ A = ∅

7. A ∪ ∅ = A A ∩ ∅ = ∅

8. A ∪ U = U A ∩ U = A

____ ___

A ∪ B = A ∩ B A ∩ B = A ∪ B

10. ∅ = U U = ∅

11. Двойного отрицания: A = A

12. A \ B =A ∩ B

13. A Δ B =A ∩ B ∪ A ∩ B

Пример доказательства варианта дистрибутивного закона:

A ∪ (B ∩ С) = (A ∪ B) ∩ (A ∪ C)

I. Докажем, что левая часть включена в правую:

A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C)

Пусть х ∈ А ∪ (В ∩ С), тогда у х есть две возможности

1. х ∈ A . Тогда х ∈ A ∪ B и х ∈ A ∪ C ⇒ х ∈ (A ∪ B) ∩ (A ∪ C).

2. х ∈ B ∩ C. Тогда х ∈ B и х ∈ C ⇒ х ∈ A ∪ B и х ∈ A ∪ C,

то есть х ∈ (A ∪ B) ∩ (A ∪ C).

II. Докажем, что правая часть включена в левую:

(A ∪ B) ∩ (A ∪ C) ⊆ A ∪ B ∩ C.

Пусть х ∈ A ∪ B и х ∈ A ∪ C. Тогда возможны два варианта:

1. х ∈ A ⇒ х ∈ A ∪ B ∩ C

2. х ∈ B и х ∈ C ⇒ х ∈ B ∩ C ⇒ х ∈ A ∪ B ∩ C.

То есть левое и правое множества равны.

1.5. Кортеж. График

Кортеж - фундаментальное неопределяемое понятие.

В кортеже существенны не только элементы, но и порядок, в котором они располагаются. Следовательно, кортеж может содержать одинаковые элементы.

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

Кортеж заключается в угловые скобки.

< a₁ ,a₂, a₃, ..., a_n > - кортеж длиной n или упорядоченная n-ка.

< 1, 1, 1 > - упорядоченная тройка - единичный вектор.

< a, b> - упорядоченная двойка или пара. Пару (и не только ее) можно представить и в традиционном виде, как множество: {a, {a, b}}. Однако использование угловых скобок упрощает представление.

График - множество пар. Можно дать и более общее определение графика в n-мерном пространстве, как множества n-ок). Однако в дальнейшем будут рассматриваться только двухмерные графики.

Примеры: G = { < a, b >, < c, a >, < d, b > } - график.

Несколько эпатирующе звучит слово график применительно к аналитической записи. Но это лишь подчеркивает его универсальность. Для множеств действительных чисел Х и У приведем графический пример графика.

У

у_i

х_i Х

Декартово (прямое) произведение множеств A и B:

A * B = {< a, b > | a ∈ A, b∈B}

В общем случае : A₁ x A₂ x A₃ x ...x A_n = {< a₁, a₂, ..., a_n >|a₁∈A₁, a₂∈A₂, ... , a_n∈A_n}

Пример : Для A = { 1, 2} и B={ 1, 2, 3} декартово произведение

А х В = {< 1, 1 >, < 1, 2 >, < 1, 3 >, < 2, 1 >, < 2, 2 >, <2, 3>}

График является полым, если он совпадает с декартовым произведением.

Композицией графиков P и Q называется график R = P • Q , если он состоит из таких пар <x, y> ∈ R , что для каждой пары найдется свое z, такое, что < x, z > ∈ P,

< z, y > ∈ Q. Очевидно, что это некоммутативная операция.

Пример :

P = {< a, b >, < 1, r >, < c, 3 >, < a, 4 >}

Q = {< 2, 3 >, < 4,5 >, < a, c >, < b, d >}

R = P • Q = {< a, d >, < a, 5 >}

Свойства графиков

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

2. График называется инъективным, если он не содержит пар с одинаковой второй и различными первыми компонентами.

3. График называется симметричным, если он равен своей инверсии.

4. График называется диагональю множества М, если он состоит из пар вида

<x, x>: Δ_M = {<x, x> | x ∈ M}

Примеры

функциональный нефункциональный

нефункциональный неинъективный

Пара <a, b> называется инверсией пары <c, d>, если a = d, b = c.

График P^-1 - инверсия графика P, если он состоит из инверсий пар графика P.

Пример

P ={<a, b>, <b, e>, <k, s>}

P^-1={<b, a>, <e, b>, <s, k>}

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

Пример

B = <2, 5, 6, 4, 2, 6>

пр.B_1,2,4 = <2, 5, 4>

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

Пример

M={<a, b, c>, <a, c, d>, <k, l, m>, <o, p, r>}

пр.M_1,3={<a, c>, <a, d>, <k, m>, <o, r>}

1.6. Соответствия

Г = <G, X, Y>

Соответствие - тройка, такая, что G ⊆ X * Y - подмножество произведения второго компонента на третий.

Первый компонент (G) - график.

Второй компонент (X) - область отправления (определения).

Третий компонент (Y) - область прибытия (значений).

Соответствие называется полным, если G = X x Y .

Свойства соответствий

1. Соответствие называется функциональным, если его график функционален.

2. Соответствие называется инъективным, если его график инъективен.

3. Соответствие называется всюдуопределенным, если проекция графика на первую ось совпадает с областью отправления. пр.G₁ = X.

4. Соответствие называется сюръективным, если проекция графика на вторую ось совпадает с областью прибытия пр.G₂ = Y