Человеческое мышление



Лог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сть sin2 X+cos2 X=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, E X или X.

Пример 5.4. Рассмотрим два бинарных предиката на множестве натуральных чисел : предикат X меньше Y и предикат X делит Y. Первый из них будем записывать в традиционной форме - X Y, а второй в виде X| Y. Тогда нетрудно убедиться, что высказывание X$ Y X Y и X$ Y X| Y является истинными, а высказывание $ Y X X Y и - $ Y X X| Y ошибочные. Истинными будут, например, высказывания X0 X2 - X+1, $ X X|11 X, X X1 X2, X2| X3| X6| X, а высказывание X0 X2 - X+1, $ X X|11 X, X X1 X2, X2| X3| X6| 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.

Пример 5.5. В усiх нижеследующих кванторних выражениях область дiї квантора пiдкреслено.

$ X 3| X 6| X, $ X 3| X6| X, X X29 X3, X X29 X3.

Первый и второй выражения, а также третий и четвертый отличаются не только областью действия квантора. Отличие между ними является существеннее, о чем следует сказать отдельно.

Рассмотрим на унiверсальнiй множинi R всiх дiйсних чисел два выражения X210 i $ X X210. Первый из них является предикатом, который зависит вiд змiнної X. Замiсть X у него можно пiдставляти рiзнi дiйснi значения i получать певнi высказывание iстиннi или хибнi. Та же предметная змiнна X входит во второе выражение iнакше. Если замiсть ее пiдставити любое дiйсне значение, дiстанемо беззмiстовний выражение.

Пусть P X - некоторый предикат на M. Перех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я не является исключением и достаточно часто встречается в других разделах математики. Например, в выражениях F X Dx, X2 i Dj параметры A, B, C, K i N - являются переменными, вместо которых можно пiдставляти певнi значения, а параметры X i J - это зв' язанi зм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льки тех B M, для которых одномiсний предикат A X, B есть iстинним для всiх X из M.

Пример 5.6. Рассмотрим двомiсний предикат A X, Y, определенный на множинi M={ A1, A2, A3, A4} с помощью таблицi 5.5.

Таблица 5.5.

X \ Y

A1

A2

A3

A4

0

1

Таблицi iстинностi для четырех вiдповiдних одномiсних предикатiв, что получаются из A X, Y путем навiшування одного квантора, наведенi в таблицi 5.6.

Таблица 5.6.

Y

XA X, Y

$ XA X, Y

X

YA X,, Y

$ YA X, Y

Во вс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 является существенным.