Презентация "Дискретная математика"

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

 

РАЗДЕЛЫ ДИСКРЕТНОЙ

МАТЕМАТИКИ

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

       Элементы математической логики

       Основы теории графов

ТЕОРИЯ МНОЖЕСТВ



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

•Множество •Множество листьев на точек на дереве. плоскости.

•Множество •N, R. слушателей в данной аудитории.

N 1,2,3,...

Ах: х 2k,k1,2,...2,4,6,...

1,22,1

ВА


1,2,35,6,7

k1

 

 


                                    AB                   AB          A\ B

 

 

                           AB Ø                  AB               A

 - универсальное множество.

Пусть А4;3;2;1;0;1;2,

                                    B4;3;2;1;0;1;2,

C4;3;2;1;0;1;2;3;4

a)АВ;б)АВ;в)АС;г)АС;д)ВС

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

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

Примеры:

«3 + 5 = 8» – истинно;

«7 – простое число» – истинно;

«Волга впадает в Чёрное море» – ложно; «Существуют внеземные цивилизации» – либо истинно, либо ложно;

«В романе Л.Н.Толстого «Война и мир» 3851385 букв» - либо истинно, либо ложно.

 

Обозначение: p, q, x, y  и т.д.

Обозначение: истина – «И», ложь – «Л».

Сложное или составное высказывание Составлено с помощью союзов «и», «или» и частицы «не» из простых высказываний.

 

Пример. 

«Москва стоит на берегу Оби» – ложно. «Новосибирск стоит на берегу Оби» - истинно.

«Москва не стоит на берегу Оби» – истинно.

«Москва стоит на берегу Оби или Новосибирск стоит на берегу Оби» – истинно.

«Москва стоит на берегу Оби и Новосибирск стоит на берегу Оби»  - ложно.

 

Операции над высказываниями

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

Читается «не р»  

Обозначение.  р

Таблица истинности

р

р

 

р

р

Л

И

0

1

И

Л

1

0

Определение.  Конъюнкцией двух высказываний р и q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.

Читается «р и q»  

Обозначение.  рq

Таблица истинности

р

q

рq

Л

Л

Л

И

Л

Л

Л

И

Л

И

И

И

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

Обозначение.  рq Читается «р или q»  

Таблица истинности

р

q

рq

Л

Л

Л

И

Л

И

Л

И

И

И

И

И

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

Читается

 «р влечёт q»

«если р, то q» «из р следует q» р – посылка импликации q – заключение импликации  

р

q

р

Л

Л

И

И

Л

Л

Л

И

И

И

И

И

Обозначение.  рq

Таблица истинности

q

Определение.  Эквиваленцией двух высказываний р и q называется высказывание, истинное тогда и только тогда, когда истинные значения р и q совпадают.

Читается

 «р эквивалентно q»

Обозначение. p~q  

Таблица истинности

р

q

p~q

Л

Л

И

И

Л

Л

Л

И

Л

И

И

И

р

Л

И

И

Л

х

у

Л

Л

 

 

 

И

Л

 

 

 

Л

И

 

 

 

И

И

 

 

 

р

q

рq

Л

Л

Л

И

Л

И

Л

И

И

И

И

И

f x, y x y;

ОСНОВЫ ТЕОРИИ ГРАФОВ

Теория графов – это один из подразделов математики, главным отличительным признаком    которого является геометрический метод в изучении объектов. Основателем ее принято    считать известного математика Л.

Эйлера. - Читайте подробнее на

FB.ru: https://fb.ru/article/46447/teoriyagrafov

     Графы строят для того, чтобы отобразить отношения на множествах. Пусть, например,

множество A = {a1, a2, ... an} - множество людей, а каждый элемент будет отображён в виде точки.

Множество B = {b1, b2, ... bm} - множество связок (прямых, дуг, отрезков - пока не важно). На множестве A задано отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой. Естественно, число знакомых у одних людей может отличаться от числа знакомых у других людей, а некоторые вполне могут и не быть ни с кем знакомы (такие элементы будут точками, не соединёнными ни с одной другой). Вот и получился граф!

       Пример 1. Пусть A - множество чисел 1, 2, 3: A = {1, 2, 3}. Построить граф для отображения отношения "<" ("меньше") на этом множестве.

ОРИЕНТИРОВАННЫЙ ГРАФ

Пример 2. Пусть A - множество чисел 2, 4, 6, 14: A = {2, 4, 6, 14}. Построить граф для отображения отношения "делится нацело на" на этом множестве.

СМЕШАНЫЙ ГРАФ

       Пример 3. Пусть даны

множества A = {α, β, γ} и B = {a, b, c}. Построить граф для отображения отношения "декартово произведение множеств".

ДВУДОЛЬНЫЙ ГРАФ

       Пример 4. В агентстве по недвижимости работают менеджеры Игорь, Сергей и Пётр. Обслуживаются объекты О1, О2, О3, О4, О5, О6, О7, О8. Построить граф для отображения отношений "Игорь работает с объектами О4, О7", "Сергей работает с объектами О1, О2, О3,

О5, О6", "Пётр работает с объектом О8".

Информация о публикации
Загружено: 29 мая
Просмотров: 1294
Скачиваний: 20
Елфимова Наталья Александровна
Математика, СУЗ, Презентации