Правила суми та добутку

Довести закони де Моргана

Огастес де Морган спочатку помітив, що в класичній пропозіціональной логіці справедливі наступні співвідношення:

not (P and Q) = (not P) or (not Q)

not (P or Q) = (not P) and (not Q)

Звичайна запис цих законів у формальній логіці:

\ neg (P \ wedge Q) = (\ neg P) \ vee (\ neg Q),

\ neg (P \ vee Q) = (\ neg P) \ wedge (\ neg Q),

або

\ overline {x \ wedge y} = \ overline x \ vee \ overline y,

\ overline {x \ vee y} = \ overline x \ wedge \ overline y.

В численні предикатів:

\ neg \ forall x \, P (x) \ equiv \ exists x \, \ neg P (x),

\ neg \ exists x \, P (x) \ equiv \ forall x \, \ neg P (x).

В теорії множин:

(A \ cap B) ^ C = A ^ C \ cup B ^ C,

(A \ cup B) ^ C = A ^ C \ cap B ^ C.

У вигляді теореми:

Якщо існує операція логічного множення двох і більше елементів, операція «і» - (A & B), то для того, щоб знайти зворотне від усього судження ~ (A & B), необхідно знайти зворотне від кожного елемента і об'єднати їх операцією логічного додавання, операцією «або»- (~ A + ~ B). Закон працює аналогічно в зворотному напрямку: ~ (A + B) = (~ A & ~ B)

Сформулюємо правило добутку:

якщо деякий елемент А можна вибрати m способами, а після кожного такого вибору інший елемент В можна вибрати (незалежно від вибору елемента А) — r способами, то пару об’єктів А і В можна вибрати mr способами.

Приклад 1. У шкільній їдальні є вибір з 3 перших і 5 других блюд. Тоді обід з першого і другого блюда можна обрати 3 ∙ 5 = 15 способами.

Правило добутку розповсюджується на три і більше елементів.

Приклад 2. Скільки трицифрових чисел можна скласти з цифр 1; 2; 3; 4; 5, якщо в числі: 1) цифри не повторюються; 2) цифри повторюються.

Розв’язання.

1) Маємо 5 способів для сотень числа (мал. 129). Після того, як місце сотень заповнене (наприклад, цифрою 1), для десятків залишається 4 способи. Міркуючи далі, для одиниць - 3 способи. Отже, маємо: «5 способів, і після кожного з них — 4, і після кожного з них — 3 способи». За правилом добутку маємо 5 ∙ 4 ∙ 3 = 60 чисел.

Розміщенням з n елементів по m (m < n) називають будь-яку впорядковану підмножину У множини X, причому дві такі підмножини вважають різними, якщо вони відрізняються складом або порядком елементів.

Приклад 1. Нехай дано множину Х = {1;2;3}. Тоді по одному можна скласти такі розміщення:

(1), (2), (3) - їх буде 3;

по два можна скласти такі розміщення:

(1;2), (1;3), (2;1), (2;3), (3;1), (3;2) - їх буде 6;

по три можна скласти такі розміщення:

(1;2;3), (1;3;2), (2;1;3), (2;3;1), (3;1;2), (3;2;1) - їх буде 6.

Кількість розміщень з n елементів по m позначають Аmn.

Правило суми.

Якщо об'єкт a може бути обраний p способами, а об'єкт b - іншими q способами, то вибір “або a, або b” може бути здійснений p+q способами.

Вибори a і b взаємно виключають одне одного. Необхідно, щоб не один зі способів вибору об'єкта a не збігся з Якім-небудь способом вибору об'єкта b. При наявності таких збігів правило суми незастосовне і результат дорівнює p+q-k, де k – це число збігів.

Правило суми: якщо деякий елемент x з множини А можна вибрати m способами, а елемент y з множини В - k способами, причому жоден із способів вибору елемента x не співпадає зі способом вибору елемента y, то елемент x або елемент y можна вибрати m + k способами.

Це правило можна поширити на випадок будь-якої скінченної кількості множин. Розглянемо застосування цього правила до розв’язання наступних задач.

Задача 1: на столі є 4 ручки i 3 олівці. Скількома способами можна взяти зі столу один предмет?

Розв’язання:

У цій задачі маємо справу із двома скінченними множинами: А - множина ручок, де n(A)=4, i В - множина олівців, де n(B)=3. Оскільки нам потрібно вибрати один предмет, тобто зробити вибір x чи y (ручка або олівець), то згідно з правилом суми це можна зробити n(A)+n(B)=4+3=7 способами. Правило суми можна було застосувати тому, що множини не перетинаються i вибір ручки не залежить від вибору олівця i навпаки.

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