На головну

 І ТЕОРІЯ АЛГОРИТМІВ |  ФОРМАЛЬНІ СИСТЕМИ (ТЕОРІЇ) |  обчислення висловлювань |  обчислення предикатів |  Зведення формул до пропозицій |  Правило резолюції для обчислення висловлювань |  Правила резолюції для обчислення предикатів |  Спростування методом резолюції |  K-значна логіка |  Повнота і замкнутість функцій k-значної логіки |

ВІДНОСИНИ

  1.  I. Відносини до чарівництва в стародавньому світі
  2.  II. Поселення в Іспанії. Взаємовідносини вестготів і римлян. Королівська влада. Система управління. Церковна політика.
  3.  III. Капіталістичні відносини в Європі
  4.  III. Людські взаємини.
  5.  Quot; А які стосунки ви будете мати? "," Умм. Дайте мені подумати про це - досить поверхневі "?
  6.  UML, артефакт - визначення. Предмети (структурні, предмети поведінки, групуються і пояснюють) - визначення і зображення. Відносини - визначення і зображення. 1 сторінка
  7.  UML, артефакт - визначення. Предмети (структурні, предмети поведінки, групуються і пояснюють) - визначення і зображення. Відносини - визначення і зображення. 2 сторінка

1.2.1. поняття відносини

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

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

ставлення  називається n - місцевим на безлічі А.

при  відношення R задає фіксований елемент безлічі А. при  відношення R являє собою підмножина безлічі А і називається унарним ставленням або властивістю. при  відношення R називається бінарним або відповідністю. при  відношення тернарного і т.д.

В математиці найчастіше використовуються бінарні відношення (відповідності). Надалі розглядаються в основному тільки такі відносини і при цьому слово "бінарні" опускається.

нехай А и В - Два безлічі. відповідністю або (Бінарним) ставленням з безлічі А в безліч В називається підмножина R прямого твори  , Т. Е.  . якщо aIA, bIB, Перебувають у відношенні, то пишуть: (A, b) IR або R (a, b), А також в інфіксной формі aRb. При цьому говорять, що b відповідає a при відповідності R або b знаходиться в відношенні R с a. якщо R = ?, То ставлення називають порожнім. ставлення  називають повним. Для будь-якого безлічі А визначається тотожне відношення - .

належність елементів а и b відношенню R наочно можна представити в наступному вигляді

областю визначення (DomR) відповідності R, Називається безліч елементів aIA, Для кожного з яких, знайдеться хоча б один елемент bIB, Такий, що aRb.

областю значення (ImR) відповідності R називається безліч елементів bIB, Для кожного з яких, знайдеться хоча б один елемент aIA, Такий, що aRb.

відповідність R називається всюди певним, якщо DomR = A, в іншому випадку - частково певним. відповідність називається сюр'ектівним, якщо ImR = B.

Для кожного aIA, Безліч елементів bIB таких, що aRb називається чином елемента aIA щодо R і позначається imRa.

прообразом елемента bIB щодо R, Називається безліч елементів aIA, Таких, що aRb. Прообраз позначається: coimRb

Зауважимо, що и .

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

Відносини, певні на кінцевих множинах  , Можуть бути задані:

списком, Т. Е. Перерахуванням тих пар елементів, для яких це відношення виконано. Наприклад, якщо A ={a, b, c} і B ={x, y}, То R ={(a, x),(a, y),(b, y),(c, x)}.

матрицею [R] розмірності  , Елементи якої  т. е. рядки цієї матриці позначаються елементами з A, А стовпці - елементами з B, А на перетині рядка ai зі стовпцем bi варто одиниця (1), якщо aRb; і нуль (0), - в іншому випадку. Тоді для вище наведеного прикладу маємо матрицю

x y
a
b
c
 
 

графіком на координатної площині, горизонтальна і вертикальна осі якої становлять елементи множин А и В відповідно.

графом, В якому елементи множин А и В зображуються точками на площині. Причому ці точки позначаються тими ж символами, що і відповідні елементи. точки a и b з'єднуються спрямованим відрізком від a к b, якщо aRb. Наприклад, для попереднього випадку відношення R зображується орієнтованим графом.

1.2.2. Операції над відносинами

Так як відносини з А в В задаються подмножествами  , Отже для них визначені ті ж теоретико-множинні операції, що і над множинами:

об'єднання .

перетин .

різниця .

доповнення .

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

Над відносинами можуть також здійснюватися іншими алгебри:

зворотне відношення .

Твір (композиція) відносин

.

ступінь відносини .

Зауважимо, що:

 , Де додавання елементів матриць здійснюється за правилами 0 + 0 = 0, 1 + 1 = 1 + 0 = 0 + 1 = 1.

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

 , Де множення матриць проводиться за звичайним правилом множення матриць.

 , Де символ T означає транспонування матриці.

1.2.3. Властивості відносин на безлічі

Нехай задано відношення на безлічі А, Т. Е.  , Тоді відношення R називається:

 рефлексивним,  якщо
 антирефлексивне,  якщо
 симетричним,  якщо
 антисиметричних,  якщо
 транзитивним,  якщо
 повним або лінійним,  якщо

Для зазначених відносин справедливі наступні твердження:

R рефлексивно U
R антирефлексивне U
R симетрично U
R антисиметрично U
R транзитивно U
R повно U

Зауважимо, що:

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

1.2.4. Відносини еквівалентності, толерантності

і порядку

ставлення R називається відношенням еквівалентності, якщо R рефлексивно, симетрично і транзитивній. Це відношення позначається символами E і ~ (тильда): aEb або a~b. Важливе значення відносини еквівалентності полягає в тому, що воно визначає ознака, по якому відбувається розбиття вихідного безлічі на підмножини, звані класами еквівалентності. нехай E - Еквівалентність на безлічі А. класом еквівалентності елемента  називається безліч  . класи еквівалентності Е називаються також Е - класами. безліч  називається фактор-множиною безлічі А по відношенню до Е. безліч  є розбиттям безлічі А. Назад, якщо  - Деякий розбиття множини А, То можна задати відповідне йому ставлення еквівалентності Е за таким правилом:  для деякого i.

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

У ряді випадків потрібне вказати старшинство, важливість, "первинність" та інші подібні властивості об'єктів. Для цього служать різні види відносини порядку.

ставлення  називається предпорядка або квазіпорядком, якщо R рефлексивно і транзитивне.

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

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

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

1.3. ПОНЯТТЯ алгебри

1.3.1. поняття відображення

Приватним видом відносини є відображення (функціональна відповідність).

відображення - Це закон, за яким кожному елементу x деякого заданого безлічі X, Однозначно відповідає певний елемент y, Іншого заданого безлічі Y. Таке відповідність записується у вигляді y = f (x) або f: x®y, При цьому говорять, що відображення f діє з X в Y і пишуть f: X ®Y. елемент y = f (x) називається чином елемента x, а x називається прообразом елемента y.

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

коли безлічі X и Y НЕ числові, відображення називається оператором. Відображення НЕ числового безлічі в числове називається функціоналом. відображення f: X®X називається перетворенням безлічі X.

Іноді розглядають відображення f, Визначене на деякій підмножині  . В цьому випадку  називається областю визначення відображення f. підмножина Im f = {f (x) | xIX} безлічі Y називається областю значень (чином)f.

Звуженням (обмеженням) відображення f: X®Y, На підмножина AIX, Називається відображення fA(X), Заданий рівністю fA(X) = f (x), для всіх xIA.

Розширенням (продовженням, поширенням) відображення f: X®Y на безлічі BEX (X - Є підмножиною B) Називається будь-яке відображення fB: B®Y, Що збігається з f на безлічі X.

Якщо задані три безлічі X, Y, Z і два відображення f: X®Y и g: Y®Z, То існує відображення h: X®Z, Яке визначається рівністю h (x) = g (f (x)). Це відображення називається композицією (суперпозицією, твором) відображень і позначається gf. Композиція відображень має властивість асоціативності, тобто h (gf) = (hg) f.

відображення називається тотожним , якщо f (x) = x, для всіх xIX. відображення f: X®Y називається ін'єкційних, Якщо для будь-яких двох елементів  , Таких що  випливає, що  . відображення називається сюр'ектівним, якщо Imf = Y. Відображення, що одночасно є ін'єкційних і сюр'ектівним називається биективное.

1.3.2. алгебраїчна операція

відображення f: An ® A називається n-місцевої алгебраїчній операцією на безлічі A. Очевидно, що n-місна алгебраїчна операція на безлічі A є ( ) - Місцевим ставленням на безлічі A. при  операція f: A0 ® A є {(?, a)} Для деякого aIA. Ця операція називається константою на безлічі A і ототожнюється з деяким елементом a цієї множини. при  операція f називається унарною, А при - бінарної.

Прикладами унарних операцій є:

Елементарні функції одного аргументу -  та інші;

Операція над множинами - доповнення ;

Операції над відносинами - доповнення  , Зворотне відношення  , Складене ставлення  та інші.

Прикладами бінарних операцій є:

Арифметичні операції - додавання, віднімання, множення, ділення, піднесення до степеня.

Операції над множинами - перетин, об'єднання і різницю.

Операція композиції функцій, відображень, відносин.

позначимо символом T довільну бінарну алгебраїчну операцію. Тоді операція над елементами  , Що дає результат  записується у вигляді aTb = c.

Властивості бінарних операцій:

Асоціативність - (aTb)Tз = aT (bTс). (Виконання цієї умови означає, що дужки в цьому виразі годі й розставляти.)

комутативність - aTb= bTa.

дистрибутивность - T(b^c) = (aTb) ^ (aTc) - Дистрибутивність операції T зліва щодо операції ^ і (a^b)Tc =(aTc) (bTc) - Дистрибутивність операції T справа щодо операції ^

Способи завдання операцій

Унарні операції задаються:

переліком всіх аргументів  і відповідних їм значень :

f=

списком всіх пар "аргумент - значення" для всіх можливих значень аргументів:f= { }.

формулою  , наприклад .

Бінарні операції задаються:

таблицею (Таблиця Келі). Зліва і зверху таблиці виписуються всі значення аргументів, а на перетині рядків і стовпців - результат операції. Наприклад, для операції "додавання по модулю 3" на множині {0,1,2} має такий вигляд:

списком, Шляхом перерахування всіх трійок  . Наприклад, для попередньої операції:

 {(0,0,0), (0,1,1), (0,2,2), (1,0,1), (1,1,2), (1.2,0), (2, 0,2), (2,1,0), (2,2,1)}

формулою  або aTb= c. наприклад:  , де  - Операція додавання по модулю 3.

1.3.3. Загальні відомості про алгебраїчних системах

Алгебраїчна система - це безліч з певними на ньому операціями і відносинами. алгебраїчна система - Це об'єкт A  , де  - Непорожня множина,  - Сімейство алгебраїчних операцій, а  - Сімейство відносин, заданих на множині  . безліч  називається носієм алгебри, а його елементи - елементами системи. Алгебраїчна система називається кінцевої, Якщо безліч  звичайно.

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

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

нехай A и B  - Дві алгебри одного і того ж типу. відображення  , називається гомомофізмом системи A в систему B, Якщо виконуються наступні умови:

и

 для всіх и .

якщо  - Гомоморфізм, то його позначають A®B.

гомоморфізм A®B є ін'єкцією, називається мономорфізму. гомоморфізм A®B, Який є сюр'єкція, називається епіморфізм і при цьому система B називається гомоморфним чином системи A. гомоморфізм A® A називається ендоморфізм. Сюр'ектівний мономорфизм A®B, для котрого  гомоморфізм, називається изоморфизмом і позначається A«B. ізоморфізм A«A називається автоморфізмом системи A.

Поняття ізоморфізму - одне з найважливіших понять в сучасній математиці. При ізоморфізмі зберігаються дію всіх основних операцій і відносин. Це дозволяє переносити вивчення властивостей з однієї системи на іншу.

1.4. РЕЛЯЦІЙНА АЛГЕБРА

1.4.1. алгебра відносин

