Дослідження бінарних відносин на рефлексивність, симетричність, транзитивність.  Виділення класів еквівалентності
Химия

Дослідження бінарних відносин на рефлексивність, симетричність, транзитивність. Виділення класів еквівалентності


Дослідження бінарних відносин на рефлексивність, симетричність, транзитивність. Виділення класів еквівалентності

Державний автономний професійний освітній заклад

Саратовської області «Енгельський політехнікум»

Реферат з дискретної математики:

«Дослідження бінарних відносин на рефлексивність, симетричність, транзитивність. Виділення класів еквівалентності»

Виконала: студентка гурту №С214

Стрєлкова Олена

Викладач: Косарьова О.А.

Енгельс, 2014

Зміст:

Бінарні відносини

2

Графічний спосіб подання бінарних відносин

3

Властивості бінарного відношення

4

Виділення класів еквівалентності

5

Список першоджерел

7

— 1 —

Бінарні відносини

Бінарні відносини служать простим і зручним апаратом для широкого кола завдань. Мова бінарних та n-арних відносин використовується в багатьох прикладних (для математики) областях, наприклад, таких як математична лінгвістика, математична біологія, математична теорія баз даних. Широке використання мови бінарних відносин легко пояснюється – геометричний аспект теорії бінарних відносин є просто теорією графів. Бінарним ставленням, визначеним на парі множин X та Y, називається будь-яке підмножина прямого твору множин X x Y.

Якщо x пов’язаний з y ставленням R, це позначають як xRy або (x, y)clip_image001R.

Бінарне відношення може задаватися своєю множиною R={(x,y)| xRy}.

Оскільки бінарні відносини є множинами, має сенс говорити про дії над бінарними відносинами як над множинами, тобто. можна визначити об’єднання перетин і різницю бінарних відносин.

Приклад:

clip_image002 – бінарне відношення, задане за допомогою характеристичної властивості;

Нехай X = {a, b, c, d}, Y = {1, 2, 3, 4, 5}. Тоді множина R={(a, 1), (b, 2), (c, 3), (d, 4)} є бінарним ставленням, заданим на парі X×Y.

Область визначення бінарного відношення R – це множина X = {x | clip_image003y (x, y)clip_image001[1]R}.
Область значень бінарного відношення R – це множина Y = {y | clip_image003[1]x (x, y)clip_image001[2]R}.
Добре відомими прикладами відносин зі шкільного курсу математики є:

на багатьох цілих чисел Z відношення «ділиться», «ділить», «рівно», «більше», «менше», «взаємно прості»;

на безлічі прямих просторів відносини «паралельні», «взаємно перпендикулярні», «схрещуються», «перетинаються», «збігаються»;

— 4 —

Графічний спосіб подання бінарних відносин

Розглянемо ще два графічні уявлення бінарних відносин. Як носій відносини для ілюструючих прикладів використовуватимемо безліч X = {a, b, c, d, e}.

Спочатку розглянемо спосіб, висхідний до аналітичної геометрії. Накреслимо пару взаємно перпендикулярних осей (OX – горизонтальна вісь, а OY — Вертикальна вісь) і на кожній відзначимо точки, що представляють елементи множини X

clip_image005

Вважаючи мітки a, b, c, d, e координатами точок на горизонтальній та вертикальній осях, відзначимо на площині точки з координатами (x, y). На малюнку 2 зображено безліч точок, що відповідає відношенню R = {(a, b), (a, c), (b, d), (c, e), (e, b), (e, e)}.

clip_image007

— 5 —

Властивості бінарного відношення

Нехай задано бінарне відношення R на парі множин X, Y. Бінарне відношення може мати наступні властивості

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

(clip_image009xclip_image001[3]X) xRx або (clip_image009[1]xclip_image001[4]X) (x, x)clip_image001[5]R

Граф рефлексивного бінарного відношення містить петлі біля кожної вершини.

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

(clip_image009[2]x, yclip_image001[6]X) xRy clip_image009[3] yRx або (clip_image009[4]x, yclip_image001[7]X) (x, y)clip_image001[8]R clip_image009[5] (y, x)clip_image001[9]R

