Алгебраїчні системи

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

Означення. Граткою називається частково впорядкована множина, в якій для будь-яких двох елементів a і b існують: a  b = с – така нижня грань a та b, що будь-яка інша нижня грань a і b менша за c, а aTb = d – така верхня грань a та b, що будь-яка інша верхня грань a і b більша за d.

Отже, гратка – це алгебраїчна система {M; ; ; T} з одним бінарним відношенням та двома бінарними операціями.

Приклади: 1) Будь-яку абсолютно впорядковану множину (наприклад множину цілих чисел) можна перетворити на гратку, означивши для будь-яких a, b  M, a  b = max(a, b), aTb = min(a, b).

2) Означимо на N відношення часткового порядку < таким чином: a < b, якщо a ділить b. Тоді a  b – найменше спільне кратне a і b, aTb – найбільший спільний дільник a, b. Наприклад, 9  12 = 36, 9T12 = 3, 5T7 = 1, 57 = 35.

Упорядкована множина не є граткою у двох випадках:

• коли які-небудь два елементи не мають верхньої або нижньої грані;

• коли для деякої пари елементів найменша верхня (або найбільша нижня) грань не є єдиною.

Гратка, в якій операції  та T є можливими для будь-яких підмножин її елементів, називається повною. Об’єднання всіх елементів повної структури – це максимальний елемент гратки, який називається одиницею структури. Переріз усіх елементів повних граток – це мінімальний елемент гратки, тобто її нуль.

Тема „Елементи комбінаторики”

Для скніченної множини A позначимо через |A| кількість її елементів. Для двох скінченних множин A і B правильні рівності: |A  B| = |A|  |B| і |A B| = |A| + |B|, якщо A B = .

Для скінченних множин A₁, …, A_n справедлива така теорема.

Теорема 1. |A₁ … A_n| = – + … + (–1)^{k + 1} + … + (–1)^{n – 1}|A₁ … A_n|.

Доведення. Теорему доводимо методом математичної індукції. Нехай n = 2 і |A₁| = p, |A₂| = q, |A₁ A₂| = r. Тоді

A₁ A₂ = (A₁ \ (A₁ A₂)) (A₂ \ (A₁ A₂)) (A₁ A₂), причому множини A₁ \ (A₁ A₂), A₂ \ (A₁ A₂), A₁ A₂ попарно не перетинаються. Тому

| A₁ A₂| = p – r + q – r + r = p + q – r = |A₁| + |A₂| – | A₁ A₂|.

Припустимо, що n  2 і теорема доведена для n множин. Доведемо, що тоді вона правильна і для n + 1 множини. Маємо

| A₁ … A_n … A_{n + 1}| = |(A₁ … A_n) A_{n + 1}| = | A₁ … A_n| + |A_{n + 1}| – |(A₁ … A_n) A_{n + 1}| = – + … + (–1)^{k – 1} + … + (–1)^{n – 1}|A₁ … A_n| – + … + (–1)^{k – 1} + … + (–1)ⁿ|A₁ … A_{n + 1}| = – + … + (–1)^{k – 1} + … + (–1)ⁿ|A₁ … A_{n + 1}|.

Теорему доведено.

Приклад 1. У науково-дослідному інституті працюють 67 співробітників. З них французькою мовою володіють 20 співробітників, англійською – 47, німецькою – 35, англійською та французькою – 12, англійською та німецькою – 23, німецькою та французькою – 11, а трьома мовами володіють 5 співробітників. Скільки співробітників не володіє жодною з трьох мов?

Розв’язування. Нехай x – кількість співробітників, які не знають жодної з трьох мов, A₁, A₂, A₃ – множини співробітників, які знають відповідно англійську, французьку або німецьку мови. Тоді застосовуючи доведену формулу при n = 3, одержимо

67 – x = 47 + 35 + 20 – 23 – 11 – 12 + 5 = 61, x = 6.

Зауваження. Якщо A₁, A₂, …, A_n – скінченні множини, які попарно не перетинаються, тобто X_i X_j =  при i  j, то

= .

У комбінаториці цей факт називається правилом суми. Для k = 2 воно формулюється так: якщо об’єкт a може бути вибраний p способами, а об’єкт b – іншими q способами, то вибір „або a, або b” може бути здійснений p + q способами.

Вибори a та b є взаємовиключними, оскільки X_i X_j = , тобто жоден із способів вибору об’єкта a не збігається з жодним із способів вибору об’єкта b. Якщо припустити, що X_i X_j = C  , де |C| = c, результат дорівнює p + q – c (с – кількість збігів).

Правило добутку. Якщо об’єкт a може бути вибраний p способами і після кожного з таких виборів об’єкт b, у свою чергу, може бути вибраний q способам, то вибір „a та b” у вказаному порядку можна здійснити pq способами.

Це правило використовують тоді, коли способи вибору a і b – незалежні.

Нехай потрібно обчислити кількість пар N вигляду (a_i, b_j), де a_i  A, b_j  B, |A| = n, |B_j| = m і елемент b_j вибирається після того, як вибрано елемент a_i. Тоді можливі випадки: 1) або A B = , тобто A і B не мають спільних елементів і вибір b_j не залежить від вибору a_i; 2) або A B   і тоді вибір b_j залежить від вибору a_i.

Для обчислення кількості всіх пар (a_i; b_j) в будь-якому із випадків 1), 2) досить будь-який спосіб вибору об’єкта a_i скомбінувати із m способами вибору b_j:

(a₁, b₁), (a₁, b₂), …, (a₁, b_m),

(a₂, b₁), (a₂, b₂), …, (a₂, b_m), (*)

…………………………

(a_n, b₁), (a_n, b₂), …, (a_n, b_m).

При цьому в множині (*) не пропущено жодної пари і будь-яка пара не повторюється. В кожному рядків сукупністю (*) є m пар, а кількість рядків n. Тому N = n  m.

Загальне правило добутку n елементів формулюється так: якщо об’єкт x₁ може бути вибраний n₁ способами, після чого об’єкт x₂ може бути вибраний n₂ способами, і для будь-якого i, де 2  i  m – 1, після вибору об’єктів x₁, ..., x_i об’єкт x_{i + 1} може бути вибраний n_{i + 1} способами, то вибір упорядкованої послідовності m об’єктів (x₁, x₂, …, x_m) може бути здійснений n₁  n₂  …  n_m способами.