Комбінаторика (стр. 3 из 7)

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

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

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

Розглянемо відношення р: „давати однакову остачу при діленні на 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) = Ш

К (а) = А

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

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

К (а) ≠ Ш

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

якщо а

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

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

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

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

арс і 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) = К (с).

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

с.

§ 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. О котрій годині ти повернешся вчора додому? – не є висловленням.