Учебное пособие для студентов специальности 2201 (Вычислительные машины, комплексы, системы и сети) Москва 2006 - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Учебно-методический комплекс по дисциплине физика специальность 230101. 1 279.94kb.
Методические указания по изучению дисциплины Для студентов специальности... 1 77.78kb.
Рабочая программа по дисциплине «Технологии программирования» для... 1 197.38kb.
Учебный план по специальности 230101. 65 «Вычислительные машины,... 4 509.18kb.
Программа дисциплины «Компьютерная графика» 1 313.66kb.
Методические указания по выполнению лабораторных работ для студентов... 4 459.11kb.
Учебное пособие предназначено для студентов очной и заочной форм... 42 5411.89kb.
Программа дисциплины «Системное программное обеспечение» 1 246.8kb.
Учебно методический комплекс дисциплины экономическая социология 3 416.92kb.
Учебно-методический комплекс учебной дисциплины отечественная история 10 2328.35kb.
По специальности 080801 «Прикладная информатика в экономике» «Вычислительные... 1 42.22kb.
1. Компьютерные технологии их назначение, особенности, достоинства... 1 46.44kb.
Направления изучения представлений о справедливости 1 202.17kb.

Учебное пособие для студентов специальности 2201 (Вычислительные машины, комплексы - страница №1/11



Маркин П.М.


Основы математического аппарата инженера-системотехника вычислительной техники.

Учебное пособие для студентов специальности 2201

(Вычислительные машины, комплексы, системы и сети)

Москва 2006

Глава 1.
Дискретная математика.

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



Дискретная математика

Математика

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

Предмет, цели и содержание читаемого курса:


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

-Целью читаемого курса является овладение студентом математического аппарата синтеза и анализа дискретных структур (систем с сосредоточенными параметрами; процессов, протекающих в дискретные моменты времени).

-Содержанием читаемого курса (1 семестр) являются теория множеств, теория алгебры логики и теория графов.
Рекомендуемая литература из библиотечного фонда МИЭМ.

а) Общая.

1.О. П. Кузнецов, Г. М. Адемсон-Вельский “Дискретная математика для инженера”, М, “Энергоатомиздат”, 1988г.

2.Д. Кук, Г. Бейз “Компьютерная математика”, М, Наука, 1990г.

б) Дополнительная.

1. С. В. Яблонский “Введение в дискретную математику”, М, Наука, 1986г.

2. Д. Л. Ершов, Е. А. Палютин “Математическая ложка”, М, Наука, 1987г.

3. А. А. Зыков “Основы теории графов”, М, Наука, 1987г.

4. В. Н. Сачков “Введение в комбинаторные методы дискретной математики”, М, Наука, 1982г.

5. Электронная версия лекций Маркина П. М. по курсу “Дискретная математика” – На кафедральном сервере или в Интернете.

6. Ф.А. Новиков «Дискретная математика для программиста.

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

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

Структура чтения теории множеств.


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



соответствия и морфизмы


Формальные системы F,S=



алгебраические системы A=

Морфизмы

µ=< A,A ,M >



Аксиоматическая

теория множеств



Соответствия q=1,M2,S>

Множества M



Реляционные системы

Алгебры





Фундаментальные

алгебры


Функциональные системы

Конечные множества



Полукольца

Подмножества

данного множества

Группоиды

Унары 1>

Бесконечные множества



Булевы алгебры 12,f22,f1>

Потенциальная бесконечность



четкие


нечеткие

Актуальная бесконечность

Основными подходами к построению теорий множеств являются формальные системы FS (FS=<L,D>, где L-язык,D-дедуктивные средства) и алгебраические системы А (А=<M,O,R>, где М ≠ Ø, О = {fji: MiM}i,j Є N, RMn (M – непустое множество, О – множество алгебраических операций, R – множество отношений).


Теория множеств, как целостная система абстрактных объектов, имеет своими структурными компонентами:

а) концептуальный базис (первичные понятия и основные отношения между ними, выражаемыми в форме аксиом, гипотез, законов);

б) дедуктивные средства (в форме тех или иных правил);

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

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

Примечание:

1) В читаемом курсе рассматриваются только теории множеств, первичными понятиями которых являются элемент, множество и отношение инцидентности (принадлежности);

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

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



Пояснение понятия “множество” с агрегатной точки зрения.

Первичные понятия «множество» и «элемент» в рассматриваемой ниже теории множеств являются исходными (неопределяемыми), поясняемые с различных точек зрения примерами.

Согласно Г. Кантору (одному из основоположников “наивной” те6ории множеств), множеством (конечным или бесконечным), является неупорядоченная совокупность строго различимых (дискретных) объектов (агрегатов), для каждого из которых можно установить принадлежность или непринадлежность его данному множеству.

Факт принадлежности объекта х (далее называемым “элементом”) множеству М символически записывается хМ (здесь  - отношение инцидентности) и непринадлежности соответственно хМ.



Примеры:

а) Учебная группа С-25 есть множество. Элементами этого множества являются студенты, принадлежность каждого из которых к группе С-25 можно установить по журналу.

б) Решение квадратного уравнения x2+2х-8=0 есть множество, элементами которого являются корни заданного уравнения (алгоритмом установления принадлежности элемента множеству решений является его подстановка в квадратное уравнение).

М=2,-4-конечное множество

Очевидно 2,-4 М, но 3М.

Действительно:

22+2(-2)-8=0

(-4)2+2(-4)-8=0

32+23-8=70

в) Все натуральные числа образуют бесконечное множество N, символическая запись которого есть:

N=1,2,3,4,5…….

г) Все точки вещественной оси есть множество равномощное множеству всех действительных чисел Д.

д) Множество, не содержащее элементов, есть пустое множество .

Замечание:

1)Сами элементы множества могут быть множествами, но М={a,b,c} множества а,b,с нельзя писать большими буквами.

2)Термин «множество» есть экспликация (уточнение) интуитивно явных понятий: «класс», «семейство», «ансамбль».

3)Термин «элемент» множества есть экспликация интуитивно ясных понятий «участник», «член», «представитель».

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

5)Элементы множества не обязательно должны существовать одновременно. Так, следующие три объекта пространства-времени:

- Студент, вчера сдавший зачет,

- Он же, сегодня защитивший курсовой проект,

- Он же, намеревающийся завтра сдать экзамен.

Образуют множество из трех элементов (символическая запись М = {x1,x2,x3}, т.е. |M|=3).



Предостережение:

Можно говорить о множестве снежинок (дождинок) при снегопаде (дожде), но нельзя говорить о множестве снежинок (дождинок) в сугробе (луже), (так как в последнем случае нет дискретности).



Пояснение исходного понятия «множество» с атрибутивной точки зрения.

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

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

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

 - оператор отношения предикации; эквивалентная запись М (х) является одноместным предикатом - логическим сказуемым,

т. е. то, что говориться об элементе х).

Любому свойству множества М соответствует потенциально бесконечная совокупность элементов, которым присуще это свойство. В этом плане понятие “конечное множество” есть структурно сложные эмпирические или абстрактные объекты (абстрактные агрегаты) множества М.

Пример:

1)Учебная группа С-25 в рамках атрибутивной точки зрения является структурно сложным эмпирическим объектом, но не множеством.

2) Абстрактный агрегат 2,4,6 является абстрактным структурно сложным элементом составных частей 2,4,6, находящихся в отношении четности к числу 2.

3)N=1,2,3,4… - множество всех натуральных чисел, т. е. хN (читается “х является натуральным числом”)



Замечание:

а) Запись хМ логично интерпретировать, как логическую структуру простого субъектно-

предикатного высказывания х, где х - является индивидной переменной (субъектом), а М-предикатом (т.е. что говорится о субъекте).



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

в) В рассматриваемом курсе классической теории множеств используется абстракция актуальной бесконечности (мыслимой, в отличие от потенциальной бесконечности, как завершённый объект), и к которой применимы все теоретико-множественные операции.

Основные понятия содержательной теории множеств.



Производные понятия

Исходные понятия






Алгебраические системы


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

морфизмы

множество

отношения

инцидентности


элементтыт


