Дискретная математика

володіють жодною з властивостей αi1,…,αik. Тоді маємо формулу:

Якщо треба знайти кількість елементів, які володіють рівно m властивостями, тоді використовують наступну формулу:

k =0

Приклади розв’язування задач.

1. Кожен день, протягом 10 днів, клієнт брав з картки гроші а) кожен день різну суму 5, 10, 15,…, 50 грн; б) 3 дні у сумі 100 грн, 5 днів у сумі 50 грн., 2 дня у сумі 20 грн, Скількома способами він це міг зробити?

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

а) усього 10 днів (n=10), і в усі ці дні клієнт брав гроші (m=10), кожен день різну суму, тобто має значення лише в який день була яка сума, тому маємо перестановку:

P10 = 10!= 3628800 ;

б) усього 10! перестановок, але 3! перестановок не відрізняються між собою тому, що в три дні сума однакова – 100 грн, також – 5! та 2! перестановки однакові, тому різних способів буде:

P103,5,2 = 310!5!!2! = 2520 ;

2. Скільки п’ятицифрових чисел можна утворити з шести цифр

1, 2, 3, 4, 5, 6?

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

Зшести цифр (n=6) необхідно вибрати – п’ять (m=5), причому цифри

учислі можуть повторюватися, і має значення в якому порядку вони записані, тому усього можливо утворити:

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

12

А65 = 65 = 7776 чисел.

3. Із 10 робітників фірми директору треба назначити бухгалтера, його помічника, двох менеджерів і трьох кур’єрів. Скількома способами це можливо зробити?

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

З початку з 10 чоловік виберемо бухгалтера – 10 способів, потім з дев’яти залишених чоловік – його помічника – 9 способів, потім з восьми –

способів буде: 10*9*28*20=50400.

4. Скількома способами можна поставити в одну шеренгу гравців двох команд (по 5 чоловік) так, щоб при цьому два чоловіка однієї команди не стояли поруч?

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

З початку поставимо в шеренгу гравців однієї команди, це можливо зробити – Р5=5!=120 способами. Потім будемо ставити між ними гравців другої команди. Усього можливих міст маємо – 6, з котрих треба вибрати п’ять без повторювань та упорядковано, тому різних способів буде -

в одну шеренгу гравців двох команд буде – 120*720=86400.

5. Скількома способами можна роздати 6 однакових іграшок трьом дітям так, щоб кожен з них отримав хоча б по однієї іграшки?

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

З початку роздамо по одній іграшці кожній дитині, між останніми трьома іграшками введемо два роздільника, так щоб кількість іграшок до першого з них були для першої дитини, кількість іграшок між першим та другим роздільником – для другої дитини, а після другого роздільника – для третьої дитини. Тоді кількість різних способів отримання дітьми іграшок буде дорівнювати кількості можливих варіантів вибору двох міст для

6. Скількома способами можна роздати 6 різних предметів трьом особам так, щоб кожна отримала по 2 предмети?

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

13

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

Це упорядковане розбиття, де n=6, n1=n2=n3=2. Тобто можливих

способов буде - С62,2,2 = 2!2!2!6! = 90 .

7. Дев’ятьох робітників одного цеху мають розподілити на групи в 2, 3 і 4 чоловіка для проходження однакових курсів підвищення кваліфікації, які проходять в різних 7 навчальних закладах, з яких можливо вибрати будь-який. Скількома способами це можна зробити?

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

З початку виберемо 3 навчальних заклади, це можливо зробити

А73 = 73 = 343 способами, потім розіб’ємо робітників на три групи, це буде не упорядковане розбиття, тобто маємо:

Далі за правилом добутку отримаємо – 343*1260=432180 різних способів.

8. У спортивному клубі займаються 38 чоловік. З них 16 грають у баскетбол, 17 – у хокей, 18 – у волейбол. Баскетболом і хокеєм захоплюється 4 чоловіки, баскетболом і волейболом – 7, волейболом і хокеєм – 5. Скільки чоловік захоплюється одночасно хокеєм, баскетболом і волейболом? Скільки чоловік захоплюється лише одним із цих видів спорту?

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

За формулою включень та виключень маємо: N=38, N0=0

S1=16+17+18=51 S2=4+7+5=16

N0 = N − S1 + S2 − S3 , тоді

S3 = N − S1 + S2 − N0 = 38 − 51+16 = 3- чоловік захоплюється

одночасно хокеєм, баскетболом і волейболом .

Лише одним із цих видів спорту захоплюються:

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

14

3 МАТЕМАТИЧНА ЛОГІКА

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

Визначення. Висловленням називається оповідальне речення, про яке можна сказати в даний момент часу, що воно істинне або хибне, але не те й інше одночасно.

