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 з MP(x) iстинно". Для позначення цiєї операцiї використовують знак , який i називають квантором загальностi. Останнє висловлення у математичнiй логiцi записують так: xP(x) (читається: "для всiх xP в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<y, а другий у вигляді x| y. Тоді неважко переконатись, що висловлення xy(x<y) і xy(x| y) є істинними, а висловлення yx(x<y) і - yx(x| y) хибні. Істинними будуть, наприклад, висловлення x(0<x2-x+1), x((x|1)((1<x))), x((x<1)(x<2)), x(((2| x)(3| x))(6| x)), а висловлення x(0<x2-x+1), x((x|1)((1<x))), x((x<1)(x<2)), x(((2| x)(3| x))(6| 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сть x(P(x)) або x(P(x)) писати вiдповiдно xP(x) або xP(x).

Loading...

 
 

Цікаве