Реферат: Комбінаторика

--PAGE_BREAK--Антитранзистивними є відношення перпендикулярності (<shape id="_x0000_i1091" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image084.wmz» o:><img width=«19» height=«20» src=«dopb62827.zip» v:shapes="_x0000_i1091">).
Відношення між елементами множин можуть мати одну, дві, три або не володіти ні однією властивістю.
Наприклад, відношення перпендикулярності в множині прямих є симетричним, але не має рефлексивної і транзитивної властивостей, відношення р „число х більше числа у” у множині натуральних чисел є транзитивним, але не володіє властивостями рефлективності і симетричності.
§ 2. 4. Відношення еквівалентності.
Бінарне відношення р називається відношенням еквівалентності, якщо воно рефлексивне, симетричне і транзитивне.
Відношення: „бути однокурсником” у множині студентів; „мати один і той же корінь” у множині слів є відношеннями еквівалентності.
Якщо між елементами деякої множини, встановлено відношення еквівалентності, то цим самим ми розбиваємо задану множину на класи.
Розглянемо відношення р: „давати однакову остачу при діленні на 3” у множині невід’ємних цілих чисел. Цим самим ми розбиваємо задану множину на такі класи, які не перетинаються:
К1 = {0, 3, 6, 9 ......} – остача нуль
К2 = {4, 7, 10 ......}   – остача один
К3 = {5, 8, 11 ......}   – остача два
Класи, на які відношення еквівалентності розбиває множину А називаються класами еквівалентності. Це розбиття характеризується такими властивостями:
         1. Ці класи не порожні
         Кі ≠ Ш для всіх і = 1, 2, 3, ......, n
         2. Будь-які два класи не перетинаються
         Кі ∩ Ку = <shape id="_x0000_i1092" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image100.wmz» o:><img width=«20» height=«20» src=«dopb62792.zip» v:shapes="_x0000_i1092"> для будь-яких і, у = 1, 2, 3, ......, n       
3. Об’єднання усіх класів дає універсальну множину А
         <shape id="_x0000_i1093" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image101.wmz» o:><img width=«23» height=«45» src=«dopb62835.zip» v:shapes="_x0000_i1093"> Кі = А
Легко переконатися, що елементи із одного класу еквівалентні між собою, а елементи із різних класів – ні.
Теорема
Будь-яке відношення еквівалентності р здійснює розбиття множини А на класи еквівалентності так, що будь-які два елементи одного класу знаходяться у відношенні р, а будь-які два елементи різних класів не знаходяться у даному відношенні між собою.
Доведення
Нехай в множині А є відношення еквівалентності р. Візьмемо з цієї множини якийсь елемент а і виділимо в окремий клас К (а) всі елементи, які знаходяться з а у відношенні р
К (а) = {у | у є А, ару}          (1)
Задане відношення р розіб’є всю множину А на ряд класів К, в результаті чого ми одержимо множину класів {К (а)}.
Доведемо, що множина  {К (а)} для всіх а є А є розбиттям на класи, тобто що вона задовольняє трьом умовам розбиття на класи, а саме, що:
1) К (а) ≠ Ш
2) К (а) ∩ К (b) = Ш
3) <shape id="_x0000_i1094" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image076.wmz» o:><img width=«16» height=«20» src=«dopb62825.zip» v:shapes="_x0000_i1094">К (а) = А
Покажемо, що справедлива перша умова.
Раз р є відношенням еквівалентності, то воно є рефлексивне, тобто ара. Значить К (а) має  хоча б один елемент а і вже К (а) не порожня множина
К (а) ≠ Ш
Покажемо, що справджується умова 2) для будь-яких а і b є А,
якщо а <shape id="_x0000_i1095" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image103.wmz» o:><img width=«16» height=«25» src=«dopb62836.zip» v:shapes="_x0000_i1095"> b.
Доведемо цю умову виходячи з протилежного.
Припустимо, що К (а) ∩ К (b) ≠ Ш. Тоді у них є спільний елемент с, тобто
с є К (а) і с є К (b)
Але елементи одного класу, відповідно до (1) знаходяться у відношенні р між собою, значить
арс  і  bрс
         Із симетричності відношення р із bрс слідує срb, а із транзитивності відношення р випливає:
якщо арс і срb, то арb.
         А це протирічить умові, що а<shape id="_x0000_i1096" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image105.wmz» o:><img width=«17» height=«28» src=«dopb62837.zip» v:shapes="_x0000_i1096">b.
         Значить, припущення не вірне і
К (а) ∩ К (b) = Ш.
         Покажемо, що виконується і умова 3).
         Із  формули  (1) видно,  що  будь-який  а є А  належить класові К (а), тобто
а є К (а). Отже, щоб одержати множину А треба об’єднати усі ці класи
<shape id="_x0000_i1097" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image107.wmz» o:><img width=«16» height=«20» src=«dopb62825.zip» v:shapes="_x0000_i1097"> К (а) = А
                                                                                         ає А
Ми довели, що відношення р розбиває множину А на класи еквівалентності.
Тепер покажемо, що: 1) два елементи одного класу еквівалентні між собою, а 2) два елементи різних класів не еквівалентні. Доведемо перше.
Нехай b і с будь-які два елементи одного класу К (а). Доведемо, що bрс. Раз b є К (а), то по формулі (1) – арb, а з того, що с є К (а) слідує, що арс. За симетричністю відношення р – з а р b слідує b р а. За транзитивністю відношення р маємо bра іарс, то bрс.
Доведемо друге. Нехай маємо два різні класи К (b) ≠ К (с). Покажемо, що b <shape id="_x0000_i1098" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image103.wmz» o:><img width=«16» height=«25» src=«dopb62836.zip» v:shapes="_x0000_i1098"> с. Доведемо від супротивного. Припустимо, що bрс. Нехай d – довільний елемент множини К (с), тоді cpd.
За симетричністю р маємо із bрс слідує срb.
За транзитивністю із bрс і срd слідуєbpd.
Значить d є К (b).
Ми довели, що якщо d є К (с), то d є К (b) для вільного d.
Отже, К (с) <shape id="_x0000_i1099" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image108.wmz» o:><img width=«16» height=«16» src=«dopb62838.zip» v:shapes="_x0000_i1099"> К (b).
Аналогічно доводимо, що К (b) <shape id="_x0000_i1100" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image108.wmz» o:><img width=«16» height=«16» src=«dopb62838.zip» v:shapes="_x0000_i1100"> К (с).
Отже, К (b) = К (с). <shape id="_x0000_i1101" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image042.wmz» o:><img width=«12» height=«23» src=«dopb62809.zip» v:shapes="_x0000_i1101">
А це протирічить умові. Значить, наше припущення не вірне і <shape id="_x0000_i1102" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image042.wmz» o:><img width=«12» height=«23» src=«dopb62809.zip» v:shapes="_x0000_i1102">b<shape id="_x0000_i1103" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image110.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1103">с.
§ 2. 5. Відношення порядку. Упорядкована множина.
Серед різних відношень ми часто зустрічаємо такі, які встановлюють у множині певний порядок.<shape id="_x0000_i1104" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image042.wmz» o:><img width=«12» height=«23» src=«dopb62809.zip» v:shapes="_x0000_i1104">
         Інтуїтивне представлення про порядок об’єктів переважно пов’язано з їх взаємним розміщенням в просторі (вище – нижче, ближче – дальше, правіше – лівіше); в часі (раніше – пізніше); з порівнянням їх розмірів (більше – менше, легше – тяжче).
         Ці відношення і подібні їм відносяться до важливого класу відношень, що називають відношеннями порядку.
Відношенням строгого порядку називається будь-яке відношення, яке є антирефлексивним, антисиметричним і транзитивним.
Отже, відношення р буде відношенням строгого порядку, якщо:
1.                х<shape id="_x0000_i1105" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image112.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1105">х для будь-якого х є А, тобто (х, х) <shape id="_x0000_i1106" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image113.wmz» o:><img width=«13» height=«23» src=«dopb62840.zip» v:shapes="_x0000_i1106"> Р для будь-якої пари
2.                 (х, х) є А І.
3.                якщо  хру, то у<shape id="_x0000_i1107" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image112.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1107">х  для будь — якого  х, у є А, тобто якщо (х, у) є Р, то
     (у, х) <shape id="_x0000_i1108" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image113.wmz» o:><img width=«13» height=«23» src=«dopb62840.zip» v:shapes="_x0000_i1108"> Р для будь-якої пари (х, у) є А І.
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-х роках ХХ ст… математична логіка дістає широке застосування в технічних науках, наприклад, електротехніці. Зараз вона є складовою частиною теоретичного фундаменту кібернетики.
Основним поняттям математичної логіки є висловлювання. Висловлювання належить до первинних понять, воно не визначеється через інші поняття, а вводяться за допомогою опису.
Під висловлюванням розуміють будь-яке твердження, відносно якого можна з’ясувати, істинне воно чи хибне. Наприклад,<shape id="_x0000_i1109" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image042.wmz» o:><img width=«12» height=«23» src=«dopb62809.zip» v:shapes="_x0000_i1109">
1.    Діагональ квадрата не сумірна з його стороною – „і” висловлювання
2.    5 > 8 – „х” висловлення
3.    О котрій годині ти повернешся вчора додому? – не є висловленням.
Висловлення позначаються малими латинськими буквами: p, q, r, s,…
Множину усіх висловлювань, яку позначимо буквою S, ділять на дві підмножини (класи)
Т – клас усіх істинних висловлювань
F – клас усіх хибних висловлювань
Два висловлювання p і q називаються рівносильними (логічно рівними), якщо вони належать до одного й того самого класу і записують
p <shape id="_x0000_i1110" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image115.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1110"> q
Із означення рівносильності висловлювань виникають властивості:
1.                     р <shape id="_x0000_i1111" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image115.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1111"> р
2.                     Якщо р <shape id="_x0000_i1112" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image115.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1112"> q, то q <shape id="_x0000_i1113" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image115.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1113"> р – симетричність
3.                     Якщо р <shape id="_x0000_i1114" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image115.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1114"> q і q <shape id="_x0000_i1115" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image115.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1115"> r, то р <shape id="_x0000_i1116" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image115.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1116"> r – транзитивність
§ 3. 2. Операції над висловленнями
У розмовній мові для сполучення двох речень вживають слова: і, або, якщо… то, тоді і тільки тоді, не. З’ясуємо те значення, в якому ці слова вживаються в логіці.
а) Логічне множення (кон’юнкція)
Логічним добутком (кон’юнкцією) двох висловлень p і q називається
таке висловлення „p і q”, яке істинне тоді і тільки тоді, коли p і q одночасно істинні. Позначається: p <shape id="_x0000_i1117" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1117">q.
Згідно з означенням маємо таку таблицю істинності для кон’юнкції.
p
q
p <shape id="_x0000_i1118" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1118"> q
i
i
i
i
x
x
x
i
x
 x
x
x
Приклад.  Нехай висловлення р буде “5<8”, а висловлення q – “ 8 < 13 “, тоді кон’юнція цих висловлень буде “ I ”, бо істинне p i q.
Переважно скорочено таку кон’юнкцію записують як подвійну нерівність 8 < 5 < 13
             Властивості кон’юнкції
1) Комутативна (переставна властивість) p <shape id="_x0000_i1119" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1119"> q <shape id="_x0000_i1120" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1120"> q <shape id="_x0000_i1121" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1121"> p
p
q
p <shape id="_x0000_i1122" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1122">q
q <shape id="_x0000_i1123" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1123">p
і
і
і
і
і
х
х
х
х
і
х
х
х
х
<img width=«9» height=«27» src=«dopb62843.zip» v:shapes="_x0000_s1026">х
<img width=«9» height=«27» src=«dopb62844.zip» v:shapes="_x0000_s1027">х
<img width=«74» height=«2» src=«dopb62845.zip» v:shapes="_x0000_s1028">
2) Асоціативна (сполучна) властивість (p <shape id="_x0000_i1124" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1124"> q) <shape id="_x0000_i1125" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1125"> s <shape id="_x0000_i1126" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1126"> p <shape id="_x0000_i1127" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1127"> (q <shape id="_x0000_i1128" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1128">s) 
p
q
s
(p <shape id="_x0000_i1129" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1129"> q)
(p <shape id="_x0000_i1130" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1130"> q) <shape id="_x0000_i1131" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1131"> s 
(q <shape id="_x0000_i1132" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1132"> s)
(q <shape id="_x0000_i1133" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1133"> s) <shape id="_x0000_i1134" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1134">p
і
і
і
і
і
і
і
і
х
х
х
х
х
х
х
і
х
х
х
х
х
х
х
і
х
х
х
х
х
і
і
х
х
і
х
і
х
і
х
х
х
х
і
і
х
і
х
х
х
х
х
х
х
х
х
х
<img width=«10» height=«27» src=«dopb62846.zip» v:shapes="_x0000_s1029"><img width=«10» height=«27» src=«dopb62847.zip» v:shapes="_x0000_s1030"><img width=«122» height=«2» src=«dopb62848.zip» v:shapes="_x0000_s1031"><img width=«122» height=«2» src=«dopb62848.zip» v:shapes="_x0000_s1032">
Означення кон’юнкції двох висловлювань розповсюдна на будь-яке скінченне число висловлювань
<shape id="_x0000_i1135" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image126.wmz» o:><img width=«32» height=«55» src=«dopb62849.zip» v:shapes="_x0000_i1135">рі = р1<shape id="_x0000_i1136" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image128.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1136">р2<shape id="_x0000_i1137" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1137">р3<shape id="_x0000_i1138" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1138">р4<shape id="_x0000_i1139" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1139">…<shape id="_x0000_i1140" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1140">рn
б) Логічне додавання (диз’юнкція)
Диз’юнкцією або логічною сумою двох висловлень p і q  називається висловлення “p і q „ яке істинне тоді і тільки тоді, коли істинне хоча б одне із висловлювань і хибне коли вони обидва хибні.
Позначення диз’юнкції: p vq
Таблиця істинності:
 p
q
pvq
i
i
i
i
x
і
x
i
і
x
x
x
                
  Закони диз’юнкції
1) Комутативний: p vq <shape id="_x0000_i1141" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1141"> q v p
p
q
p vq
q vp
і
і
і
і
і
х
і
і
х
і
і
і
х
х
<img width=«9» height=«27» src=«dopb62850.zip» v:shapes="_x0000_s1033">х
<img width=«9» height=«27» src=«dopb62851.zip» v:shapes="_x0000_s1034">х
<img width=«74» height=«2» src=«dopb62852.zip» v:shapes="_x0000_s1035">
2) Асоціативний закон диз’юнкції (pvq) vs<shape id="_x0000_i1142" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1142"> pv(qvs)
p
q
s
p vq
(p vq) vs 
q vs
p v (q vs)   
і
і
і
і
і
і
і
і
х
х
і
і
х
і
х
і
х
і
і
і
і
х
х
і
х
і
і
і
х
і
і
і
і
і
і
і
х
і
і
і
і
і
і
і
і
і
і
і
і
х
х
х
х
<img width=«10» height=«27» src=«dopb62853.zip» v:shapes="_x0000_s1036">х
х
<img width=«9» height=«27» src=«dopb62844.zip» v:shapes="_x0000_s1037">х
<img width=«122» height=«2» src=«dopb62854.zip» v:shapes="_x0000_s1038"><img width=«122» height=«2» src=«dopb62854.zip» v:shapes="_x0000_s1039">
3) Дистрибутивні закони, які пов’язують кон’юнкцію і диз’юнкцію
(pvq) <shape id="_x0000_i1143" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1143">s<shape id="_x0000_i1144" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image134.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1144"> (p <shape id="_x0000_i1145" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1145">s) v(q <shape id="_x0000_i1146" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1146">s)
(p<shape id="_x0000_i1147" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1147">q) vs<shape id="_x0000_i1148" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image135.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1148"> (p vs) <shape id="_x0000_i1149" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1149"> (q vs)
Довести дома самостійно.
в) Заперечення висловлення
Запереченням висловлення р називається висловлення „не р“, яке істинне, коли р хибне, і хибне коли р істинне.
                                           Позначення: <shape id="_x0000_i1150" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1150">.
р
<shape id="_x0000_i1151" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1151">
і
х
х
і
Закони  заперечення
1) Заперечення заперечення висловлення рівносильне висловленню р:
<shape id="_x0000_i1152" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image137.wmz» o:><img width=«17» height=«29» src=«dopb62855.zip» v:shapes="_x0000_i1152"><shape id="_x0000_i1153" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1153"> р
2) Закон суперпозиції
p<shape id="_x0000_i1154" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1154"><shape id="_x0000_i1155" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1155"><shape id="_x0000_i1156" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1156"> х
р
<shape id="_x0000_i1157" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1157">
p<shape id="_x0000_i1158" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1158"><shape id="_x0000_i1159" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1159">
і
х
х
х
і
х
3) Законвключення третього
qv <shape id="_x0000_i1160" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1160"> <shape id="_x0000_i1161" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1161"> i
Кожне висловлення q або істинне або хибне, третього не може бути qv <shape id="_x0000_i1162" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1162"> =i
q
<shape id="_x0000_i1163" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1163">
qv <shape id="_x0000_i1164" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1164">
і
х
i
х
і
i
4) Закони де Моргана
<shape id="_x0000_i1165" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image141.wmz» o:><img width=«39» height=«28» src=«dopb62857.zip» v:shapes="_x0000_i1165"> <shape id="_x0000_i1166" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1166"> <shape id="_x0000_i1167" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1167">v<shape id="_x0000_i1168" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1168">
<shape id="_x0000_i1169" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image143.wmz» o:><img width=«45» height=«29» src=«dopb62858.zip» v:shapes="_x0000_i1169"> <shape id="_x0000_i1170" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1170"> <shape id="_x0000_i1171" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1171"><shape id="_x0000_i1172" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1172"><shape id="_x0000_i1173" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1173"><shape id="_x0000_i1174" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image034.wmz» o:><img width=«13» height=«25» src=«dopb62805.zip» v:shapes="_x0000_i1174">
Заперечення кон’юнкції двох висловлень рівносильне диз’юнкції заперечень і заперечення диз’юнкції рівносильне кон’юнкції заперечень цих висловлень.
<shape id="_x0000_i1175" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image141.wmz» o:><img width=«39» height=«28» src=«dopb62857.zip» v:shapes="_x0000_i1175"> <shape id="_x0000_i1176" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image119.wmz» o:><img width=«15» height=«12» src=«dopb62841.zip» v:shapes="_x0000_i1176"> <shape id="_x0000_i1177" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1177">v<shape id="_x0000_i1178" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1178">
р
q
p<shape id="_x0000_i1179" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image117.wmz» o:><img width=«16» height=«17» src=«dopb62842.zip» v:shapes="_x0000_i1179">q
<shape id="_x0000_i1180" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image141.wmz» o:><img width=«39» height=«28» src=«dopb62857.zip» v:shapes="_x0000_i1180">
<shape id="_x0000_i1181" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1181">
<shape id="_x0000_i1182" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1182">
<shape id="_x0000_i1183" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image136.wmz» o:><img width=«17» height=«27» src=«dopb62839.zip» v:shapes="_x0000_i1183">v <shape id="_x0000_i1184" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image139.wmz» o:><img width=«15» height=«27» src=«dopb62856.zip» v:shapes="_x0000_i1184">
і
i
i
х
x
x
x
i
x
x
і
x
i
i
x
i
x
i
i
x
i
x
x
x
<img width=«10» height=«27» src=«dopb62859.zip» v:shapes="_x0000_s1040">x
x
x
<img width=«10» height=«27» src=«dopb62859.zip» v:shapes="_x0000_s1041">x
г) Логічне слідування (імплікація)
Слідуванням (імплікацією) двох висловлень p і q називається висловлення “якщо p, то q„, яке хибне тоді і тільки тоді, коли p – істинне, а q – хибне.   Позначається імплікація: p<shape id="_x0000_i1185" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image146.wmz» o:><img width=«23» height=«17» src=«dopb62860.zip» v:shapes="_x0000_i1185">q
 p
q
p<shape id="_x0000_i1186" type="#_x0000_t75" o:ole=""><imagedata src=«13856.files/image146.wmz» o:><img width=«23» height=«17» src=«dopb62860.zip» v:shapes="_x0000_i1186">q
i
i
i
i
x
x
x
i
і
x
x
i
    продолжение
--PAGE_BREAK--