Зіставимо кожному висловленню змінну, що має значення істина - 1, якщо воно істинно, і значення хибність - 0, якщо висловлення хибне. Значення істинності складеного висловлення залежить від значень істинності складових його висловлень. Для складання складних висловлень застосовуються логічні зв'язки:

Ú – логічне додавання (або), диз'юнкція; Ù – логічне множення (і), кон’юнкція; (Ø) - логічне заперечення (не).

Якщо P і Q – деякі висловлення, то можна скласти нові висловлення PÚQ, PÙQ,`P,`Q, причому істинність складених висловлень визначається за допомогою таблиць істинності:

Властивості булевих операцій:

1.Ідемпотентність: AÚA=A, AÙA= A.

2.Комутативність: A ÚB= B Ú A, A Ù B = B Ù A.

3.Асоціативність: AÚ(BÚC)=(AÚ B)Ú C, A Ù(B Ù C)=(A Ù B)Ù C.

4.Дистрибутивність: A Ù( B Ú C) = (A Ù B)Ú( A Ù C).

A Ú( B Ù C) = (A Ú B)Ù( A Ú C).

6.Інволюція: A = A .

7.Правила де Моргана: ìïíA Ú B = A Ù B,

ïA Ù B = A Ú B.

î

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

15

8. Склеювання: (A B) (A B) = A, (A B) (A B) = A.

9.Поглинання: Α(A B)=A, A (ΑB)=A.

10.Закон протиріччя: A A = 0 .

11.Закон виключеного третього: A A =1.

12. Дії з нулем і одиницею: 0 = 1; A 0 = A; A 1 = 1; 1 = 0; A 0 = 0; A 1 = A.

В логіку крім трьох основних булевих операцій для утворення складних висловлень вводять ще дві: імплікація (слідування) – (A→B) («якщо A, то B»); еквівалентність – (A ↔ B) або ( ) («якщо і тільки якщо»), що мають наведені таблиці істинності.

можна побудувати таблицю істинності. Якщо складене висловлення залежить від n

складових, то в таблиці істинності такого висловлення буде 2n рядків. Приклад. Побудувати таблицю істинності висловлення,

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

16

Визначення. Складене висловлення, що істинне незалежно від значень висловлень, що входять у нього, називається тавтологією, таблиця істинності тавтології містить тільки значення “істинно”, а його функція тотожно дорівнює одиниці. Складене висловлення, що хибне незалежно від значень висловлень, що входять у нього, називається протиріччям.

Щоб перевірити, чи є висловлення тавтологією або

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

У численні висловлень формули будуються за наступними правилами:

-змінна є формула;

-якщо F і P – формули, то формулами будуть також F , Φ ,

F Φ , F Φ , F → Φ , F Φ ;

-інших формул немає.

Визначення. Формули, що представляють ту саму функцію,

називаються еквівалентними або рівносильними.

Приклад. Штрих Шеффера: x1 x2 = x1 x2 = x1 x2 ;

стрілка Пірса: x1 ↓ x2 = x1 x2 = x1 x2 .

Для спрощення формул використовують властивості булевих операцій, а також наступні три тотожності, що дозволяють замінити імплікацію (→) і еквівалентність ( ) булевими операціями:

13.x → y = x y

14.x y = (x y) (x y)

15.x y = (x y) (x y) .

Правила спрощення формул такі:

-за допомогою формул 14 і 15 виключити з формули еквівалентність;

-за допомогою формули 13 виключити імплікацію;

-за правилами де Моргана опустити заперечення формул до рівня змінних (властивість 7);

-застосувати тотожності дистрибутивності (властивості 4, 5);

-привести подібні.

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

17

Приклад.

(a ® b ) Ù (b ~ c) = {формули 13, 14} = (a Ú b ) Ù (b Ú c) Ù (b Ú c) =

= a Ù b Ù c Ú a Ù b Ù c Ú b Ù c Ú b Ù b Ù c = {властивості 9, 12}

{

=0

=a Ù b Ù c Ú a Ù b Ù c Ú b Ù c = {властивості 4, 2}=

=b Ù c Ù (a Ú1) Ú a Ù b Ù c) = {властивість 12} = b Ù c Ú a Ù b Ù c .

