Алгебра логики предикатов.

Алгебра логики предикатов (алгебра кванторной логики, алгебра неоднородных логических функций) – раздел математической логики, изучающий операции над высказываниями субъектно-предикатной структуры, то есть _n=F_n, U, Л²U, Л, , , где F_n- множество предикатных формул вида Рⁿ(х₁, х₂…х_n)

с нелогическими переменными х_i (выражение Рⁿ(х₁, х₂…х_n) понимается, как переменная, высказывание, истинность которого определяется подстановкой предметных констант вместо предметных переменных.

Выражение отношений посредством многоместных предикатов.

Неоднородная логическая функция Рⁿ(х₁, х₂…х_n): МⁿВ есть n-местный предикат, где Рⁿ n-местная предикаторная константа, М универсум (область) рассмотрения предикатов, В=U, Л - двоичное множество истинных значений высказывания.

Пояснения:

1. Выражение Рⁿ(а₁, а₂…а_n), где а₁, а₂…а_n М являются предметными константами, есть высказывание, а выражение Рⁿ(х₁, х₂…х_n) есть логическая (двоичная) переменная (при этом х₁, х₂…х_n – нелогические переменные).

2. Поскольку предикаты могут принимать два значения (интерпретируются как переменные высказывания), то из них можно образовывать сложные формулы логики высказываний (сам предикат Рⁿ(х₁, х₂…х_n), являющийся элементарной формулой, рассматривается в сложной формуле как логическая переменная).

Утверждения:

1. Всякий предикат Рⁿ(х₁, х₂…х_n) определяет отношение R Мⁿ такое, что а₁, а₂…а_nR, если и только если Рⁿ(а₁, а₂…а_n)=U. При этом R задает область истинности предиката Рⁿ(х₁, х₂…х_n) .

2. Каждому n-местному отношению R Мⁿ соответствует предикат Рⁿ(х₁, х₂…х_n) такой, что Рⁿ(а₁, а₂…а_n)=U, если и только если а₁, а₂…а_nR.

Эти утверждения можно проиллюстрировать графически бинарным функциональным соответствием q= Мⁿ, B, P, с помощью которого возникает высказывание , если в качестве значений х_i ( i = 1…n)

B=J_mP

Dom P

Область истинности предикатов R_u Мⁿ

Мⁿ

u

л

Говорят, что предикат является выполнимым, если R_u  и R_u Мⁿ (т.е. предикат выполняется хотя бы для одного набора значений аргументов, само соответствие сюрьективно). В том случае, если область истинности предиката Pⁿ(x₁, x₂,…, x_n) пуста, т.е. R_u , то говорят, что предикат является тождественно-ложным (невыполнимым), а в случае R_u Мⁿ=Dom P предикат является тождественно-истинным (общезначимым) – он выполняется для всех наборов аргументов (такой предикат выражает закон логики)

1. Пример. Для двухместного предиката Р²(х₁, х₂), где Р² – быть братом на множестве детей М₁ = {a,в,c} (где а - Алла, в – Володя, с – Сергей) область определения Dom Р²(х₁, х₂) выполняемого предиката, есть область истинности:

R_u ={<в, а>, <в,c >, <c, в>, <c, a >} М² ;

2. М₂ = {a,в,c} (где а – Алла, в – Вера, с - - Светлана) имеем невыполнимый предикат, т.е. Dom Р²(х₁, х₂)= R_u =

3. М₂ = {a,в,c} (где а – Андрей, в – Володя, с – Сергей) имеем тождественно-истинный предикат (закон), для которого R_u ={<а, в>, <a, c >, <в, а >, <в,c >, <c, a >,<c, в>}

Утверждение 3. Всякой алгебраической операции f: Мⁿ M можно поставить в соответствие (n+1)-местный предикат такой, что Pⁿ⁺¹(x₁, x₂,…, x_n+1) истинен, если и только если fⁿ(a₁, a₂,…, a_n)= а_n+1

Однако обратное соответствие, т.е. от (n+1)-местного предиката к n-местной функции возможно не всегда, а только при условии, чтобы для любого а¹_n+1а_n+1 Pⁿ⁺¹(а₁, а₂,…, а¹_n+1 )=  (т.е. предикат был бы ложным).

семьи М, то в случае: