На бирже курсовых и дипломных проектов можно найти готовые бесплатные и платные работы или заказать написание уникальных курсовых работ, дипломов, лабораторных работ, контрольных работ, диссертаций, рефератов по самым низким ценам. Добавив заявку на написание требуемой для вас работы, вы узнаете реальную стоимость ее выполнения.

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Быстрая помощь студентам

 

Результат поиска


Наименование:


курсовая работа Поняття предиката

Информация:

Тип работы: курсовая работа. Добавлен: 02.06.2012. Сдан: 2010. Страниц: 9. Уникальность по antiplagiat.ru: < 30%

Описание (план):


   Зміст
    Вступ
    Поняття предиката
    Лог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 властивостi, або що цi об’єкти знаходяться мiж собою у певному вiдношеннi.
     Наприклад, в iстинному висловленнi «3 є просте число» пiдмет «3» - це об’єкт, а присудок «є просте число» виражає деяку його властивiсть.
     У латинськiй граматицi присудок називається  предикатом, звiдси цей термiн i увiйшов у математичну логiку. Головним для логiки предикатiв є саме друга складова речення-висловлення - присудок-властивiсть. Вона фiксується, а значення об’єкта пропонується змiнювати так, щоб кожен раз отримувати осмисленi речення, тобто висловлення.
     Наприклад, замiнюючи у наведеному вище висловленнi 3 на 1, 5, 9 або 12, матимемо вiдповiдно такi висловлення: «1 є просте число», «5 є  просте число», «9 є просте число», «12 є просте число», з яких друге є iстинним, а решта - хибними висловленнями.
     Таким чином, можна розглянути вираз «x є просте число», який не є висловленням, а є так званою пропозицiйною (висловлювальною) формою. Тобто формою (або формуляром), пiсля пiдстановки в яку замiсть параметра (змiнної) x об’єктiв (значень) з певної множини M, дiстаємо висловлення.
     Аналогiчно  можна трактувати, наприклад, пропозицiйнi форми «a є українцем», «b i c є однокурсники», «c важче d», або «точка x лежить мiж точками y i z». У першi двi з них можна пiдставляти замiсть параметрiв a, b i c прiзвища конкретних людей. У третю замiсть c i d назви будь-яких об’єктiв (предметiв), якi мають вагу. Для четвертої множиною M значень змiнних x, y i z є множина точок певної прямої.
     Перша з цих пропозицiйних форм задає, як i в наведенiй ранiше формi, певну властивiсть для об’єкта a. Iншi три форми описують деякi вiдношення мiж вiдповiдними об’єктами.
     Розглянувши конкретнi приклади i коротко зупинившись  на мотивацiї та змiстовнiй iнтерпретацiї подальших понять, перейдемо до формальних математичних означень.
     n-мiсним  предикатом P(x1,x2,...,xn) на множинi M називається довiльна функцiя типу Mn®B, де B = {0,1} - бульовий (двiйковий) алфавiт.
     Множина M називається предметною областю, або унiверсальною множиною, а x1,x2,...,xn - предметними змiнними, або термами предиката P.
     Множина елементiв (a1,a2,...,an)IMn таких, що P(a1,a2,...,an) = 1 називається областю iстинностi (або характеристичною множиною) предиката P.
     Якщо  P(a1,a2,...,an) = 1, то згiдно з логiчною iнтерпретацiєю будемо говорити, що предикат P є iстинним на (a1,a2,...,an). У противному разi, казатимемо, що предикат P є хибним.
     Взагалi кажучи, можна означити так званий багатосортний предикат, як функцiю типу M1?M2?...?Mn®B, дозволивши різним його аргументам приймати значення з рiзних множин. Iнодi це буває доцiльним; однак частiше в логiцi предикатiв використовують наведене ранiше означення.
     Неважко зрозумiти, що пропозицiйна форма  є одним зi способiв задання  предиката.
     Для 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)IR тодi i тiльки тодi, коли P(a1,a2,...,an) = 1. Очевидно, що при цьому R є областю iстинностi предиката P.
     Крiм  того, за будь-якою вiдповiднiстю C мiж множинами A i B (тобто CIA?B) можна побудувати бiнарний двосортний предикат P(x,y) таким чином:
     P(a,b) = 1 тодi i тiльки тодi, коли (a,b)IC для aIA i bIB.
     Зокрема, будь-як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льш загального поняття предиката.
     
 

