рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Відношення часткового порядку

Реферат Курсовая Конспект

Выберите учебное заведение

Відношення часткового порядку

Відношення часткового порядку - раздел Математика, Основи Дискретної математики Бінарне Відношення R, Задане На Множині А, Нази...

Бінарне відношення R, задане на множині А, називається відношенням часткового порядку (частковим порядком на А), якщо R рефлексивне, антисиметричне, транзитивне. Множина А, на якій задано відношення часткового порядку, називається частково упорядкованою. Множину А, частково упорядковану відношенням R, позначатимемо <A,R>. Часто відношення часткового порядку позначається символом £.

Наприклад, відношення R={<1,2>,<2,2>,<1,3>,<3,3>,<1,1>,<4,4>}, задане на множині А={1,2,3,4}, є рефлексивним, антисиметричним та транзитивним, отже, є частковим порядком на А. Прикладами відношень часткового порядку є відношення ³ та £ на множині R. Відношення {<1,2>,<1,1>,<2,1>} на множині А={1,2} не рефлексивне (й не транзитивне), отже, воно не є частковим порядком на А. Відношення А² на будь-якій множині А, що має понад один елемент, не антисимет-ричне (містить пари виду <x,y> та <y,x>, де x¹y), тому не є частковим порядком на А. Відношення і_А на будь-якій множині А є частковим порядком на А. Відношення включення Í на булеані деякої множини А є частковим порядком, оскільки воно рефлексивне (ХÍХ для будь-якої підмножини Х множини А), антисиметричне (якщо Х та Y – підмножини множини А й XÍY та YÍX, то X=Y), транзитивне (якщо X, Y – підмножини множини А й XÍY та YÍZ, то XÍZ).

Теорема 9. Нехай R та R₁ – часткові порядки на А. Довести, що:

а) RÇR₁ – частковий порядок на А;

б) R^-1 – частковий порядок на А.

Доведення. Покажемо, що відношення RÇR₁ рефлексивне, антисиметричне, транзитивне. Оскільки R та R₁ – часткові порядки на А, то відношення R та R₁ рефлексивні, а тоді й відношення RÇR₁ рефлексивне. Нехай <x,y>ÎRÇR₁ та <y,x>ÎRÇR₁. Тоді <х,у>ÎR й <у,х>ÎR, звідки х=у в силу антисиметричності R. Нехай <x,y>ÎRÇR₁ та <y,z>ÎRÇR₁. Тоді <x,y>ÎR, <y,z>ÎR, <x,y>ÎR₁, <y,z>ÎR₁, звідки <x,z>ÎR та <x,z>ÎR₁ в силу транзитивності R та R₁. Отже, <x,z>ÎRÇR₁. Таким чином, RÇR₁ є частковим порядком на А.

Як відомо (див. задачі XXXI, XXXIV, XXXVI до попереднього розділу), відношення R^-1 рефлексивне, антисиметричне та транзитивне, якщо таким є відношення R, отже, відношення, обернене до часткового порядку, є частковим порядком.

Бінарне відношення R, задане на множині А, називається відношенням строгого порядку на А (строгим порядком на А), якщо R антирефлексивне та транзитивне. Часто відношення строгого порядку позначається символом <.

Наприклад, відношення {<1,2>,<1,3>,<1,4>} є строгим порядком на множині {1,2,3,4,5}. Прикладами відношень строгого порядку на множині N є відношення < та >. Відношення Р на множині людей, задане умовою хРу Û х є предком у, є антирефлексивним та транзитивним, отже, є відношенням строгого порядку. Відношення М на множині людей, задане умовою хМу Û х – мати у, є антирефлексивним, але не є транзитивним, отже, й не є відношенням строгого порядку.

Бінарне відношення R, задане на множині А, називається відношенням передпорядку на А (передпорядком на А), або відношенням квазіпорядку на А (квазіпорядком на А), якщо R рефлексивне та транзитивне.

Зрозуміло, що будь-який частковий порядок на множині А є також передпорядком на А.

Наприклад, відношення R={<1,1>,<2,3>,<2,2>,<3,2>,<3,3>} та S={<2,2>, <2,3>,<3,3>,<1,1>} є передпорядками на множині А={1,2,3}; S є частковим порядком на А, а R – ні. Відношення строгого порядку не є передпорядком. Відношення {<1,1>,<2,2>,<3,3>,<2,1>,<3,2>} на множині А={1,2,3} не транзитивне, отже, не є передпорядком на А.

Нехай R – частковий порядок на А. Елементи х та у множини А називаються такими, що порівнюються відносно часткового порядку R, якщо <x,y>ÎR або <y,x>ÎR.