Подмножества данного множества

Операции



Алгебраические

Не алгебраические

четкие

нечеткие


Основные производные понятия содержательных теории множеств.

Определение1.

Множество А, каждый элемент которого является элементом другого множества М, называется подмножеством данного множества М.

Символическая запись А  М (здесь  - символ отношения включения всех элементов А в М, А является несобственным подмножеством М) и АМ (А – собственное подмножество М).

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

Диаграмма Вена:

собственное подмножество несобственное подмножество


U


U






Пример1:

M={a,b,c}. Подмножеств 8: собственных 6 ({a},{b},{c},{a,b},{b,c},{a,c}), несобственных 2 ({a,b,c},)


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

F(x)= 0, если хМ; (или условно: fA(х):М0,1)



1,если х М.

Пример2:

Дано: М={a,b,c}. Представить все его подмножества с помощью индикатора.

Решение: F(x)= 1, если хМ → хА;

0,если х М → х А.

1)М={,,} – индикатор для множества М;

2)А1={,,} – индикатор для множества А1 , {a,b}

3)A2={,,} – {a,c}

4)A3={,,} − {b,c}

5)A4={,,} – {a}

6)A5={,,} – {b}

7)A6={,,} − {c}

8)A7={,,} – {a,b,c}

9)A8={,,} – 

Пояснения:


  1. Кортеж – это конечная последовательность, допускающая повторяющиеся элементы данного множества (или данных множеств), обозначается: .(см. опр.2 ниже)

2) В этих выражениях (1-9) множество есть множество кортежей (спаренных векторов), первой компонентой которых являются элементы множества M, а второй компонентой – единица/ноль (т.е. принадлежность/непринадлежность элемента множества M множеству A).

3) Говорят что индикатор fA(х) множества А, определенный на множестве М, задает четкое подмножество А множества М.

4) Если степень принадлежности элемента множества M множеству A~ есть субъективно множественная оценка FA~(x)= 0, если хА,

[1,0],если хА;

то говорят о нечетком подмножестве A~ множества М (множество М всегда четко!), и записывают A~  М.

Логическая экспликация (разъяснение) понятия подмножества А множества М с агрегатной и атрибутивной точек зрения следующие:

х(() (1)

( (2)

где метасимволы  и следует считать соответственно как “эквивалентность” и “если…то”.

Примеры:

а) Множество красавиц МГИЭМа, есть нечеткое подмножество A~ всех студенток МГИЭМ M, т.е. A~ М (это очевидно потому, что понятие “красавица” для каждого человека субъективно и, следовательно, степени оценки красоты той или иной студентки различны для различных людей).

б) Пусть M={0,1,2,3,4,5,6,7,8,9}. Привести подмножество ”большие цифры”. Возможный вариант (субъективный):

A={<0,0>,<1,0>,<2,1/1000>,<3,1/100>,<4,1/10>,<5,0.5>,<6,0.6>,<7,0.7>,<8,0.9>,<9,1>}. Здесь первая компонента каждого кортежа есть цифра множества M, а вторая компонента этих же кортежей есть степень оценки принадлежности цифры к искомому подмножеству.


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

Условно кортеж записывают последовательностью элементов заданного множества в угловых скобках (пусть А={a,b,c}, тогда: < a,a,b> - кортеж длины 3 или тройка, - пара).



Примеры:

1.Слово в алфавите A есть кортеж.

2.Команда в программе для ЭВМ есть последовательность символов из алфавита языка программирования.

3.Алфавит русского языка есть кортеж длины 32.

4.Программа для ЭВМ есть кортеж кортежей.

5.Координаты точки в n-мерном пространстве образуют кортеж.



Пояснения:

1.В условной записи кортежа элементы, его образующие, называются компонентами (координатами).

2.Число компонент кортежа называется его длиной. Так, принято кортеж длиной два 1,a2> называть парой (или упорядоченной парой), кортеж длины три 1,x2,x3> - тройкой

3.Кортеж длины n можно интерпретировать как n-мерный вектор, или как точку в n-мерном пространстве, а каждую компоненты кортежа можно рассматривать в этом случае как проекции вектора на соответствующие оси.



