Логіка предикатів з одним змінним

Логіка

Міністерство Освіти Російської Федерації
Поморський Державний Університет ім. М. В. Ломоносова

КУРСОВА РОБОТА ПО
Математична логіка

НА ТЕМУ:

Логіка предикатів з одним змінним

Виконав студент II-го курсуматематичного факультету
Бережний Андрій Віталійович

Коряжма
1997

ЗМІСТ

Введення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .3
Основні поняття. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .4
§ 1. Логіка предикатів з одним змінним. . . . . . . . . . . . . . . . .
. . . . . . . . . . .5
§ 2. Практика за рішенням проблеми розв'язання формул, що містять предикативід одного змінного. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .9
Література. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . 12

ВСТУП

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

Постановка проблеми розв'язання для логіки предикатів аналогічнапостановці цієї проблеми для алгебри висловлювань. Її рішення, що єметою даної курсової роботи. Отже, проблема ставиться таким чином:дати ефективний спосіб для визначення - чи є дана формулаздійсненним чи ні.
Уміючи вирішувати питання про здійснимість, ми тим самим зможемо вирішувати і питання проістинності будь-якої формули. Справді, якщо формула U істинна, то формула
нездійсненна, і назад. Тому, довівши здійснимість абонездійсненною, ми тим самим перевіримо істинність U. Проблемарозв'язності для логіки предикатів є посиленням проблеми розв'язаннядля обчислення висловлювань, так як усі формули обчислення висловлюваньвходять до числа формул логіки предикатів. Однак у той час як рішенняпроблеми розв'язання для обчислення висловлювань ніяких труднощів непредставляє, проблема можливості розв'язання для логіки предикатів виявиласяпов'язаної з серйозними труднощами.
Сучасні дослідження пролили світло на природу цих труднощів. Уданий час є досить ясним, що вирішення цієї проблемиу зазначеному сенсі взагалі неможливо. Інакше кажучи, не може існуватижодного конструктивного правила, яке дозволяло б визначати для будь-якоїформули логіки предикатів, чи є вона тотожно істинною чи ні.
Для деяких приватних типів формул, однак, проблема можливості розв'язання вирішується.
Ми розглянемо найбільш важливий тип формул, для яких рішення проблемирозв'язання може бути здійснено, це формули логіки предикатів,залежні від одного змінного.

Основні поняття
Нехай M - деякий безліч предметів і a, b, c, d - якісьпевні предмети з цієї безлічі. Тоді висловлювання про ціпредметах ми будемо позначати у вигляді

P (a), Q (b), R (c, d) і т.д.
P (a) означає висловлювання про предмет a, Q (b) - висловлювання про предметb, R (c, d) - висловлювання про предмети c і d і т.д.
Такі висловлювання можуть бути як істинні, так і помилкові, що позначаютьсявідповідно символами І і Л. Ці значення ставляться у відповідністьпевних предметів або групам предметів.
Нехай M - довільне непорожній безліч, а x представляє собоюдовільний предмет з цієї безлічі. Тоді вираз F (x) позначаєвислів, що стає певним, коли x заміщенопевним предметом з M. F (a), F (b), ... вже є цілкомпевні висловлювання. Наприклад, якщо M натуральний ряд, то F (x) можепозначати: "x є просте число".
Це невизначений вислів стає певним, якщо x замінитидеяким числом, наприклад: "3 просте число", "4 просте число" і т. д.
Нехай S (x, y) позначає: "x менше y".
Це висловлювання стає певним, якщо x і y замінити числами: "1менше 3 "," 5 менше 2 "і т. д.
Так як з нашої точки зору кожне певне висловлюванняявляє собою І чи Л, то вираз F (x) означає, що кожномупредмету з M поставлено у відповідність один з двох символів І чи Л. Інакшекажучи, F (x) являє собою функцію, визначену на множині M іприймає лише два значення І та Л. Таким же чином невизначенийвислів про двох і більше предметів H (x, y), G (x, y, z) і т. д.предвтавляет собою функцію двох, трьох і т. д. змінних. При цьомузмінні x, y, z пробігають безліч M, а функція приймає значення І і
Л. Ці невизначені висловлювання, або функції одного або декількохзмінних, ми будемо називати логічними функціями або предикатами.
Предикатом з одним змінним можна висловити властивість предмета, наприклад "x є просте число "," x - прямокутний трикутник "і т.д.
Всі поняття, які ми будемо вводити, завжди відносяться до деякогобезпідставного безлічі M, яке ми будемо називати полем. Елементи цьогополя будемо позначати малими латинськими літерами (іноді ці букви ми будемопостачати індексами). Літери кінця латинського алфавіту x, y, z, u, v, x1, x2, ...позначають невизначені предмети поля. Їх ми будемо називати предметнимизмінними. Літери початку алфавіту a, b, c, a1, a2, ...позначають певні предмети поля. Їх ми будемо називати індивідуальнимипредметами або предметними постійними.
Великими латинськими літерами

