Алгебра предикатів. Квантори

Міністерство  освіти і науки, молоді та спорту України

Національний  університет «Львівська політехніка»

Інститут прикладної математики та фундаментальних наук

Кафедра прикладної математики

Курсова робота

з курсу  «Дискретна математика»

на  тему

«Алгебра предикатів. Квантори»

виконав:

студент групи  ІФ-31

Купіч Андрій

прийняла:

Тесак Ірина  Євгенівна

Львів 2013

 

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

This work discusses the concept of predicate and quantifier, and their formulas and logic equivalence these formulas. For practical experience with quantifiers and predicates were given a few examples. Also the program was implemented to test the truth of predicate.

 

Зміст

 

Вступ

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

Однiєю з причин цього є те, що у численнi висловлювань будь-яке просте висловлення розглядається як вихiдний об’єкт дослiдження, неподiльне цiле, позбавлене частин i внутрiшньої структури, яке має лише одну властивiсть - бути або iстинним, або хибним.

Для того, щоб  побудувати систему правил, яка дозволяла  б проводити логiчнi мiркування для  виведення нетривiальних правильних висновкiв з урахуванням будови i змiсту простих висловлень, використовується формальна теорiя, що дiстала назву числення предикатiв.

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

  • Кожний друг Івана є другом Петра. Сидір не є другом Івана. Отже, Сидір не є другом Петра.
  • Просте число два – парне. Отже існують прості парні числа.

Коректність цих  висновків ґрунтується на внутрішній структурі самих речень і значень слів “кожний” та “існують”.

Існують такі види логічних формул, які не можна записати у вигляді формул числення висловлювань. Наприклад:

  • Всі риби, окрім акул, добре відносяться до дітей;
  • Всі люди смертні. Сократ – людина. Значить Сократ смертний.

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

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

 

1.Поняття предиката

Теорiя предикатiв  починається з аналiзу граматичної  будови простих висловлювань i базується на такому висновку: простi висловлювання виражають той факт, що деякi об’єкти (або окремий об’єкт) мають певнi властивостi, або що цi об’єкти знаходяться мiж собою у певному вiдношеннi.

Наприклад, в iстинному висловлюванні «3 є просте число» пiдмет «3» - це об’єкт, а присудок «є просте число» виражає деяку його властивiсть.

У латинськiй граматицi присудок називається предикатом, звiдси цей термiн i увiйшов у математичну логiку. Головним для логiки предикатiв є саме друга складова речення-висловлення - присудок-властивiсть. Вона фiксується, а значення об’єкта пропонується змiнювати так, щоб кожен раз отримувати осмисленi речення, тобто висловлення.

Розглянемо речення, що залежить від параметрів, наприклад «х – парне число», «х менше у», «х + у = z», «х – батько у», «х та у – брати» тощо. Якщо х, у, z у перших трьох реченнях замінити деякими числами, то матимемо певні висловлення, які можуть бути істинними або хибними. Наприклад, «3 – парне число», «2 менше 5», «3 + 2 = 7». Останні два речення виражають родинні відносини між членами сім’ї і перетворюються на певні висловлення, істинні або хибні, при заміні х та у іменами членів сім’ї: «Іван – батько Петра», «Іван і Олег брати».

Речення такого типу називаються  предикатами. Точніше предикатом Р(х1,...,хn) називається функція, змінні якої набувають значень із деякої множини М, а сама вона набуває двох значень: 1 (істинне) і 0 (хибне), тобто Р(х1,...,хn): Мn → {1, 0}.

Множина M називається предметною областю, або унiверсальною множиною, а x1,x2,...,xn - предметними змiнними, або термами предиката P.

Множина елементiв (a1,a2,...,an)ÎMn таких, що P(a1,a2,...,an) = 1 називається областю iстинностi (або характеристичною множиною) предиката P.

Якщо P(a1,a2,...,an) = 1, то згiдно з логiчною iнтерпретацiєю будемо говорити, що предикат P є iстинним на (a1,a2,...,an). У супротивному разi, стверджуємо, що предикат P є хибним.

Предикат n аргументів називається n-місним. Множина М значень змінних визначається математичним контекстом. Наприклад, основне співвідношення елементарної геометрії «будь-які дві точки х, у лежать на одній прямій» можна виразити предикатом змінних х, у; а «будь-які три точки лежать в одній площині» - предикатом трьох змінних х, у, z.

Для n = 1 предикат P(x) називається одномiсним або унарним, для n = 2 P(x,y) - двомiсним або бiнарним, для n = 3 P(x,y,z) - трьохмiсним або тернарним предикатом.

Очевидно, що коли в n-арному предикатi P(x1,x2,...,xn) зафiксувати деякi m змiнних (тобто надати їм певних значень з множини M), то отримаємо (n-m)-мiсний предикат на множинi M. Це дозволяє вважати висловлення нульмiсними предикатами, якi утворено з багатомiсних предикатiв пiдстановкою замiсть усiх їхнiх параметрів певних значень з предметної областi. Таким чином, висловлення можна розглядати як окремий випадок предиката.

Для довiльної множини M i довiльного n iснує взаємно однозначна вiдповiднiсть мiж сукупнiстю всiх n-мiсних предикатiв на M i множиною всiх n-арних вiдношень на M. А саме, будь-якому предикату P(x1,x2,...,xn) вiдповiдає вiдношення R таке, що (a1,a2,...,an)ÎR тодi i тiльки тодi, коли P(a1,a2,...,an) = 1. Очевидно, що при цьому R є областю iстинностi предиката P.

Зокрема, будь-якiй  функцiональнiй вiдповiдностi або  функцiї f: Mn®M можна поставити у вiдповiднiсть (n+1)-мiсний предикат P на M такий, що P(a1,a2,...,an,an+1) = 1 тодi i тiльки тодi, коли f(a1,a2,...,an) = an+1.

Отже, такi фундаментальнi математичнi поняття як вiдповiднiсть (зокрема, функцiя), вiдношення, висловлювання можна розглядати як окремi випадки бiльш загального поняття предиката.

Предикати позначають великими літерами латинського алфавіту. Іноді буває зручно вказувати  число змінних предикатів. У таких  випадках символи предикатів доповнюють верхнім індексом, який вказує число  аргументів, наприклад Р(n)(х1,...,хn) – n-місний предикат. Висловлення вважається нуль- місним предикатом.

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

2. Логiка предикатiв

Як з елементарних висловлень за допомогою логiчних операцiй можна утворювати складенi висловлення, так i, використовуючи простi (елементарнi) предикати i логiчнi зв’язки (операцiї), можна будувати складенi предикати або предикатнi формули.

Як правило, основнi логiчнi операцiї Ù, Ú, Ø, ®, ~ встановлюють для предикатiв, що заданi на однiй i тiй самiй предметнiй областi M i залежать вiд тих самих змiнних.

Нехай P(x1,x2,...,xn) i Q(x1,x2,...,xn) - n-мiснi предикати на множинi M.

Кон’юнкцiєю P(x1,x2,...,xn)ÙQ(x1,x2,...,xn) називають предикат R(x1,x2,...,xn), який набуває значення 1 на тих i тiльки тих наборах значень термiв, на яких обидва предикати P(x1,x2,...,xn) i Q(x1,x2,...,xn) дорiвнюють 1.

Очевидно, що область iстинностi предиката R(x1,x2,...,xn) = P(x1,x2,...,xn)ÙQ(x1,x2,...,xn) збiгається з теоретико-множинним перетином областей iстинностi предикатiв P(x1,x2,...,xn) i Q(x1,x2,...,xn).

Диз’юнкцiєю P(x1,x2,...,xn)ÚQ(x1,x2,...,xn) називають предикат T(x1,x2,...,xn), який набуває значення 1 на тих i тiльки тих наборах значень термiв, на яких або предикат P(x1,x2,...,xn), або предикат Q(x1,x2,...,xn) дорiвнює 1.

Областю iстинностi предиката T(x1,x2,...,xn) буде об’єднання областей iстинностi предикатiв P(x1,x2,...,xn) i Q(x1,x2,...,xn).

Запереченням ØP(x1,x2,...,xn) предиката P(x1,x2,...,xn) називають предикат S(x1,x2,...,xn), який дорiвнює 1 на тих i лише тих значеннях термiнів, на яких предикат P(x1,x2,...,xn) дорiвнює 0.

