Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгебра предикатів. Квантори. Означення. Операції
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2007
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Група:
ПМ-31
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра прикладної математики
КУРСОВА РОБОТА
з курсу
“Дискретна математика”
на тему:
“Алгебра предикатів. Квантори.
Означення. Операції. ”
Зміст
Вступ
Поняття предиката
Лог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.Поняття предиката
Теор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стю C мiж множинами A i B (тобто C(A(B) можна побудувати бiнарний двосортний предикат P(x,y) таким чином: P(a,b) = 1 тодi i тiльки тодi, коли (a,b)(C для a(A i b(B.
Зокрема, будь-як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 остаточних тверджень, висновкiв, лем або теорем при проведеннi математичних мiркувань або доведень.
Квантор загальності.
Нехай, Р(х) – деякий предикат, який набуває значень 1 або 0 для кожного елемента х множини М. Тоді під виразом (( х) Р(х) матимемо на увазі істинне висловлення, коли Р(х) – істинне для кожного елемента х із множини М, і хибне – в іншому випадку. Читається цей вираз так: «для всіх х Р(х)» або «для будь-якого х Р(х)». Це висловлення вже не залежить від х. Символ ( називається квантором загальності.
Квантор існування.
Нехай, Р(х) – деякий предикат. Під виразом (( х) Р(х) будемо розуміти істинне висловлення, коли існує елемент множини М, для якого Р(х) – істинне, та хибне – в іншому випадку. Читається цей вираз так: «існує х таке, що Р(х)» або «існує х, для якого Р(х)». Символ ( називається квантором існування. Операцію зв’язування квантором можна застосувати також до предикатів більшого числа змінних (детальніше про це йтиметься далі).
Приклад: Для предикатів, наведених у попередньому прикладі, маємо
(( х) (Р(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 зм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:
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дповiдних одномiсних предикатiв, що отримуються з A(x,y) шляхом навiшування одного квантора, наведенi у наступній таблицi:
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 зм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) – формула, яка називається атомарною. Всі предметні змінні атомарних формул є вільними, зв’язаних змінних немає.
Нехай, А – формула. Тоді Ā – також формула. Вільні й зв’язані змінні формули Ā – це відповідно вільні та зв’язані змінні формули А.
Нехай, А і В – формули, причому немає таких предметних змінних, які були б зв’язаними в одній формулі, але вільними в іншій. Тоді
(А ( В), (А ( В), (А ( В), (А ( В)
є формулами, в яких вільні змінні формул А та В залишаються вільними, а зв’язані змінні формул А і В – зв’язаними.
Нехай, А – формула, яка містить вільну змінну х. Тоді
(( х) А, (( х)А (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) не є формулою.
Значення формули визначено лише тоді, коли задано яку-небудь інтерпретацію символів, що входять до неї.
Означення 2. Під інтерпретацією розуміють систему М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 мають одну і ту саму множину вільних змінних (зокрема, порожню).
Означення 3. Формули F та G є рівносильними в заданій інтерпретації, якщо на будь-якому наборі значень вільних змінних вони набувають однокових значень (тобто якщо формули виражають у цій інтерпретації один і той самий предикат). Формули F та G є рівносильними на множині М, якщо вони рівносильні у всіх інтерпретаціях, заданих на множині М. Формули F та G є рівносильними (в логіці предикатів), якщо вони рівносильні на всіх множинах (тоді писатимемо F ( G ).
Приклад.
На множині М = {a, d} задамо предикат Р1 (х, у) та Р2 (х, у). Розглянемо дві формули:
А1(2) (х1, х2) ( А1(2) (х1, х3); (1)
А1(2) (х1, х2) ( А1(2) (х2, х3). (2)
Якщо областю інтерпретації слугує множина М і формула А1(2) інтерпретується як предикат Р1, то формули (1) і (2) є рівносильними в цій інтерпретації, оскільки набувають значення 1 тільки на двох наборах вільних змінних: (а, а, а( та (d, d, d(.
Якщо областю інтерпретації є множина М, але формула А1(2) інтерпретується як предикат Р2, то формули (1) і (2) – нерівносильні, оскільки в наборі (а, d, d( формула (1) набуває значення 1, а формула (2) – значення 0.
Формули (( х1) А1(1) (х1) й (( х1) А1(1) (х1) є рівносильними на одноелементній множині. Справді, якщо область інтерпретації – одноелементна множина, то який би предикат не взяти інтерпретацію А1(1) на цій множині, він набуває тільки одного значення: 1 або 0. у першому випадку обидві формули набувають значення 1, у другому – 0, і, отже, вони є рівносильними на цій множині. З іншого боку, на двоелементній множині {a, b} ці формули – нерівносильні. Досить як інтерпретацію А1(1) розглянути предикат Р такий, що Р(а) = 1, Р(b) = 0. Наведемо кілька правил переходу від одних формул до інших, рівносильних їм (у всіх інтерпретаціях).
Очевидно, для формул логіки предикатів зберігаються всі рівносильності правила рівносильних перетворень логіки висловлень. Крім того, можна довести такі правила.
Зв’язок кванторів із запереченням.
Нехай, А – формула, що містить вільну змінну х. Тоді справджуються рівносильності:
(( х) А(х) ( (( х) Ā(х) (2)
(( х) А(х) ( (( х) Ā(х) (3)
Доведемо спочатку рівносильність (2). Нехай х1,...., хn – множина (може бути порожньою) всіх вільних змінних формули А, відмінних від х. Нехай М(=(М, (( - довільна інтерпретація. Доведемо, що на будь-якому наборі значень своїх вільних змінних ( а1,...., аn(, аі є М, формули (( х) А(х) й (( х) Ā(х) набувають однакових значень істинності.
Можливими є два випадки:
для будь-якого елемента а є М А(х)(( а, а1, ....,аn( = 1;
для деякого елемента а0 є М А(х)(( а0, а1, ....,аn( = 0;
У першому випадку для будь-якого елемента а є М маємо А(х)(( а,а1, ....,аn( = 0. Звідси за означенням (( х) Ā(х)(( а1, ....,аn( = 0. З іншого боку, в цьому випадку (( х) А(х)(( а1, ....,аn( = 1. Звідси (( х) А(х)(( а1, ....,аn( = 0.
У другому випадку для елемента а0 є М маємо Ā(х)(( а0,а1, ....,аn( =1. Звідси (( х) Ā(х)(( а1, ....,аn( =1. З іншого боку, в цьому випадку (( х) А(х)(( а1, ....,аn( = 0. Звідси (( х) А(х)(( а1, ....,аn( = 1. Рівносильність (2) доведено.
Доведемо тепер рівносильність (3). Застосуємо рівносильність () до формули Āх. Тоді (( х) Ā(х) ( (( х) Ā(х) ( (( х) А(х). Застосувавши рівносильність 11 основних рівносильностей логіки висловлень, дістанемо: (( х) А(х)( (( х) Ā(х) ( (( х) Ā(х).
Винесення квантора за дужки.
Нехай, А(х) містить вільну змінну х, формула В не містить змінної х й обидві вони задовольняють п. 3 означення формул. Тоді
(( х)( А(х)( В) ( (( х) А(х)( В;
(( х)( А(х)( В) ( (( х) А(х)( В;
(( х)( А(х)( В) ( (( х) А(х)( В;
(( х)( А(х)( В) ( (( х) А(х)( В;
Доведемо першу з цих рівностей (інші доводяться аналогічно).
Нехай, хі,1 ,...,хі,n - усі вільні змінні формули (( х)( А(х)( В). Тоді вони ж будуть усіма вільними змінними формули (( х) А(х)( В.
Розглянемо довільну інтерпретацію з множиною М. Нехай, (а1, ..., аn(, аі є М – довільний набір значень вільних змінних хі,1 ,...,хі,n . Оскільки формула В не містить вільної змінної х, можна визначити значення цієї формули в наборі (а1, ..., аn( (точніше, в його частині, що стосується вільних змінних формули В). Якщо В(( а1, ....,аn( = 0 , то ((( х) А(х)( В) ( а1, ....,аn( = 0 і для будь-якого елемента а з множини М у наборі значень (а1, ..., аn( своїх вільних змінних х, хі,1 ,...,хі,n формула А(х)( В набуває значень 0. Звідси (( х) А(х)( В(( а1, ....,аn( = 0. Якщо В(( а1, ....,аn ( =1 , то для будь-якого елемента а з множини М у наборі значень (а, а1, ..., аn( формули А(х)( В й А(х) набувають однакових істинностей. Звідси, ((( х) А(х)( В)(( а1, ....,аn( = (( х) А(х)( ( а1, ....,аn( = (( х) А(х)( В(( а1, ....,аn.
Зазначимо, що коли не вимагати, щоб формула В не містила змінної х, то будуть справджуватися тільки дві рівносильності:
(( х) (А(х)) ( В(х) ( (( х) А(х) ( (( х) В(х);
(( х) (А(х) ( В(х)) ( (( х) А(х) ( (( х) В(х).
Переставлення однойменних кванторів.
Для кванторів ( та( маємо
(( у) (( х) А(х, у) ( (( х) (( у) А(х, у);
(( у) (( х) А(х, у) ( (( х) (( у) А(х, у).
Перейменування зв’язаних змінних.
Замінюючи зв’язану змінну формули А іншою змінною, що не входить у цю формулу, у кванторі й усюди в області його дії дістаємо формулу, рівносильну А.
Це твердження легко доводиться за довжиною формули.
Розглянемо спосіб спрощення формул, що спирається на зведені рівносильності. Під довжиною формули тут і далі розумітимемо загальне число символів предикатів, логічних символів та символів кванторів, які входять до неї. Так, формула (( х1) А1(2) (х1, х2) ( (( х3) А2(1)(х3) має довжину 5.
Формули, в яких із логічних символів застосовуються тільки символи (, (, ¯ , причому символ ¯ зустрічається лише перед символами предикатів, будемо називати зведеними.
Приклад.
Розглянемо такі формули:
А1(1) (х1) ( А2(2) (х1, х2).
(( х1) А1(1) (х1) ( (( х2) Ā2(2)(х2, х3).
(( х) А1(1) (х1) ( (( х2) Ā1(1)(х2).
Лише перші дві формули є зведеними.
Теорема1.
Для будь-якої формули існує рівносильна їй зведена формула, причому множини вільних і зв’язаних змінних цих формул збігаються.
Така зведена формула називається зведеною формою заданої формули.
Користуючись рівносильностями логіки висловлень, легко вказати формулу, рівносильну заданій, що містить із логічних символів тільки (, (, ¯. Тому будемо вважати, що формули, які розглядаються, містять тільки ці логічні символи.
Доведемо це твердження методом індукції за довжиною формули. При n=1 формула є атомарною і, отже, зведеною.
Припустимо, що для формул, довжина яких менша від n, твердження теореми справджується. Доведемо його для формули F завдовжки n. Позначимо довжину формули F через .
Формула F має вигляд: або .
Випадок1. Оскільки , за індуктивним припущенням існують зведені формули та формули G й H відповідно, і множини вільних та зв’язних змінних формул і G, й H збігаються. Тоді - формула, . Звідси - зведена форма формули із тією самою множиною вільних і зв’язаних змінних, що й .
Випадок2. Він аналогічний випадку 1.
Випадок3. Тут формула G може мати такий вигляд:
3.1) ;
3.2) ;
3.3) ;
3.4) ;
3.5) ;
Випадок3.1. Тут , де . За індуктивним припущенням існують зведені формули та , рівносильні та відповідно, і множинивільних та зв’язаних змінних формул і , і збігаються. Тоді - зведена форма формули з тією самою множиною вільних змінних.
Випадок3.2. Він аналогічний випадку 3.1.
Випадок3.3. . Тут , де . Застосовуючи індуктивне припущення до формули , дістаємо зведену форму формули з тією самою множиною вільних та зв’язаних змінних.
Випадок3.4. Тут , де . За індуктивним припущенням існує зведена формула , рівносильна формулі , з тією самою множиною вільних та зв’язаних змінних. Тоді - зведена форма формули .
Випадок3.5. Він аналогічний випадку 3.3.
Випадок4. Формула має довжину . За індуктивним припущенням існує зведена форма цієї формули з тією самою множиною вільних та зв’язаних змінних. Тоді - зведена форма формули .
Випадок5. Він аналогічний випадку 4. Теорему доведено.
Зведена формула називається нормальною, якщо вона не містить символів кванторів або всі символи кванторів записані попереду (тобто логічні символи і символи предикатів знаходяться в області дії кожного квантора).
Приклад. Розглянемо такі формули:
- нормальна формула.
- зведена формула, що не є нормальною.
Теорема2.
Для будь – якої зведеної формули існує рівносильна їй нормальна формула тієї самої довжини.
Така формула називається нормальною формулою заданої зведеної формули.
Доведення проведемо методом індукції за довжиною n формули. При n=1 формула є атомарною і, отже, нормальною.
Припустимо, що твердження теореми справджується для всіх формул, довжина яких менша від n. Нехай F - формула завдовжки n. Тоді формула F має вигляд: або .
Випадок1. За умовою - зведена формула. Тоді та також є зведеними формулами, довжина яких менша від n. За індуктивним припущенням існують рівосильні їм нормальні формули та відповідно, де . Якщо формули й не містять символів кванторів, то - нормальна форма завдовжки n формули .
Нехай, наприклад, формула містить символ квантора. Тоді має вигляд: , де (випадок коли має вигляд , є аналогічним).Якщо змінна х входить в формулу , то тільки як зв’язна (інакше порушується означення формули). Застосувавши правило перейменування зв’язаних змінних, перейдемо до формули , рівносильної і такої, що не має змінної х. Очевидно, - зведена формула тієї самої довжини, що й . За правилом винесення квантора за дужки .
Оскільки , за індуктивним припущенням існує рівносильна нормальна їй формула тієї самої довжини. Тоді - нормальна форма формули тієї самої довжини.
Випадок2. Він аналогічний випадку 1.
Випадок3. Оскільки формула - зведена, є атомарною формулою, і тоді - нормальна формула.
Випадок4. Тут - зведена формула, . За індуктивним припущенням існує рівосильна їй нормальна формула тієї самої довжини. Тоді - нормальна форма формули завдовжки n.
Випадок5. Він аналогічний випадку 4. Теорему доведено.
Теорема3.
Для будь – якої формули існує рівносильна їй нормальна формула.
6.Здійснюваність. Загальнозначущість.
Розглянемо деяку інтерпретацію з множиною М.
Означення 4. Кажуть, що формула А є здійснюваною в заданій інтерпретації, якщо існує набір (а1, ..., аn(, аі є М, значень вільних змінних х1 ,...,хn формули А такий, що А((а1,..., аn( = 1. Кажуть, що формула А є істинною в заданій інтерпретації, якщо вона набуває значень 1 у будь-якому наборі (а1, ..., аn(, аі є М, значень своїх вільних змінних х1 ,...,хn . Кажуть, що формула А є загальнозначущою або тотожно-істинною (в логіці предикатів), якщо вона – істинна в кожній інтерпретації. Кажуть, що формула А є здійснюваною (в логіці предикатів), якщо існує інтерпретація, в якій А – здійснювана формула.
Очевидно, формула А є загальнозначущою тоді і тільки тоді, коли формула Ā не є здійснюваною, і здійснюваною тоді і тільки тоді, коли формула Ā не є загальнозначущою.
Очевидно, якщо F і G – рівносильні (в логіці предикатів) формули, то
F ~ G є загальнозначущою формулою.
Твердження 1.
Формула
(( х) А(х) ( А(y) (4),
де змінна у не входить у формулу А(х), – загальнозначуща.
Нехай - усі вільні змінні формули . Тоді - перелік вільних змінних формули (4). Розглянемо довільну інтерпретацію з множиною .
Нехай , де - довільний набір значень вільних змінних формули (4). Доведемо, що
.
Справді для формули або існує елемент такий, що в наборі значень вільних змінних
,
або для будь – якого елемента у наборі значень вільних змінних
У першому випадку
і тоді
.
У другому випадку
; , і тоді
.
Твердження 2.
Формула А(у) ( (( х) А(х), де змінна у не входить у формулу А (х), є загальнозначущою.
У наслідок попереднього твердження формула - загальнозначуща. Маємо:
Отже, формула є загальнозначущою. Як зазначилося вище, одноіменні квантори можна переставляти. Тому формули
~
~
будуть загальнозначущими.
Загальнозначущою є також формула . Однак формула не є загальнозначущою. Справді, нехай формула - це атомарна формула . Розглянемо інтерпретацію, областю якої є множина цілих чисел; символу поставимо у відповідність предикат x<y.
Тоді формула в цій інтерпретації є істиною, а формула - хибною.
Твердження 3.
Нехай А – тотожньо-істина формула логіки висловлення, а - список її змінних. Підставивши замість кожної змінної , k=1,2,...,n, формули логіки предикатів , дістанемо загальнозначущу формулу логіки предикатів.
Задача розпізнавання загальнозначущості формул логіки предикатів істотно складніша, ніж формул логіки висловлень. Так само, як і в логіці висловлень, вона називається проблемою розв’язуваності і формулюється так: указати ефективний спосіб (алгоритм) розпізнавання загальнозначущості формул (тобто чи є задана формула загальнозначущою).
Загалом ця проблема в логіці предикатів - нерозв’язувана. Тому наводимо це твердження без доведення.
Теорема 2 (теорема Черча).
Не існує алгоритму, який для будь-якої формули логіки предикатів установлює, загальнозначуща вона чи ні.
Однак у деяких окремих випадках проблема розв’язуваності вирішується. Наприклад, якщо розглядати формули логіки предикатів, які містять тільки одномісні предикатні символи, то такий алгоритм існує. Логіка, в якій використовуються тільки одномісні предикати, відповідає логіці, що була описана ще Арістотелем.
Алгоритм перевірки загальнозначущості формул, які містять тільки одномісні предикатні символи, грунтується на такому твердженні.
Твердження 4.
Нехай, F – формула, що містить n одномісних предикатних символів. Для того, щоб формула F була здійснюваною, необхідно й достатньо, щоб вона була здійснюваною в усіх інтерпретаціях (M, f ( із множиною М, які містять не більше як 2 n елементів.
Нехай в інтерпритаціях та одномісними предикатними символами формули поставлені у відповідність предикати і , j=1,2,... . Кажуть, що інтерпретації та - гоморфні, якщо існує сур’єкція така, що для будь – якого і для будь – якого . Тоді, як випливає з індуктивного означення, формула, що містить тільки одномісні предикатні символи, в гоморфних інтерпретаціях одночасно або здійснювана, або нездійснювана.
Покажемо, що коли формула F, яка містить n однотипних предикатних символів , є здійснюваною, вона здійснювана також у деякій інтерпретації зі скінченною множиною М, що містить не більш як елементів. Нехай - інтерпретація, в якій є здійснюваною формула F, і нехай у цій інтерпретації предикатним символам відповідають предикати Для будь – якого розглянемо підмножину , яка складається з таких елементів b, що
Число таких підмножин не перевищує числа наборів з 1 і 0 завдовжки n, тобто не перевищує . Виберемо в кожній з цих підмножин по одному представнику і складемо з них множину . Тоді інтерпретацї та , де - обмеження функції на , - гомоморфні, й, отже, формула F є здійснювоною в інтерпретації з множиною , що містить не більш як елементів. Звідси випливає твердження 4.
Задача розпізнавання загальнозначущості формул логіки предикатів є складна. Вона називається проблемою розв’язуваності і формулюється так: вказати ефективний спосіб розпізнавання загальнозначущості формул (тобто чи є задана формула загальнозначущою). Загалом ця проблема в логіці предикатів – нерозв’язана. Тому твердження наводяться без доведень.
ЛІТЕРАТУРА:
Ю. В. Капітонова, С. Л. Кривий, О. А. Летичевський, Г. М. Луцький, М. К. Печорін: Основи дискретної математики. – Київ, “Наукова Думка”, 2002.
Ю. М. Бардачов, Н. А. Соколова, В. Є. Ходаков: Дискретна математика / За ред. доктора технічних наук, професора В. Є. Ходакова. – Київ: “Вища школа”, 2002.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора