Перестановки з повтореннями та без повторення. 3 страница

Таблиця № 4. Таблиця істинності для операції диз’юнкції.

Означення: диз'юнкцією двох висловлень а і b називають таке нове висловлення аÚb, яке істинне тоді і тільки тоді, коли істинне хоча б одне із висловлень а і b.

Яку операцію над числами нагадує нам означення диз’юнкції двох висловлень задане таблицею істинності? – певним чином операцію додавання чисел. Саме тому операцію диз'юнкції називають логічним додаванням. Означення операції диз'юнкції двох висловлень можна поширити на три, чотири та на будь-яке скінченне число висловлень. Наприклад: диз’юнкцією висловлень а, b, с називається таке нове висловлення, яке хибне тоді і тільки тоді, коли хибне кожне з висловлень а, b і с, тобто аÚbÚс=(аÚb)Ú с. Враховуючи сказане, зазначимо, що всі твердження, які ми будемо доводити для двох висловлень щодо диз’юнкції, будуть, майже завжди, істинними для будь-якого скінченого числа висловлень.

Безпосередньо із означення диз’юнкції двох висловлень легко переконатися у справедливості таких властивостей (законів): 1) аÚ1=1; 2) аÚ0=а; 3) аÚа=а – закон ідемпотентності. Крім вказаних законів, операція диз’юнкції висловлень підкоряється таким законам:

3. аÚв=вÚа –комутативний (переставний) закон.

4. (аÚв)Úс=аÚ(вÚс) – асоціативний (сполучний) закон.

5. аÙ(вÚс)=(аÙв)Ú(аÙс) – дистрибутивний (розподільний) закон операції кон’юнкції відносно диз’юнкції.

6. аÚ(вÙс)=(аÚв)Ù(аÚс) – дистрибутивний (розподільний) закон операції диз’юнкції відносно кон’юнкції (п’ятий та шостий закони пов’язують операції кон’юнкції та диз’юнкції).

7. аÙв=āÚв.

8. аÚв=āÙв - закони де Моргана, які пов’язують операції заперечення, кон’юнкції та диз’юнкції.

Закони 3-8 потребують доведення. Його проводять, використовуючи таблиці істинності. Покажемо це на прикладі останнього закону де Моргана (див. таблицю № 5). Кількість стовпців таблиці істинності дорівнює 7, а кількість рядків – 2²+1=5 (як це визначили?). Заповнення стовпців виконаємо аналогічно до того, як це робилося при побудові таблиці істинності у попередньому пункті.

а	В	Ā	в	аÚв	аÚв	āÙв

Таблиця № 5. Доведення закону де Моргана.

5.2. Диз'юнкція двох предикатів.

5.2. Для того, щоб визначити операцію диз’юнкції предикатів, розглянемо на множині абітурієнтів предикати: А(х): „х – склав всі екзамени” і В(х): „х – набрав прохідний бал”. Як можна назвати предикат „х – склав всі екзамени або набрав прохідний бал” - диз'юнкцією заданих предикатів. Отже, приймемо таке означення.

Означення: диз'юнкцією двох предикатів А(х) і В(х), заданих на одній і тій самій множині Х, називається такий новий предикат А(х)ÚВ(х), який визначений на множині Х і який хибний при всіх тих хÎХ, при яких одночасно хибні обидва предикати.

При оперуванні із складенимипредикатами доводиться знаходити їх множини істинності. Знайдемо множину істинності предиката А(х)ÚВ(х). Позначимо область визначення предикатів через Х, множину істинності предиката А(х) через Т_А, а множину істинності предиката В(х) – через Т_В. Щоб знайти множину істинності предиката А(х)ÚВ(х), тобто Т_АÚ_В, на діаграмі Ейлера-Венна зафарбуємо спочатку множину істинності предиката А(х), а потім - множину істинності предиката В(х). Тоді множина істинності предиката А(х)ÚВ(х) буде зображатися тією частиною множини Х, яка зафарбована (див. таблицю №6).

Таким чином, множина істинності предиката А(х)ÚВ(х) є об’єднанням множин істинності предикатів А(х) і В(х), тобто справедлива рівність Т_АÚ_В=Т_АÈТ_В. Операція диз’юнкції предикатів підкоряється тим же самим законам, що і операція диз’юнкції висловлень. Пропонуємо студентам записати відповідні закони самостійно.

Таблиця № 6. Множина істинності диз’юнкції предикатів Т_АÚВ=Т_АÈТ_В.

6. Операція імплікації над висловленнями та предикатами. Її таблиця істинності. Основні властивості (закони) операції імплікації.

6.1. Операція імплікації висловлень.

6.1. Ми вже розглянули три операції над висловленнями та предикатами. Кожній з них, певним чином, відповідали частка не чи сполучники: і, або. У математиці досить часто використовуються словосполучення «якщо …, то …», слова «випливає», «слідує» тощо. Розглянемо два висловлення: а=„число 2 просте” і в=„число 2 – парне”. Утворимо з цих двох простих висловлень за допомогою словосполучення «якщо …, то …» або слова «слідує» нове висловлення: „якщо число 2 – просте, то воно парне” або «із того, що число 2 – просте, слідує (випливає), що воно парне». Воно є складеним (Чому?). У математичній логіці таке нове висловлення називають імплікацією (грецьк. Implico– тісно зв'язую) даних висловлень і позначають так: а→b або аÞb. Символічний запис а→b або аÞb читають так: „якщо а, то b”, або „з а слідує (випливає) b”, або „імплікація а і b”, або „а імплікує в b”. Тепер сформулюємо строге математичне означення цієї операції над висловленнями.

Означення: імплікацією двох висловлень а і b називається таке нове висловлення а→b, яке хибне тоді і тільки тоді, коли висловлення а істинне, а висловлення b – хибне, і істинне в усіх інших випадках.

За допомогою таблиці істинності операцію імплікації можна задати так (див. таблицю №7).

Таблиця № 7. Таблиця істинності для операції імплікації висловлень.

В імплікації а→b висловлення а називають або умовою, або посилкою, або основою імплікації, а висловлення b – висновком або наслідком імплікації. Зв'язок між операцією імплікації та операціями заперечення та диз'юнкції задається за допомогою такої формули: а→b=āÚв.Доведемо її за допомогою таблиці істинності (див. таблицю №8). Порівнюючи 3 і 5 стовпчики, бачимо, що вони набувають однакових значень істинності при будь-яких наборах значень істинності висловлень а і b.

Таблиця № 8: доведення формули а→b=āÚв.

Розглянемо імплікацію:а→b=„якщо число закінчується на 0, то воно ділиться на 5”.Домовимося називати її даною або прямою імплікацією. Переставивши місцями умову та висновок, одержимо нову імплікацію b→а=„якщо число ділиться на 5, то воно закінчується нулем”. Така імплікація називається оберненою до даної. Замінимо в даній імплікації а→bумову і висновок їх запереченнями. Отримаємо нову імплікацію`ā→b=„якщо число не закінчується на 0, то воно не ділиться на 5”, яку називають імплікацією, протилежною до даної. Поміняємо в останній імплікації місцями умову та висновок. Тоді одержимо імплікацію`в→ā=„якщо число не ділиться на 5, то воно не закінчується нулем”. Цю імплікацію називають імплікацією протилежною до оберненої або оберненою до протилежної. Таким чином, маємо чотири види імплікації: 1) а→b – пряма; 2) b→а – обернена до даної; 3) ā→b - протилежна до прямої; 4)`b→ā - протилежна до оберненої або обернена до протилежної. Виникає запитання: як ці види імплікацій пов’язані між собою? Для виявлення зв'язку між імплікаціями побудуємо таблицю істинності (див. таблицю №9).

а	в	`а	`b	а →b	b→а	`а→b	`b →а

Таблиця № 9. Доведення рівносильності різних видів імплікацій.

Аналізуючи побудовану таблицю, бачимо, що значення 5-го і 8-го стовпців приймають однакові значення істинності при всіх наборах значень істинності висловлень, що до них входять. Саме тому можна твердити, що справедливі такі рівності: а→b=b→а та b→а=а→b.Таким чином, маємо дві пари рівносильних між собою імплікаційа→b=b→а та b→а=а→b. Це дає змогу визначати істинність не всіх чотирьох імплікацій, а лише двох (по одній із кожної пари), бо істинність двох інших випливатиме із рівносильності пар імплікацій.

6.2. Операція імплікації предикатів.

6.2. Для того, щоб визначити операцію імплікації предикатів, розглянемо на множині абітурієнтів предикати: А(х): „х – склав всі екзамени” і В(х): „х – набрав прохідний бал”. Як можна назвати предикат „якщо х – склав всі екзамени, то він набрав прохідний бал” – імплікацією заданих предикатів. Отже, приймемо таке означення.

Означення: імплікацією двох предикатів А(х) і В(х), заданих на одній і тій самій множині Х, називається такий новий предикат А(х)®В(х), який визначений на тій самій множині Х і який хибний при всіх тих хÎХ, при яких предикат А(х) – істинний, а предикат В(х) – хибний.

Оскільки при оперуванні із складенимипредикатами доводиться знаходити їх множини істинності, то знайдемо множину істинності предиката А(х)→В(х). Позначимо область визначення предикатів через Х, множину істинності предиката А(х) через Т_А, а множину істинності предиката В(х) – через Т_В. Щоб знайти множину істинності предиката А(х)→В(х), тобто Т_А→_В, можна використати міркування або діаграми Ейлера-Венна. Зазначимо, що міркуваннями множину істинності Т_А®В можна знайти, використавши рівність А(х) ®В(х)=Ā(х)ÚВ(х). Отже, маємо: Т_А®В =`Т<sub>А</sub>ÈТ<sub>В</sub>=Т<sub>`А</sub>ÈТ_В.

Відомо, що предикат А(х)®В(х) буде хибним для тих значень хєХ, для яких предикат А(х) істинний, а предикат В(х) – хибний, тобто на множині Т_АÇТ_В =`Т<sub>А</sub>È`Т_В = Т_`А È Т_В. Отже, множиною істинності предиката А(х)®В(х) – є об'єднання множини істинності предиката В(х) і доповнення до множини істинності предиката А(х) (див. таблицю №10).

Таблиця № 10. Зображення множини істинності імплікації Т_А®_В=`Т_АÈТ_В.

Чи розглядають імплікації в шкільному курсі математики? – так, але найчастіше розглядаються імплікації, які істинні при всіх хÎХ. Прикладами таких предикатів можуть бути такі: „Якщо число закінчується цифрою 5, то воно ділиться на 5”; „Якщо протилежні сторони чотирикутника попарно паралельні, то такий чотирикутник є паралелограмом”.

7. Операція еквіваленції над висловленнями та предикатами. Її таблиця істинності. Основні властивості (закони) операції еквіваленції.

7.1. Операція еквіваленції висловлень.

7.1. Ми вже розглянули чотири операції над висловленнями та предикатами. Кожній з них, певним чином, відповідали: частка не; сполучники і, або; слова чи словосполучення «якщо…, то…», «випливає», «слідує», «імплікує». У математиці досить часто використовуються словосполучення «тоді і тільки тоді», «необхідно і достатньо», слова «рівносильно», «еквівалентно» тощо. Розглянемо два висловлення: а=„число 2 просте” і в=„число 2 – парне”. Утворимо з цих двох простих висловлень за допомогою словосполучення «тоді і тільки тоді» або «необхідно і достатньо» нові висловлення: „число 2 просте тоді і тільки тоді, коли воно парне” або «для того, щоб число 2 було простим, необхідно і достатньо, щоб воно було парним». Воно є складеним (Чому?). У математичній логіці таке нове висловлення називають еквіваленцією даних висловлень і позначають так: а↔b або аÛb. Символічний запис а↔b або аÛb читають так: „а рівносильно b”, або „а еквівалентно b”, або „еквіваленція висловлень а і b”, або „для а необхідно і достатньо b”, або „а тоді і тільки тоді, коли b”. Тепер сформулюємо строге математичне означення цієї операції над висловленнями.

Означення: еквіваленцією двох висловлень а і b називається таке нове висловлення а↔b, яке істинне тоді і тільки тоді, коли значення істинності висловлень а і b співпадають (або коли вони одночасно істинні або одночасно хибні).

За допомогою таблиці істинності операцію еквіваленції можна задати так (див. таблицю №11). Зв'язок між операціями еквіваленції, імплікації, кон’юнкції, заперечення та диз'юнкції виражається за допомогою таких формул: 1) а↔b=(а→b)Ù(b→а); 2) а↔b=(āÚb)Ù(bÚа). Другу формулу легко одержати із першої, якщо врахувати формулу:а→b=āÚb.

Таблиця № 11. Таблиця істинності еквіваленції висловлень.

7.2. Операція еквіваленції предикатів.

7.2. Для того, щоб визначити операцію еквіваленції предикатів, розглянемо на множині абітурієнтів два предикати: А(х): „х – склав всі екзамени” і В(х): „х – набрав прохідний бал”. Як можна назвати предикат „для того, щоб х – склав всі екзамени, необхідно і достатньо, щоб він набрав прохідний бал” – еквіваленцією заданих предикатів. Отже, приймемо таке означення.

Означення: еквіваленцією двох предикатів А(х) і В(х), заданих на одній і тій самій множині Х, називається такий новий предикат А(х)↔В(х), який визначений на тій самій множині Х і який істинний при всіх тих хÎХ, при яких значення істинності предикатів А(х) і В(х) співпадають.

Оскільки при оперуванні із складенимипредикатами доводиться знаходити їх множини істинності, то знайдемо множину істинності предиката А(х)↔В(х). Позначимо область визначення предикатів через Х, множину істинності предиката А(х) через Т_А, а множину істинності предиката В(х) – через Т_В. Щоб знайти множину істинності предиката А(х)↔В(х), тобто Т_А↔_В, можна використати міркування або діаграми Ейлера-Венна. Зазначимо, що міркуваннями множину істинності Т_А↔_В можна знайти, використавши рівність А(х)↔В(х)=((Ā(х)ÚВ(х))Ù(В(х)ÚА(х))). Отже, маємо: Т_А↔_В=(Т_АÈТ_В)Ç(Т_ВÈТ_А).Оскільки відомо, що предикат А(х)↔В(х) буде істинним для тих значень хєХ, для яких предикати А(х) і В(х) одночасно істинні або хибні, тобто на множинах Т_АÇТ_В і Т_{`А</sub>ÇТ<sub>`в}. Отже, множиною істинності предиката А(х)↔В(х) – є об'єднання цих множин, тобто Т_А↔_В=(Т_АÇТ_В)È(Т_{`А</sub>ÇТ<sub>`в}) (див. таблицю №12).

Таблиця № 12. Множина істинності еквіваленції предикатів.

8. Логічні формули. Порядок виконання логічних операцій у формулах. Рівносильні формули. Тотожньо істинні формули (логічні закони). Відношення логічного слідування та рівносильності на множині предикатів.

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

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

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

3) якщо у формулі немає дужок, то порядок виконання логічних операцій такий: а) заперечення; б) кон’юнкція; в) диз’юнкція; г) імплікація; д) еквіваленція. Застосування вказаних правил проілюструємо на наступній вправі.

Вправа: спростити вираз (aÚbÚcÚd)Ù(aÚbÚcÚd)Ù(aÚbÚc)Ù(aÚb)Ùā=(aÚbÚc)Ù(dÚd)Ù(aÚbÚc)Ù(aÚb)Ùā=(aÚbÚc)Ù1Ù(aÚbÚc)Ù(aÚb)Ùā=(aÚbÚc)Ù(aÚbÚc)Ù(aÚb)Ùā=(aÚb)Ù(сÚс)Ù(aÚb)Ùā=(aÚb)Ù1Ù(aÚb)Ùā=(aÚb)Ù(aÚb)Ùā=aÙ(bÚ b)Ùā=aÙ1Ùā=aÙā=0.

Побудуємо таблицю істинності для двох формул: a↔b і a→b.

Аналіз таблиці №13 дозволяє зробити висновок про те, що формула a→b набуває значення 1 при тих значеннях логічних змінних, при яких формула a↔b також набуває значення 1. В цьому випадку говорять, що формула a→b логічно випливає з формули a↔b. Символічно це позначають так a↔b╞a→b, а читають цей запис наступним чином: формула a→b логічно випливає з формули a↔b.

Таблиця № 13.

Означення: формула b називається логічним наслідком формули а (або формула b логічно випливає з формули а), якщо формула b набуває значення 1 при всіх тих наборах значень логічних змінних, при яких формула а також набуває значення 1.

Нехай на множині Х задано предикати А(х) і В(х) такі, що їх множини істинності Т_А і Т_В знаходяться у відношенні Т_АÌТ_В. З’ясуємо, якою буде імплікація А(х)→В(х) при певних значеннях хєХ. Виберемо довільне аєХ. При цьому можливі два випадки: 1) аєТ_А. Тоді аєТ_В, а тому А(а)=1 і В(а)=1, тобто А(а)→В(а)=1→1=1; 2) аєТ_А. Тоді А(а)=0, а імплікація А(а)→В(а)=0→В(а)=1. В таких випадках також говорять, предикат В(х) логічно випливає або логічно слідує із предиката А(х). Символічно це позначають так: А(х)╞ В(х).

Означення: якщо предикати А(х) і В(х) задані на одній множині Х, то кажуть, що предикат А(х) логічно випливає із предиката В(х), тоді і тільки тоді, коли Т_АÌТ_В.

Означення: якщо імплікація А(х)→В(х)=1 при всіх хєХ, то говорять, що предикат В(х) логічно слідує з предиката А(х).

Про такі предикати говорять, що вони знаходяться у відношення логічного слідування. Як же визначити чи знаходяться предикати у відношенні логічного слідкування? – слід дотримуватися такого алгоритму: 1) з’ясувати, чи на одній множині задані обидва предикати; 2) знайти множини істинності кожного з предикатів; 3) виявити співвідношення між множинами істинності предикатів; 4) якщо одна з множин істинності є підмножиною іншої, то зробити висновок про відношення логічного слідування між предикатами. Проілюструємо сказане на наступному прикладі.

Вправа: з’ясувати, чи знаходяться предикати А(х): «натуральне число х ділиться на 4» і В(х): «натуральне число х- парне» у відношенні логічного слідування.

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

В обох предикатах мова йде про натуральні числа, а тому областю визначення предикатів є множина натуральних чисел. Отже, предикати задані на одній множині. Знайдемо множини істинності предикатів. Т_А={4, 8, 12, 16, …, 4n, …}. Т_В={2, 4, 6, 8, …, 2n, …}. Звідси легко бачити, що Т_АÌТ_В. Таким чином, А(х)╞ В(х). Предикат А(х)→В(х) можна прочитати так: із того, що натуральне число ділиться націло на 4, логічно слідує, що натуральне число парне. До розв’язування цієї вправи можна підійти по-іншому. Утворимо імплікацію заданих предикатів А(х)→В(х). Легко бачити, що вона істинна. Отже, відповідно до другого означення можна твердити, що А(х)╞ В(х).

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

Означення: два предикати А(х) і В(х), які задані на множині Х, називаються рівносильними, якщо еквіваленція цих предикатів А(х)↔В(х) істинна при всіх хєХ (тобто, коли Х=Т_А↔_В).

Символічно це записують так: А(х)≡В(х). Щоб перевірити, чи рівносильні предикати слід з’ясувати наступне: 1) чи задані предикати на одній множині; 2) утворити еквіваленцію заданих простих предикатів; 3) знайти множину істинності еквіваленції; 4) порівняти область визначення та множину істинності; 5) якщо вони співпадають, то зробити висновок про те, що предикати знаходяться у відношенні рівносильності.

Вправа: з’ясувати, чи рівносильні предикати А(х): «натуральне число х ділиться націло на 5» і В(х): «десятковий запис натурального числа х закінчується на 0 чи 5».

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

Легко бачити, що предикати задані на одній множині натуральних чисел. Утворимо еквіваленцію А(х)↔В(х): «натуральне число х ділиться націло на 5 тоді і тільки тоді, коли його десятковий запис закінчується цифрами 0 чи 5». Отже, А(х)↔В(х)=1 при всіх хєХ, а тоді Т_А↔_В=Х. Таким чином, А(х)≡В(х).

Розглянемо деяку імплікацію А(х)→В(х), де хєХ. Нехай вона істинна при всіх хєХ. Якщо такі умови виконуються, то предикат А(х) називають достатньою умовою для предиката В(х), а предикат В(х) – необхідною умовою для предиката А(х). Якщо одночасно А(х)→В(х)=1 і В(х)→А(х)=1 при всіх хєХ, то кожен із предикатів називають необхідною і достатньою умовою для іншого. Теореми, які сформульовані у термінах необхідно і достатньо, називають ознаками. Прикладом ознак є ознаки подільності чисел, ознаки паралелограма, паралельності прямих і площин тощо.

Логічні операції над висловленнями (Ù, Ú, →, ↔, ¾) до певної міри відповідали сполучникам, словосполученням, частці „не”. Квантор існування можна розглядати як узагальнення диз'юнкції. Дійсно, нехай Х={а₁, а₂, а₃,...а_к} Р(х), де хÎХ, тоді висловлення... ($х)Р(х) рівносильне диз'юнкції Р(а₁)ÚР(а₂)Ú...ÚР(а_к). Квантор загальності можна розглядати, як узагальнення операції кон'юнкції. Дійсно, якщо Р(х), де хÎХ={а₁, а₂, а₃,..., а_к}, то висловлення ("х)Р(х) рівносильне кон'юнкції Р(а₁)Ù Р(а₂)Ù... Ù Р(а_к). Не важко здогадатися, що операції об’єднання в алгебрі множин відповідає операція диз’юнкції із алгебри висловлень, операції перетину – операція кон’юнкції, операції доповнення – операція заперечення. Ми з Вами розглянули основні операції алгебри висловлень та їх основні властивості (аÚв=вÚа, аÙв=вÙа, аÚ(вÚс)=(аÚв)Úс, аÙ(вÙс)=(аÙв)Ùс, аÙ(вÚс)=(аÙв)Ú(аÙс), аÚ(вÙс)=(аÚв)Ù(аÚс), аÚ0=0Úа=а, аÙ0=0Ùа=0, аÚ1=1Úа=1, аÙ1=1Ùа=а, аÙа=а, аÚа=а тощо). Побудувавши таблиці істинності можна довести справедливість наступних законів: