Дискретная математика - (реферат)

Дата добавления: март 2006г.

    Дискретная математика
    Введение

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

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

В дисциплине мало методов, но много определений и терминов. В основе дискретной математике 4 раздела:

    Язык дискретной математики;
    Логические функции и автоматы;
    Теория алгоритмов;
    Графы и дискретные экстремальные задачи.

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

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

Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно сложные задачи (задачи перебора) и неразрешимые задачи.

Мы будем заниматься решением задач реальной размерности с учетом ограниченности временных и емкостных ресурсов ЭВМ.

    Множества и операции над ними
    Одно из основных понятий математики – множество.
    Определение:

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

    Множество обозначают: M, N …...
    m1, m2, mn – элементы множества.
    Символика
    A О M – принадлежность элемента к множеству;
    А П М – непринадлежность элемента к множеству.
    Примеры числовых множеств:
    1, 2, 3, … множество натуральных чисел N;
    …, -2, -1, 0, 1, 2, … - множество целых чисел Z.
    множество рациональных чисел а.
    I – множество иррациональных чисел.
    R – множество действительных чисел.
    K – множество комплексных чисел.

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

    А Н В – А подмножество В (нестрогое включение)
    Множества А и В равны, если их элементы совпадают.
    A = B
    Если А Н В и А № В то А М В (строгое включение).
    Множества бывают конечные и бесконечные.
    |М| - мощность множества (число его элементов).
    Конечное множество имеет конечное количество элементов.
    Пустое множество не содержит элементов: M = Ж.
    Пример: пустое множество:

1) множество действительных корней уравнения x2+1=0 пустое: M = Ж. 2) множество D, сумма углов которого № 1800 пустое: M = Ж.

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

Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики …

Если универсальное множество состоит из n элементов, то число подмножеств = 2n. Если , состоящее из элементов E, не принадлежащих А, называется дополненным. Множество можно задать:

    Списком элементов {a, b, c, d, e};
    Интервалом 1    Порождающей процедурой: xk=pk sinx=0;
    Операции над множествами

Объединение множеств А и В (союз или). Множество, состоящие из элементов, которые принадлежат хотя бы одному из множеств А или В называется объединенным.

    А И В

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

    Объединение двух множеств
    Объединение системы множеств можно записать
    - объединение системы n множеств.
    Пример: объединение множеств, когда они
    заданы списком.
    A = {a, b, d} B = {b, d, e, h} AUB = {a, b, c, d, e, h}

2) Пересечением множеств А и В называется множество, состоящие из элементов принадлежащих одновременно множествам А и В.

    A ЗB
    Пересечение прямой и плоскости

если прямые || пл. , то множество пересечений – единственная точка; если прямые II пл. , то M №Ж;

если прямые совпадают, то множество пересечений = множество прямой.

    Пересечение системы множеств:

Разностью 2-х множеств А и В называется множество, состоящее из всех элементов А, не входящих в В.

    С = А \ В
    A \ B
    А \ В
    A = {a, b, d}; B = {b, c, d, h} C = A \ B={a}.

В отличии от предыдущих операций разность: 1) строго двухместна; 2) не коммутативна, т. е. A\B № B\A.

    4) дополнение
    E – универсальное множество.
    -- дополнение

Операции объединения, пересечения и дополнения называются Булевыми.

    Основные законы операций над множествами.

Некоторые свойства И, Зпохожи на алгебраические операции, однако многие свойства операций над множествами все же отличаются.

    Основные свойства

AUB=BUA; AЗB=BЗA – переместительный закон объединения и пересечения. (АUB)UC = AU(BUC); (AЗB)ЗC=AЗ(BЗC) – сочетательный закон.

    АUЖ=A, AЗЖ=Ж, A \ Ж=A, A \ A=Ж
    1, 2, 3 – есть аналог в алгебре.
    3. а) Ж \ A = Ж - нет аналога.
    Ж; E \ A =; A \ E=Ж; AUA=A; AЗA=A; AUE=E; AЗE=A;

5. а) свойства 1-4 очевидны и не нуждаются в доказательствах. AЗ(BUC)=(AЗB)(AЗC) – есть аналогичный распределительный закон З относительно U.

    Прямые произведения и функции

Прямым декартовым “х” множеством А и В называется множество всех пар (a; b), таких, что аОА, bОB.

    С=AхВ, если А=В то С=А2.

Прямыми “х” n множеств A1x, …, xAn называется множество векторов (a1, …an) таких, что a1ОA1, …, AnОAn. Через теорию множеств введем понятие функции.

Подмножество FОMx x My называется функцией, если для каждого элемента хОMx найдется yОМу не более одного. (x; y)ОF, y=F(x).

Соответствие между аргументом и функцией можно изобразить с помощью диаграммы Венна:

Определение: Между множествами MX и MY установлено взаимноодназночное соответствие, если каждому хОMX соответствует 1 элемент yОMY и обратное справедливо. Пример: 1) (х, у) в круге

    x=2 а y=2
    y=2 а x=2...4
    не взаимнооднозначное соответствие.
    2) x = sinx
    Rа R

Пусть даны две функции f: AаB и g: BаC, то функция y: AаC называется композицией функций f и g. Y=f o g o – композиция.

    Способы задания функций:
    таблицы, определены для конечных множеств;
    формула;
    графики;
    Способы 1-3 частные случаи выч. процедуры.

Пример процедуры, не относящейся к 3 способам задания функций n! Взаимнооднозначное соответствие и мощности множеств.