Розглянемо, наприклад, частковий порядок R={<1,1>,<1,2>,<2,2>, <3,3>} на множині A={1,2,3}. Оскільки хRх для кожного елемента х з множини А, то 1 та 1, 2 та 2, 3 та 3 порівнюються відносно R. Елементи 1 та 2 також порівнюються відносно R. 1 та 3, а також 2 та 3 не порівнюються відносно R. Розглянемо відношення включення на булеані множини {a,b,c}. Оскільки {a}Ë{b} й {b}Ë{a}, то {a} та {b} не порівнюються відносно Í.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Основи Дискретної математики

Київський національний університет технологій та дизайну... М К МОРОХОВЕЦЬ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Відношення часткового порядку

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

КИЇВ КНУТД 2005
УДК 51.681.3517 Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402 / Автор М.К.Мороховец

Лекція 1. Поняття множини. Операції над множинами
Теорія множин як математична дисципліна створена німецьким мате-матиком Г.Кантором. Згідно з його визначенням, множиною є довільне зі-брання певних об’єктів н

Способи подання множин
Множина може бути задана явно або неявно. Якщо об’єктів, що склада-ють множину, небагато, множина задається явно шляхом перерахування цих об’єктів (а точніше, їх імен). На письмі мн

Включення та рівність множин
Нехай А та В – множини. Будемо говорити, що А включається у В, або А є підмножиною В (й позначати АÍВ), якщо кожен елемент множини

Операції над множинами
Об’єднанням множин А та В (позначається АÈВ) називається множина усіх об’єктів, що є елементами множини А або В, тобто А

Властивості операцій над множинами
Теорема 1. Для будь-яких підмножин А, В, С універсальної множини U наведені нижче рівності є тотожностями (вираз А' слід розуміти як UА

Булеан множини
Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо

Задачі та вправи
І. Описати словами множини: 1) {x| x=2y+1, yÎN}, 2) {x| x=2y-1, yÎN},

Декартів добуток множин
Упорядкованою парою об’єктів х та y (позначається <x,y>) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у

Поняття відношення
Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням R, заданим на множинах А та В, називається довільна підмножина декар

Операції над відношеннями
Нехай R1, R2 – відношення, задані на множинах A1,…,An. Об’єднанням відношень R1 та R2

Види бінарних відношень
Бінарне відношення R на множині А називається симетричним, якщо <x,y>ÎR Þ <y,x>ÎR. Пару

Відношення еквівалентності
Рефлексивне, симетричне та транзитивне відношення на множині А називається відношенням еквівалентності на А. Прикладом відношення еквівалентності на мн

Фактор-множина
Нехай R – відношення еквівалентності на А. Тоді, як відомо, існує розбиття множини А, яке визначається відношенням R. Позначимо це розбиття через А

Замикання відношень
Рефлексивним замиканням бінарного відношення R, заданого на множині А (позначається Rr), називається відношення Rr=i

Задачі та вправи
І. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) Rr=Sr; 2) Rs=Ss; 3)

Відношення лінійного та повного порядку
Відношенням лінійного порядку (лінійним порядком) на множині А називається такий частковий порядок на множині А, відносно якого порівнюються будь-які еле

Задачі та вправи
І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 1) часткового порядку, 2) строгого порядку, 3) передпорядку, 4) лінійного порядку, 5) повного порядку.

Поняття відображення
Відношення R, задане на множинах А та В, називається функціональним, якщо для кожного елемента xÎА існує не більше одного елемента

Види відображень
Відображення F множини А у множину В називається відображенням А на В (або сюр’єктивним відображенням, або сюр’єкцією), як

Задачі та вправи
І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними, в) ін’єктивними, г) взаємно однозначними. А={a,b,c,d}, B={b

Рівнопотужні множини
Множини А та В називаються рівнопотужними (еквівалентними), якщо існує взаємно однозначне відображення А на В. Наприклад, множини

Потужність множини
Визначимо відношення ~ на множині усіх множин U: A~В Û А та В рівнопотужні. Дане відношення рефлексивне (А~А), симетричне (якщ

Трансфінітна індукція
Твердження, що стосуються елементів деякої повністю упорядкованої множини, можна доводити, використовуючи метод трансфінітної індукції, який є узагальненням методу математичної інду

Задачі та вправи
І. Навести приклад множини Y, еквівалентної множині X={1,2,3,4,5}. Скільки взаємно однозначних відображень існує між Х та Y? ІІ. Чи рівнопотужні

СПИСОК ВИКОРИСТАНОЇ ТА РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ
1. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. – 400 с. 2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программировани

СИМВОЛИ ТА ПОЗНАЧЕННЯ
N – множина усіх невід’ємних цілих чисел N+ – множина усіх додатних цілих чисел Z – м