Область iстинностi предиката S(x1,x2,...,xn) = ØP(x1,x2,...,xn) - це доповнення (до множини Mn) областi iстинностi предиката P(x1,x2,...,xn).

Аналогiчним чином вводять й iншi логiчнi операцiї ®, ~ тощо. Як правило, кожнiй iз цих операцiй вiдповiдає певна теоретико-множинна операцiя над областями iстинностi предикатiв-операндiв. Неважко узагальнити означення всiх введених операцiй для предикатiв P(x1,x2,...,xn) i Q(y1,y2,...,ym), що залежать вiд рiзних змiнних i мають рiзну мiснiсть.

Знаючи, як виконуються  окремi операцiї, можна утворювати вирази або формули, операндами яких є предикати. Наприклад розглянемо формулу P1(x)Ú(ØP3(x,z)®P2(y,x,z)), що задає деякий предикат Q(x,y,z). Значення предиката Q неважко обчислити для будь-якого набору значень його термiв x, y, z, виходячи зi значень предикатiв P1, P2, P3 на цьому наборi.

Приклад: Нехай, Р(1)(х) позначає предикат “х ділиться на два”, Q(1)(х) – предикат “х ділиться на три”. Тоді вираз Р(1)(х) &  Q(1)(х) позначає предикат “х ділиться на два та х ділиться на три”, тобто позначає предикат ділення на шість.

Крім операцій логіки висловлень будемо ще застосовувати  операції зв’язування квантором.

3. Квантори

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

Найпопулярнiшими i найбiльш часто вживаними виразами у математицi є фрази або формулювання типу «для всiх» i «iснує». Вони входять до бiльшостi промiжних i остаточних тверджень, висновкiв, лем або теорем при проведеннi математичних мiркувань або доведень.

Квантор загальності

Нехай, Р(х) – деякий предикат, який набуває значень 1 або 0 для кожного елемента х множини М. Тоді під виразом (" х) Р(х) матимемо на увазі істинне висловлення, коли Р(х) – істинне для кожного елемента х із множини М, і хибне – в іншому випадку. Читається цей вираз так: «для всіх х Р(х)» або «для будь-якого х Р(х)». Це висловлення вже не залежить від х. Символ " називається квантором загальності.

Історія вивчення кванторів

Квантори вживаються в  будь-якому осмисленому тексті. Однак, протягом тисячоліть їхнє вживання було чисто інтуїтивним і не до кінця усвідомленим навіть в математиці; кванторні вирази формулювалися словами, спеціальних символів для їхнього позначення не було. Як теоретичні об'єкти квантори вперше введені Ґ. Фреґе в роботі Begriffsschrift 1879 р. разом із теорією їхнього застосування (див.: Теорія квантифікації). Терміни «квантор» і «квантифікація» ввів у 1885 р. Чарлз Пірс, який перевідкрив тоді квантори.

Сучасна символіка на позначення кванторів належить Б. Расселу, який модифікував відповідні позначення Дж. Пеано. Сучасні математики, на відміну від логіків, продовжують формулювати кванторні вирази переважно словами, однак вивчають теорію квантифікації з метою уникнення помилок при навішуванні кванторів.

Символіка й термінологія

Якщо предикат   не містить інших змінних, окрім  , вирази   та   є реченнями, що виражають істинні або хибні висловлювання. Перше називається універсальним висловлюванням (або висловлюванням загальності), а друге — екзистенціальним висловлюванням (або висловлюванням існування). Універсальне висловлювання означає, що властивість   мають всі індивіди (предмети) з обраної індивідної області; екзистенціальне висловлювання означає, що властивість   має бодай один індивід з розглядуваної індивідної області. Коли висловлюватися в теоретико-множинних термінах, універсальне висловлювання говорить, що область істинності предиката   є універсальною (збігається з індивідною областю), а екзистенціальне висловлювання говорить, що область істинності предиката   непорожня.

Змінна, яка пишеться після знака квантора, є операторною  змінною даного квантора; кажуть, що вона входить в цей квантор. Послідовність знаків кванторів разом з їхніми операторними змінними, виписані на початку деякої (квазі)формули, разом називаються її префіксом. Частина (квазі)формули після префікса називається основою цієї (квазі)формули; основа є областю дії кванторів, що входять у префікс. Змінна, що входить в область дії квантора по цій змінній, називається зв'язаною змінною в даній (квазі)формулі. Формула не залежить від своїх зв'язаних змінних: їм не можна приписувати значення, бо квантор, який зв'язує таку змінну, говорить про всю її область значень.

 

Квантор існування

Нехай, Р(х) – деякий предикат. Під виразом ($ х) Р(х) будемо розуміти  істинне висловлення, коли існує елемент множини М, для якого Р(х) – істинне, та хибне – в іншому випадку. Читається цей вираз так: «існує х таке, що  Р(х)» або «існує х, для якого Р(х)». Символ $  називається квантором існування. Операцію зв’язування квантором можна застосувати також до предикатів більшого числа змінних (детальніше про це йтиметься далі).

Приклад: Для предикатів, наведених у попередньому прикладі, маємо

($ х) (Р(1)(х) &  Q(1)(х)) – істинне висловлення, а (" х) (Р(1)(х) &  Q(1)(х)) - хибне.

Важливу роль у  логiцi предикатiв вiдiграє поняття областi дiї квантора, пiд якою розумiтимемо той вираз, до якого вiдноситься цей квантор. Область дiї квантора позначається за допомогою дужок. Лiва дужка, що вiдповiдає початку областi дiї, записується безпосередньо пiсля кванторної змiнної даного квантора, а вiдповiдна їй права дужка означає закiнчення областi дiї цього квантора. Там, де це не викликає невизначенностi, дужки можна опускати i замiсть "x(P(x)) або $x(P(x)) писати вiдповiдно "xP(x) або $xP(x).

Перехiд вiд P(x) до "xP(x) або $xP(x) називається зв’язуванням змiнної x. Iншi назви - навiшування квантора на змiнну x (або на предикат P(x)), або квантифiкацiя змiнної x.

Змiнна x, на яку навiшено квантор, називається зв’язаною, у протилежному випадку змiнна x називається вiльною.

Зв’язана змiнна, як було продемонстровано вище, вже не є  змiнною у класичному розумiннi цього  поняття. Вона потрiбна лише для iдентифiкацiї  терма, вiд якого залежить вiдповiдна пропозицiйна форма. Вираз "xP(x) не залежить вiд x i при фiксованих P i M має певне значення. Звiдси, зокрема, випливає, що можна здiйснювати перейменування зв’язаної змiнної (тобто перехiд вiд "xP(x) до "tP(t)) i воно не змiнює значення iстинностi виразу.

Навiшувати квантори можна й на багатомiснi предикати. Наприклад, застосовуючи квантори " i $ до змiнних x i y двомiсного предиката A(x,y), отримаємо чотири рiзнi одномiснi предикати "xA(x,y), $xA(x,y), "yA(x,y) i $yA(x,y). У перших двох змiнна x є зв’язаною, а змiнна y - вiльною, а у двох останнiх - навпаки.

Вираз "xA(x,y) (читається «для всiх x, A вiд x i y») є одномiсним предикатом B(y). Вiн є iстинним для тих i тiльки тих bÎM, для яких одномiсний предикат A(x,b) є iстинним для всiх x з M.

Приклад: Розглянемо двомiсний предикат A(x,y), визначений на множинi M = {a1,a2,a3,a4} за допомогою таблицi 1:

 

Таблиця 1

x \ y

a1

a2

a3

a4

a1

0

1

1

0

a2

0

1

1

1

a3

0

0

1

1

a4

0

0

1

0


Таблиці iстинностi для чотирьох вiдповiдних одномісних предикатів, що отримуються з A(x,y) шляхом навішування одного квантора, наведені у наступній таблиці:

 

Таблиця 2

y

"xA(x,y)

y

$xA(x,y)

x

"yA(x,,y)

x

$yA(x,y)

a1

a2

a3

a4

    0

    0

    1

    0

a1

a2

a3

a4

    0

    1

    1

    1

a1

a2

a3

a4

     0

     0

     0

     0

a1

a2

a3

a4

    1

    1

    1

    1


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

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

"x("yA(x,y)) = 0,      "y("xA(x,y)) = 0,

$x($yA(x,y)) = 1,     $y($xA(x,y)) = 1,

$y("xA(x,y)) = 1,       $x("yA(x,y)) = 0,

"y($xA(x,y)) = 0,       "x($yA(x,y)) = 1.

Неважко переконатись, що висловлення, якi мiстять однаковi квантори, рiвносильнi. Обидва висловлення "x("yA(x,y)) і "y("xA(x,y)) є iстинними тодi i тiльки тодi, коли предикат A(x,y) приймає значення 1 на всiх кортежах значень (a,b) з M2. Висловлення $x($yA(x,y)) i $y($xA(x,y)) iстиннi тодi i тiльки тодi, коли iснує принаймнi одна пара (a,b) така, що A(a,b) = 1.

У той же час  усi чотири висловлення з рiзнойменними  кванторами є, взагалi кажучи, не рiвносильними. Особливо слiд пiдкреслити, що суттєвим є порядок слiдування рiзнойменних кванторiв. Висловлення "x($yA(x,y)) i $y("xA(x,y)), взагалi кажучи, нерiвносильнi. Наприклад, у термiнах табличного задання предиката A(x,y), iстиннiсть першого висловлення "x($yA(x,y)) означає, що кожен рядок таблицi iстинностi мiстить принаймнi одну одиницю. А друге висловлення $y("xA(x,y)), iстинне тодi i лише тодi, коли у таблицi є стовпчик, що складається тiльки з одиниць.

Неважко поширити всi наведенi вище мiркування i висновки на предикати бiльшої арностi. Навiшування  одного квантора завжди зменшує число вiльних змiнних i арнiсть предиката на одиницю. Застосування кванторiв до всiх змiнних предиката перетворює його у висловлення (iнодi таку предикатну формулу називають замкненою формулою). Порядок слiдування рiзнойменних кванторiв у формулi є суттєвим.

 4.Формули логіки предикатів

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

 предметних змінних х1, х2, ..., хn... ;

 предикатів А1(t), А2 (t), ..., Ак(t), ..., де t = 0,1,2,...;

 логічні &, Ú, ®, ~, Ø;

 кванторів $, ";

 дужки і кому ) , (.

Щоб зменшити кількість  індексів, символи предметних змінних  будемо позначати через х, у, z, а символи предикатів – через P, S, Q, R тощо.

Слово в алфавіті логіки предикатів називається формулою, якщо воно задовольняє таке індуктивне означення (одночасно визначаються поняття вільної та зв’язаної змінних у формулі):

  1. Якщо Аі(t) – символ предиката, хі,1 , хі,2 , ...,хі,t – символи предметних змінних, не обов’язково різних, то Аі(t)( хі,1 , хі,2 , ...,хі,t) – формула, яка називається атомарною. Всі предметні змінні атомарних формул є вільними, зв’язаних змінних немає.
  2. Нехай,  А – формула. Тоді Ā – також формула. Вільні й зв’язані змінні формули Ā – це відповідно вільні та зв’язані змінні формули А.
  3. Нехай, А і В – формули, причому немає таких предметних змінних, які були б зв’язаними в одній формулі, але вільними в іншій. Тоді  

(А Ú В), (А & В), (А ® В), (А ~ В)

є формулами, в  яких вільні змінні формул А та В залишаються вільними, а зв’язані змінні формул А і В – зв’язаними.

  1. Нехай, А – формула, яка містить вільну змінну х. Тоді

 (" х) А, ($ х)А  (1)

також є формулами. Змінна х у них – зв’язана. Інші ж змінні, які є у формулі А є вільними, залишаються й вільними у формулах (1). Змінні, які у формулі А є зв’язаними, залишаються зв’язаними й у формулах (1). У першій із формул (1) формула А називається областю дії квантора " , а в другій – областю дії квантора $.

  1. Слово в алфавіті логіки предикатів є формулою тільки в тому випадку, якщо це випливає з правил 1-4. Зазначимо, що за означенням формули жодна змінна не може бути одночасно вільною та зв’язаною.

Приклади:

1) Такі вирази  є формулами логіки предикатів: А5(3) (х1, х5, х7) – атомарна формула, в якій х1, х5, х7 – вільні змінні; ("х1) ($х2) А1(3) (х1, х2, х3) ® ("х1) А1(2) (х1, х4) – формула, в якій х1, х2 – зв’язані, а х3, х4 – вільні змінні.

2) Вираз ($х2) ("х2) А1(2) (х1, х3) & А2(2) (х1, х3) не є формулою.

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

Під інтерпретацією розуміють систему Мf = áМ, fñ, яка складається з не порожньої множини М і відповідності f, що стоять у відповідності кожен з кожним предикатним символом Аj(t) певний t-місний предикат (будемо позначати предикати, поставлені у відповідність предикатним символам, тими самими символами).

При заданій інтерпретації  вважають, що предметні змінні пробігають множину М, а символи ¯, Ú, &, ®, ~, Ø, і символи кванторів мають своє звичайне значення. Для заданої інтерпретації кожна формула без вільних змінних є висловленням, яке істинне чи хибне, а кожна формула з вільними змінними виражає деякий предикат на множині М, який істинний при одних значеннях змінних з цієї множини та хибний при інших.

Значення формули F на наборі áа1, ..., аnñ, аі є М, своїх вільних змінних хі,1 ,...,хі,n позначимо символом Fêá а1, ....,аnñ.

Приклади:

1) Розглянемо три формули:

А1(2) (х1, х2);

(" х2) А1(2) (х1, х2);

($ х1) А1(2) (х1, х2).

Візьмемо як область  інтерпретації множину цілих  додатних чисел й інтерпретуємо А1(2)(х, у) як х £  у. Тоді перша формула – це предикат х1 £, х2, який набуває істинного значення для всіх пар (а, b) цілих додатних чисел таких, що а £ b. Друга формула виражає властивість “ для кожного цілого додатного числа у матимемо х £  у ”, яка виконується тільки при х=1. Нарешті, третя формула – це істинне висловлення про існування найменшого цілого додатного числа. Якби як область інтерпретації ми розглядали множину цілих чисел, то третя формула була б хибним висловленням.

2) Нехай, Мf = á N, f ñ, де N – множина натуральних чисел; f – відповідність, що ставить у відповідність із предикатними символами S(3) (x, y, z), Р(3) (x, y, z) предикати S(3) (x, y, z): x + y = z; Р(3) (x, y, z): x y = z.

Запишемо формули, істинні  в М тоді й тільки тоді, коли виконано такі умови:

    • х = 0;
    • х = 1;
    • х – парне;
    • х – просте число;
    • х = у;
    • х £ у;
    • х ділить у;
    • комутативність додавання.

Це відповідно формули:

    • F1 (x) = (" y) S (3) (x, y, y), оскільки х + у = у для будь-якого у тоді й тільки тоді, коли х = 0;
    • F2 (x) = (" y) Р (3) (x, y, y);
    • F3 (x) = ($ y) S (3) (у, y, х);
    • F4 (x) = F1 (x) & (" y) (" z) (Р (3) (у, z, х)® (F2 (y)Ú F2 (z))), де F1, F2 – формули, визначені вище;
    • F5 (x) =(" z) (" u) S (3) (x, z, u)® S (3) (y, z, u));
    • F6 (x, y) =($ z) S (3) (x, z, y);
    • F7 (x, y) =($ z) P (3) (x, z, y);
    • (" x) (" y) (" z) S (3) (x, y, z)® S (3) (y, x, z)).

5.Рівносильність формул

Нехай, формули F і G мають одну і ту саму множину вільних змінних (зокрема, порожню).

Формули F та G є рівносильними  в заданій інтерпретації, якщо на будь-якому наборі значень вільних змінних вони набувають однокових значень (тобто якщо формули виражають у цій інтерпретації один і той самий предикат). Формули F та G є рівносильними  на множині М, якщо вони рівносильні у всіх інтерпретаціях, заданих на множині М. Формули F та G є рівносильними (в логіці предикатів), якщо вони рівносильні на всіх множинах (тоді писатимемо F º G ).

Алгебра предикатів. Квантори 📙 Курсовая → 🆔 6287

Алгебра предикатів. Квантори 📙 Курсовая → 🆔 6287

Алгебра предикатів. Квантори