Логiка предикатiв
   Як  з елементарних висловлень за допомогою логiчних операцiй можна утворювати складенi висловлення, так i, використовуючи простi (елементарнi) предикати i логiчнi зв’язки (операцiї), можна будувати складенi предикати або предикатнi формули.
   Як  правило, основнi логiчнi операцiї U, U, O, ®, ~ означають для предикат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)UQ(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)UQ(x1,x2,...,xn) збiгається з теоретико-множинним перетином областей iстинностi предикатiв P(x1,x2,...,xn) i Q(x1,x2,...,xn).
   Диз’юнкцiєю P(x1,x2,...,xn)UQ(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).
   Запереченням OP(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) = OP(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)U(OP3(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)(х) позначає предикат “х ділиться на два та х ділиться на три”, тобто позначає предикат ділення на шість.
    Крім  операцій логіки висловлень будемо ще застосовувати операції зв’язування квантором.
 

Квантори
   Додатково в лог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льки тих bIM, для яких одномiсний предикат A(x,b) є iстинним для всiх x з M.
   Приклад: Розглянемо двомiсний предикат A(x,y), визначений на множинi = {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 є суттєвим. 

 

     Формули логіки предикатів
   Наведемо iндуктивне означення поняття  формули логiки предикатiв (предикатної формули або просто формули ) на предметнiй областi M.
   1. Усi предикати P(x1,x2,...,xn) на множинi M є формулами. Такi формули називають елементарними, або атомарними.
   2. Якщо A i B - формули, то (OA), (OB), (AUB), (AUB), (A®B), (A~B) теж є формулами.
   3. Якщо A - формула, а x - вiльна змiнна в A, то ("x(A)) i ($x(A)) теж формули.
   4. Iнших формул, крiм утворених за  правилами 1-3, немає. 
   Це  означення дозволяє твердити, що усi формули алгебри висловлень є  формулами логiки предикатiв, оскiльки висловлення - це нульмiснi предикати.
   За  допомогою наведеного означення  неважко також переконатись, що вирази ("x($y(A(x,y))®(B(x)U($z(C(x,z))))) i ("x("y(A(x,y)UB(x))®($y(C(x,y)))) є формулами логiки предикатiв, а вираз ("x(A(y)®($x(B(x))))) не є формулою, оскiльки у виразi (A(y)®($x(B(x)))), який є правильною формулою, змiнна x є зв'язаною, тобто не є вiльною змiнною i квантор "x до неї застосувати не можна.
   Для зручност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во).
   Нехай F(x1,x2,...,xn) - деяка формула логiки предикатiв на множинi M. При логiчнiй (iстинностнiй) iнтерпретацiї формули F можливi такi три основнi ситуації.
   1. Iснує набiр значень змiнних, для  якого формула F перетворюється на iстинне висловлення. У цьому разi формула F називається виконуваною в областi M.
   Якщо  для F iснує область M, в якiй F є виконуваною, то формула F називається просто виконуваною.
   2. Якщо формула F приймає значення 1 (тобто є виконуваною) для всiх наборiв значень з M, то вона називається тотожно iстинною в M. Формула, тотожно iстинна у будь-яких M, називається тотожно iстинною або логiчно загальнозначущою (скорочено - лзз).
   3. Якщо формула F є невиконуваною в M, то вона називається тотожно хибною в M. Формула, невиконувана в усiх M, називається тотожно хибною, або суперечнiстю.
   Приклад. Формула $xA(x,y)®"xA(x,y) є виконуваною i вона ж є тотожно iстинною в усiх одноелементних областях M. Формула F(x1,x2,...,xn)UOF(x1,x2,...,xn) тотожно iстинна, а формула F(x1,x2,...,xn)UOF(x1,x2,...,xn) тотожно хибна. Тотожно iстинними будуть формули "xP(x)®P(y) i P(y)®$xP(x).
   Формули F1 i F2 називаються рiвносильними (еквiвалентними), якщо при всiх можливих пiдстановках значень замiсть їх змiнних вони набувають однакових значень; позначається FF2.
   Наприклад, усi тотожно iстиннi (усi тотожно хибнi) формули рiвносильнi мiж собою. Очевидно також, що коли F1 i F2 рiвносильнi, то формула F1~F2 є тотожно 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альний алгоритм, що породжує шукану множину T тотожно iстинних формул. Послiдовно будуємо всi формули, кожну з них за вiдомою процедурою перевiряємо на тотожну iстиннiсть i вносимо до множини T т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дстановку. Застосовувати цей метод можна також, коли предметна область M
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.