Формула включень та виключень

Нехай є N предметів, деякі з них мають властивості . При цьому кожний предмет може або не мати жодної з цих властивостей, або має одну або декілька властивостей. Позначимо через число предметів, що мають властивостями Якщо предмет не має якоїсь властивості, то цю властивість пишемо з рискою. Наприклад, - число предметів, що мають властивості і не мають властивості . Число предметів, що не мають жодної з зазначених властивостей, позначається за цим правилом Формула включень та виключень полягає у тому, що

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

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

Приклад 4.У науково-дослідному інституті працює 67 осіб. З них 47 знають англійську мову, 35 - німецьку і 23 - обидві мови. Скільки співробітників в інституті не знають ні англійської, ні німецької мови?

Розв’язок.Колектив співробітників можна розбити на частини: першу з них складають ті, хто знає тільки англійську мову;другу - ті, хто знає тільки німецьку мову;третю - ті, хто знає обидві мови;

четверту - ті, хто не знає жодної мови.

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

- знання англійської мови; - знання німецької мови;

N - число співробітників інституту; - число співробітників, що знають англійську мова; - число співробітників, що знають німецьку мова; - число співробітників, що не знають жодної мови. За формулою включень та виключень одержуємо:

Перестановки, сполуки, розміщення.

Різні упорядковані множини, що відрізняються лише порядком елементів (тобто можуть бути отримані з тої ж самої множини), називаються перестановками цієї множини. Число різних перестановок із n елементів дорівнює

Довільна k - елементна підмножина n - елементної множини називається сполукою із n елементів по k. Число сполук із n елементів по k дорівнює

Упорядковані k - елементні підмножини з n елементів називаються розміщеннями із n елементів по k. Число розміщень із n елементів по k дорівнює

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

Приклад 5. В ящику находиться 10 деталей, середи котрих 3 недосконалих. З ящика наугад витягають 5 деталей. Кількість існують способів витягнути деталі таким чином, щоб середи них окажетеся дві недосконалих , а три добрих.

Для рішення задачі застосуємо правило множення та сполуки.

Дві недосконалі деталі можливо витягнути кількістю способів , а три добрих кількістю способів . За правилом множення дві недосконалих, а три добрих кількістю способів способів.

Перестановки и сполуки з повтореннями.

Дотепер ми розглядали предмети, що були попарно різними. А тепер розглядатемо сукупності, у яких є однакові предмети. Нехай є предмети k різних типів, число предметів першого типу дорівнює , другого типу - k-го типу -

Число різних перестановок, що можна зробити з даних елементів, дорівнює

Число m - елементарних підмножин, порядок у який не приймається до уваги, дорівнює

Можно довести справедливость рівнянь:

1. (a+b)ⁿ= C_n^ka^kb^n-k. Ця формула носить назву бином Ньютона

2. C_n^k.= 2ⁿ Цю формулу получаемо, якщо в формуле бинома a=b=1 .

3. . Цю формулу получаемо, якщо в формуле бинома a=1, b=-1 .

4.

5.

Лекція 6. ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ

Логічні операції та їхні властивості

Під елементарним висловленням будемо розуміти оповідальне речення, про яке можна сказати однозначно: істинне воно чи хибне. Позначають елементарні висловлення латинськими буквами: A, B, C, …, X, Y, Z,а їхні значення (істину або хибність) відповідно або 1 і 0. Над елементарними висловленнями можуть провадитися логічні операції: кон’юнкція, диз'юнкція, імплікація, еквівалентність, заперечення.

Кон’юнкція (позначається “ ” або “&”) двох висловлень утворить нове висловлення, яке істинне тоді і тільки тоді, коли A і B істинні. Кон’юнкції відповідає така істинностна таблиця:

A	B

Диз'юнкція (позначається “Ú”) двох висловлень A B істинна тоді і тільки тоді, коли хоча б одне з висловлень істинне. Таблиця істинності.

A	B

Імплікація або проходження (позначається “ ”) / A B хибна тоді і тільки тоді, коли A - істинне, а B - хибна. Таблиця істинності така:

A	B

Еквівалентність або подвійна імплікація (позначається ~ або «) A «B істинна тоді і тільки тоді, коли A і B обидва істинні або хибні. Таблиця істинності така:

A	B

Заперечення (позначається “-”) хибне тоді і тільки тоді, коли А істинне і навпаки.

Таблиця істинності:

A

Дві формули алгебри висловлень називаються рівносильними, якщо їх таблиці істинності збігаються. Для логічних операцій справедливі такі властивості:

1) комутативність

2) асоціативність

3) дистрибутивність

4) закони де Моргана

5)

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

Для побудови таблиці істинності складного висловлення слід підготувати таблицю, що містить рядків (де n - кількість елементарних висловлень, що утворює дане складне висловлення), заповнених можливими значеннями елементарних висловлень. Потім треба виконати логічні операції, використовуючи властивості застосованих операцій і звертаючи увагу на порядок їх виконання. Спочатку виконуються дії в дужках (дужки, як правило, опускаються під знаком операції заперечення).За пріоритетом першою виконується операція доповнення, потім кон’юнкція, диз'юнкція, імплікація та еквівалентність.

Лекція 7. ПЕРЕВІРКА ПРАВИЛЬНОСТІ МІРКУВАНЬ

Міркування є твердженням того, що деяке висловлення (висновок) випливає з інших висловлень (посилок). Міркування вважається правильним тільки у тому випадку, якщо з кон’юнкції посилок випливає висновок.

Нехай - посилки, а Q - висновок. Міркування є правильним, якщо імплікація є тотожно істинним висловленням (тавтологією). При невеликому числі посилок для встановлення правильності міркування можна побудувати істинностну таблицю висловлення і переконатися у тому, що вона тотожно істинна.

Правильність міркування можна встановити також, переконавшись, що контрапозиція тотожно істинна (методом “від супротивного”).

Метод “від супротивного” полягає у припущенні, що висновок хибний та, і встановленні того факту, що при цьому кон’юнкція - хибна (що має місце у тому випадку, якщо хоча б одна з посилок ( приймає значення “хибне”). Якщо це виконується, то міркування вірне, у противному випадку - ні. Таким чином, у випадку правильного міркування ми переконуємося в тому, що контрапозиція - тотожно істинна.

Приклад 6. Треба встановити, чи правильне міркування:

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

У запропонованому для розгляду міркуванні посилки і висновок складаються з таких елементарних висловлень:

А - функція неперервна на даному інтервалі;

В - функція має різні знаки на кінцях інтервалу;

С - функція обертається в нуль усередині даного інтервалу.

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

_______________________________

Міркування є вірним, якщо імплікація тотожно істинна.

Для перевірки правильності міркувань будуємо істинностну таблицю:

А	В	С

Переконуємося, що міркування є вірним.

Лекція 8. НОРМАЛЬНІ ФОРМИ АЛГЕБРИ ВИСЛОВЛЕНЬ

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

Елементарним добутком називається кон’юнкція елементарних висловлень або їхніх заперечень. Наприклад,

Елементарною сумоюназивається диз'юнкція елементарних висловлень або їхніх заперечень. Наприклад,

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

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

Теорема 1.Формула алгебри висловлень є тотожно істинною тоді і тільки тоді, коли кожний множник її КНФ містить пару доданків, один з яких є елементарним висловленням, а інший - його запереченням.

Теорема 2.Формула алгебри висловлень і є тотожно хибною тоді і тільки тоді, коли кожний доданок її ДНФ містить пару співмножників, один із яких є елементарним висловленням, інший - його заперечення.

Теореми 1, 2 дозволяють вирішувати питання про здійсненність будь-якої формули алгебри висловлень.

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

Для кожної формули алгебри висловлень можна знайти множину ДНФ і КНФ. Для цього потрібно:

1) позбутися від логічних операцій імплікації та еквівалентності, що містяться у формулі, замінивши їх основними - кон’юнкцією, диз'юнкцією, запереченням. Це можна зробити використовуючи рівносильні формули

2) замінити знак заперечення, що ставиться до виразів типу або знаками заперечення, що ставляться до окремих висловлень на підставі формул (закони де Моргана);

3) позбутися від знаків подвійного заперечення на підставі рівності

4) застосувати, якщо потрібно, до операцій кон’юнкції і диз'юнкції властивості дистрибутивності.

Потім на побудованій диз’юнктивні нормальній формі перевірити виконання умови теореми 2 і якщо ДНФ задовольняє їі, то формула є нездійсненною. Можна побудувати КНФ для заперечення вихідної формули. Якщо виявиться, що вона задовольняє умови теореми 1, то вихідна формула - тотожно істинна. В інших випадках - формули здійсненні.

Приклад 7. Побудувати КНФ для формули алгебри висловлень:

1. Позбудемося від знаків імплікації, використовуючи рівносильні формули:

2. Позбудемося від знака еквівалентності, використовуючи рівносильну формулу

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

4. Позбудемося від подвійних і потрійних заперечень:

5. Застосуємо закони дистрибутивності

одержимо , що є КНФ для даної формули S.

6. Використовуючи властивості і , спростимо КНФ для S:

Отже, формула S - здійснена.

Лекція 9. ДОСКОНАЛІ НОРМАЛЬНІ ФОРМИ

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

1. Вона не містить двох однакових доданків.

2. Жодний із співмножників не містить двох однакових доданків.

3. Жодний із співмножників не містить одночасно деяке змінне висловлення і його заперечення.

4. Кожний співмножник ДДНФ містить доданок або змінне висловлення, або його заперечення для всіх змінних висловлень, що входять у формулу.

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

1. Вона не містить двох однакових співмножників.

2. Жоден із співмножників не містить двох однакових доданків.

3. Жоден із співмножників не містить одночасно деяке змінне висловлення та його заперечення.

4. Кожен співмножник ДКНФ містить як доданок або змінне висловлення, або його заперечення для всіх змінних висловлень, що входять у формулу.

Визначення СКНФ так само є конструктивним.

Приклад 8. Дана КНФ .

Побудувати СКНФ.

1.

2.

3.

4.

Обчислення предикатів

Під обчисленням розуміється система, в який існує деяке число вхідних об`єктів (аксіом) і деяке число правил побудови ( правил висновку) нових об`єктів з вхідних і вже постійних. При цьому в обчисленнях (в відзнаку від алгоритмів) порядок застосування правил висновку може бути довільним. В обчисленні предикатів основним об`єктом є змінне висловлювання (предикат), істинність або хибність якого залежить від значень що входять в нього змінних. Істинність предиката « X був фізиком» залежить від значення змінної X. Для позначки області значень змінних в обчисленні предикатів використовуються два квантора: квантор спільності і квантор існування . Тоді затвердження x P(x) читається так: «для всіх x має місце P(x)» , а xQ(x) –

« існує таке x, що Q(x)». В обчисленні предикатів існує ще одне поняття – формула. Формули будуються використовуючи логічні операції, наприклад

(

де A,B,C.D – висловлювання.

Обчислення предикатів включає в себе всі формули обчислення висловлювань , а також формули, що містять окрім символів висловлювань предикатні символи з кванторами. Наприклад,

Виділене підмножина тотожно істинних формул, істинність яких не залежить від істинності висловлювань, що входять в них, називаються аксіомами. В обчисленні предикатів є безліч правил висновку. Наприклад, класичне правило modus ponens: , що читається так:

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