Лог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(читается: «для всiх x P вiд x»).