Презентация «Булевы отношения»

Pic.1

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

Pic.2

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

Pic.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 …

Pic.4

Примеры

Pic.5

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

Pic.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 …

Pic.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 является …

Pic.8

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

Pic.9

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

Pic.10

поскольку ……

Pic.11

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

Pic.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), тогда …

Pic.13

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

Pic.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)}. …

Pic.15

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

Pic.16

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

Pic.17

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

Pic.18

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

Pic.19

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

Pic.20

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

Pic.21

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

Pic.22

Определения Ориентированный граф, или орграф G состоит из множества V вершин и отношения E на V, называемого множеством ориентированных ребер или просто ребер, если понятно, что граф ориентирован. …

Pic.23

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

Pic.24

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

Pic.25

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

Pic.26

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

Pic.27

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

Pic.28

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

Pic.29

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

Pic.30

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

Pic.31

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

Pic.32

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

Pic.33

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

Pic.34

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

Pic.35

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

Pic.36

Определение

Pic.37

Pic.38

Pic.39

Pic.40

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

Pic.41

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

Pic.42

Пример Отношение R1 есть отношение эквивалентности на множестве А = {1, 2, 3, 4, 5, 6}. Классы эквивалентности по отношению R1 были получены путем определения класса эквивалентности каждого элемента …

Pic.43

Также:

Pic.44

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

Pic.45

Из примера видно, что любой элемент класса эквивалентности порождает класс эквивалентности. Если b  [a], то [a] = [b]. Любой класс эквивалентности представляет класс. Каждый класс эквивалентности …

Pic.46

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

Pic.47

Pic.48

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

Pic.49

Определения Совокупность классов эквивалентности разделяет все множество А на непустые взаимоисключающие, или непересекающие подмножества, в том смысле, что никакие два из них не имеют общих …

Pic.50

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

Pic.51

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

Pic.52

Последний слайд лекции

Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!