A, B, ..., X, A1, A2, ... ми будемо позначати змінні, що приймають значення І та Л. Їх ми назвемозмінними висловлюваннями. Ми будемо також розглядати і постійнівисловлювання. Їх ми будемо також позначати великими латинськими літерами, як -небудь зазначеними або просто з додатковою обмовкою.
Великі латинські літери і символи предикатів як індивідуальнихпредметів, так і від предметних змінних ми будемо називати елементарнимиформулами.
Ми будемо говорити, що в формулах

((х) U (х) і ((х) U (х)квантори ((х) і ((х) відносяться до змінному х або що змінна х пов'язановідповідним квантором.
Предметна змінна, не пов'язане ніяким квантором, ми будемо називативільним змінним.
Формули, в яких з операцій алгебри висловлювань є тількиоперації, і, а знаки заперечення відносяться тільки доелементарним предикатів та відгуків, будемо називати наведенимиформулами.
Наведена формула називається нормальною, якщо вона не містить кванторівабо якщо при утворенні її з елементарних формул операції зв'язуванняквантором слідують за всіма операціями алгебри висловлювань.
Якщо дві формули U і B, віднесені до деякого полю M, при всіхзаміщених змінних предикатів, змінних висловлювань і вільнихпредметних змінних відповідно індивідуальними предикатами,визначеними на M, індивідуальними висловами та індивідуальнимипредметами з M, приймають однакові значення І чи Л, то ми будемоговорити, що ці формули рівносильні на полі M.
Якщо дві формули рівносильні на будь-яких полях M, то ми будемо їх називатипросто рівносильними.
Нормальну формулу, рівносильну деякою формулою U, ми будемо називатинормальною формою формули U.

§ 1. Логіка предикатів з одним змінним

Ми будемо розглядати формули логіки предикатів, що містять предикати,які залежать тільки від одного змінного. Логіка, в якійвживаються тільки такі вирази, відповідає тій, яка описана
Аристотелем і увійшла як традиційний елемент в систему гуманітарногоосвіти. Відомі форми висловлювань цієї логіки і формиумовиводів, так звані «модуси силогізмів», виражаються повністю всимволіці логіки предикатів від одного змінного.
Теорема. Якщо формула логіки предикатів, що містить тільки предикати відодного змінного, здійснена на деякому полі M, то вона здійснена на полі
, Що містить не більше елементів, де n - число предикатів,що входять у розглянуту формулу.
Нехай формула U (A1, ..., An), що містить тільки символи предикатів A1,
..., An, кожен з яких залежить від одного змінного, здійснена надеякому полі M. цю формулу ми можемо припускати представленої внормальній формі, а всі предметні змінні в ній пов'язаними. У самомусправі, якою б не була формула U, ми можемо, зробивши над неюперетворення, привести її до вигляду, в якому всі квантори передуютьіншим символам формули, при цьому склад її предикатів і предметнихзмінних не змінюється. Якщо в U є вільні предметні змінні, томожна пов'язати їх квантором спільності.
Отже, припустимо, що U - нормальна формула. Тоді ми можемо уявити їїнаступним чином:

((x1) ((x2 )...(( xp) B (A1, ..., An, x1, ..., xp),де кожен із символів ((xi) означає квантор ((xi) або ((xi), а формула

B (A1, ..., An, x1, ..., xp)кванторів не містить.
У формулі B (A1, ..., An, x1, ..., xp) всі змінні x1, ..., xp входять допредикати A1, ..., An, і її можна записати у вигляді

B (A1 (), ..., An ()),де i1, ..., in - числа від 1 до p. Однак, буде зручніше користуватисявиразом

B (A1, ..., An, x1, ..., xp),якщо мати на увазі, що B є логічною функцією предикатів Ak, акожен предикат Ak залежить від якогось одного змінного.
Покажемо, що якщо для деякого поля M існують індивідуальніпредикати

,...,,для яких формула U (,...,) істинна, то ця формула істинна іна деякій підмножині цього поля, що містить не більше елементів,бо інакше наше твердження тривіально. Розіб'ємо елементи множини M накласи в такий спосіб. Для кожної послідовності, яка містить nсимволів І і Л в довільному порядку (І, Л, Л, ..., І,), існує частина
(може бути, порожній) множини M, що містить ті і тільки ті елементи x, дляяких послідовність значень предикатів (x), (x), ..., (x) збігається з даною послідовністю символів І і Л.
Позначимо через 1, 2, ..., nпослідовність символів І і Л, де i є І чи Л,а відповідний цієї послідовності клас елементів x позначимо

,, ...,.
Деякі з цих класів можуть виявитися порожні, тому що може трапитися,що для деякої послідовності 1, 2, ..., n НЕіснує такого елемента, для якого предикати,, ...,приймають відповідні значення 1, 2, ..., n. Разом зтим кожен елемент множини M належить одному з класів, ірізні класи загальних елементів не мають. Число всіх класів (порожніх інепустих) дорівнює кількості послідовностей 1, 2, ..., n, тобто
. Отже, число q непустих класів не перевищує.
Виберемо з кожного непорожньої класу по одному елементу і позначимо ціелементи a1, a2, ..., aq.
Безліч всіх цих елементів позначимо. доведемо, що якщо формула
U (, ...,) істинна на полі M, то вона істинна і на полі (такяк - частина поля M, то предикати визначені на). кожномуелементу x поля M поставимо у відповідність елемент з, що належитьтого ж класу, що і х. У існує один і тільки один такийелемент. Елемент з, поставлений у відповідність х, позначимо
(х). Можна сказати, що ми побудували функцію, визначену намножині M і приймає значення з безлічі.
Легко бачити, що має місце наступна Рівносильність:

(х) (((х)).
Дійсно, (x) належить того ж класу, що і x. Але, завизначенням, для елементів одного і того ж класу кожен предикатприймає одне і те ж значення. Звідси випливає, що якщо у формулі
U (, ...,) для кожного предметного змінного t замінити кожневираз (t) через ((х)), то формула U (, ...,)перейде у формулу (, ...,), рівносильну першим. Написанняформули відрізняється від U тільки тим, що всі предметні змінні x,y, z, ..., u формули U заміщені відповідно через (х), (y), ..., (u). Це випливає з того, що за умовою формула U (, ...,)містить лише предикати, і тому будь-яке предметне зміннавходить тільки під знаком одного з цих предикатів.
Нехай R (x, y, ..., u) - предикат, визначений на полі M. Введемопозначення

R (x, y, ..., u).
Під цим виразом ми будемо розуміти предикат, що залежить від y, z, ..., u
(або висловлювання, якщо, y, z, ..., u відсутні) і приймає значення
І, коли R (y, z, ..., u) має значення І для даних y, z, ..., u і длявсіх x, що належать полю, і приймає значення Л впротилежному випадку. Введемо також вираз

R (x, y, ..., u),що є предикат від y, ..., u і приймає значення І,коли R (x, y, ..., u) має значення І для y, ..., u і принаймні дляодного значення x з поля, і значення Л в протилежному випадку.
Знаки і будемо називати обмеженими квантора. Якщо ми всізмінні предиката R (x, y, ..., u) зв'яжемо обмеженими квантора,наприклад

... R (x, y, ..., u),то отримаємо формулу, віднесену до поля. покажемо, що вираз

((x) R ((х), y, ..., u)рівносильно висловом

R (x, y, ..., u).
Нехай ((x) R ((х), y, ..., u) має значення І. У такому разі R
((х), y, ..., u) має значення І для даних y, ..., u і для кожногоx. Але так як функція (х) пробігає все поле, коли x пробігаєполі M, то R (x, y, ..., u) має значення І для даних y, ..., u і длявсіх x з. У силу визначення R (x, y, ..., u) також березначення І. Зворотно, якщо R (x, y, ..., u) приймає значення І, то R
(x, y, ..., u) має значення І для даних y, ..., u і для кожного x з
. У такому випадку вираз R ((х), y, ..., u) має значення Ідля даних y, ..., u і для кожного x з M, тому що (х) для будь-якого xналежить.
Аналогічним чином можна показати, що вирази

() R ((х), y, ..., u) і () R (x, y, ..., u)також рівносильні.
Розглянемо формулу U (, ...,), яку можна представити уформі

((x1) ((x2 )...(( xp) B (, ...,, x1, ..., xp).

B (, ...,, x1, ..., xp) являє собою предикат, визначений на полі M і залежний від pзмінних x1, ..., xp. Кожне з цих змінних входить у формулу B тількичерез предикати, ...,. З іншого боку, ми бачили, щопредикати (х) і ((х)) рівносильні. Тому якщо у формулі
B (, ...,, x1, ..., xp) ми замінимо xi на (хi), то отримаєморівносильно вираз:

B (, ...,, x1, ..., xp) (B (, ...,, (x1), ...,

(xp)).
Звідси випливає, що

((xp) B (, ...,, x1, ..., xp) (((xp) B (, ...,,

(x1), ..., (xp)).
Далі можна зробити висновок, що
((xp) B (, ...,, (x1), ..., (xp)) (

(B (, ...,, (x1), ..., (xp-1), xp).
Розмірковуючи аналогічним чином, ми отримаємо
((Xp-1) ((xp) B (, ...,, x1, ..., xp-1, xp) (

(B (, ...,, (x1) , ..., (xp-2), xp-1, xp)і, нарешті, прийдемо до наступного:
((X1) ((x2 )...(( xp) B (, ...,, x1, ..., xp) (

(B (, ...,, x1, ..., xp).
Права частина останньої Рівносильність, згідно з глузду символу,представляє не що інше, як формулу

((x1 )...(( xp) B (, ...,, x1, ..., xp),віднесену до поля.
Таким чином, ми довели, що формула U (, ...,) зберігаєсвоє значення, якщо її віднести до поля, і теорема, таким чином,доведена.
С л е д с т в и е. Якщо формула U, що містить лише предикати, що залежатьвід одного змінного, є тотожно істинною для кожного поля, неперевищує елементів, де n - число предикатів в U, то формула Uтотожно істинна (тобто істинна для будь-якого поля). Справдіприпустимо, що U не є тотожно істинною формулою. У такому випадкуїї заперечення здійснимо на деякому полі. Так як такожзадовольняє умови теореми, то знайдеться поле, що містить не більшеелементів, на якому формула здійсненна. Отже, U не можебути істинною на цьому полі, що суперечить умові. Отже, припущення,що U не є тотожно істинною, призводить до протиріччя, що йтреба було довести.

§ 2. Практика за рішенням проблеми розв'язання формул, що містять предикати від одного змінного

Доведена (у попередньому пункті) теорема дозволяє вирішувати проблемурозв'язання для формул, що містять тільки предикати, що залежать від одногозмінного. З слідства видно, що для того, щоб встановити, чи єЧи формула U тотожно істинною чи ні, достатньо перевірити, чи єЧи вона тотожно істинною для кожного поля, яке містить не більше ніж
елементів.
Зауважимо, що достатньо перевірити, чи є дана формула Uтотожно істинною на поле, що складається рівно з елементів. Цевипливає з того, що для формул даного типу має місценаступне: якщо формула U тотожно істинна на деякому полі, то вонатотожно істинна на будь-якої його частини.
Розглянемо довільне поле з рівно елементів:,
, ...,. Легко бачити, що будь-яка формула, що має ви??:

((x) B (x),віднесена до даного полю, рівносильна формулою

B () (B () (... (B ().
А формула, що має вигляд:

(x) B (x),рівносильна формулою

B () B () ... B ().
У такому випадку довільна формула U, віднесена до поля (, ..., ), Рівносильна формулою, в якій всі квантори заміненіопераціями логічного твори і логічної суми. Якщо в U входилитільки предикати A1, ..., An, що залежать від одного змінного, тоявляє собою формулу, утворену тільки операціями алгебривисловлювань над виразами Ai (xj), 1 (i (n, 1 (j (. Так якпредикати Ai (x) абсолютно довільні, то вираження Ai (xj) представляютьсобою зовсім довільні висловлювання. Формулу тоді можнарозглядати як формулу алгебри висловлювань, у якої Ai (xj) єелементарними змінними висловлюваннями. Тоді питання про тотожноюістинності U на полі,, ..., виявляється еквівалентнимпитання про тотожною істинності, як формули алгебри висловленьіз змінними висловлюваннями Ai (xj).
Зауважимо, що формула алгебра висловлювань по суті не залежить відтого, які елементи поля (, ...,), а залежить тільки від їхчисла, тому що якщо ми візьмемо інше поле ((, ..., (), то в
відбудеться тільки зміна позначень змінних висловлювань Ai (xj)на Ai (xj (). Саме тому ми можемо сказати, що якщо тотожнеістинна, як формула алгебри висловлювань, то формула U тотожнеістинна на будь-якому полі з p елементів, і назад. З іншого боку, бувотриманий конструктивний спосіб визначати - є довільна формулаалгебри висловлювань тотожно істинною чи ні. Застосовуючи цей критерій,ми можемо встановити, чи довільна формула U, що містить тількипредикати від одного змінного, тотожно істинною на будь-якому полі,що містить p = елементів. У такому випадку в силу висловленого вищеположення ми можемо вирішити також і питання про те, чи буде формула Uтотожно істинною чи ні.
Розберемо це конкретно на прикладах.

П Р И М Е Р 1: Отже, нехай дана формула U, що має вигляд:

((x) [P (x) (P (x))],віднесена до деякого полю L. Для того, щоб встановити тотожнуістинність цієї формули, нам достатньо перевірити, чи є вонатотожно істинною на полі, що містить рівно елементів (див. вище).
У даному випадку число предикатів (n) дорівнює 2, тобто L може бутипредставлено як (a1, a2, a3, a4).
Легко бачити, що формула U рівносильна: ((x) [P (x) (Q (x) P (x))],яка, віднесена до поля L, рівносильна:
[P () (Q () P ())] [P () (Q () P ())]
[P () (Q () P ())] [P () (Q ()
P ())]. Таким чином, являє собою формулу, утворену тількиопераціями алгебри висловлювань над виразами P () і Q (), деi =, тобто її можна розглядати як формулу алгебри висловлювань, уякої P () і Q () є елементарними зміннимивисловлюваннями. Значить, відповівши на питання про тотожною істинності,ми зможемо сказати, чи є формула U тотожно істинною чи ні.
є тотожно істинною в алгебрі висловлювань U такожтотожно істинна формула на поле, що містить елементів. Цеоеначает, що U тотожно істинна.

П Р И М Е Р 2: Довести, що формула U, віднесена до деякого полю L,представлена як

[((х) (Q (x)) P (x)],є тотожно істинною.
Для цього вона повинна бути тотожно істинною на полі, що містить рівно
елементів. У даному випадку n = 2, тобто L можна знову визначити як (a1, a2, a3, a4).
Застосовуючи рівносильні перетворення над U, можемо укласти їїРівносильність формулою: ((х) [(Q (x)) P (x)], яка,віднесена до поля L, рівносильна: [(Q ()) P ()]
[(Q ()) P ()]
[(Q ()) P ()]
[(Q ()) P ()]. Легко бачити, що, як і в попередньому прикладі, єформулу, утворену тільки операціями алгебри висловлювань надвиразами P () і Q (), де i =, а тому її можна віднести доформулами алгебри висловлювань, у якої P () і Q () єелементарними змінними висловлюваннями. Чи є формулатотожно істинною?
Формула являє собою диз'юнкції деяких формул. Томувсякий раз, коли одна з них істинна, сама (за визначеннямдиз'юнкції) буде тотожно істинною. Складемо таблицю істинності:

PQQ (Q) P

0 0 1 0
1

0 1 1 1
0

1 0 0 1
1

1 1 0 1
1

Таким чином, формула (Q) P є здійсненним,отже, є тотожно істинною формулою в алгебрівисловлювань U також тотожно істинна формула на полі,що містить елементів. Це оеначает, що U тотожно істинна.

ЛІТЕРАТУРА

П. С. Новиков, "Елементи математичної логіки", державневидавництво фізико-математичної літератури, М., 1959