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

Содержание

• 
  Слайд 1

  Дискретная математика

  Отношения. Бинарные отношения и их свойства

• 
  Слайд 2
  

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

• 
  Слайд 3
  

  Подмножество называетсяn-местным отношениемR на непустом множестве М. При n=2 отношение R называется бинарным. То есть бинарным отношением между элементами множеств А и В называют любое подмножество R множества АхВи записывают R АхВ. Для отношения R обратным является отношение R-1  BxA.

• 
  Слайд 4

  Композиция отношений

• 
  Слайд 5
  

  Бинарные отношения принято записывать в виде aRb, где а, b М. Запись читается как «а и b находятся в отношении R». Например, а||b (параллельные прямые), а b (действительные числа), а = logc b и т.д. Рассмотрим примеры бинарных отношений. Бинарное отношение R: х  у показано на рис. Заштриховано множество точек, для координат которых это отношение выполняется (истинно).

• 
  Слайд 6
  

  Графики прямых и обратных бинарных отношений, определенных на множестве действительных чисел, симметричны относительно биссектрисы I и III квадрантов. Это свойство обратных бинарных отношений используют при построении графиков обратных функций, например: у = log2x иу=2х Пример 1. у = х2и у = x, где х О (рис. a);

• 
  Слайд 7
  

  Пример 2. у = sinx и у = arcsinx, где 0 х /2 (рис. б).

• 
  Слайд 8

  Свойства бинарных отношений:

  1) рефлексивность: Например: «быть не больше»; «быть делителем» на множестве N; «быть коллинеарным» на множестве векторов;

• 
  Слайд 9
  

  2) антирефлексивность: Это отношение имеет место, когда оно не обладает свойством 1 для любых а, например: «быть больше», «быть младше», «быть перпендикулярной» на множестве прямых и др.

• 
  Слайд 10
  

  3) симметричность: Отношение R на множестве М называется симметричным, если для любых a, b  M одновременно справедливо aRb и bRa (т.е.R=R-1). Например: Симметрична параллельность прямых, так как если а ||b, то b || а. Симметрично отношение «быть равным» на любом множестве или «быть взаимно-простым» на N.

• 
  Слайд 11
  

  4) антисимметричность: Если для несовпадающих элементов а  b верно отношение aRb, то ложно bRa. Антисимметричными являются отношения «быть больше», «не меньше» на множестве R, «быть делителем» на множестве N и др.

• 
  Слайд 12
  

  5) транзитивность: Если aRb и bRc, то aRс для любых a, b, c  M. Транзитивны отношения «быть больше», «быть параллельным», «быть равным» и др.

• 
  Слайд 13
  

  6) антитранзитивность: Имеет место, когда отношение не обладает свойством 5. Например, «быть перпендикулярным» на множестве прямых плоскости ( а  b, b  с, но неверно aс).

• 
  Слайд 14
  

  7) асимметричность: Ни для одной пары а и b не выполняется одновременно aRb и bRa. Например: «быть больше»; «быть меньше»; «быть отцом».

• 
  Слайд 15
  

  8) связность: Для любых аи b, если а b, то aRb или bRa. Например: «быть больше», «быть меньше» на множестве N, R; «быть больше или равным», «быть меньше или равным» на множестве обыкновенных дробей. Каждое конкретное отношение может обладать или не обладать указанным свойством. или

• 
  Слайд 16

  Свойства бинарных отношений

• 
  Слайд 17

  Основные виды бинарных отношений.

  Бинарное отношение R называется отношением эквивалентности, если оно одновременно обладает тремя свойствами: рефлективностью, симметричностью и транзитивностью, т.е. если для любых х, у, z выполняется: • xRx (рефлективность); • если xRy, то уRх (симметричность); • если xRy, a yRz, то xRz (транзитивность).

• 
  Слайд 18
  

  Примеры отношений эквивалентности: Отношение «быть равным на множестве чисел», быть подобным на множестве геометрических фигур. Обозначение эквивалентных отношений: a Q b или а ~ b, что означает «а эквивалентно b в отношении Q» рефлексивность симметричность транзитивность Отношение эквивалентности

• 
  Слайд 19
  

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

• 
  Слайд 20
  

  Отношение эквивалентности – частный случай отношения толерантности. Отношения «быть другом», «быть знакомым», - отношения толерантности, так как они рефлексивны, симметричны, но не транзитивны. Отношение «иметь непустое пересечение» для множеств – отношение толерантности. Отношение толерантности рефлексивность симметричность

• 
  Слайд 21
  

  Множество М, которое обладает отношением порядка, называется упорядоченным. Отношение порядка антисимметричность транзитивность + рефлексивность + антирефлексивность Отношение нестрогого порядка ≤ Отношение строгого порядка

• 
  Слайд 22
  

  Отношение называется отношением полного порядка, если сравнимы все элементы множества, на котором задано это отношение. Пример. Отношения «больше» и «меньше» на множестве действительных чисел. Отношение называется отношением частичного порядка, если сравнимы невсе элементы множества, на котором задано это отношение. Пример. Отношение «быть подмножеством» на множестве В(U) (булеан).