Множества. Высказывания. Лекция 1

Август 21, 2022

Главная
Математика
Множества. Высказывания. Лекция 1

Содержание

2. Введение в информационные системы и технологии Технология при переводе с греческого означает искусство, мастерство, умение, а
3. Информационная система (ИС) - взаимосвязанная совокупность средств, методов и персонала, используемых для хранения, обработки и выдачи
4. Определение. Множеством называют совокупность элементов, объединенных по некоторому общему признаку. Примеры: множество курсантов, множество программ, множество
5. Определение. Множество А, содержащее конечное число элементов, называется дискретным конечным множеством. Определение. Множество, содержащее бесконечное число
6. Примеры. Множество А = {a1, а2, ... ,аn ... } содержит элементы а1, a2…, an,…; B=
7. Основные числовые множества: N=(1,2,3,4, …) – множество натуральных чисел; Z=(0,±1, ±2, ±3, ±4, …)– множество целых
8. Определение. Дополнением множества А называют множество D, которое состоит из элементов универсального множества U, не принадлежащих
9. Определение. Пересечением (или произведением) двух множеств А и В называют третье множество D, которое состоит из
10. Определение. Объединением или суммой двух множеств А и В называют третье множество D, которое состоит из
11. Определение. Разностью множеств А и В называют множество, состоящие из тех элементов множества А, которые не
12. Определение. Симметрической разностью множеств А и В называют множество С, определяемое, обозначаемое С=АΔВ и определяемое формулой
13. Некоторые свойства операций над множествами: A ∪ В = В ∪ А -коммутативность объединения множеств. А∩В
14. Порядок действий в формулах теории множеств. 1) Если в формуле нет скобок, то 1. Дополнение. 2.
15. Понятие соответствий и бинарных отношений Определение. Будем говорить, что между множествами X, Y установлено соответствие (зависимость
16. Пример. На предприятии: две грузовые автомашины α, β и автобус γ в штате три шофера а,
17. Определение. Композицией соответствий называют последовательное применение двух соответствий. Пример. Если Q - соответствие, определяющее распределение шоферов
18. Определение. Отображение f: X → Y является сюръективным, если каждый элемент y∈Y имеет хотя бы один
19. Пример 3. Если в примере 1 исключить из рассмотрения шофера с, и машину γ, то получим
20. Определение. Бинарным отношением R из множества А во множество В, называется подмножество декартового произведения А ×
21. Все пары (а,b) элементов из М, между которыми имеет место бинарное отношение R образуют подмножество из
22. Свойства бинарных отношений Определение. Отношение R, определенное на множестве X, называется рефлексивным, если хRх истинно, т.е.
23. Определение. Отношение R называется антисимметричным, если из хRу и уRх → х=y. Определение. Отношение R называется
24. Примеры отношений эквивалентности 1. отношение «быть на одном курсе», определенное на множестве курсантов факультета; 2. отношение
25. Пример. Пусть X — множество студентов первого курса. Определим на этом множестве бинарное отношение «быть студентом
26. Рассмотрим отношения порядка, которые определяют некоторый порядок расположения элементов множества на основе понятий «раньше» и «позже»,
27. Определение. Отношением строгого порядка на множестве Х называют отношение, обладающее следующими свойствами: 1. х 2. если
28. Определение. Пусть X – множество людей. Если х в чем-то превосходит у, то на множестве Х
29. Соответствие f называется: Всюду определенным, если область определения D(f)=A. Сюръективным, если область значений Е(f)=В. Однозначным, если
30. Пример. Из одного города в другой можно проехать по железной дороге (ж.д.), автобусом (авт.) или самолетом
31. Общее понятие функции Определение. Функцией называется биективное (одновременно сюръективное и инъективное) отображение Г: Х→Y. Такое отображение
33. Функции как отношения
35. Различные виды отношений
36. 1. Графиком. 2. Таблицей. 3. Формулой. 4. Реккурентной вычислительной процедурой (рекурсивная функция).
37. y = 3x (mod 7)
40. Степень, образованная из множеств Определим операцию возведения в степень. Для этого рассмотрим (для данных А и
43. Эквивалентность множеств Тот факт, что множества А и В эквивалентны между собой будем обозначать А⇔В и
44. Примеры. 1. Покажем, что множество натуральных чисел эквивалентно множеству четных положительных чисел. Для этого установим между
45. Из свойства эквивалентности множеств следует: 1. два ограниченных множества могут быть эквивалентны тогда и только тогда,
47. Скачать презентацию

Слайд 2

Введение в информационные системы и технологии
Технология при переводе с

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

Слайд 3

Информационная система (ИС) - взаимосвязанная совокупность средств, методов и персонала,

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

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

Слайд 4

Определение. Множеством называют совокупность элементов, объединенных по некоторому общему признаку.
Примеры: множество

курсантов, множество программ, множество функций, множество чисел.
Множества обозначаются большими буквами латинского алфавита A,B,C,…X,Y,Z а элементы множеств - соответствующими малыми буквами a, b, c,… возможно с нижними индексами, нумерующими сами элементы.

Понятие множества. Операции над множествами

Слайд 5

Определение. Множество А, содержащее конечное число элементов, называется дискретным конечным

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

Слайд 6

Примеры. Множество А = {a1, а2, ... ,аn ... } содержит

элементы а1, a2…, an,…; B= {1, +, 2, *}.
а ∈ А - элемент а принадлежит множеству А.
Определение. Множество В называют подмножеством множества А, если каждый элемент В является также и элементом множества А.
Любое множество является своим подмножеством.
Пустое множество является подмножество любого множества.

Слайд 7

Основные числовые множества:
N=(1,2,3,4, …) – множество натуральных чисел;
Z=(0,±1, ±2, ±3,

±4, …)– множество целых чисел;
Q=(m/n: m, n∈Z)– множество рациональных чисел;
R=(-∝,+∝)– множество вещественных (действительных) чисел.
Определение. Множество А равно множеству В, если эти множества содержат одни и те же элементы.

Слайд 8

Определение. Дополнением множества А называют множество D, которое состоит из элементов

универсального множества U, не принадлежащих множеству А.
Дополнение множества А изображается штриховкой на диаграмме Эйлера (рис. 1), где плоскостью показано универсальное множество U
Рис. 1. Диаграмма Эйлера для изображения
дополнения множества A

Слайд 9

Определение. Пересечением (или произведением) двух множеств А и В называют третье

множество D, которое состоит из элементов, принадлежащих одновременно множествам А, В.
Пересечение двух множеств А и В обозначается A∩В или А·В. Пишется D = A ∩ В или D =А·В.
Пример. А={1,3,5}, B={4,7,1,3}, тогда A ∩ B={1,3}
Рис. 2. Диаграмма Эйлера для изображения пересечения множеств A,B

Слайд 10

Определение. Объединением или суммой двух множеств А и В называют третье

множество D, которое состоит из элементов, принадлежащих хотя бы одному из множеств А, В.
Объединение двух множеств А и В обозначается A∪В или А+В. Пишется D= A ∪ В или D=А+В.
Пример. А={1,3,5}, B={4,7,1,3}, тогда A ∪ B={1,3,5,4,7}
Рис. 3. Диаграмма Эйлера для изображения объединения множеств A,B

Слайд 11

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

элементов множества А, которые не принадлежат В. Разность множеств В и А обозначается А\В.
Пример. А={1,3,5}, B={4,7,1,3}, тогда А\В={5}
Рис. 4.Диаграмма Эйлера для изображения объединения множеств A,B

Слайд 12

Определение. Симметрической разностью множеств А и В называют множество С, определяемое,

обозначаемое С=АΔВ и определяемое формулой
АΔВ=(А ∪В)\(А∩В)
Пример. А={1,3,5}, B={4,7,1,3}, тогда АΔВ ={5,4,7}.
Рис. 5. Диаграмма Эйлера для изображения симметрической разности множеств А,В

Слайд 13

Некоторые свойства операций над множествами:
A ∪ В = В ∪

А -коммутативность объединения множеств.
А∩В = В∩А -коммутативность пересечения множеств.
A∪(B∪C)=(A∪B)∪C -ассоциативность объединения множеств.
А∩(В∩С)=(А∩В)∩С -ассоциативность пересечения множеств.
A∩(B∪C)=A∩B∪А∩C - дистрибутивность пересечения относительно объединения.
A∪(B∩C)=(A∪B)∩(А∪C) - дистрибутивность объединения относительно пересечения.
Законы де Моргана
8. A∪(А∩C)=A –закон поглощения
9. A∩(А∪C)=A –закон поглощения
10. A∪А=A
11. A∩А=A

Слайд 14

Порядок действий в формулах теории множеств.
1) Если в формуле нет

скобок, то
1. Дополнение.
2. Пересечение.
3. Объединение, разность.
4. Симметрическая разность.
2) Если есть скобки, то сначала выполняются операции в скобках в порядке 1), затем вне скобок в порядке 1).

Слайд 15

Понятие соответствий и бинарных отношений
Определение. Будем говорить, что между множествами X,

Y установлено соответствие (зависимость между элементами множеств), если по заданному правилу каждому элементу множества А⊂Х сопоставляется элемент множества В ⊂ Y.
При этом совершенно необязательно, чтобы в сопоставлении участвовали все элементы множеств X и Y.

Слайд 16

Пример. На предприятии:
две грузовые автомашины α, β и автобус γ

в штате три шофера а, b, с, причем с - в отпуске. Любое распределение шоферов по машинам представляет собой соответствие.
Одним из возможных будет следующее соответствие: Q={(a, α), (a, γ), (b, α)}), в котором область определения соответствия А= {a, b}, область значений В={α, γ }(рис.6) и Q=A×B.
Рис.6.Соответствие между водителями и машинами: а - прямое соответствие, б - обратное соответствие.

Слайд 17

Определение. Композицией соответствий называют последовательное применение двух соответствий.
Пример. Если Q -

соответствие, определяющее распределение шоферов по автомашинам, Р - соответствие, определяющее распределение автомашин по маршрутам, то соответствие Q(P) есть соответствие, определяющее распределение шоферов по маршрутам.
Определение. Соответствие Q называется отображением множества X во множество Y, если в соответствии участвуют все элементы Х.
Обозначается отображение f: Х→Y. При этом, если
f(x) = y, то элемент y называется образом элемента x при отображении f, а элемент x называется прообразом элемента y при отображении f -1.

Слайд 18

Определение. Отображение f: X → Y является сюръективным, если каждый элемент

y∈Y имеет хотя бы один прообраз.
Определение. Отображение f: X → Y называется инъективным, если для любого элемента y∈Y существует не более одного прообраза.
Суръективное отображение f: {0,1,3,4} → {2,5,7,8} представлено на рис. 7.
Рис. 7. Суръективное отображение

Слайд 19

Пример 3. Если в примере 1 исключить из рассмотрения шофера с,

и машину γ, то получим сюръективное отображение f: Х→Y, в котором Х={а,b}- множество шоферов; Y={α, γ} - множество автомашин; отображение f={(а,α), (a,γ), (b.α)} - распределение шоферов по автомашинам (рис. 8).
Рис. 8. Геометрическое представление отображения.

Слайд 20

Определение. Бинарным отношением R из множества А во множество В, называется

подмножество декартового произведения А × В. В частн6ом случае множества А, В могут совпадать.
Бинарные отношения используются для определения каких-то взаимосвязей, которыми характеризуются пары элементов во множестве М.
На множестве людей могут быть заданы, например, следующие бинарные отношения: «быть студентом одной группы», «жить в одном городе», «быть моложе», «быть сыном», «работать в одной организации».

Слайд 21

Все пары (а,b) элементов из М, между которыми имеет место бинарное

отношение R образуют подмножество из множества элементов М×М=М2, т.е. (а, b)∈R, при этом R∈ М2.
Примеры бинарных отношений в математике: равенство, неравенство, эквивалентность, отношение порядка.
Пример. Пусть X — множество людей. Обозначим через Гх отношение быть ребенком человека х. Тогда композиция отношений Г(Гх)=Г2х — множество внуков человека х; Г3х - множество правнуков человека х; обратное отображение Г–1х - множество родителей человека х и.т.д.

Слайд 22

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

если хRх истинно, т.е. х находится в отношении х и антирефлексивным, если хRх ложно.
Определение. Отношение R называется симметричным, если из хRу → уRх, в противном случае - несимметричным.

Слайд 23

Определение. Отношение R называется антисимметричным, если из хRу и уRх →

х=y.
Определение. Отношение R называется транзитивным, если из хRу и уRz→ хRz.
Определение. Отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно, т.е. для любых элементов x,y,z, принадлежащих множеству Х имеет место:
1. хRх;
2. Если хRy, то yRx;
3. Если хRу и уRz, то хRz.

Слайд 24

Примеры отношений эквивалентности
1. отношение «быть на одном курсе», определенное на множестве

курсантов факультета;
2. отношение параллельности на множестве прямых плоскости.
Определение. Подмножество элементов, эквивалентных некоторому элементу х∈Х, будем называть классом эквивалентности.
Отношение эквивалентности разбивает множество на непересекающиеся подмножества, называемые классами эквивалентности.

Слайд 25

Пример. Пусть X — множество студентов первого курса.
Определим на этом

множестве бинарное отношение «быть студентом заданной группы», которое является отношением эквивалентности.
Тогда группа, в которой учится студент х∈Х, будет классом эквивалентности, эквивалентным этому студенту.
Отношение эквивалентности разбило исходное множество Х студентов первого курса на непересекающиеся классы эквивалентности (группы), объединение которых дает полное множество Х студентов первого курса.

Слайд 26

Рассмотрим отношения порядка, которые определяют некоторый порядок расположения элементов множества на

основе понятий «раньше» и «позже», «больше» и «меньше».
Различают отношение нестрогого порядка, для которого используется символ ≤, и отношение строгого порядка, для которого используется символ < .
Определение. Отношением нестрогого порядка на множестве Х называют отношение, обладающее следующими свойствами:
1. х ≤ х истинно (рефлексивность);
2. Если х ≤ y и y ≤ х истинно, то х=y (антисимметричность);
3. Если х ≤ y и y ≤ z истинно, то х ≤ z (транзитивность).

