трусики женские украина

На головну

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

Міністерство Освіти Російської Федерації

Поморський Державний Університет ім. М. В. Ломоносова

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

Математичної логіки

НА ТЕМУ:

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

Виконав студент 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 - нормальна формула. Тоді ми можемо уявити її наступним чином:

(S x1) (s x2) ... (s xp) B (A1, ..., An, x1, ..., xp),

де кожен із символів (s 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 (, ...,), яку можна представити у формі

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

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

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

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

Звідси випливає, що

(S xp) B (, ... ,, x1, ..., xp) ~ (s xp) B (, ... ,, (x1), ..., (xp)).

Далі можна зробити висновок, що

(S xp) B (, ... ,, (x1), ..., (xp)) ~

~ B (, ... ,, (x1), ..., (xp-1), xp).

Розмірковуючи аналогічним чином, ми отримаємо

(S xp-1) (s xp) B (, ... ,, x1, ..., xp-1, xp) ~

~ B (, ... ,, (x1), ..., (xp-2), xp-1, xp)

і, нарешті, прийдемо до наступного:

(S x1) (s x2) ... (s xp) B (, ... ,, x1, ..., xp) ~

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

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

(S x1) ... (s 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 () є елементарними перемінними висловлюваннями. Чи є формулатождественно істинної?

Формулапредставляет собою диз'юнкції деяких формул. Тому щоразу, коли одна з них істинна, сама (за визначенням диз'юнкції) буде тотожно істинною. Складемо таблицю істинності: P QQ (Q) P

0 0 1 0 1

0 1 січня 1 0 Попереднє

1 0 0 1 січня

1 1 0 1 січня

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

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

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка