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

Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

  Определение 1.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат, который принимает значение “истина” при тех и только тех значениях, при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение.

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 2.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат, который принимает значение “ложь” при тех и только тех значениях, при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Определение 3.

Отрицанием предиката P(x) называется новый предикат, который принимает значение “истина” при всех значениях, при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях, при которых предикат P(x) принимает значение “истина”.

Очевидно, что, т.е. множество истинности предиката является дополнением к множеству I_P.

Определение 4.

Импликацией предикатов P(x) и Q(x) называется новый предикат, который является ложным при тех и только тех значениях, при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном справедлива равносильность, то.

Определение 5.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат, который обращается в “истину” при всех тех и только тех, при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

 

Классификация предикатов

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

Определение 2.

Предикат Р(х), определенный на множестве М, называется  тождественно истинным, если его множество истинности совпадает с областью определения, т. е. I_p=M.

Определение 3.

Предикат Р(х), определенный на множестве М, называется тождественно ложным, если его множество истинности является пустым множеством, т. е. I_p=0.

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношения между предметами.

Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение “меньше ”. Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой “х<y”, где, то–есть является функцией двух переменных Р(х,y), определенной на множестве упорядоченных пар целых чисел ZхZ=Z² c множеством значений {1;0}.

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

Операции связывания переменных кванторами.

1.1 Квантор всеобщности.

Пусть Р(х) – предикат, определенный на множестве М. Под выражением понимают высказывание, истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.

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

1.2 Квантор существования.

Пусть P(x) - предикат определенный на множестве М. Под выражением понимают высказывание, которое является истинным, если существует элемент, для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат (или одноместный предикат), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:

Рассмотрим предикат P(x) определенный на множестве M={a₁,…,a_n}, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a₁),P(a₂),…,P(a_n). При этом истинными будут высказывания и конъюнкция.

Если же хотя бы для одного элемента P(a_k)окажется ложным, то ложными будут высказывание и конъюнкция. Следовательно, справедлива равносильность