Булевы отношения - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Булевы отношения. Доклад-сообщение содержит 52 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Булевы отношения

Слайд 2

Описание слайда:

Декартово произведение Отношением R множества А и В называется произвольное подмножество АВ. Если (a, b)R, записывают aRb. Говорят, что a и b находятся в отношении R, или a относится к b. Если А=В, то отношение есть подмножество АА; такое отношение называется бинарным отношением (или отношение) на А.

Слайд 3

Описание слайда:

Пример A={1, 2, 3}, B={r, s} AB= {(1,r), (1,s), (2,r), (2,s), (3,r), (3,s)} Тогда R={(1,r), (1,s), (3, s)} – отношение множеств А и В. (3, s)R 3Rs Множество А B содержит 6 элементов. 2^6=64 подмножеств множества А B 64 различных отношения на А B

Слайд 4

Описание слайда:

Примеры

Слайд 5

Описание слайда:

Определения Область определения отношения R на А и В есть множество всех хА таких, что для некоторых у В (х,у) R. Область определения R есть множество всех первых координат упорядоченных пар из R. Множество значений отношения R на А и В есть множество всех у В таких, что (х, у) R для некоторого хА. Множество значений R есть множество всех вторых координат упорядоченных пар из R.

Слайд 6

Описание слайда:

С каждым отношением R на A  B связано отношение R -1 на B  A. Пусть R AB есть отношение на AB. Тогда отношение R -1 на В А определяется следующим образом: R -1={(b, a): (a, b) R}. (b, a) R -1 тогда и только тогда, когда (a, b) R, что равносильно bR -1a тогда и только тогда, когда aRb. Отношение R -1 называется обратным отношением к данному отношению R.

Слайд 7

Описание слайда:

Примеры Пусть R={(1, r), (1, s), (3, s)}, тогда R -1 = {(r, 1), (s,1), (s, 3)}. Пусть {(x,y): x - является мужем y}, тогда R -1 – отношение {(x,y): у – жена х}. Пусть R – отношение {(x,y): y является родственником х}, тогда R = R -1. Пусть R – отношение {(x,y): х2 + y2 =4}, тогда R = R -1.

Слайд 8

Описание слайда:

Определение Пусть RAB – отношение на AB, а SBC – отношение на BC. Композицией отношений S и R называется отношение TAC, определенное таким образом: Т={(a, c): существует такой элемент b из B, что (a, b)R и (b, с)S}. Это множество обозначается Т = S  R.

Слайд 9

Описание слайда:

Пример Пусть А={1, 2, 3}, B={x, y}, C= Пусть отношения R на A  B и S на B  C заданы в виде: тогда

Слайд 10

Описание слайда:

поскольку ……

Слайд 11

Описание слайда:

Пример Пусть R и S – бинарные отношения на множестве положительных целых чисел, заданные в виде S = {(x, x+2): x – положительное целое число} и R = {(x, x2): x –положительное целое число} и R  S = {(x, (x+2)2): x – положительное целое число}

Слайд 12

Описание слайда:

Теорема Композиция отношений ассоциативна: если A, B, C и D – множества и если R  A  B, S  B  C и T  C  D, тогда T  (S  R ) = (T  S)  R. Доказательство: Пусть (a, d)  T  (S  R), тогда существует такое с  С, что (a, c)  S  R и (c, d)  T. Поскольку (a, c)  S  R, существует такое b  B, что (a, b)  R и (b, c)  S. Поскольку (b, c)  S и (c, d)  T, (b, d)  T  S. Поскольку (b, d)  T  S и (a, b) R, (a, d)  (T  S)  R. Таким образом, T  (S  R)  (T  S)  R. Вторая часть доказательства, что (T  S)  R  T  (S  R) аналогична.

Слайд 13

Описание слайда:

Определения Отношение R на AA называется рефлексивным, если (a, a) принадлежит R для всех a из А. Отношение R называется антирефлексивным, если из (a, b)  R следует a  b. Отношение R симметрично, если для всех a и b, принадлежащих А, из (a, b)  R следует, что (b, a)  R. Отношение R транзитивно, если для всех a, b и с из А, (a, b)  R и (b, с)  R, следует, что (a, c)  R. Отношение R называется антисимметричным, если для всех a и b из А, из принадлежности (a, b) и (b, a) отношению R следует, что a=b.

Слайд 14

Описание слайда:

Пример Пусть А = {1, 2, 3, 4, 5, 6} и пусть отношение R1  A  A есть множество R1 = {(1,1), (2, 2), (3, 3), (4, 4), (5, 5), (6,6), (1, 2), (1, 4), (2, 1), (2, 4), (3, 5), (5, 3), (4, 1), (4, 2)}. Отношение R1 рефлексивно, так как для каждого a  A, (a, a)  R1. Отношение R1 является симметричным:

Слайд 15

Описание слайда:

Отношение R1 является транзитивным: Проанализировав каждый возможный случай, когда (a, b)  R1 и (b, c)  R1, получаем (a, с)  R1 . R1 не является антисимметричным, поскольку (1, 2)  R1 и (2, 1)  R1 , но 1  2.