Определение: Множества равномощны |A|=|B| если между ними взаимнооднозначное соответствие. Теорема: Если для конечного множества А мощность равна |A| то количество всех подмножеств 2|A|=2n.

Множества равномощные N называются счетными, т. е. в них можно выполнить нумерацию элементов. N– множество натуральных чисел.

    Множество N2 – счетно.
    Доказательство
    Разобьем N2 на классы
    К 1-ому классу отнесем N1 (1; 1)
    Ко 2-му классу N2 {(1; 2), (2; 1)}
    К i-му классу Ni (a+b=i+1
    Каждый класс будет содержать i пар.

Упорядоченный классы по возрастанию индекса i, а пары внутри класса упорядоченные по направлению первого элемента а.

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

    Аналогично доказывается счетность множеств N3, …, Nk.
    Теорема Кантора:

Множество всех действительных чисел на отрезке [0; 1] не является счетным.

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

Допустим это множество счетно изобразим его числа десятичными дробями.

    1-я 0, a11, a12 ….
    2-я 0, а21, a22 ….
    ………………….
    Возьмем произвольное число 0, b1, b2, b3
    b1 № a11, b2 № a22, …

Эта дробь не может выйти в последовательность т. к. отличается от всех чисел, значит нельзя пронумеровать числа на отрезке [0; 1].

Множество нечетно и называется континуальным, а его мощность континуум.

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

    Отношение
    Пусть дано RНMn – n местное отношение на множество М.

Будем изучать двухместные или бинарные отношения. Если а и b находятся в отношении R, то записывается а R b.

    Проведем отношение на множество N:
    А) отношение Ј выполняется для пар (7, 9) (7, 7_
    Б) (9, 7) не выполняется.
    Пример отношения на множество R

А) отношение находится на одинаковом расстоянии от начала координат выполняется для пар (3; 4) и (2; Ц21)

    Б) (3; 4) и (1; 6) не выполняется.

Для задания бинарных отношений можно использовать любые способы задания множеств.

Для конечных множеств используют матричный способ задания множеств. Матрица бинарного отношения на множество M={1; 2; 3; 4}, тогда матрица отношения С равна

Отношение Е заданные единичной матрицей называется отношением равенства. Отношением назовется обратным к отношением R, если ajRai тогда и только тогда, когда ajRai обозначают R-1.

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

Если aRa ==> очн. рефлексивное и матрица содержит на главной диагонали единицу если ни для какого а не … ==> отношение антирефлексивное

    главная диагональ содержит нули
    Пр. отношнний
    Ј рефлексивное
    < антирефлексивное

2. Если из aRb следует bRa, ==> отношение R симметричное. В матрице отношения элементы

сумм Cij=Cji. Если из aRb и bRa следует a=b ==> отношение R – антисимметричное. Пр. Если а Ј b и b Ј a ==> a=b

Если дано " a, b, c из aRb и aRc следует aRC ==> отношение называемое транзитивным. Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

    Пр. отношение равенства E

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

    если оно антирефлексивно, антисимметрично и транзитивно.
    Пр. а) отношение Ј u і для чисел отношение нестрогого
    б) отношение < u > для чисел отношение строгого
    Элементы общей алгебры
    Операции на множествах

Множество М вместе с заданной на нем совокупностью операций W = {j1, …, jm}, т. е. система А = {М1; j1, …, jm} называется алгеброй. W - сигнатура. Если M1МM и если значения j( M1), т. е. замкнуто ==> A1={М1; j1, …, jm} подалгебра A. Пр. 1. Алгебра (R; +; *) – называется полем действительных чисел обе операции бинарные и поэтому тип этой алгебры (2; 2)

    B=(Б; И; З) – булева алгебра. тип операций (2; 2; 1)
    Р. Свойства бинарных алгебраических операций
    запись ajb.
    1. (ajb)jc=aj(bjc) – ассоциативная операция
    Пр. +, x – сложение и умножения чисел ассоциативно
    2. ajb = bja – коммутативная операция
    Пр. +, x – коммутат.
    –; : – некоммут.
    умножение мат AЧB № BЧA – некоммутативно.
    3. aj(bjc) = (ajb) j(ajc) –дистрибутивность слева
    (ajb)jc) = (ajс) j(bjc) –дистрибутивность справа.

Пр. (ab)e=aebe – возведение в степень дистрибутивного отношения произведения справа но не abc № abac

    Гомоморфизм и изоморфизм

Алгебры с разными членами имеют различные строения. Алгебры с одинаковыми членами имеют сходство. Пусть даны две алгебры A=(K; jI) и B=(M; jI) – одинакового типа. Пусть отображение Г: KаM при условии Г(jI)= jI(Г), (1) т. е. результат не зависит от последовательности возможных операций: Или сначала вып. операцииjI b А и затем отображении Г, или сначала отображение Г, или сначала отображение Г и затем отображениеjI в В.

Тогда условие (1) называется Гомоморфизмом алгебры А в алгебру В. Когда существует взаимооднозначный гомоморфизм его называют изоморфизмом. В этом случае существует обратное отображение Г-1.

    Мощности изоморфных алгебр равны.

Пр. Алгебры (QN; +) и (Q2; +) – отображение типа и условие (1) запишется как 2(а+b)=2а+2b. Отношение изоморфизма является отношением эквивалентности на множестве алгебр, т. е вычисление рефлексивное, симметричности и транзитивности. Изоморфизм важнейшее понятие в математике. Полученные соотношения в алгебре А автоматически …. на изоморфные алгебры.