Исчисление предикатов

Средства, предоставляемые логикой высказываний, ока­зываются недостаточными для анализа многих математи­ческих рассуждений. Например, средствами логики выска­зываний нельзя установить правильность такого рассужде­ния: «Всякое целое число является рациональным числом; 25 —целое число, следовательно, 25 —рациональное число». Это объясняется тем, что в логике высказываний простые высказывания, из которых с помощью логических опера­ций строятся сложные, рассматриваются как нерасчленяемые. Поэтому возникает необхо­димость в построении такой логической системы, средст­вами которой можно исследовать строение тех высказываний, которые в логике высказываний рассматриваются как элементарные. Такой логической системой является ло­гика предикатов, содержащая как часть логику вы­сказываний.

Вматематике широко исполь­зуются буквенные обозначения. Различные буквы могут обозначать как один и тот же объект, так и различные объекты. Используемые таким образом буквы называются свободными переменными.

Допустимыми значениямисвободной переменной назы­ваются те объекты определенного вида, для обозначения которых употребляется эта переменная. Так, допустимыми значениями свободной переменной могут быть высказывания.

Рассмотрим предложение

1) х+у = 3, содержащее натуральные переменные хну. Это предложение не является высказыванием, так как о нем нельзя сказать, истинно оно или ложно. Оно называется предикатомили условием(на х и у). Приведем другие примеры предложений с переменными:

2) х есть простое число;

3) х есть четное число;

4) х меньше у;

5) х есть общий делитель у, z.

Будем считать, что допустимыми значениями перемен­ных х, у и z являются натуральные числа. Если в пред­ложениях 1)—5) заменить переменные их допустимыми значениями, то получатся высказывания, которые могут быть как истинными, так и ложными. Например,

0 + 1=3;

2 есть простое число;

3 есть четное число;

5 меньше 7;

3 есть общий делитель 6 и 12.

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

Предложения 1)—5) могут служить примерами пре­дикатов.

По числу входящих свободных переменных различают предикаты одноместные, двухместные, трехместныеи т. д. Предикаты 2) и 3) — одноместные, предикаты 1) и 4) — двухместные, предикат 5) — трехместный. Высказывания будем считать нульместными предикатами.

Заменяя в одноместном предикате {2) переменную на­туральными числами, будем получать высказывания:

0 есть простое число;

1 есть простое число;

2 есть простое число;

3 есть простое число и т. д.

Некоторые из них являются истинными. Таким образом, данный одноместный предикат выделяет среди натуральных чисел те, при подстановке которых вместо переменной по­лучается истинное высказывание, и его можно рассматри­вать как условие на значения свободной переменной, вхо­дящей в предикат. В данном случае числа, удовлетворяю­щие этому условию, — простые.

Одноместный предикат можно рассматривать как усло­вие на объекты данного вида; двухместный — как условие на пары объектов данного вида и т. д.

Предикаты можно задавать различными способами. В алгебре часто рассматривают предикаты, заданные с по­мощью уравнений, неравенств, а также систем уравнений или неравенств. Например, неравенство х + х^-1>0задает одноместный предикат, уравнение х²+у = 0 — двухместный, а система уравнений х + у = 0, х — у + z = 0 — трехместный (х, у, z— рациональные переменные).

Обозначать предикаты будем большими буквами латин­ского алфавита (возможно, с нижними индексами) с указа­нием в скобках всех свободных переменных, входящих в этот предикат. Например, А (х,y) —обозначение двухместного предиката, R(х, у, z) — трехместного и Q(х₁ ..., х_п) — обозначение n-местного предиката.

В дальнейшем мы будем говорить об истинностном значении произвольного предиката на том или ином наборе входящих в него свободных переменных, понимая под этим истинностное значение высказывания, которое получается в результате замены свободных переменных соответствующими им значениями из рассматриваемого набора.

Высказывание, которое получается при подстановке в предикат R(x₁ ..., х_п) набора допустимых значений (a₁ ..., а_п) вместо его переменных, будем обозначать R(a₁ ..., а_п). Если это высказывание истинное (ложное), говорят, что набор значений (a₁ ..., а_п) удовлетворяет (не удовлетворяет) предикату R(x₁ ..., х_п).

Отметим, что следует различать предикаты, выражаю­щие одно и то же условие, но имеющие переменные с раз­личными допустимыми значениями. Например, предикат, заданный уравнением 2х — 3 = 0, где х — целочисленная пе­ременная, следует отличать от предиката, заданного тем же уравнением, если при этом х рассматривается как ра­циональная переменная. Первый предикат не принимает значений «истина» ни при каких допустимых значениях х> а вто­рой принимает значение «истина» при допустимом значении пере­менной х=³/₂- Таким образом, при задании предиката нужно указывать область допустимых значений переменных этого предиката.

Предикаты, как и выска­зывания, принимают значения 1 и 0, поэтому над ними можно производить логические операции, аналогичные опе­рациям логики высказываний.

Начнем с простого частного случая — одноместных пре­дикатов, у которых области допустимых значений перемен­ных совпадают. Образуем из двух предикатов Р (х) и Q (у) новый предикат Р(х) /\Q(y). Это предикат от двух сво­бодных переменных х и у, и истинностное значение его на любом наборе (а, b) допустимых значений переменных опре­деляется как истинностное значение высказывания Р(а)/\Р(b). Аналогично определяются предикаты

