Лог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»).