Слайд 16

Описание слайда:

Пример Пусть А – множество положительных чисел. Отношение R: (x, y) R, y кратно х. R рефлексивно, т.к. для каждого положительного числа n, n=1  n и (n, n)  R. R не является симметричным, так как (2, 4)  R, но (4, 2)  R. R антисимметрично, так как если (m, n)  R и (n, m)  R, тогда n кратно m и m кратно n, так что m=n. R транзитивно, потому что если (m, n)  R и (n, p)  R, тогда n кратно m и p кратно n, так что p кратно m и (m, p)  R.

Слайд 17

Описание слайда:

Определения Пусть R – бинарное отношение на множестве А. Рефлексивное замыкание R есть наименьшее рефлексивное отношение на А, содержащее R как подмножество. Симметричное замыкание R есть наименьшее симметричное отношение на А, содержащее R как подмножество. Транзитивное замыкание R есть наименьшее транзитивное отношение на А, содержащее R как подмножество.

Слайд 18

Описание слайда:

Теорема Пусть R – отношение на множестве А и I = {x: x=(a, a) для некоторого a  A}. Тогда: R  I есть рефлексивное замыкание R; R  R -1 есть симметричное замыкание R; Если А – конечное множество, содержащее n элементов, то отношение R  R 2  R 3  …  R n есть транзитивное замыкание R.

Слайд 19

Описание слайда:

Начальные сведения о графах. Подробно в о 2 семестре Граф – наглядное представление конечного антирефлексивного симметричного отношения Граф – конечное множество V, называемое множеством вершин, на котором задано симметричное антирефлексивное отношение R и выделено множество Е двухэлементных подмножеств V, определяемое как {a, b}  E тогда и только тогда, когда (a, b)  R и a  b. Множество Е называется множеством ребер. Всякий элемент Е называется ребром. Граф обозначается G(V, E). Элементы a и b графа V соединены или связаны ребром {a, b}, если {a, b}  E.

Слайд 20

Описание слайда:

Конечный граф изображается при помощи диаграммы, в котором вершины представлены точками, ребра, соединяющее вершины, линиями между точками. Пример Граф, в котором множество вершин V= {a, b, c}, E={{a, b}, {b, c}} может иметь вид или

Слайд 21

Описание слайда:

Пример Граф, в котором множество вершин V={a, b, c, d , e}, Е={{a, b}, {a, e}, {b, e}, {b, d}, {b, c}, {c, d}} имеет диаграмму

Слайд 22

Описание слайда:

Определения Ориентированный граф, или орграф G состоит из множества V вершин и отношения E на V, называемого множеством ориентированных ребер или просто ребер, если понятно, что граф ориентирован. Обозначается G(V, E) Элемент множества Е называется ориентированным ребром. Если (a, b)  E, тогда a называется начальной вершиной (a, b), b - его конечной вершиной.

Слайд 23

Описание слайда:

В случае ориентированного графа допускается наличие петель. Пример Орграф с вершинами V={a, b, c} и ребрами E={(a, b), (b, c), (c, b), (c, a)} Порядок имеет значение. (a, b) может быть ребром диаграммы, (b, a) – нет.

Слайд 24

Описание слайда:

Пример Орграф с вершинами V={a, b, c, d} и ребрами E={(a, b), (b, c), (c, c), (b, d), (c, d), (d, a)}

Слайд 25

Описание слайда:

Определение Отношение R на А есть отношение частичного порядка, если оно рефлексивно, симметрично и транзитивно. Если отношение R на А является отношением частичного порядка, то (А, R) называют частично упорядоченным множеством (или ЧУ-множеством с порядком R). Если отношение порядка R предполагается по умолчанию, то (А, R) можно обозначить просто через А.

Слайд 26

Описание слайда:

Пример (*) Пусть С = {1, 2, 3}, Х – множество всех подмножеств множества С: Определим отношение R на Х посредством (T, V)  R, если T  V. ({2}, {1, 2})  R, поскольку {2}  {1, 2} и ({1, 2}, {3})  R, поскольку {2, 3}  {3}. R – отношение частичного порядка, (A, R) – ЧУ-множество.

Слайд 27

Описание слайда:

Пример Пусть S – множество действительных чисел, R1 – отношение, определенное условием (x, y)  R1, если х  у. R1 – отношение частичного порядка, (S, R1) – ЧУ-множество. Обозначение. Частично упорядочение принято обозначать через  а ЧУ-множество - через (S, ).  -частичный порядок на множестве S.

Слайд 28

Описание слайда:

Определение Два элемента a и b ЧУ-множества (S, ) сравнимы, если a  b или b  a. Если каждые два элемента ЧУ-множества (S, ) сравнимы, то (S, ) называется вполне упорядоченным множеством, или цепью.

Слайд 29

Описание слайда:

