Булеві операції над множинами (поняттями)

Нехай X - кінцева множина та |Х| - число її елементів. Сформулюємо аксіоматичне правило, яке лежить в основі багатьох комбінаторних обчислень і оцінок.

І Правило суми. Якщо X - кінцева множина, то

Бінарні відповідності і бінарні відношення

Матриці, елементи яких приймають значення 0 та 1, называють

діагоналлю множини X.

Бінарному відношенню R на кінцевій множині X ставиться у відповідність геометричний об’єкт, названий орієнтованим графом.

Рис.9

Кожному елементу х ∈ X ставиться у відповідність точка на площині, яка зветься вершиною. Якщо (х, x^,) ∈ R, то об’єкт між двома точками х та х’ звуть дугою. Діаграма (X, R) є сукупністю вершин і дуг, відношення R.

Бінарне відношення R на множині X зветься відношенням еквівалентності, якщо воно одночасно рефлексивно, симетрично і транзитивно.

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

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

2.2.5