--PAGE_BREAK--Антитранзистивними є відношення перпендикулярності ().
Відношення між елементами множин можуть мати одну, дві, три або не володіти ні однією властивістю.
Наприклад, відношення перпендикулярності в множині прямих є симетричним, але не має рефлексивної і транзитивної властивостей, відношення р „число х більше числа у” у множині натуральних чисел є транзитивним, але не володіє властивостями рефлективності і симетричності.
§ 2. 4. Відношення еквівалентності.
Бінарне відношення р називається відношенням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне.
Відношення: „бути однокурсником” у множині студентів; „мати один і той же корінь” у множині слів є відношеннями еквівалентності.
Якщо між елементами деякої множини, встановлено відношення еквівалентності, то цим самим ми розбиваємо задану множину на класи.
Розглянемо відношення р: „давати однакову остачу при діленні на 3” у множині невід’ємних цілих чисел. Цим самим ми розбиваємо задану множину на такі класи, які не перетинаються:
К1 = {0, 3, 6, 9 ......} – остача нуль
К2 = {4, 7, 10 ......} – остача один
К3 = {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} є відношенням часткового порядку, тому що воно транзитивне, рефлексивне і антисиметричне.
У математиці та її застосуваннях особливу роль відіграють такі відношення порядку р, які дають можливість порівняти довільні різні елементи певної множини А. Ці відношення називаються відношеннями лінійного порядку у множині А.
Відношення строгого (нестрогого) порядку називається відношенням лінійного строгого (нестрогого) порядку, якщо для будь-яких різних елементів х і у із А здійснюється одне із відношень хру або урх.
Проілюструємо сказане на прикладі. Нехай А – множина студентів групи. Р – відношення „студент х вищий за студента у”. Це відношення антирефлексивне, антисиметричне і транзитивне.
Значить, воно відношення строгого порядку. Якщо в даній множині А немає студентів однакового росту, то тоді про будь-яких двох студентів можна сказати, що або студент х вищий за у або студент у вищий студента х. Отже, відношення Р є відношенням строгого лінійного порядку.
Множина А називається лінійною упорядкованою, якщо в А введено відношення Р і для будь-якої пари (х, у) є А І, якщо х ≠ у, то хру або
урх.
Так, множина натуральних чисел лінійно упорядкована відношенням строгого порядку „менше”, тобто 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.
Згідно з означенням маємо таку таблицю істинності для кон’юнкції.
p
q
p q
i
i
i
i
x
x
x
i
x
x
x
x
Приклад. Нехай висловлення р буде “5
Переважно скорочено таку кон’юнкцію записують як подвійну нерівність 8
Властивості кон’юнкції
1) Комутативна (переставна властивість) p q q p
p
q
p q
q p
і
і
і
і
і
х
х
х
х
і
х
х
х
х
х
х
2) Асоціативна (сполучна) властивість (p q) s p (q s)
p
q
s
(p q)
(p q) s
(q s)
(q s) p
і
і
і
і
і
і
і
і
х
х
х
х
х
х
х
і
х
х
х
х
х
х
х
і
х
х
х
х
х
і
і
х
х
і
х
і
х
і
х
х
х
х
і
і
х
і
х
х
х
х
х
х
х
х
х
х
Означення кон’юнкції двох висловлювань розповсюдна на будь-яке скінченне число висловлювань
рі = р1р2р3р4…рn
б) Логічне додавання (диз’юнкція)
Диз’юнкцією або логічною сумою двох висловлень p і q називається висловлення “p і q „ яке істинне тоді і тільки тоді, коли істинне хоча б одне із висловлювань і хибне коли вони обидва хибні.
Позначення диз’юнкції: p vq
Таблиця істинності:
p
q
pvq
i
i
i
i
x
і
x
i
і
x
x
x
Закони диз’юнкції
1) Комутативний: p vq q v p
p
q
p vq
q vp
і
і
і
і
і
х
і
і
х
і
і
і
х
х
х
х
2) Асоціативний закон диз’юнкції (pvq) vs pv(qvs)
p
q
s
p vq
(p vq) vs
q vs
p v (q vs)
і
і
і
і
і
і
і
і
х
х
і
і
х
і
х
і
х
і
і
і
і
х
х
і
х
і
і
і
х
і
і
і
і
і
і
і
х
і
і
і
і
і
і
і
і
і
і
і
і
х
х
х
х
х
х
х
3) Дистрибутивні закони, які пов’язують кон’юнкцію і диз’юнкцію
(pvq) s (p s) v(q s)
(pq) vs (p vs) (q vs)
Довести дома самостійно.
в) Заперечення висловлення
Запереченням висловлення р називається висловлення „не р“, яке істинне, коли р хибне, і хибне коли р істинне.
Позначення: .
р
і
х
х
і
Закони заперечення
1) Заперечення заперечення висловлення рівносильне висловленню р:
р
2) Закон суперпозиції
p х
р
p
і
х
х
х
і
х
3) Законвключення третього
qv i
Кожне висловлення q або істинне або хибне, третього не може бути qv =i
q
qv
і
х
i
х
і
i
4) Закони де Моргана
v
Заперечення кон’юнкції двох висловлень рівносильне диз’юнкції заперечень і заперечення диз’юнкції рівносильне кон’юнкції заперечень цих висловлень.
v
р
q
pq
v
і
i
i
х
x
x
x
i
x
x
і
x
i
i
x
i
x
i
i
x
i
x
x
x
x
x
x
x
г) Логічне слідування (імплікація)
Слідуванням (імплікацією) двох висловлень p і q називається висловлення “якщо p, то q„, яке хибне тоді і тільки тоді, коли p – істинне, а q – хибне. Позначається імплікація: pq
p
q
pq
i
i
i
i
x
x
x
i
і
x
x
i
продолжение
--PAGE_BREAK--