Комбінаторика

Розділ I. Елементи теорії множин

§1.1. Поняття множини

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

Об’єкти, із яких складається множина, називаються її елементами. Множини позначається великими буквами, а її елементи малими. Те, що елемент а належить множені А записується так а А. Запис а є А або а А означає, що елемент а не належить множені А.

Окремі найважливіші множини мають загальноприйняте позначення

· N – множина натуральних чесел (1, 2, 3, 4…)

· Z – множина цілих чисел (…-3, -2, -1, 0, 1, 2, 3…)

· Q – множина раціональних чисел (Z + дробові числа)

· I – множина всіх ірраціональних чисел

· R – множина дійсних чисел ( Q + ірраціональні чисела)

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

Множина, яка містить скінчену кількість елементів називається скінченою.

Запис A={a₁, a₂, a₃… a_n} означає, що множина А скінчена і містить n елементів. Множина Х={x₁, x₂… , x_n….} – є незкінченою. Множина, яка не містить жодного елементу називаєтся порожньою і позначається символом .

Приклади: Множина дійсних коренів рівняння x²+1=0, множина усіх цілих чисел, що діляться на 4, але не діляться на 2.

Нехай P(x) – деяка властивість (закон, правило, форма) числа х, тоді запис

{x| P(x)} означає множину всіх тих чисел х, для яких виконується властивість Р(х). Наприклад:

1. {x|x є R, x² + 3x + 4 =0} множина тих дійсних чисел х, які є розв’язками рівняння x² + 3x + 4 =0.

2. А={x| x є z, |x|≤100} – множина тих цілих чисел модуль яких не більший за 100, тобто елеменетами множини А є цілі числа по порядку від -100 до +100.

Множину можна подати у вигляді відрізку на числовій осі:

x

-3 -2 -1 0 1 2 3 4 5 6

мал.1.1

А={x| x є R, 2 ≤ x < 5} A=[2,5)

Числові проміжки позначаються так:

Нехай а і b – дійсні числа, причому а<b.

Розглянемо числові множини.

· [a; b] = {x|a ≤ x ≤ b } – закритий відрізок, сегмент;

· (a; b) = {x|a < x < b } – відкритий інтервал;

· (a; b] = {x|a < x ≤ b } – напівінтервал, напіввідкритий інтервал,

· [a; b) = {x|a ≤ x < b } – напівсегмент;

· (- ∞; + ∞) = {x|- ∞ < x < + ∞ } – нескінченно відкритий інтервал.

Введемо інтервал, що називається околом точки. Нехай х₀ – довільне дійсне число. Околом точки х₀ називається будь-який інтервал (α; β), що містить цю точку, тобто α < x₀ < β. Так околом точки x₀ = 1 є інтервал ( - 0,5; 1,5), (0,2) і т. д.

Інтервал ( x₀ – Е, x₀ + Е ), де Е > 0 називається Е – околом точки х₀, при цьому точку х₀ називають центром, а число Е – радіусом околу. Цей окіл буде досить малий, якщо число Е теж буде мале.

Нехай задано дві множини А і В. Якщо кожен елемент множини А є елементом мнгожини В, то множину А називають підмножиною множини В і пишуть АВ (А міститься в В).

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

Якщо множини А і В містять одні і ті ж елементи, тобто АВ і ВА, то їх називають рівними і пишуть А=В.

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

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

А не має спільних елементів з В і С , а В і С мають спільні елементи.

мал.1.2

§1. 2 Операції над множинами. Об’єднання і переріз двох множин.

Об’єданням двох множин А і В, називається множина А U В, елементи якої належать хочаб одній із цих множин.(мал.1.3)

мал.1.3

Об’єдання декількох множин.

A_i = A₁ U A₂ U A₃ U…U A_n

A_i ={x | x є А₁ або х є А₂ або х є А₃ або …х є А_n }

Перерізом двох множин А і В називається множина А ∩ В елементи якої належать як і множині А, так і множені В. (мал.1.4)

А ∩ В={x | х є А і х є В}

A_i={x | x є А₁ і х є А₂, х є А₃…х є А_n}

мал.1.4

Властивості об’єдання і перерізу множин:

Комутативний (переставний) закон

А U B = В U А;

А ∩ В = В ∩ А;

Асоціативний (сполyчний) закон.

А ∩ (В ∩ С) = (А ∩ В) ∩ С

А U (В U С) = (А U B) U С

Дистрибутивний (розподільний) закон.

А U (В ∩ С)=(А U B) ∩ (А U С)

А ∩ (В U С)=(А ∩ В) U (А ∩ С)

А U Ш = А.

А ∩ Ш = Ш.

Ці закони легко довести за допомогою діаграм. Доведемо 3-й дистрибутивний закон:

А U (В С) = (А U B) ∩ (А U С)

А U (В U С) (А U B) ∩ (А U С)

мал.1.5 мал.1.6

А ∩ (В U С)=(А ∩ В) U (А ∩ С)

А ∩ (В U С) (А ∩ В) U (А ∩ С)

мал.1.7 мал.1.8

§1. 3 Різниця і доповненя множин.

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

Різницею множин А та В називається множина АВ, яка складається зусіх тих елементів, які належать множині А і не належать В.(мал.1.9)

А В = {x | x є A I x ў B}

мал.1.9

Властивості різниці :

· А В ≠ В А – не комутативна .

· А (В С) ≠ (А В) С – не асоціативна

· А U Ш = А.

· А ∩ Ш = Ш.

· (B U C) A=(B A) U (C A) – дисрибутивний закон віднімання відносно об’єдання;

· (B ∩ C) A = (B A) ∩ (C A) – дистрибутивний закон віднімання відносно перерізу;

Якщо А є В, то різницю В А називають доповненням множини А до множини В і записують - = В А

мал.1.10

Отже, доповненням до підмножини А в множину В називається множина всіх елементів із множини В, які не належать А

Властивості доповнення, якщо АВ

Для довільних підмножин А і В універсальної множини М, доповнення до множин А і В дорівнюють перерізу множин , а доповнення до перізу множин А і В дорівнює об’єднанню їх доповнень .

Доведемо цей закон за допогою діаграм Ейлера – Венна:

1) ||| = ||| =

||| =

мал.1.11 мал.1.12

2)

||| = ||| -

# =

мал.1.3 мал.1.4

Розділ 2. МНОЖИНИ З ВІДНОШЕННЯМ

§ 2. 1. Упорядковані пари. Прямий (декартів) добуток множин.

Множини {1,5} і {5,1}, що містять одні і ті ж самі елементи, рівні, причому запис порядку їх елементів не має значення. Проте, якщо розглядати на площині дві точки А (1,5) і В (5,1), то порядок запису їх координат (1 ; 5) має принципове значення. Можна навести і інші приклади, коли треба врахувати порядок розміщення елементів множини (вектор на площині, вектор у просторі). У зв’язку з цим вводиться поняття упорядкованої сукупності об’єктів, зокрема упорядкованої пари.

Упорядкована пара це двоелементна множина, елементи якої розміщені в певному порядку.

Якщо а є А і b є В, то пару утворену з цих елементів позначають (a; b).

Елемент а називають лівою (першою) координатою (компонентою), а

b – правою (другою) координатою упорядкованої пари (а; b).

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

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

Отже, А х В = {(а; b)| а є А, b є В}

Декартів добуток множин не комутативний

А х В ≠ В х А

А х В = В х А лише тоді, коли А = В або одна із множин порожня.

Щодо асоціативного закону, то йому декарті добуток не підлягає навіть тоді, коли множини А, В і С рівні. Отже, якщо А ≠ Ш, то А х (А х А) ≠ (А х А) х А.

Для прямого добутку справедливі такі дистрибутивні закони:

(А В) х С = (А х С) (В х С)

А х (В С) = (А х В) (А х С)

(А ∩ В) х С = (А х С) ∩ (В х С)

А х (В ∩ С) = (А х В) ∩ (А х С)

А х (В С) = (А х В) (А х С)

Декартів добуток АхА називають декартовим квадратом і позначається

А І = А х А = {(a, b) | а є А, b є А}

Декартів добуток множин А, В, С визначається так само як і декартів добуток двох множин

А х В х С = {(a, b, с) | а є А, b є В, с є С}

Декарті добуток А х А х А називається декартовим кубом і позначається

А і = А х А х А

Якщо множину дійсних чисел R = (- ∞: + ∞) можна ототожнювати з числовою прямою, то декартів квадрат R х R дійсних чисел можна ототожнювати з числовою площиною. Очевидно, R х R – сукупність всіх можливих упорядкованих пар дійсних чисел (х; y).

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

У зв’язку з цим прямий добуток множин і називають декартовим.

§ 2. 2. Бінарні відношення. Способи задання відношень.

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

Розглянемо бінарне відношення, тобто відношення між двома елементами однієї або різних множин.

Спочатку розглянемо приклад бінарного відношення між елементами двох множин А і В.

А = {Сашко, Борис, Володя, Галя, Таня, Оленка}

В = {футбол, волейбол, плавання, гімнастика, теніс}

За допомогою слів „займатися яким-небудь видом спорту” між елементами цих множин встановлено зв’язок, або, як говорять в математиці, відношення. В результаті ми одержали третю множину Р

Р = {(Сашко, волейбол), (Сашко, теніс), (Борис, футбол),

(Володя, плавання), (Галя, волейбол), (Оленка, теніс)}

Наведений приклад показує, що будь-яке бінарне відношення (відповідність) між елементами множин А і В повністю характеризується трьома множинами: А, В і Р – множиною пар, що є підмножиною А х В.

Р А х В

Множину упорядкованих пар Р називають графіком розглядуваного відношення.

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

У математиці досить часто доводиться мати справу з тими чи іншими відношеннями між певними об’єктами.

Найважливіші з них мають певні назви і позначення:

відношення рівності (═); відношення перпендикулярності (); відношення паралельності (║); відношення подільності ; відношення включення (); відношення конгруентності (); відношення подібності (~).

Бінарне відношення можна задати сукупністю впорядкованих пар, стрілочним і графічним способами.

Стрілочний спосіб полягає в тому, що множини А і В зображають кругами, їх елементи точками. Потім з’єднують стрілками елементи кожної пари (х; у), які належать графіку Р заданого відношення. В результаті одержимо фігуру, яку називають графіком розглядуваного відношення Р

При графічному зображенні відношення Р на площині ставимо точки, які відповідають парам (х; у), що належать відношенню Р. Множина цих точок і буде графіком даного відношення.

§ 2. 3. Властивості бінарних відношень.

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

Бінарне відношення р називається рефлексивним, якщо для будь-якої пари (х, х) є А І, елемент х знаходиться у відношенні р сам з собою.

Антирефлексивним називається таке відношення для якого х не знаходиться у відношенні р з х для будь-якої пари (х, х) є А І.

Рефлексивним є, наприклад, такі відношення рівності (═), не більше (≤), подільності (), рівносильності висловлювань (), паралельності (║), конгруентності () та подібності (~).

Антирефлексивними є відношення нерівності (≠), більше (>), менше (<), перпендикулярності (), не подільності ().

Бінарне відношення р називається симетричним, якщо для пари

(х, у) є А І із хру випливає урх.

Антисиметричним називається таке відношення для якого для будь-якої пари (х, у) є А І із хру випливає .

Симетричними є відношення рівності (═), рівносильності (≡), перпендикулярності (), конгруентності (), подібності (~).

Асиметричними є відношення більше (>), менше (<), не більше (≤), включення ().

Бінарне відношення р називається транзитивним, якщо для будь-яких трьох елементів х, у, z з множини А із хру і урz випливає xpz.

Антитранзистивним відношенням називається таке відношення для якого для будь-яких трьох елементів х, у, z з множини А із хру і урz випливає

Транзитивним є відношення менше (<), не більше (≤), подільності (), рівносильності (≡), конгруентності (), паралельності (║), подібності (~).

Антитранзистивними є відношення перпендикулярності ().

Відношення між елементами множин можуть мати одну, дві, три або не володіти ні однією властивістю.

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

§ 2. 4. Відношення еквівалентності.

Бінарне відношення р називається відношенням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне.

Відношення: „бути однокурсником” у множині студентів; „мати один і той же корінь” у множині слів є відношеннями еквівалентності.

Якщо між елементами деякої множини, встановлено відношення еквівалентності, то цим самим ми розбиваємо задану множину на класи.

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

К₁ = {0, 3, 6, 9 ......} – остача нуль

К₂ = {4, 7, 10 ......} – остача один

К₃ = {5, 8, 11 ......} – остача два

Класи, на які відношення еквівалентності розбиває множину А називаються класами еквівалентності. Це розбиття характеризується такими властивостями:

1. Ці класи не порожні

К_і ≠ Ш для всіх і = 1, 2, 3, ......, n

2. Будь-які два класи не перетинаються

К_і ∩ К_у = для будь-яких і, у = 1, 2, 3, ......, n

3. Об’єднання усіх класів дає універсальну множину А

К_і = А

Легко переконатися, що елементи із одного класу еквівалентні між собою, а елементи із різних класів – ні.

Теорема

Будь-яке відношення еквівалентності р здійснює розбиття множини А на класи еквівалентності так, що будь-які два елементи одного класу знаходяться у відношенні р, а будь-які два елементи різних класів не знаходяться у даному відношенні між собою.

Доведення

Нехай в множині А є відношення еквівалентності р. Візьмемо з цієї множини якийсь елемент а і виділимо в окремий клас К (а) всі елементи, які знаходяться з а у відношенні р

К (а) = {у | у є А, ару} (1)

Задане відношення р розіб’є всю множину А на ряд класів К, в результаті чого ми одержимо множину класів {К (а)}.

Доведемо, що множина {К (а)} для всіх а є А є розбиттям на класи, тобто що вона задовольняє трьом умовам розбиття на класи, а саме, що:

1) К (а) ≠ Ш

2) К (а) ∩ К (b) = Ш

3) К (а) = А

Покажемо, що справедлива перша умова.

Раз р є відношенням еквівалентності, то воно є рефлексивне, тобто ара. Значить К (а) має хоча б один елемент а і вже К (а) не порожня множина

К (а) ≠ Ш

Покажемо, що справджується умова 2) для будь-яких а і b є А,

якщо а b.

Доведемо цю умову виходячи з протилежного.

Припустимо, що К (а) ∩ К (b) ≠ Ш. Тоді у них є спільний елемент с, тобто

с є К (а) і с є К (b)

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

арс і bрс

Із симетричності відношення р із bрс слідує срb, а із транзитивності відношення р випливає:

якщо арс і срb, то арb.

А це протирічить умові, що аb.

Значить, припущення не вірне і

К (а) ∩ К (b) = Ш.

Покажемо, що виконується і умова 3).

Із формули (1) видно, що будь-який а є А належить класові К (а), тобто

а є К (а). Отже, щоб одержати множину А треба об’єднати усі ці класи

К (а) = А

^{а є А}

Ми довели, що відношення р розбиває множину А на класи еквівалентності.

Тепер покажемо, що: 1) два елементи одного класу еквівалентні між собою, а 2) два елементи різних класів не еквівалентні. Доведемо перше.

Нехай b і с будь-які два елементи одного класу К (а). Доведемо, що bрс. Раз b є К (а), то по формулі (1) – арb, а з того, що с є К (а) слідує, що арс. За симетричністю відношення р – з а р b слідує b р а. За транзитивністю відношення р маємо bра і арс, то bрс.

Доведемо друге. Нехай маємо два різні класи К (b) ≠ К (с). Покажемо, що b с. Доведемо від супротивного. Припустимо, що bрс. Нехай d – довільний елемент множини К (с), тоді cpd.

За симетричністю р маємо із bрс слідує срb.

За транзитивністю із bрс і срd слідує bpd.

Значить d є К (b).

Ми довели, що якщо d є К (с), то d є К (b) для вільного d.

Отже, К (с) К (b).

Аналогічно доводимо, що К (b) К (с).

Отже, К (b) = К (с).

А це протирічить умові. Значить, наше припущення не вірне і bс.

§ 2. 5. Відношення порядку. Упорядкована множина.

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

Інтуїтивне представлення про порядок об’єктів переважно пов’язано з їх взаємним розміщенням в просторі (вище – нижче, ближче – дальше, правіше – лівіше); в часі (раніше – пізніше); з порівнянням їх розмірів (більше – менше, легше – тяжче).

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

Відношенням строгого порядку називається будь-яке відношення, яке є антирефлексивним, антисиметричним і транзитивним.

Отже, відношення р буде відношенням строгого порядку, якщо:

1. хх для будь-якого х є А, тобто (х, х) Р для будь-якої пари

2. (х, х) є А І.

3. якщо хру , то ух для будь - якого х, у є А, тобто якщо (х, у) є Р, то

(у, х) Р для будь-якої пари (х, у) є А І.

4. якщо хру і урz, то хрz для будь-яких х, у, z є А, тобто якщо (х, у) є Р і (у, z) є Р, то і (х, z) є Р для будь яких пар (х, у) (у, z) є А І.

Так відношення р: „ х < у у множині А = {1, 2, 3, 4, 5} є відношенням строгого порядку, тому що воно антирефлексивне, антисиметричне, транзитивне.

Відношення р називається відношенням нестрогого (часткового) порядку, якщо воно рефлексивне, антисиметричне і транзитивне.

Так, відношення „число х – дільник числа у” у множині А = {1, 2, 3, 4, 5} є відношенням часткового порядку, тому що воно транзитивне, рефлексивне і антисиметричне.

У математиці та її застосуваннях особливу роль відіграють такі відношення порядку р, які дають можливість порівняти довільні різні елементи певної множини А. Ці відношення називаються відношеннями лінійного порядку у множині А.

Відношення строгого (нестрогого) порядку називається відношенням лінійного строгого (нестрогого) порядку, якщо для будь-яких різних елементів х і у із А здійснюється одне із відношень хру або урх.

Проілюструємо сказане на прикладі. Нехай А – множина студентів групи. Р – відношення „студент х вищий за студента у”. Це відношення антирефлексивне, антисиметричне і транзитивне.

Значить, воно відношення строгого порядку. Якщо в даній множині А немає студентів однакового росту, то тоді про будь-яких двох студентів можна сказати, що або студент х вищий за у або студент у вищий студента х. Отже, відношення Р є відношенням строгого лінійного порядку.

Множина А називається лінійною упорядкованою, якщо в А введено відношення Р і для будь-якої пари (х, у) є А І, якщо х ≠ у, то хру або

урх.

Так, множина натуральних чисел лінійно упорядкована відношенням строгого порядку „менше”, тобто N = {1, 2, 3, 4, ....}

Розділ 3. СИМВОЛІКА МАТЕМАТИЧНОЇ ЛОГІКИ

§ 3. 1. Поняття висловлення

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

Д. Буль (1815 – 1864 р.р.), батько відомої англійської письменниці Войнич (її чоловік був революціонером), автора роману „Овод”. Темп розвитку математичної логіки різко зростає у XIX ст. У 90-х роках ХХ ст.. математична логіка дістає широке застосування в технічних науках, наприклад, електротехніці. Зараз вона є складовою частиною теоретичного фундаменту кібернетики.

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

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

1. Діагональ квадрата не сумірна з його стороною – „і” висловлювання

2. 5 > 8 – „х” висловлення

3. О котрій годині ти повернешся вчора додому? – не є висловленням.

Висловлення позначаються малими латинськими буквами: p, q, r, s, ......

Множину усіх висловлювань, яку позначимо буквою S, ділять на дві підмножини (класи)

Т – клас усіх істинних висловлювань

F – клас усіх хибних висловлювань

Два висловлювання p і q називаються рівносильними (логічно рівними), якщо вони належать до одного й того самого класу і записують

p q

Із означення рівносильності висловлювань виникають властивості:

1. р р

2. Якщо р q, то q р – симетричність

3. Якщо р q і q r,то р r – транзитивність

§ 3. 2. Операції над висловленнями

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

а) Логічне множення (кон’юнкція)

Логічним добутком (кон’юнкцією) двох висловлень p і q називається

таке висловлення „p і q”, яке істинне тоді і тільки тоді, коли p і q одночасно істинні. Позначається: p q.

Згідно з означенням маємо таку таблицю істинності для кон’юнкції.

Приклад. Нехай висловлення р буде “5<8”, а висловлення q – “ 8 < 13 “, тоді кон’юнція цих висловлень буде “ I ”, бо істинне p i q .

Переважно скорочено таку кон’юнкцію записують як подвійну нерівність 8 < 5 < 13

Властивості кон’юнкції

1) Комутативна (переставна властивість) p q q p

2) Асоціативна (сполучна) властивість (p q) s p (q s)

Означення кон’юнкції двох висловлювань розповсюдна на будь-яке скінченне число висловлювань

р_і = р₁р₂р₃р₄…р_n

б) Логічне додавання (диз’юнкція)

Диз’юнкцією або логічною сумою двох висловлень p і q називається висловлення “p і q „ яке істинне тоді і тільки тоді, коли істинне хоча б одне із висловлювань і хибне коли вони обидва хибні.

Позначення диз’юнкції: p v q

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

Закони диз’юнкції

1) Комутативний: p v q q v p

2) Асоціативний закон диз’юнкції (p v q) v s p v (q v s)

3) Дистрибутивні закони, які пов’язують кон’юнкцію і диз’юнкцію

(p v q) s (p s) v (q s)

(p q) v s (p v s) (q v s)

Довести дома самостійно.

в) Заперечення висловлення

Запереченням висловлення р називається висловлення „не р“, яке істинне, коли р хибне, і хибне коли р істинне.

Позначення : .

Закони заперечення

1) Заперечення заперечення висловлення рівносильне висловленню р:

р

2) Закон суперпозиції

p х

3) Закон включення третього

q v i

Кожне висловлення q або істинне або хибне, третього не може бути q v = i

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

v

Заперечення кон’юнкції двох висловлень рівносильне диз’юнкції заперечень і заперечення диз’юнкції рівносильне кон’юнкції заперечень цих висловлень.

v

г) Логічне слідування (імплікація)

Слідуванням (імплікацією) двох висловлень p і q називається висловлення “якщо p, то q„, яке хибне тоді і тільки тоді, коли p – істинне, а q – хибне. Позначається імплікація: p q

Операцію імплікації двох висловлень можна виразити через операцію заперечення і диз’юнкцію:

p q v q

д) Еквіваленція (рівносильність) двох висловлень

Еквіваленцією (рівносильністю) двох висловлень p і q називається висловлення „р тоді, і тільки тоді, коли q, яке істинне тоді і тільки тоді, коли p і q одночасно істинні, або одночасно хибні“

Позначається: p q , p q

Еквіваленція

(p q) (p q q p)

§ 3.3. Предикати

(неозначуване висловлення або висловлювальна форма)

Розглянемо речення

1. х – парне число

2. Поет х написав поему “ Сон”.

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

Предикатом називається твердження, в яке входять вільні змінні і яке при заміні їх коректними значеннями стає висловленням.

Це є одномісні предикати.

Для кожного предиката треба, вказати множину значень, які може приймати змінна х. Цю множину називають областю визначення предиката і в першому прикладі область визначення – N, у другому - множина прізвищ поетів.

Предикат позначають великими буквами:

P(x), Q(x), R(x), S(x), де х Х.

Множина тих значень змінних, при яких предикат набуває істиного значення називається областю істинності предиката і позначається Т. Область істиності є підмножиною області визначення Т Х.

У першому прикладі Т = {x | x N i є парне}

У другому прикладі Т = { Шевченко }

Предикат в який входить дві змінні називаються двомісним. Приклади:

1. x > y;

2. “Поет х написа поему у “

Двомісні предикати позначаються P(x, y), Q(x, y) які визначені на множенні Х Ч У.

В математиці зустрічаються багато предикатів, причому деякі з них мають спеціальні позначення

„х = у“; „х < у“; „х ║ у“; „х у“ і т.д.

В математиці зустрічається і трьох, чотирьох і т.д. місні предикати. Приклади:

1. Число х ділиться на число у і на число z.

2. Всі числа, які діляться на х і у, діляться і на z.

3. Сума чисел х і у дорівнює добутку чисел U і V.

4. а₁х₁ + а₂х₂ + а₃х₃ + … + а_nx_n = b n–місний предикат

Нехай Q (a, b) – двомісний предикат.

(a - b)І = аІ – 2ab + bІ. Цей предикат перетворюється на істинне висловлення при всіх дійсних значеннях „a” і „b”. Областю істинності предиката Q є множина всіх дійсних чисел R. Такий предикат називається тотожно істинним.

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

§ 3. 4. Квантори.

У математиці часто використовують вирази „для всіх”, „для кожного”, „яке б не було”, „існує”, „знайдеться хоча б одне”.

Для позначення цих виразів вживаються символи, які називаються кванторами: квантор загальності , який позначається , у звичайній мові йому відповідає вираз „для кожного”, „для всякого”, „для всіх”.

Нехай Р(х) – „Трикутник х прямокутний», то вираз (х є Х) Р(х) читається:

1. Будь-який трикутник прямокутний

2. Кожний трикутник прямокутний

3. Всі трикутники прямокутні

Усі ці висловлення є хибними. Отже, в результаті квантифікації (приписуванні кватора) предикат перетворюється у висловлення. Цей квантор називається квантором загальності.

Розглянемо ще квантор існування, який позначається . У звичайній мові йому відповідає вираз: „існує”, „знайдеться хоча б одне”.

Нехай Р(х): „х > 5”

Вираз ( х є R) (х > 5) читається:

1. Існує дійсне число х таке, що х > 5

2. знайдеться таке дійсне число х, яке > 5

3. хоча б одне дійсне число > 5

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

Над предметами, так само, як і над множинами можна проводити операції кон’юнкцію, диз’юнкцію, заперечення, імплікацію і еквіваленцію.

§ 3. 5. Поняття про теореми.

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

Теорема – це математичне твердження, істинність якого з’ясовується доведенням (міркуванням).

Формулювання будь-якої теореми складається з двох частин: умови і висновку, який випливає з даної умови.

Розглянемо приклад. Теорема: „Якщо точка лежить на бісектрисі кута, то вона рівновіддалена від сторін цього кута”.

Якщо умову позначити через Р (х), то вона буде виражатися реченням: „Точка лежить на бісектрисі”, а висновок позначити через Q (х), то це буде речення „Точка рівновіддалена від сторін кута”. Як умова так і висновок є предикатами, які задані на множині Х всіх точок площини. Тому дану теорему можна записати у вигляді

(х є Х) (Р(х) Q (х))

Отже, в цій теоремі ми виділили такі три частини:

1. Умова теореми: предикат Р (х), заданий на множині Х усіх точок площини.

2. Висновок теореми: предикат Q (х), який заданий на множені Х

3. Пояснювальна частина х є Х: в ній описується множина об’єктів, про які йде мова в теоремі.

Умова і висновок не завжди є елементарними висловленнями, а можуть мати складну логічну структуру, найчастіше кон’юктивну або диз’юнктивну.

Наприклад:

1. Якщо діагоналі паралелограма взаємно перпендикулярні або ділять його кути пополам, то цей паралелограм ромб.

(х є Х) (Р₁ (х) v Р₂ (х)) Q (х))

Р₁ (х) – діагоналі взаємно перпендикулярні

Р₂ (х) – діагоналі паралелограма ділять його кут пополам

Q (х) – цей паралелограм – ромб.

2. Теорема про середню лінію трапеції

„Якщо чотирикутник є трапеція, то пряма, яка з’єднує середини непаралельних сторін паралельна основі трапеції і рівна їх півсумі”

(х є Х) (Р (х) (Q₁ (х) Q₂ (х))

Р (х) – чотирикутник трапеція

Q₁ (х) – середня лінія паралельна основі трапеції

Q₂ (х) – середня лінія рівна півсумі основ

(х є Х) – для будь-якого чотирикутника.

Теорема може мати і ще складнішу форму, включаючи різнойменні квантори.

§ 3. 6. Види теорем.

Ще у школі ми зустрічалися з різними видами теорем: пряма, обернена, протилежна. Розглянемо їх з точки зору предикатів.

Теорема: „Якщо сума цифр числа ділится на 3, то і це число ділиться на 3”.

Вона зипишеться: (х є N) (Р (х) Q(х))

х є N – теорема справедлива для всіх натуральних чисел.

Р (х) – умова теореми: „Сума цифр числа х : 3”.

Q(х) - висновок теореми: „Число х ділиться на 3 ”.

Будемо вважати, що це є пряма теорема.

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

(х є N) (Q (х) Р (х))

Обернена теорема: „Якщо число ділиться на 3, то сума цифр цього числа ділиться на 3”.

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

(х є N) ( )

„Якщо сума цифр даного числа не ділится на 3, то й саме число не ділиться на 3”.

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

(х є N) ( )

„Якщо число не ділиться на 3, то й сума цивр цього числа не ділиться на 3”.

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

Справедливі такі твердження:

1) Пряма теорема рівносильна теоремі, протилежній до оберненої

2) Обернена теорема рівносильна протилежній теоремі. Цю залежність можна зиписати:

(х є Х) (Р (х) Q(х) (х є Х) ()

(х є Х) (Q (х) Р (х) (х є Х) ()

§ 3. 7. Необхідні і достатні умови.

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

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

Приклади:

1. Подільність числа на 2 і 3 є необхідною умовою подільності на 12. Але це не достаня умова , бо є числа 18, 30. які діляться на 2 і 3, а на 12 не діляться.

2. Необхідною умовою рівності 2-х трикутників є рівність відповідних кутів цих трикутників.

3. Необхідною умовою подібності трикутніків є пропорційність відповідних сторін трикутників.

Необхідні умови формулюються переважно у вигляді протилежної або оберненої теореми:

(х є Х) (Q (х) Р (х))

(х є Х) ( )

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

Приклади:

Достатньою умовою рівності трикутників є рівність їх відповідних сторін.

Достатні умови будуть тоді, коли (х є Х) (Q (х) Р (х)) – істинна.

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

Приклади:

1. Подільність числа n на 2 і 3 є необхідною і достатньою умовою для подільності його на 6.

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

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

Умови можуть бути достатніми, але не необхідними.

Подільність числа на 6 є достатньою умовою того, щоб число було парним. Але чи буде вона необхідною? Ні? Існують числа 2, 4, 8, 10, 14, … які не дівляться на 6, але є парні. Візьмемо твердження: „Якщо многокутник правильний, то навколо нього можна описати коло”. Це достатня, але не необхідна умова. Існують і неправильні многокутники, навколо яких можна описати коло.

Бувають умови необхідні, але не достатні.

Приклади:

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

2. Подільність числа n на 2 є необхідною умовою для подільності на число 6. Але чи достатньо подільність числа на 2, щоб воно при всіх обставинах ділилося на 6. Є числа 4, 8, 10, 14, які ділятся на два але не ділятся на 6.

Ми одержимо такий переклад термінів “необхідно” і “достатню” на логічну мову.