Логические и кванторные операции над предикатами

1)Логические

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

Из этого определения следует, что множеством истинности предиката является разность множеств и , где − множество истинности предиката , что записывается так: . Конъюнкцией двух предикатов и называется новый предикат , который принимает значение “истина” при тех значениях , при которых оба эти предиката принимают значение “истина” и принимают значение “ложь” во всех остальных случаях.

Множеством истинности предиката является общая часть множеств истинности предикатов и , т.е. пересечение . Так, например, для предикатов − “ − четное число ” и − “ − кратно 5”, определенных на , конъюнкцией является предикат “ −четное число и −кратно 5”. Так как I_P = {2,4,6,8,10,12,14,16,18,20,…}, , то множество истинности .

Дизъюнкцией двух предикатов и называется новый предикат , который принимает значение “ложь” при тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.Очевидно, что множеством истинности предиката является объединение множеств истинности предикатов и , т.е. . Так, для тех же предикатов, что и в выше приведенном примере, их дизъюнкцией будет предикат “ −четное число или кратно 5”, множество истинности которого есть Импликацией предикатов и называется новый предикат , который является ложным при тех значениях , при которых предикат принимает значение “истина”, а предикат − значение “ложь” и принимает значение “истина” во всех остальных случаях. Множество истинности этой импликации определяется из следующих рассуждений: следовательно .

Так, для предикатов − “ кратно 4” и − “ – четное число”, определенных на , импликацией является предикат словесная формулировка которого будет: “если кратно 4, то – четное число. Так как , ,то т.е. все натуральные числа.

2)Кванторные

Таких операций две. Они имеют собственное название и символически обозначаются с помощью так называемых кванторов (от лат. quantum − сколько) всеобщности и существования. Квантор всеобщности обозначается символом −перевернутая первая буква английского All − все, а квантор существования обозначается символом − перевернутая первая буква английского слова Exist − существует.

Квантор всеобщности. Пусть ─ предикат, определенный на множестве . Под выражением понимают высказывание, которое является истинным, когда предикат истинен для всех элементов ,и ложным в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение будет “для всякого истинно” или “для всех x истинно”.

Переменную x в предикате называют свободной (ей можно придавать различные значения из множества M), в высказывании переменная x уже является связанной квантором . Квантор существования. Пусть ─ предикат, определенный на множестве M. Под выражением понимают высказывание, которое является истинным, если существует элемент , для которого предикат истинен, и ложным в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение читается так: “существует , при котором истинно”.

В предикате переменная x является свободной, а в высказывании она уже связана квантором .