Правило суми

В основі розв'язання багатьох задач комбінаторики лежать два простих правила — правило суми та правило добутку. Правило суми стверджує, що якщо є можливість вибрати елемент з деякої множини елементів А способами, а елемент з множини В, яка не має спільних елементів з множиною А, — способами, то вибрати елемент множини А або елемент множини В можна способами.

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

35. Переріз і об’єднання множин. Закони комутативності і асоціативності перерізу та об’єднання множин

Переріз — ортогональна проекція фігури, одержана в одній чи декількох площинах або поверхнях за уявного розсічення предмета, що проектуєтьсУ математиці, зокрема в теорії множин, об'єднання множин є множиною, яка включає в себе всі елементи об'єднуваних множин і нічого більше.Вирази (1а) - (3а) виражають закони комутативності, асоціативності і дистрибутивності для об`єднання.Об’єднання А і В (А∪В) – множина, що складається з усіх елементів
множин А, всіх елементів множини В і не містить ніяких інших елементів, тобто
А∪В = {x | x∈A або x∈В}.

Закон комутативності

Бінарна операція на множині S є комутативною, якщо

x × y = y × x

для всіх x і y ∈ S. В іншому випадку × є некомутативною. Якщо

x × y ≠ y × x

для окремої пари елементів x, y, тоді кажуть, що x і y комутують.

Найвідомішими прикладами комутативних бінарних операцій є операції додавання "+" і множення "×" дійсних чисел, наприклад:

· 4 + 5 = 5 + 4 (оскільки обидва вирази дорівнюють 9)

· 2 × 3 = 3 × 2 (оскільки обидва вирази дорівнюють 6)

Серед некомутативних бінарних операцій: віднімання (a − b), ділення (a / b), піднесення до степеня (a^b), композиція функцій (f (g (x))), тетрація (a ↑↑ b).

Інші приклади комутативних бінарних операцій: додавання і множення комплексних чисел; додавання векторів; перетин, об'єднання та симетрична різниця множин.

Важливими некомутативними операціями є множення матриць та векторне множення.

Група, операція якої є комутативною, називається абелевою групою.

Асоціативна операція (сполучний закон) — бінарна операція, яка володіє властивістю асоціативності (від латинського слова associatio — «з'єднання»), тобто виконується:

для довільних елементів .

Для асоціативної операції результат обчислення не залежить від порядку обчислення (розташування дужок), і тому можна опускати дужки у записі виразу. Для неасоціативної операції значення виразу при не визначено.

Довільна групова операція — асоціативна.

Дата добавления: 2014-12-16