Граф симетричного бінарного відношення містить лише неорієнтовані ребра або петлі. Графік симетричного відношення симетричний щодо бісектриси І-ІІІ координатних кутів.

Транзетивність

(clip_image009[6]x, y, zclip_image001[10]X) xRy / yRz clip_image009[7] xRz або (clip_image009[8]x, y, zclip_image001[11]X) (x, y)clip_image001[12]R/(y, z)clip_image001[13]R clip_image009[9] (x, z)clip_image001[14]R

Перевіримо всі властивості відношення:

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

(clip_image009[10]xclip_image001[15]А) (x, x)clip_image001[16]R – це хибне висловлювання
Можна навести контр приклад, х=3, пара (3,3) не належить множині R. Бінарне відношення не є рефлексивним.

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

(clip_image009[11]x, yclip_image001[17]А) (x, y)clip_image001[18]R clip_image009[12] (y, x)clip_image001[19]R – це хибне висловлювання
Можна навести контр приклад, х=1, y=2 пара (1,2) належить множині R, а пара (2, 1) не належить множині R. Бінарне відношення не є симетричним.

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

(clip_image009[13]x, y, zclip_image001[20]А) (x, y)clip_image001[21]R/(y, z)clip_image001[22]R clip_image009[14] (x, z)clip_image001[23]R – це хибне висловлювання
Можна навести контр приклад, х=1, y=2, z=3 пара (1,2) належить множині R і пара (2,3) належить множині R, а пара (1, 3) не належить множині R. Бінарне відношення не є транзитивним.

— 6 —

Виділення класів еквівалентності

Клас еквівалентності – це клас, у межах якого всі тести є еквівалентними.

Еквівалентні тести — це тести, які призводять до одного і того ж результату.

Тобто, якщо ми виконаємо два будь-які тести з одного класу еквівалентності, то отримаємо той самий результат.

Класи еквівалентності зазвичай тестують на кордонах та їх девіаціях (+-1, наприклад), тому що ймовірність зловити помилку на таких значеннях вища через можливі помилки на операціях порівняння.

Справжній клас еквівалентності — Це те, що описано вище. Це той клас, у якому всі тести є еквівалентними. Для такого класу ймовірність помилки або успіху для кожного окремого тесту однакова, а значить, тестувати такий клас на межах не має сенсу, ці тести дадуть таку ж ймовірність помилки, як і будь-які інші з даного класу. На те він справжній.

Парадокс 1: якщо клас еквівалентності справжній (правильний), то тестувати його на межах немає сенсу, можна вибрати будь-який тест та перевірити лише на ньому. При цьому можна стверджувати, що решта тестів з даного класу також призведуть до такого ж результату (pass або fail).

Передбачуваний клас еквівалентності — це клас еквівалентності, в якому ми не впевнені, але який визначили як такий на підставі якихось критеріїв (специфікації, коду, роздумів, переконань, аналізу тощо). Оскільки ми в ньому не впевнені (він не справжній), то, відповідно, ми його тестуємо на кордонах та прикордонних значеннях. І це логічно. Але цього мало. У нас немає достатньої впевненості, що сам клас ми визначили правильно і теоретично ми цілком можемо пропустити помилку десь у середині цього класу. Оскільки насправді це може виявитися не один клас, а кілька, і ось у цих не знайдених класах ми можемо не запустити жоден тест і пропустити там помилку.

— 7 —

Парадокс 2: Тестувати передбачуваний клас еквівалентності на межах мало, ймовірність пропустити помилку все одно є, оскільки немає впевненості в тому, що ми правильно розбили тести за класами еквівалентності.

Враховуючи парадокси 1 та 2, виходить, що справжній клас еквівалентності тестувати на кордонах немає сенсу, а передбачуваний – не надійно. Навіщо ж тоді взагалі потрібні ці граничні значення? У розділі «практика» опишу своє бачення.

8

Список першоджерел

http://mgogi.ru/site1.2/binarotno.html

http://testingforall.com/blog/?p=209

http://www.studfiles.ru/dir/cat32/subj1340/file14237/view152250/page2.html

— 7 —

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *