Презентация на тему "Лекция 2. Бинарные отношения и свойства"

Содержание

• 
  Слайд 1

  Лекция 2. Бинарные отношения и свойства

  2008 г. Дискретная математика. Математическая логика ИОП МИФИ Проф., д.т.н. Гусева А.И., доцент Порешин П.П., аспирант Цыплаков А.C.

• 
  Слайд 2

  Бинарное отношение

  Бинарным отношениемТ(М) на множестве М называется подмножество , Инфиксная форма записи бинарного отношения a T b= .

• 
  Слайд 3

  Виды бинарных отношений

  Обратное отношение Дополнительное отношение Тождественное отношение Универсальное отношение

• 
  Слайд 4

  Способы задания бинарных отношений

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

• 
  Слайд 5

  Пример

  Матрица смежности 1 5 2 3 4 Графическое задание

• 
  Слайд 6

  Фактор-множество

  Фактор-множествоR/Mмножества М по отношению к R называется множество окрестностей единичного радиуса для всех элементов М при заданном R R/M=

• 
  Слайд 7

  Функция

  называется функцией, если для каждого элемента х найдется не более одного элемента у такого, что , т.е. выполняется свойство однозначности полученного результата Множество X - область определения функции, и множество Y - область значений функции Х и У могут не иметь общих элементов

• 
  Слайд 8

  Инъекция

  Функция F: X →Y называется инъективной, или инъекцией, или вложением, если она переводит разные элементы Х в разные У, то есть

• 
  Слайд 9

  Сюръекция

  Функция F: X → Yназывается сюръективной, или сюръекцией, или наложением, если множество ее значений есть все Y, т.е.

• 
  Слайд 10

  Биекция

  Функция F: X →Y называется биекцией или взаимно однозначным соответствием, если она одновременно является инъекцией и сюръекцией (вложением и наложением)

• 
  Слайд 11

  Операция

  Частным случаем функции является операцияО В этом случае область значения Х и область определения У совпадают, т.е

• 
  Слайд 12

  Рефлексивность

  Бинарное отношение T(M)называется рефлексивным тогда и только тогда, когда для каждого элемента пара (х, х)принадлежит этому бинарному отношению, т.е. Бинарное отношение T(M) называется иррефлексивным тогда и только тогда, когда для каждого элемента пара (х, х) не принадлежит этому бинарному отношению, т.е.

• 
  Слайд 13
  

  Если бинарное отношение T(M) не обладает ни свойством рефлексивности, ни свойством иррефлексивности, то оно является нерефлексивным

• 
  Слайд 14

  Симметричность

  Бинарное отношение T(M) называется симметричным тогда и только тогда, когда для каждой пары (х, у)из Т, обратная пара (у, х) также принадлежит этому бинарному отношению, т.е. Бинарное отношение T(M) называется антисимметричным тогда и только тогда, когда для каждой пары различных элементов (х, у) из Т пара (у, х) не принадлежит этому бинарному отношению, т.е.

• 
  Слайд 15
  

  Если бинарное отношение T(M) не обладает ни свойством симметричности, ни свойством антисимметричности, то оно является несимметричным

• 
  Слайд 16

  Транзитивность

  Бинарное отношение T(M) называетсятранзитивным тогда и только тогда, когда длякаждых двухпар элементов (х, у) и (у, z),принадлежащихбинарному отношению, пара (x, z) такжепринадлежит этому бинарному отношению, т.е.

• 
  Слайд 17
  

  Бинарное отношение T(M) называется интранзитивным тогда и только тогда, когда для каждых двух пар элементов (х, у) и (у ,z), принадлежащих бинарному отношению , пара (x, z) не принадлежит этому бинарному отношению, т.е. Транзитивность

• 
  Слайд 18

  Транзитивность

  Если бинарное отношение T(M) не обладает ни свойством транзитивности, ни свойством интранзитивности, то оно является нетранзитивным

• 
  Слайд 19

  Примеры рефлексивности

• 
  Слайд 20

  Примеры симметричности

  a c b d a c b d a c b d

• 
  Слайд 21

  Примеры транзитивности

  a c b d a c b d a c b d

• 
  Слайд 22

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

  b f a c d e нерефлексивность (часть вершин имеет петли, часть –нет) несимметричность (есть симметричные и антисимметричные дуги) интранзитивность (бинарное отношение обладает несколькими путями длины два, но ни на один из них нет транзитивного замыкания)