Определение3. Декартовым (прямым) произведением множеств Mi(i=1…n) называется множество, элементами которого являются кортежи длиной n такие, что каждая

j-ая компонента есть элемент множества Mj.

Пi=1..nМi1 * М2 * …*Мn = {<x1,x2,...,xn>: xjMj, j=1..n}

Замечание:

В том случае, если M1=M2=…=Mn =М, то говорим об универсальном полном отношении и записываем: Мn (M2, M3 и т.д.)



Пример 1. Сколько вариантов окраски квадрантов круга возможно, если допускается пять цветов краски.

Решение: Поставленная задача всех вариантов окраски круга решается с привлечением математического понятия универсального отношения Mn.






, , ,…………,

Очевидно, что кортеж длины 4, каждая компонента которого есть цвет краски, есть элемент декартового произведения. Пусть цвета краски образуют множество M = {к, б, з, с, ф}. Тогда М4 = М  М  М  М и М4 = 54 = 625 (здесь условная запись |Mn| означает число картежей длины 4).

Пример 2. Всё множество координат всех клеток шахматной доски можно записать декартовым произведением вида {a,b,c,d,e,f,g,h}  {1,2,3,4,5,6,7,8} = {, …, , , …, , …, }. M1={a,b,c,d,e,f,g,h}, M2={1,2,3,4,5,6,7,8}, имеем число всех пар, т.е. |M1M2|, равным 64.

Определение 4. Подмножество S декартового произведения Пi=1..nМi называется n-арным соответствиeм элементов множеств Mi.

Формально S  Пi=1..nМi.

Частные случаи.


  1. Если n=2, то говорят о бинарном соответствии S  M1  M2 и пишут: q=1,M2,S>



  1. Если говорят о подмножестве кортежей универсального отношения Mn, то имеют в виду n-арное отношение R, т.е. R  Mn.

  2. R  M2 называют бинарным отношением на множестве M ( пишут: q=2>).

  3. Однозначное n-арное отношение есть n-местная функция

Пример функции:

р
В этом случае Rf P2 является функциональным (однозначным) бинарным отношением на множестве Р





p
Пример не являющийся функцией:




p


Это функциональное соответствие элементов двух множеств, т.е. Sf P×T



t
Пример. Пусть M = {х123} и R ={1, x1>,< x2, x1>,< x3, x1>}.

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



М Rf M


Замечание. Поскольку S является подмножеством, то можно говорить о нечётких соответствиях, отношениях, функциях.




Определение 5. Алгебраической n-арной (n-местной) операцией на множестве M называется n-местная функция у = f(x1,x2,…,xn), у которой область определения аргументов xi и область значений функции совпадают (n N).

Формальная запись f: MnM означает, что алгебраическая операция функциональна (однозначна) и замкнута.



Пояснение.

1. Тот факт, что алгебраическая операция является частным случаем бинарного однозначного соответствия (отражается в её формальной записи f: Mn  M.), можно пояснить графически:






Мn Mn
Rf


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

  1. Поскольку алгебраическая операция по n элементам множества M определяет (n+1) элемент этого же множества M, то n-местную алгебраическую операцию можно рассматривать и как (n+1)-арное однозначное отношение на множестве M.

  2. Если f: M  M, то говорят об унарной (одноместной) алгебраической операции; f: M2  M, то имеют в виду бинарную (двухместную) алгебраическую операцию.


Определение6. Алгебраической системой A называется кортеж , первая компонента которой M есть непустое множество, вторая компонента O – множество алгебраической операций, третья компонента R – множество отношений на множестве M.

Пояснение.

  1. Множество M алгебраической системы A называют несущим, или основным множеством.

  2. Совокупность алгебраических операций и отношений алгебраической системы называют сигнатурой . В этом случае алгебраическая система записывается парой .

  3. Алгебраическая система называется универсальной алгеброй (или просто алгеброй), если на основном множестве M множество отношений R пусто (т.е. R = ).

  4. Алгебраическая система A = называется реляционной системой (или моделью), если на основном множестве M заданы только отношения R (т.е. в этом случае пусто множество операций O, что означает O = )

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

