Шпоры по дискретной математики - файл n1.doc

приобрести
Шпоры по дискретной математики
скачать (565.3 kb.)
Доступные файлы (1):
n1.doc1935kb.15.06.2009 15:09скачать

n1.doc

  1   2   3   4
1

Множество – совокупность определённых и различных между собой объектов мыслимых как единое целое.

Объекты входящие в мн-во назыв элементами.

Мн-во А назыв подмн-ом мн-ва B, если всякий элемент из А явл элементом B:



Если А В, В А, то А – Собственное подмн-во мн-ва В.

Мн-во не содерж эл-ов назыв пустым

Мн-ва А и В назыв равными, если состоят из одних и тех же эл-ов.

А В, В А А=В

2А=р(А) – булеан мн-ва – мн-во всевозможных подмн-в заданного мн-ва.

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

Формы задания:

  1. Перечисление А={a1, a2,, an}

  2. Предикатом A={x|p(x)}

  3. С помощью порождающей ф-ции A={x|x=a}

Операции: - пересеч

- объединен

- разность

- семетрич разность

- абсолют дополнение

Диаграмма Элера-Венна – геом схема с помощью которой можно изобразить отношение между подмн-ами, для наглядного представления .Где универс мн-во изображ как прямоугол, а все остальные как окруж.

4

Диаграмма Хасе – графическое представление частич упорядоч мн-ва р= в котором с каждой точкой их Х сопоставляется точка плоскости таким образом, что меньшеая точка всегда расположена ниже большей.

Пр.



– линейно упорядоченное множество
Два частично упорядоченных множества называются изоморфными.

х, у – изоморфные

сохраняется порядок

– биективная

изоморфизм частично упорядоченных множеств

2. основные тождества

1) – закон иденпедентности;

2) ; – закон коммутативности;

3) – закон ассоциативности;

4) – закон поглощения;

5) – модулярный закон;

6) – закон дистрибутивности;

7) – закон дистрибутивности;

8) ;

9) – закон дополняемости;

10) – Правило Де Моргана.
Метод включений:



Доказательство:

и



и ( или )

( и ) или ( и )

и

и

Доказательство с использованием характеристической функции.

- каппа А

Правила характеристической функции:

1) ;

2) ;

3) ;

4) ;

5) ;

.

С помощью формы от х

А  (В С) = {x | A и x  (В С)} =  {x | A и (x В или С)} =
= {x |(x A и x В)  или ( A и С)} = (А В)  (А С).

С помощью тождеств

А  (A B) = (A A)  (A B) = A  (A B) = A.  


3

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



Бинарное отношение – множество упорядоченных пар.

Областью определения для отношения и областью значений являются:



Декартово произведение двух множеств.



Обратное отношение : .

Композиция двух отношений и .



Определение: Функцией называется некоторое отношение , если .

Определения:

- инъективная функция ;

- сюрьективная функция ;

- биективная функция одновременно является и инъективной, и сюрьективной.

Утверждение 1: Если f1 – функция и f2 – функция, то – функция.
Отношением линейного порядка называется отношение частичного порядка такое, что или , или (отношение полного порядка).

Если на множестве X задано отношение частичного порядка, то множество X называется частично упорядоченным.

Если на множестве X задано отношение линейного порядка, то множество X называется линейно упорядоченным.

Если на множестве X задано отношение полного порядка, то множество X называется вполне упорядоченным.

Все они полностью упорядочены.

5 Функция Мёбиуса.

Пусть задано конечное частично упорядоченное множество с отношением частичного порядка .

Рассмотрим последовательность функций:



При

Определение. Функцией Мёбиуса называется функция, определяющаяся по формуле: .

Теорема о произведении.

Пусть задано и ; и – их функции Мёбиуса. Имеет место следующее равенство:


7

Типы отношений:

Рефлексивное / иррефлексивное .

Симметричное если , то /антисимметричное если .

Транзитивное если .

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

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

Классом эквивалентности [x], порожденным элементом x, называется подмножество элемента x, состоящее из тех элементов x, для которых .

Разбиение множества x – семейство:

– элемент разбиения.

Фактор множества – совокупность классов эквивалентности этого множества.


8

Фактор множества – совокупность классов эквивалентности этого множества.

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

Бинарное отношение называется толерантностью, если оно рефлексивно и симметрично.

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

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

Энарной алгебраической операцией на множестве М называется функция вида

n – .

– унарная операция;

– бинарная операция;

– триарная операция.

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

Свойства:

1) Коммутативность: ; .

2) Ассоциативность: ; .

Нейтральный элемент множества М для бинарной алгебраической операции называется элемент:

;

.


6

Формула обращения.

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

1) ;

2) .

Доказательство:

Пусть матрица А – матрица смежности для . Тогда выполнение равенства (1) равносильно , .

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

Получим равносильность из (1) в (2). #

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

Справедливость метода математической индукции.

  1. Базис по индукции. Пусть P(1) – верно, т.е. верно P(k) для некоторого .

  2. Индуктивный шаг. Если (P+k) – верно, то P(n) – верно.

Лемма. Множество является решеткой относительно операций , max, min.

Докажем метод математической индукции от противного.

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

Пусть они образуют множество – решетка min(m,k)=m.

  1. Если , то противоречие с первым условием.

  2. Если , то (m-1) – не натуральное.

P(m-1+1) – верно, значит, P(m) – верно (противоречие со вторым условием). #


9. Мультипликативные и аддитивные формы. Суперпозиция функций.

Мультипликативная функция ― арифметическая функция одного аргумента f(m), удовлетворяющая условию

f(mn) = f(m)f(n) для любой пары взаимно простых чисел m и n. Обычно предполагается, что f не равна тождественно нулю (что равносильно условию f(1) = 1).

МУЛЬТИПЛИКАТИВНАЯ ФУНКЦИЯ называется сильно мультипликативной, если f(p^?) = f(p) для всех простых p и всех натуральных ?. Если условие мультипликативности выполняется для произвольных двух чисел m и n не обязательно взаимно простых, то f называется вполне мультипликативной; в этом случае f(p^?) = f(p)^?

Примеры

Функция ?(m) ― число натуральных делителей натурального m.

Функция a(m) ― сумма натуральных делителей натурального m.

Функция Эйлера ?(m).

Функция Мёбиуса ?(m).

Функция является сильно мультипликативной.

Степенная функция f(m) = m^? является вполне мультипликативной.

АДДИТИВНАЯ ФУНКЦИЯ кольца ― группа, элементами которой являются все элементы данного кольца, а операция совпадает с операцией сложения в кольце.

Суперпозиция функций.

Суперпозицией булевых функций f0 и f1,...,fn называется функция f(x1,...,xm) = f0(g1(x1,...,xm),...,gk(x1,...,xm)), где каждая из функций gi(x1, ...,xm) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1,...,fn.
10. Решетки, дистрибутивные решетки. Булеан и теорема о числе элементов множества всевозможных подмножеств заданного множества.
Решетка — это множество М с двумя бинарными операциями , такими что выполнены следующие условия (аксиомы решетки):

1. идемпотентность:

а а = a, aa = а;

2. коммутативность:

аb = bа ab = ba;

3. ассоциативность:

b) с = а (b с), (а b) с = а (b с);

4. поглощение:

B) а = а, b) a = а;

5. Решетка называется дистрибутивной, если

a(bc)= b) с), а (bс) = b) с).
Булеан и теорема о числе элементов множества всевозможных подмножеств;

Множество всех подмножеств множества М называется булеаном и обозначается 2м:



ТЕОРЕМА Для конечного множества М .

Доказательство;

Индукция по |M|. База: если |M |=0, то и . Следовательно, .

Индукционный переход: пусть . Рассмотрим .

Положим M1:=и M2:= .

Имеем 2M= M1 M2 и M1 M2=. По индукционному предположению |M1|=2k-1, |M2|=2k-1. Следовательно, |2M|=|M1|+|M2|=2k-1+2k-1=.

Пересечение, объединение и разность подмножеств множества U (универсума) являются подмножествами множества U. Множество всех подмножеств множества U с операциями пересечения, объединения, разности и дополнения образует алгебру подмножеств множества U.

№ 11. Диагональный метод Кантора, счетные и несчетные множества.
Рассмотрим квадратную таблицу nЧn клеток, в которой некоторые клетки заштрихованы, а остальные клетки — белые. Пусть нам нужно построить такую строку, которой нет в этой таблице. Если n конечно, то это возможно, выписав диагональ матрицы в строчку, и перекрасив цвета на противоположные, если же n стремится к бесконечности, то

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

Из этого вытекает следующий замечательный факт, невозможно все бесконечные последовательности из нулей и единиц выписать в таблицу.
Счетные и несчетные множества.
Пусть N множество всех натуральных чисел N={1, 2, 3, . . .}, тогда всякое множество А эквивалентное множеству N будет называться исчислимым, или счётным множеством а неэквивалентное несчетным.

Для того чтобы множество Х было счётным необходимо и достаточно, чтобы его можно было «перенумеровать», то есть представить в форме последовательности: Х={x, x, x, . . . ,x, . . . } .

Доказательство необходимости: Пусть множество Х счетное, то из определения счётного множества следует существование взаимно однозначного соответствия j между множеством Х и множеством натуральных чисел N. Достаточно обозначить через х, тот из элементов множества Х, который в соответствии с j отвечает числу n,чтобы получить представление множества Х в форме (*).

Доказательство достаточности: Если множество Х представлено в форме (*), то достаточно каждому его элементу х, соотнести индекс n этого элемента, чтобы получить взаимно однозначного соответствия j между множеством Х и множеством натуральных чисел N, так что из определения счётного множества следует, что множество Х счётное.
13. Парадокс Рассела. Основной принцип комбинаторики. Число элементов декартового произведения множеств.
Парадокс Рассела — открытая в 1903 году Бертраном Расселом и позднее независимо переоткрытая Э. Цермело теоретико-множественная антиномия, демонстрирующая противоречивость наивной теории множеств Г. Кантора.

Антиномия Рассела формулируется следующим образом:

Пусть K — множество всех множеств, которые не содержат себя в качестве своего элемента. Содержит ли K само себя в качестве элемента? Если да, то, по определению K, оно не должно быть элементом K — противоречие. Если нет — то, по определению K, оно должно быть элементом K — вновь противоречие.

Существует много популярных формулировок этого парадокса. Одна из них традиционно называется парадоксом брадобрея и звучит так:

Одному деревенскому брадобрею приказали «брить всякого, кто сам не бреется, и не брить того, кто сам бреется», как он должен поступить с собой?
Основной принцип комбинаторики.

Если А и В – мн-ва и

Предположим утверждение неверно:

а) , тогда противоречит (фи)-биек

б) , тогда противоречит (фи)-биек
Число элементов декартового произведения множеств.

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


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации