Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Математика->Реферат
ИНТЕГРАЛ (от лат. Integer - целый) - одно из важнейших понятий математики, возникшее в связи с потребностью, с одной стороны отыскивать функции по их ...полностью>>
Математика->Реферат
Человек проявляет интерес к правильным многогранникам на протяжении всей своей сознательной деятельности – от двухлетнего ребенка, играющего деревянны...полностью>>
Математика->Лабораторная работа
37мм. 0,1171мм . Среднее квадратичное отклонение: 0.07 5мм. Граница случайной погрешности … .78*0.07 5=0. 13мм, где tP,n — коэффициент Стьюдента для ч...полностью>>
Математика->Курсовая работа
Карпова Ю.А. Методы нахождения условного и безусловного экстремума: ТПЖА 220201.052 ПЗ: Курс. работа / ВятГУ, каф. АТ; рук. В. И. Микрюкова.– Киров, 2...полностью>>

Главная > Лекция >Математика

Сохрани ссылку в одной из сетей:

68


Содержание

1. ТЕОРИЯ МНОЖЕСТВ 2

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

1.2 Графическая интерпретация множеств и операций над ними 3

1.3 Свойства операций 5

1.4 Тождества и их доказательство 6

1.5 Отношения на множествах 7

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

1.7 Декартово произведение множеств 9

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

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

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

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

2 МАТЕМАТИЧЕСКАЯ ЛОГИКА. АЛГЕБРА ЛОГИКИ. 24

3. БУЛЕВА АЛГЕБРА 28

3.1 Совершенные нормальные формы 30

3.1.1 Совершенная дизъюнктивная нормальная форма 30

3.1.2Разложение по переменным 31

3.1.3 Алгоритм преобразования формулы в СДНФ 33

3.2 Совершенная конъюнктивная нормальная форма (СКНФ) 37

3.2.1Алгоритм преобразования формулы в СКНФ 37

4 ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ 42

4.1 Равносильные формулы и их доказательство 42

4.2Равносильные формулы 43

4.3 Доказательство равносильностей 46

Основные тавтологии 49

Доказательство утверждений 49

5. БУЛЕВЫ ФУНКЦИИ 50

5.1 Полнота системы булевых функций 50

6. ЛОГИКА ПРЕДИКАТОВ 52

6.1 Операции над предикатами 53

6.2 Кванторы 53

6.3 Формулы 55

7. ТЕОРИЯ ГРАФОВ 57

7.1 Понятие смежности 57

7.2 Матрица инцидентности и списки ребер 59

7.3 Матрица смежности графа 61

7.4 Операции над членами графов 62

9. ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ 64

ЛИТЕРАТУРА 67

ПРИЛОЖЕНИЕ I 68

1. ТЕОРИЯ МНОЖЕСТВ
1.1 Понятие множества и подмножества

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

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

Объекты, составляющие множество называются элементами этого множества.

Множества обозначаются большими латинскими буквами, а элементы – маленькими латинскими буквами.

Если элемент а принадлежит множеству А, то будем использовать запись , в противном случае используется запись .

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

Множество можно задать различными способами. Самые распространенные это: перечисление элементов: ; указание свойств элементов: , (после двоеточия указаны свойства х).

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

- знак нестрогого включения (говорят В содержит или покрывает А).

- знак строгого включения.

- не включение.

Очевидно: если и , то эти множества состоят из одних и тех же элементов и А=В.

1.2 Графическая интерпретация множеств и операций над ними

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

Над множествами выполняются три двуместные операции:

  • Пересечение;

  • Объединение;

  • Разность множеств.

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

АВ

Пример:

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

АВ

Пример:

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

А\ В из А вычесть В

Пример:

.

Кроме рассмотренных двухместных операций существует одна одноместная операция – дополнение. Дополнением множества М является множество (не М) = .

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

1.3 Свойства операций
  1. Ассоциативность;

  2. Коммутативность;

  3. Дистрибутивность.

Операция называется ассоциативной, если выполняется равенство:

.

Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении можно не расставлять. Сложение и умножение чисел - ассоциативные операции, что и позволяет не ставить скобки (пример: a+b+c; abc) пример неассоциативной операции: возведение в степень (ab)c здесь скобки необходимы.

Операция называется коммутативной, если выполняется условие: . Сложение и умножение являются коммутативными (от перемены мест слагаемых сумма не меняется). Вычисление и деление – некоммутативные, некоммутативной так же является операция умножения матриц.

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

1.4 Тождества и их доказательство

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

Доказать, что M=N, где M и N – выражения с множествами.

Доказательство производится в два этапа: 1) «в одну сторону», 2) «в обратную сторону».

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

«если , то ».

  1. На втором этапе предполагается, что элемент х принадлежит правой части равенства: .

Пример №1

Доказать тождество:

.

Решение:

  1. ;

  2. .

1.5 Отношения на множествах

Отношения бывают одноместными, двуместными (бинарными) и n-местными. Одноместное отношение– это просто подмножество. Мы остановимся на бинарных отношениях.

  1. упорядоченная пара (x, y) есть совокупность двух элементов записанных в определенном порядке.

  2. Две пары (x, y) и (x1, y1) считаются равными тогда и только тогда x1 = х, y1 = y.

  3. Прямым произведением x y называется совокупность пар (x,y)таких, что .

Можно привести следующие примеры бинарных отношений:

  • Отношение «иметь общий делитель отличный от 1» выполняется для пар (6,9); (4,2); (2,4); (4,4), но не выполняется для пар (7,9); (4,7).

  • Отношение «быть делителем», т. е. x делит y выполняется для пар (2,4); (4,4), но не выполняется для пар (4,2); (7,9).

  • Отношение выполняется для пар (7,9); (7,7), но не выполняется для пары (9,7).



Похожие страницы:

  1. Дискретная математика (5)

    Реферат >> Математика
    ... является дискретной. Дискретная математика – область математики, занимающаяся изучением свойств дискретных ... n-1 место для положений вертикальных линий. Это ... Ориентированные и неориентированные графы. Основные понятия для неориентированных и ориентированных ...
  2. Дискретная математика. Теория вероятностей и математическая статистика

    Книга >> Математика
    ... Социально – психологического факультета. СОДЕРЖАНИЕ ДИСКРЕТНАЯ МАТЕМАТИКА 3.1. Элементы теории множеств ………..……….………………………....... ... ДИСКРЕТНАЯ МАТЕМАТИКА 3.1. Элементы теории множеств Понятие множества является одним из основных первичных понятий математики ...
  3. Дискретная математика. Курс лекций

    Конспект >> Математика
    ... понятие дискретной математики ... В находятся в общем положении. Пересечение множества А ... поглощения А(АВ)=А А(АВ)=А; _ _ 9.Законы Порецкого А(АВ)=АВ А(АВ)=АВ ; Следствием основных законов являются следующие соотношения: _ _ АI=A ; AI=I ; AA= ...
  4. Основные положения теории переходных процессов

    Реферат >> Физика
    ... Физики Реферат на тему: «Основные положения теории переходных процессов в ... учитывают при расчете усилителей дискретных сигналов, фазосдвигающих цепочек, ... которое решается относительно известными из математики методами. Аналогичное уравнение получается ...
  5. Основные положения синтеза электрических цепей

    Реферат >> Физика
    ... Кафедра Физики Реферат «Основные положения синтеза электрических цепей» Орёл ... была впервые сформулирована великим русским математиком П.Л. Чебышевым (1821-1894), ... то результаты решения непрерывной и дискретной задач чебышевского приближения совпадают, ...

Хочу больше похожих работ...