алгебра відносин - Це алгебра, носієм якої є безліч відносинP= {P1, P2, ..., Pm, ...}. Сигнатура ? алгебри відносин складається з символів двомісних операцій об'єднання  , перетину  , Різниці \ і декартова твори 'відносин.

відносини Рi и Pj називаються сумісними, якщо Рi, Pj I Аn для деякого безлічі А і числа n IN.

об'єднанням Рi Pj двох сумісних відносин Рi и Pj називається безліч всіх кортежів X, Кожен з яких належить хоча б одному з цих відносин: Рi Pj= {X|XI Рi або ХIPj}.

перетином Pj Рi двох сумісних відносин Рi и Pj називається безліч всіх кортежів X, Що належать як стосовно Рi,, Так і стосовно Pj: Рi Pj = {X|XIРi и ХIPj}.

різницею Рi\Pj двох сумісних відносин Рi и Pj називається безліч всіх кортежів X, довжини n що належать відношенню Рi і які не належать Pj: Рi\Pj= {X|XI Рi и ХIPj}.

приклад. якщо Р = {(a, b, d), (b, c, e)}, Q = {(a, b, d), (b, d, e)}, То P Q= {(A, b, d), (b, c, e), (b, d, e)}, P Q = {(a, b.d)}, P\Q = {(b, c, e)}.

декартових твором Рi?Pj двох відносин Рi и Pj називаються безліч всіх кортежів z таких, що z - Конкатенація кортежів xIРi и yIPj:  , де  , якщо х= (х1, ..., Xr), y= (y1, ..., Ys). Отже .

приклад якщо Р= {(a, b), (b, c)}, Q= {(b, c, a), (c, a, a)}, То  {(a, b, b, c, a), (a, b, c, a, a), (b, c, b, c, a), (b, c, c, a, a)}.

Алгебри відносин використовуються для формалізації реальних об'єктів. Розглянемо, застосування алгебри відносин при створенні інформаційного забезпечення - розробці реляційної бази даних. Основою побудови реляційної баз даних є двовимірна таблиця. кожен i - Й стовпець таблиці відповідає i - Му домену. якщо n - Місцеве відношення Rn міститься в D1?D2'...Dn, то i - м доменом відносини Rn, де i = 1, ...,n, Називається безліч Di .

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

приклад. Розглянемо 4-місне відношення R4 (Розклад іспитів).

R4 D1 D2 D3 D4
 А - 1А - 2А - 2А - 1А - 1А - 2  ІнформатікаФізікаАналізФізікаАналізІнформатіка  10 января10 января15 января16 января21 января21 січня  Ауд. 320Ауд. 324Ауд. 324Ауд. 320Ауд. 324Ауд. 320

ставлення R4 є підмножиною декартового добутку D1?D2?D3?D4, І тому кожне з множин Di є доменом:

- домен D1 (Група) містить значення А-1, А-2, тобто D1 = {A - 1, A - 2};

- домен D2 (Дисципліна) - D2 = {Інформатика, Фізика, Аналіз};

- домен D3 (Дата) - D3 = {10 Січня., 16 Січня., 21 Січня.};

- домен D4 (Аудиторія) - D4 = {Ауд.320, Ауд. 324}.

Порядок стовпців в таблиці фіксований, а рядки в загальному випадку розташовуються довільно. Цифри першого стовпчика 1,2, ..., 6 є ідентифікаторами відносини R4.

Таким чином, кожному відношенню можна поставить у відповідність певну таблицю.

1.4.2. реляційна алгебра

Для перетворення відносин використовується реляційна алгебра. Носій реляційної алгебри є безліч відносин, а набір операцій крім введених операцій E, C, \, 'включає спеціальні операції над відносинами - вибір, проекцію і з'єднання.

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

Наприклад за допомогою операції вибору з відносини R4 (Розклад іспитів), будується, наприклад, ставлення  (Розклад іспитів з фізики). Результатом операції вибору є рядки, в яких домен D2 представлений значенням «Фізика», це 2-я і 4-я рядки. В результаті виходить:

R4 1 D2 D3 D4
 А-2А-1  ФізікаФізіка  10 января16 січня  Ауд. 324Ауд. 320

результатом операції проекції відносини RnI А12'...'Аn на Аi1, Аi2, ..., Аim, де {i1, ..., Im} I {1,2, ...,n} ijk при j , Називається безліч

 {(ai1, ai2, ..., Aim) | (a1, a2, ..., An) I Rn}. наприклад, p1Rn= {a1| (a1, a2, ..., An) I Rn}.

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

Наприклад, проекція p2,3R4 відносини R4 визначає безліч пар, кожна з яких містить назву дисципліни і дату:

p2,3R4 D2 D3
 ІнформатікаФізікаАналізФізікаАналізІнформатіка  10 января10 января15 января16 января21 января21 січня

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

Наприклад, знайдемо за двома заданими таблицями R4 и R ?4

R4 D1 D2 D3 D4
   А - 1 А - 2  Інформатика Фізика  10 січня 10 січня  Ауд. 320 Ауд. 324
R ?4 D1 D2 D3 D4
   А - 2 А - 1  аналіз Фізика  15 січня 16 січня  Ауд. 324 Ауд. 320

Результат з'єднання по домену D1

R7 D1 D2 D3 D4 D ?2 D ?3 D ?4
   А - 1 А - 2  Інформатіо Фізика  10 Січня 10 Січня  А -320А -324  фізика Аналіз  16янв 15янв  А -320 А -324

В даному прикладі кортежі з'єднуються за умовою рівності відповідних координат, що з'єднують кортежі, тобто а = (a1, ..., Ai, ..., An) і b = (b1, ..., Bi, ..., Bn), Коли ai = bi.

Залежно від практичних потреб, операцію з'єднання можна визначати і за іншими правилами.

2. ОСНОВИ МАТЕМАТИЧНОЇ ЛОГІКИ

2.1. АЛГЕБРА ВИСЛОВЛЮВАНЬ

2.1.1. загальні поняття

Логіка (в перекладі з давньогрецької) означає слово, що виражає думку. У сучасному розумінні логіка - Це наука про способи мислення. математична логіка служить для створення алгоритмів логічного висновку.

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

Математична логіка має справу з висловлюваннями. висловлювання - Це оповідної пропозицію, про який має сенс говорити, що воно істинно або хибно, але ні те і інше разом. Зазвичай, висловлювання позначаються великими літерами латинського алфавіту, а їх значення, тобто істина і брехня - 1 і 0 відповідно.

Логічна структура складного висловлювання. В процесі міркувань (не тільки в математики) з одних висловлювань формуються інші, так звані складні висловлювання, Отримані з елементарних за допомогою частки «НЕ» або шляхом з'єднання елементарних висловлювань за допомогою зв'язок «І», «АБО», «ЯКЩО .., тО» ТОДІ І ТІЛЬКИ ТОДІ, КОЛИ »та інших. Ці зв'язки позначають певні логічні зв'язки між висловлюваннями. Їх можна розглядати як деякі операції над висловлюваннями. Ці операції дозволяють судити про істинність або хибність складного висловлювання по істинності і хибності складових його висловлювань.

2.1.2. Операції над висловлюваннями (закони логіки)

1. заперечення 'А - Означає, що висловлювання, яке істинно, коли А - Помилково і помилково, коли А - Істинно. У звичайній мові воно відповідає частці «НЕ».

2. кон'юнкція АUВ означає вислів, яке істинно в тому випадку, коли А и В обидва істинні. Відповідає зв'язки "І".

3. диз'юнкція АUВ означає, що висловлювання істинно в тому випадку, коли істинно одне з висловлювань А або В. Відповідає зв'язці «АБО».

4. імплікація А®В означає вислів, яке помилково тоді і тільки тоді, коли А - Істинно, а В - Помилково. Відповідає зв'язки «ЯКЩО .., тО ...».

5. еквівалентність А«В означає вислів, яке істинно тоді і тільки тоді, коли А и В обидва істинні або обидва хибні. Відповідає зв'язці «ТОДІ І ТІЛЬКИ ТОДІ, КОЛИ».

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

 



 множинами |  ФОРМУЛИ логіки ВИСЛОВЛЮВАНЬ
© um.co.ua - учбові матеріали та реферати