WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЛогіка → Лог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 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.
Квантори
Додатково в лог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йсних чисел x виконується рiвнiсть sin2x+cos2x = 1", "для заданих натуральних a i b завжди iснує натуральне число d, яке є бiльшим від чисел a i b", "для всiх натуральних n справедливе твердження: якщо n дiлиться нацiло на 6 i на 15, то n дiлиться на 30" тощо.
Поняття, що вiдповiдає словам "для всiх", лежить в основi квантора загальностi, який означається таким чином.
Нехай P(x) - предикат на множинi M. Тодi квантор загальностi - це операцiя, що ставить у вiдповiднiсть P(x) висловлення "для всiх x з M P(x) iстинно". Для позначення цiєї операцiї використовують знак , який i називають квантором загальностi. Останнє висловлення у математичнiй логiцi записують так: xP(x) (читається: "для всiх x P вiд x").
Iснує й iнший квантор, що є у певному смислi двоїстим до квантора загальностi i називається квантором iснування. Позначається вiн знаком . Якщо Q(x) - деякий предикат на множинi M, то висловлення "існує в множинi M елемент x такий, що Q(x) iстинно" записується у виглядi xQ(x) i читається скороченно "iснує такий x, що Q вiд x" або "є такий x, що Q вiд x".
Походження обраних позначень пояснюється тим, що символ є перевернутою прописною першою лiтерою нiмецького слова "alle" або англiйського слова "all", що перекладається "усi". А символ вiдповiдає першiй лiтерi слiв "existieren" (нiм.) або "exist" (англ.) - iснувати.
Вираз x читають також як "всi x", "для кожного x", "для довiльного x", "для будь-якого x", а вираз x - як "деякий x", "для деякого x", "знайдеться такий x" тощо.
Зазначимо також, що, окрiм введених символiчних позначень кванторiв, використовують й iншi позначення. Так, замiсть x iнодi пишуть (x), (x) або x, а замiсть x вiдповiдно - (x), (Ex) або x.
Приклад 5.4. Розглянемо два бінарні предикати на множині натуральних чисел: предикат "x менше y" і предикат "x ділить y". Перший з них будемо записувати у традиційній формі - x
  • <<
  • Перша Попередня 1 2 Наступна Остання
  • >>
  • Loading...

     
     

    Цікаве