Следует различать предикаты: двухместный P(x)/\Q(y) и одноместный P(x)/\Q(x); в первый допустимые значения подставляют вместо свободных переменных х и у незави­симо друг от друга, а во второй — вместо единственной свободной переменной х.

Над многоместными предикатами аналогично опреде­ляются операции: конъюнкция, дизъюнкция, отрицание, импликация и эквиваленция. Рассмотрим, например, слу­чай двухместных предикатов. Пусть Р(х,у), Q(y, z) — два предиката, у которых совпадают области допустимых зна­чений переменных. Тогда Р(х,y)/\Q(y,z) есть трехмест­ный предикат от х, у, z, истинностное значение которого на любом наборе (a, b, с) допустимых значений свободных переменных определяется как значение высказывания P(a_t b)/\Q(b> с). Заметим, что при рассмотрении операций над предикатами нужно следить, какие переменные обозначены различными буквами, а какие —одинаковыми.

Рассмотрим еще несколько примеров:

Предикат A(x)VB(x, у) принимает значение 1 на на­боре значений (a, b), если хотя бы одно из высказываний А (а) и В (а, b) будет истинно, и принимает значение 0, если оба эти высказывания ложны. Аналогично можно установить истинностные значения остальных предикатов на том или ином наборе значений свободных переменных.

Логическое следствие. Равносильные предикаты.

Предикат А(х₁, ..., х_п) называется тождественно истинным, если для любого набора допустимых значений входящих в него свободных переменных его истинностным значением является 1.

Примером тождественно истинного предиката может служить трехместный предикат, заданный неравенством (x + y)²+Z²≥0 где х, у, z — рациональные переменные.

Пусть A (х₁,..., х_т) и В (y₁ ,..., у_п) — предикаты, имею­щие одинаковые области допустимых значений свободных переменных.

Предикат В(у₁ ,..., у_п) называется логическим следствием предиката А (х₁,..., х_т), если пре­дикат А(х₁,..., х_т)→В (у₁ ,..., у_п) является тождественно истинным.

Запись А(х₁ ,.., x_m)|=B(y_l ,..., у_п) означает, что предикат В(у₁,..., у_п) есть логическое следствие предиката А(х₁ ,.., x_m).

Например, если х — целочисленная переменная, R (х) — обозначение предиката «х — четное число», Р (х) — обозна­чение предиката «х кратно 4», то R(x) логически следует из Р(х), т. е. P(x)|=R(x). Здесь предикат Р(х) не сле­дует логически из предиката R(x).

Предикат B(z_l, ..., z_n) называется логическим следствиемпредикатов А₁(х₁ ,..., х_т),…, A_k(y₁,..., y_l) если предикат

А₁(х₁ ,..., х_т)/\... /\ A_k(y₁ ,..., y_l)→ B(z_l, ..., z_n)

является тождественно истинным. (При этом предпола­гается, что все свободные переменные рассматриваемых предикатов имеют одни и те же допустимые значения.) Пример. Пусть P(х) — предикат «x— четное число», Q (х) — предикат «х кратно трем», R (х) — предикат «х кратно шести». Тогда Р(х) /\Q(x)|=R(x).

Предикаты A(x_l,..., х_т) и В(y₁,…,y_п) называются равносильными (логически экви­валентными), если предикат A(x_l,..., х_т) ↔В(y₁,…,y_п) является тождественно истинным. Запись А(х₁,..., х_т) ≡ В(y₁,…,y_п)означает, что предикаты A(x_l,..., х_т) и В(y₁,…,y_п) равносильны.

Легко видеть, что предикаты A(x_l,..., х_n) и В(y₁,…,y_п) равносильны тогда и только тогда, когда A(x_l,...,х_т) |=B(y₁,…,y_п) и B(y₁,…,y_п) |= A(x_l,...,х_т)

Нетрудно доказать, что предикаты A(x_l,..., х_т) и В(x_l,..., х_n) равносильны тогда и только тогда, когда их истинностные значения совпадают на любом наборе допу­стимых значений переменных х₁₉ ..., х_п. Примером равно­сильных предикатов могут служить предикаты, заданные уравнениями х³ — у³=0 и 2(x— у)(х²+ ху+y²)=0, где х, у—рациональные переменные.

Предикат А(х₁,..., х_п) называется тождественно ложным, если его истинностным значением является 0 для любого набора допустимых значений вхо­дящих в него свободных переменных. Например, тождественно ложным является предикат х+1=х, где x— целочисленная переменная.

Предикат А(х₁,..., х_п) называется выполнимым, если существует хотя бы один набор допу­стимых значений входящих в него свободных переменных, на котором его истинностным значением является 1. Например, выполнимыми являются предикаты «а —про­стое число», «x делится на у».

Из данных определений вытекает, что тождественно ис­тинный предикат логически следует из любого предиката, а из тождественно ложного предиката логически следует любой предикат.

Любой предикат либо тождественно истинен, либо вы­полним, либо тождественно ложен.