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

Министерство Освіти Російської Федерації Поморський Державний Університет їм. М. У. Ломоносова КУРСОВАЯ РОБОТА ПО МАТЕМАТИЧНОЇ ЛОГИКЕ НА ТЕМУ:

Логіка предикатів з однією переменным Выполнил студент II-го курсу математичного факультету Бережний Андрій Витальевич Коряжма 1997.

СОДЕРЖАНИЕ Введение. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .3 Основні поняття. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .4 § 1. Логіка предикатів з однією змінним. .. .. .. .. .. .. .. .. .. .. .. .. .. .5 § 2. Практика щодо проблеми разрешимости формул, містять предикати від однієї змінного. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .9 Література. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... 12.

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

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

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

P (a), Q (b), R (c, d) тощо. P (a) позначає висловлювання про об'єкт a, Q (b) — висловлювання про об'єкт b, R (c, d) — висловлювання про предметах з і 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 і приймаючу лише 2 значення І і Л. Так само невизначений висловлювання про поїздку двох і більше предметах H (x, y), G (x, y, z) тощо. буд. предвтавляет собою функцію двох, трьох тощо. буд. змінних. У цьому перемінні x, y, z пробігають безліч M, а функція приймає значення І і Л. Ці невизначені висловлювання, чи функції однієї чи кількох змінних, ми називати логічними функціями чи предикатами. Предикатом з однією змінним можна сформулювати властивість предмета, наприклад «x є просте число », «x — прямокутний трикутник «тощо. Усі поняття, які ми вводити, ставляться завжди до певного произвольному безлічі M, яку ми називатимемо полем. Елементи цього поля будемо позначати малими написом (інколи ці літери ми постачати індексами). Букви кінця латинського алфавіту x, y, z, u, v, x1, x2, … позначають невизначені предмети поля. Їх ми називати предметними перемінними. Букви початку алфавіту a, b, з, a1, a2, … позначають певні предмети поля. Їх ми називати індивідуальними предметами чи предметними постійними. Великими латинськими буквами.

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

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

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

Ми розглядатимемо формули логіки предикатів, містять предикати, які залежать лише від однієї змінного. Логіка, у якій вживаються лише висловлювання, відповідає тій, яка описана Арістотелем й Україна ввійшла як традиційний елемент до системи гуманітарного освіти. Відомі форми висловлювань цієї логіки й форми умовиводів, звані «модуси силогізмів», виражаються цілком у символіці логіки предикатів від однієї змінного. Теорему. Якщо формула логіки предикатів, яка містить лише предикати від одного змінного, виконано на деякому полі M, вона реалізовано на полі [pic], що містить трохи більше [pic] елементів, де 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([pic]), …, An ([pic])), де i1, …, in — числа від 1 до p. Проте, буде зручніше користуватися выражением.

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

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

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

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

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

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

[pic][pic].. pic] R (x, y, …, u), одержимо формулу, отнесённую від поля [pic]. покажемо, що выражение.

((x) R ([pic](х), y, …, u) рівносильне выражению.

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

([pic]) R ([pic](х), y, …, u) і ([pic]) R (x, y, …, u) також рівнозначні. Розглянемо формулу U ([pic], …, [pic]), що можна явити у форме.

((x1)((x2)…((xp) B ([pic], …, [pic], x1, …, xp).

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

B ([pic], …, [pic], x1, …, xp) (B ([pic], …, [pic],[pic](x1), …,.

[pic](xp)). Звідси випливає, что.

((xp) B ([pic], …, [pic], x1, …, xp) (((xp) B ([pic], …, [pic],.

[pic](x1), …, [pic](xp)). Далі можна зрозуміти, що ((xp) B ([pic], …, [pic], [pic](x1), …, [pic](xp)) (.

([pic] B ([pic], …, [pic], [pic](x1), …, [pic](xp-1), xp). Міркуючи аналогічно, ми матимемо ((xp-1) ((xp) B ([pic], …, [pic], x1, …, xp-1, xp) (.

([pic][pic] B ([pic], …, [pic], [pic](x1), …, [pic](xp-2), xp-1, xp) і, нарешті, прийдемо ось до чого: ((x1)((x2)…((xp) B ([pic], …, [pic], x1, …, xp) (.

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

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

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

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

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

B ([pic]) (B ([pic]) (… (B ([pic]). А формула, має вид:

([pic]x) B (x), рівносильна формуле.

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

П Р І М Є Р 1: Отже, нехай дана формула U, має вид:

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

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

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

P Q [pic] [pic][pic]Q ([pic][pic]Q)[pic]P.

0 0 1 0 1.

0 1 1 1 0.

1 0 0 1 1.

1 1 0 1 1.

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

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