Примеры Пусть Т – множество положительных делителей числа 30 и 1 есть отношение m 1 n, если m делит n нацело. Целые числа 5 и 15 сравнимы, поскольку 5 делит 15 нацело, а 5 и 6 – нет. Пусть А – множество целых чисел и R= 2 – отношение х 2 у, если х меньшее или равно у. Упорядоченное множество (А, 2) является цепью.

Слайд 30

Описание слайда:

Пример Пусть S – множество всех подмножеств множества {a,b,c} 3 есть отношение частичного порядка в примере (*). Множества {a, b} и {a,b,c} сравнимы, однако {a, b} и {b,c} таковыми не являются. ЧУ-множество (S, 3) цепью не является.

Слайд 31

Описание слайда:

Диаграммы Гессе Для изображения ЧУ-множеств. Для заданного ЧУ-множества (А, 2) диаграмма Гессе состоит из совокупности точек и линий, в которой точки представляют элементы А, и если a  c для элементов a и с множества А, тогда а помещено ниже с, и они соединены линией, если не существует такое b  a, c, что a  b  c. Если рассмотрение отношений ограничено отношениями частичного порядка, для них диаграммы Гессе – просто ориентированный граф, в котором петли не указаны. Если a  b  c, тогда линия от a к с не указана.

Слайд 32

Описание слайда:

Диаграмма Гессе, соответствующая множеству (Т, 1) Диаграмма Гессе, соответствующая множеству (Т, 1)

Слайд 33

Описание слайда:

Диаграмма Гессе, соответствующая множеству (S, 3) Диаграмма Гессе, соответствующая множеству (S, 3)

Слайд 34

Описание слайда:

Задания для самостоятельной работы 1. 2.

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

Определение

Слайд 37

Описание слайда:

Слайд 38

Описание слайда:

Слайд 39

Описание слайда:

Слайд 40

Описание слайда:

Пример Пусть множество А – набор разноцветных шаров, а отношение R задается условием: (a, b)  R тогда и только тогда, когда a и b имеют одинаковый цвет. Поскольку R – отношение эквивалентности, каждый класс эквивалентности будет состоять из шаров, имеющих одинаковый цвет. Если определить отношение R условием: (a, b)  R тогда и только тогда, когда шары a и b имеют одинаковый диаметр, то каждый класс эквивалентности будет состоять из шаров одинакового размерами.

Слайд 41

Описание слайда:

Определение Пусть a  A, и R - отношение эквивалентности на А  А. Пусть [а] обозначает множество {x: xRa} = {x: (x, a)  R}, называемое классом эквивалентности, содержащим а. Символ [A]R обозначает множество всех классов эквивалентности множества А по отношению R.

Слайд 42

Описание слайда:

Пример Отношение R1 есть отношение эквивалентности на множестве А = {1, 2, 3, 4, 5, 6}. Классы эквивалентности по отношению R1 были получены путем определения класса эквивалентности каждого элемента множества А: где 1 [1], поскольку (1, 1)  R1, 2 [1], поскольку (2, 1)  R1, 4 [1], поскольку (4, 1)  R1, и не существует иного х из А, что (х, 1)  R1. Также:

Слайд 43

Описание слайда:

Также:

Слайд 44

Описание слайда:

Имеется только три различных класса эквивалентности: поэтому

Слайд 45

Описание слайда:

Из примера видно, что любой элемент класса эквивалентности порождает класс эквивалентности. Если b  [a], то [a] = [b]. Любой класс эквивалентности представляет класс. Каждый класс эквивалентности содержит по крайней мере один элемент. В силу рефлексивности отношения, множество всех элементов, эквивалентных элементу а, должно содержать а. С другой стороны, никакой элемент не может принадлежать двум различным классом эквивалентности.

Слайд 46

Описание слайда:

Пример Рассмотрим отношение эквивалентности R3 и примера (**). Для множества А всех целых чисел R3  А  А определено посредством R3 = {(a, b): a – b = 5  k для некоторого целого числа k}. Поскольку следует

Слайд 47

Описание слайда:

Слайд 48

Описание слайда:

представляют собой различные классы эквивалентности по отношению R3 . Таким образом Элементы [0] “похожи” в том смысле, что каждый из них кратен пяти. Элементы другого класса эквивалентности “похожи” том смысле, что имеют один и тот же остаток при делении на пять.

Слайд 49

Описание слайда:

Определения Совокупность классов эквивалентности разделяет все множество А на непустые взаимоисключающие, или непересекающие подмножества, в том смысле, что никакие два из них не имеют общих элементов. Такое разделение множества называется его разбиением. Пусть A и I – множества и пусть А = {Ai : i  I}, где I непусто, есть множество непустых подмножеств множества А. Множество А называется разбиением А, если выполнены условия:

Слайд 50

Описание слайда:

Теорема Непустое множество подмножеств А множества А есть разбиение А тогда и только тогда, когда А = [A]R по некоторому отношению эквивалентности R.

Слайд 51

Описание слайда:

Пример Пусть Рассмотрим разбиение Необходимо определить R таким образом: R = {(a, b) : a  Ai и b  Ai для некоторого i }. Итак есть отношение, соответствующее данному разбиению.