Алфавит языка теории множеств.


А=А1А2А3А4




Основные символы

А1А2А3


Вспомогательные (разделительные) символы



Символы

операций А2



индивидуальные

общие

Знаки препинания

скобки

точка

двоеточие

круглые ( )

фигурные {}

прямые | |

угловые < >

Символы соответствий А3

Символы объектов А1

Индивидуальные

(собственные) символы соответствий



Общие символы соответствий

Индивидуальные (именные) символы объектов

Общие символы

объектов


Индивидуальные символы функций

индивидуальные символы отображений

индивидуальные символы отношений

функций

отображений

отношений

множеств

множеств

элементов множеств

элементов множеств



    1. Общие символы множеств и элементов множеств.

Общим обозначением множеств и элементов множеств соответственно являются заглавные и строчные буквы любого алфавита естественного языка (часто с индексами для одного символа).

Пример:

а) x,y,z – элементы множества М, т.е. M={x,y,z};

б) х1, х2, х3 – элементы множества Х, т.е. X={ х1, х2, х3}.


    1. Индивидуальные символы множеств:

Z – множество целых чисел;

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

Q – множество рациональных;

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

В(М) – булево множество (множество всех подмножеств данного множества М).

П(М) – множество разбиений множества М.

U – универсальное множество (множество, содержащее в качестве своих подмножеств любое множество).

Ø – пустое множество (часто записывают и так: {}, |M|=0 ).



    1. Индивидуальные символы элементов множеств.

Примем за имена конкретных элементов натуральные числа nN.

Примером далее изучаемых структурированных множеств является алгебраическая система (где O = {, } – множество из операции объединения  и операции дополнения , а R = {} – множество, состоящее из отношения включения ).

Алгебра Кантора (алгебра множеств) , (несущим множеством которой является булеан B(М) (т.е. множество всех подмножеств данного множества М), а множеством операций

O = {, , } - булевы операции объединения , пересечения  и дополнения ), алгебра логики.

Примерами реляционной системы является: метрическое пространство , (где P – метрика), языки науки - 1>, < A,S1,S2> ( здесь А - множество символов алфавита, S1,S2 –соответственно, отношения синтаксиса и семантики).

Примером является так называемое дискретное множество, т.е. множество (оно всегда дискретно!), на котором задано расстояние, причем любое из них не меньше некоторой величины ε.


Символический язык содержательных теорий множеств.

В процессе изучения курса будем различать объектный язык теории множеств и метаязык, средствами которого изучается объектный язык. Под языком теории множеств будем понимать реляционную систему L==< A,S1,S2>, основным множеством которой являются символы алфавита A, а отношения синтаксиса позволяют получать синтаксически правильные языковые выражения, среди которых выделяют формулы F.

В этом плане L = , B  A  A2  … An, F B.
Определение7. Алфавитом языка A теории множеств называют множество непересекающихся подмножеств символов объектов A1, операций A2, правил сопоставления A3, и разделительных знаков A4.

Формально A = A1  A2  A3  A4

A1  A2 = , A1  A3 = , A1  A4 = , A2  A3 = , A2  A4 = , A3  A4 =  (в этом случае говорят, что множество A разбито на подмножества). Графически это может быть представлено так:





Синтаксис языка L часто описывают формальной грамматикой. В этом случае формальная порождающая грамматика- кортеж, состоящий из множества терминальных Т (основных) символов, нетерминальных N символов, начального символа J и множества продукций P, т.е.

J =, где J - грамматика

TH=A, TH=, Jначальный символ (это нетерминальный символ)

Символический язык теории множеств может быть записан с помощью порождающей грамматики:

x, , , , , , , , , , ,  },

H={J,K}, J, P={J(JJ), J(JJ), J(J), J(JJ), J(JJ), J(JJ), J(JJ), J(JJ), J(JJ)

Этот язык теории множеств как множество формул F основные символы этой формальной порождающей процедуры (основные символы- обозначения множеств),



следующая страница >>



Хитрый дерется, пока мудрый уступает. Карел Чапек
ещё >>