Слайд 27

Определение. Отношением строгого порядка на множестве Х называют отношение, обладающее следующими

свойствами:
1. х < х ложно (антирефлексивность);
2. если х < y истинно, то y < х ложно (несимметричность);
3. Если х < y и y < z истинно, то х < z (транзитивность).

Слайд 28

Определение. Пусть X – множество людей. Если х в чем-то превосходит

у, то на множестве Х определено отношение доминирования.
В этом случае говорят, что х доминирует над у, и пишут х>>y.
Отношение доминирования является:
- антирефлексивным (нельзя доминировать над самим собой);
- несимметричным(в каждой паре только один доминирует над другим);
- не является транзитивным.
Например, если в соревнованиях команда х победила команду y, а команда y победила команду z, то отсюда еще не следует, что команда х обязательно победит команду z.

Слайд 29

Соответствие f называется:
Всюду определенным, если область определения D(f)=A.
Сюръективным, если область

значений Е(f)=В.
Однозначным, если каждому a€D(f) соответствует единственный элемент из В, т.е. (а,b) €f и (а,b1) €f ↔ b= b1.
Инъективным, если разным элементам из D(f) соответствуют разные элементы из В, т.е.
(а,b) €f и (а1,b) €f ↔а=а1.
Определение. Отображение - это всюду определенное однозначное соответствие (свойства 1 и 3).
Определение. Биекцией называется всюду определенное, сюръективное, однозначное и инъективное соответствие (свойства 1-4).

Слайд 30

Пример. Из одного города в другой можно проехать по железной дороге

(ж.д.), автобусом (авт.) или самолетом (сам.). Стоимость билета равна соответственно 700, 900 и 1500 руб.
Стоимость билета можно представить как функцию от вида транспорта. Для этого рассмотрим множества Х={ж.д., авт., сам.}; У={700, 900, 1500}.
Функция f: X→Y представляется прямым произведением Х×Y, которое записывается в виде f={(ж.д., 700), (авт., 900), (сам., 1500)}.

Слайд 31

Общее понятие функции
Определение. Функцией называется биективное (одновременно сюръективное и инъективное) отображение

Г: Х→Y.
Такое отображение однозначно, т.е. если для любого x из множества X существует единственный элемент y из множества Y.
Множество X называется областью определения, а Y – областью значений функции.
Для обозначения функций применяются латинские буквы (f, g, h, ...).

Слайд 32

Слайд 33

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

Слайд 34

Слайд 35

Различные виды отношений

Слайд 36

1. Графиком.
2. Таблицей.
3. Формулой.
4. Реккурентной вычислительной процедурой (рекурсивная функция).

Слайд 37

y = 3x (mod 7)

Слайд 38

Слайд 39

Слайд 40

Степень, образованная из множеств
Определим операцию возведения в степень. Для этого рассмотрим

(для данных А и В) множество всех функций вида f(В)=А. Это множество обозначается АВ, и его мощность будет результатом операции возведения в степень.
Если множества А и В конечны и содержат a и b элементов соответственно, то АВ содержат аb элементов.

Слайд 41

Слайд 42

Слайд 43

Эквивалентность множеств
Тот факт, что множества А и В эквивалентны между собой

будем обозначать А⇔В и использовать представление

Слайд 44

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

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

Слайд 45

Из свойства эквивалентности множеств следует:
1. два ограниченных множества могут быть эквивалентны

тогда и только тогда, если числа их элементов равны.
2. Ограниченное множество никогда не может быть эквивалентным его некоторой части.

Множества. Высказывания. Лекция 1

Содержание

Введение в информационные системы и технологии Технология при переводе с

Информационная система (ИС) - взаимосвязанная совокупность средств, методов и персонала,

Определение. Множеством называют совокупность элементов, объединенных по некоторому общему признаку. Примеры: множество

Определение. Множество А, содержащее конечное число элементов, называется дискретным конечным

Примеры. Множество А = {a1, а2, ... ,аn ... } содержит

Основные числовые множества: N=(1,2,3,4, …) – множество натуральных чисел; Z=(0,±1, ±2, ±3,

Определение. Дополнением множества А называют множество D, которое состоит из элементов

Определение. Пересечением (или произведением) двух множеств А и В называют третье

Определение. Объединением или суммой двух множеств А и В называют третье

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

Определение. Симметрической разностью множеств А и В называют множество С, определяемое,

Некоторые свойства операций над множествами: A ∪ В = В ∪

Порядок действий в формулах теории множеств. 1) Если в формуле нет

Понятие соответствий и бинарных отношений Определение. Будем говорить, что между множествами X,

Пример. На предприятии:две грузовые автомашины α, β и автобус γ

Определение. Композицией соответствий называют последовательное применение двух соответствий. Пример. Если Q -