Операции над предикатами.

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

Начнем с простого частного случая — одноместных предикатов, у которых области допустимых значений переменных совпадают. Образуем из двух предикатов новый предикат . Это предикат от двух свободных переменных х и у, и истинностное значение его на любом наборе допустимых значений переменных определяется как истинностное значение высказывания Аналогично определяются предикаты

Следует различать предикаты: двухместный и одноместный в первый допустимые значения подставляют вместо свободных переменных х и у независимо друг от друга, а во второй — вместо единственной свободной переменной

Над многоместными предикатами аналогично определяются операции: конъюнкция, дизъюнкция, отрицание, импликация и эквиваленция. Рассмотрим, например, случай двухместных предикатов. Пусть — два предиката, у которых совпадают области допустимых значений переменных. Тогда есть трехместный предикат от , истинностное значение которого на любом наборе допустимых значений свободных переменных определяется как значение высказывания . Заметим, что при рассмотрении операций над предикатами нужно следить, какие переменные обозначены различными буквами, а какие — одинаковыми.

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

Предикат принимает значение И на наборе значений , если хотя бы одно из высказываний будет истинно, и принимает значение Л, если оба эти высказывания ложны. Аналогично можно установить истинностные значения остальных предикатов на том или ином наборе значений свободных переменных.

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

ОПРЕДЕЛЕНИЕ. Предикат называется тождественно истинным, если для любого набора допустимых значений входящих в него свободных переменных его истинностным значением является И.

Примером тождественно истинного предиката может служить трехместный предикат, заданный неравенством где х, у, z — рациональные переменные.

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

ОПРЕДЕЛЕНИЕ. Предикат называется логическим следствием предиката если предикат является тождественно истинным.

Запись означает, что предикат есть логическое следствие предиката

Например, если — целочисленная переменная, обозначение предиката — четное число», — обозначение предиката кратно 4», то логически следует из Здесь предикат не следует логически из предиката

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

Доказательство этого утверждения предоставляется читателю.

ОПРЕДЕЛЕНИЕ. Предикат называется логическим следствием предикатов если предикат

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

Пример. Пусть — предикат — четное число», — предикат кратно трем», — предикат кратно шести». Тогда

ОПРЕДЕЛЕНИЕ. Предикаты называются равносильными (логически эквивалентными), если предикат является тождественно истинным.

Запись означает, что предикаты равносильны.

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

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

ОПРЕДЕЛЕНИЕ. Предикат называется тождественно ложным, если его истинностным значением является Л для любого набора допустимых значений входящих в него свободных переменных.

Например, тождественно ложным является предикат где целочисленная переменная.

ОПРЕДЕЛЕНИЕ. Предикат называется выполнимым у если существует хотя бы один набор допустимых значений входящих в него свободных переменных, на котором его истинностным значением является И.

Например, выполнимыми являются предикаты простое число», делится на у», где — целочисленная переменная.

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

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