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

Если множество Мх в определении функции у=F(x) является декартовым произведением множеств М х1, М х2,…., М хn, то получаем определение n-местной функции у=F(х1, х2,….,хn).

1.8 Функция как отношение

Функцией называется функциональное соответствие.

Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция f имеет тип А="images/referats/7492/image053.png">В, обозначается f: АВ. каждому элементу а из своей области определения функция f ставит в соответствие единственный элемент b из области значений. Обозначается f(a)=b.

Элемент а называется аргументом функции, элемент b называется значением функции на а.

Полностью определенная функция f: AB называется отображением А и В.

Областью определения называется выражение D=

Функция называется инъективной, если из отношений (x1,y)f, (x2,y)f x1=x2

Функция называется сюръективной, если для каждого уY существует хХ.

Инъективная и сюръективная функции образуют биекцию – это взаимнооднозначное отношение множеств.

1.9 Отношение порядка

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

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

Элементы a,b сравнимы по отношению порядка, если выполняется aRb или bRa. Множество М, на котором задано отношение порядка называется полностью упорядоченным, если любые два элемента множества М сравнимы, в противном случае – частично упорядоченным.

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

Отношение эквивалентности

Отношение называется отношением эквивалентности (эквивалентностью), если оно одновременно рефлективно, симметрично и транзитивно.

Примеры:

1. отношение равенства на любом множестве является отношением эквивалентности;

2. утверждение вида (a+b)(b-a)=a2-b2 – формулы соединенные знаком равенства задают бинарное отношение. Такое отношение называют отношением равносильности. Оно отличается от равенства, т. к. может выполняться для различных формул.

3. Отношение подобия геометрических фигур, «быть соседями по квартире», «быть ровесниками» так же являются отношениями эквивалентности.

Каждое отношение эквивалентности является в определенном смысле равенством, например, отношение «быть ровесником» означает равенство возрастов.

Задание №3

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

Решение: необходимо проверить каждое из свойств отношений (аналогично заданию №2) и определить эквивалентность или порядок отношений.

2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

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

2.1 Преобразование к модели

1. Эксперимент на модели должен быть проще эксперимента на оригинале.

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

Существуют различные модели, которые используют в физике и математике.

В физике под моделью понимается реальный объект, в математике модель не обязательно является реальным объектом. однако суть этих моделей одинакова:

ü модель должна отражать характеристики и свойства объекта,

ü модель должна прогнозировать поведение объекта,

ü модель должна быть более простой, чем оригинал, но с другой стороны она должна как можно полнее отражать свойства объекта.

2.2 Способы моделирования

1. Макетное. Широко применяется в строительстве.

2. Физическое. Основой для такого моделирования является теория подобия.

3. Электрическое моделирование.

4. Математическое моделирование.

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

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

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

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

2.3 Алгебраические модели

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

3. ТЕОРИЯ КОДИРОВАНИЯ

В теории передачи информации существует проблема кодирования – декодирования, обеспечивающая надежную передачу информации при наличии помех.

Пусть А и В два конечных алфавита.

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

И R – некоторое множество конечных слов в алфавите А. Однозначное отображение множества R в некоторое множество слов в алфавите В называется кодированием множества R.

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

 Скачать реферат