{

=1

Введемо позначення: x0 = x, x1 = x . Тоді, якщо позначити через α змінну, що приймає значення 0 або 1, то справедливе

Теорема. Усяку логічну функцію n змінних f (x1, x2 ,..., xn ) можна представити у вигляді

де диз'юнкція береться по всім тим наборам змінних, при яких f=1.

Це розкладання функції по n змінним називається досконалою диз'юнктивною нормальною формою (ДДНФ) функції f. ДДНФ функції f містить рівно стільки кон’юнкцій, скільки одиниць у таблиці істинності f.

Зауваження. Для нуля не існує ДДНФ: 0 = x x ; для одиниці ДДНФ є: 1 = x x .

Кожна функція f (x1,...,x1) P2 (множини логічних функцій n змінних), причому така, що f ≡/ 0 , має ДДНФ, що будується в такий спосіб: у таблиці істинності виділяють ті рядки, тобто ті набори змінних σ1,...,σn , для яких f (σ1, ...,σ n ) =1. Для кожного

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

18

позначеного рядка утворюють кон’юнкцію x1σ1 ... xσn n . Складають

вигляд:

x1x2 x3 x1x2 x3 x1x2 x3 x1x2 x3 .

Визначення. Елементарною кон’юнкцією називається кон’юнкція змінних або їхніх заперечень, у яку кожна змінна входить не більш одного разу. Диз'юнкція елементарних кон’юнкцій називається диз'юнктивною нормальною формою (ДНФ).

Приклад. f (x1,...,x5 ) = x1 x3 x5 x2 x4 x5 (ДНФ);

f (x1,..., x5 ) = (x1 x2 x3 x4 x5 ) (x1 x2 x3 x5 x5 ) (СДНФ)

Різниця між ДНФ і ДДНФ полягає в тому, що в ДДНФ кожна елементарна кон’юнкція містить усі n змінних або їхніх заперечень, у той час як у ДНФ деякі змінні можуть бути відсутні. У той час як для кожної функції ДДНФ існує єдина, ДНФ для тієї ж функції існує зліченна множина.

Диз'юнктивну нормальну форму, у тому числі і досконалу, можна побудувати за допомогою еквівалентних перетворень за наступним алгоритмом:

а) виключити “→” і “ ” за допомогою формул 13-15; б) за допомогою правил подвійного заперечення і де Моргана

виключити заперечення над операціями; в) розкрити дужки і застосувати властивість ідемпотентності,

закони виключеного третього і протиріччя; г) виключити константи по властивостях 12.

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

19

Правило побудови ДДНФ по ДНФ. Усяку ДНФ можна привести до ДДНФ розщепленням кон’юнкцій до всіх змінних, тобто елементарні кон’юнкції, у які співмножниками входять не всі змінні, множать на одиниці, представлені у вигляді диз'юнкцій кожної відсутньої змінної і її заперечення (закон «виключеного третього»), і розкривають дужки за законом дистрибутивності 4. Нарешті, виключають повторення доданків.

Приклад. Дану формулу привести до ДНФ і ДДНФ за допомогою еквівалентних перетворень.

F2 = (A → B) (B C) .

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

F2 = (A → B) (B C) = {формули 13, 14}

=(A B) (B C) (B C ) = {властивості 4, 5, 1} =

=(A B B A C B C) (B C ) = {властивості 4, 5} =

=A B B B B A B C B B C A B C B C

123 123 123

= A B C A B C B C – отримана ДНФ для функції, представленої формулою F2 .

Приведемо тепер ДНФ до ДДНФ за описаним правилом. A B C A B C B C = {додамо змінну A у третю

кон’юнкцію} = A B C A B C (A A) B C =

14243

=1

{властивість 4} = A B C A B C A B C A B C =

{властивості 2, 1 приводять до ДДНФ}=

= A B C A B C A B C .

Визначення. Елементарною диз'юнкцією називається диз'юнкція змінних або їхніх заперечень, у яку кожна змінна входить не більш одного разу. Кон’юнктивною нормальною формою (КНФ)

називається формула, представлена у вигляді кон’юнкції елементарних диз'юнкцій.

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

20

нормальні форми для функції трьох змінних.

Кожна формула алгебри висловлень має множину різних КНФ.

Визначення. Досконалою кон’юнктивною нормальною формою

(ДКНФ) формули алгебри висловлень називається КНФ, у якій:

-кожен співмножник містить доданками всі змінні, причому кожну тільки один раз із запереченням або без;

-відсутні повторення співмножників.

За допомогою еквівалентних перетворень будь-яка формула

приводиться до КНФ аналогічно її приведенню до ДНФ. В отриманій КНФ до елементарних диз'юнкцій, у які доданками входять не всі змінні, додати нулі, представлені у вигляді кон’юнкцій кожної відсутньої змінної і її заперечення (закон протиріччя), і за допомогою закону дистрибутивності диз'юнкції відносно кон’юнкції (властивість 5) привести ці співмножники до сум першої степені, тобто сум, що не містять добутків. Нарешті, виключити повторення співмножників.

Приклад.

(x y z) (x y z) = (x y z) (x y z) (x y z) – ДКНФ.

У табличному способі розглядаються тільки ті рядки таблиці істинності, де функція приймає значення 0. Кожному такому рядкові відповідає диз'юнкція всіх змінних, причому аргумент, що приймає значення 0, береться без заперечення, а той, що приймає значення 1, –

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com