Терм, формула, свободные и связанные переменные. Логика предикатов

Рассмотрим следующие алфавиты:

1. s ₁ = (x,y,z,...,x_i , y _i , z _i, ...) - символы предметных переменных;

2. s ₂ = (a,b,c,...,a_i , b _i , c _i, ...) - символы предметных констант;

3. s ₃ = (f,g,h,...,f_i , g _i ,h _i, ...) - символы функциональных переменных;

4. s ₄ = (P,Q,R,...,P_i , Q _i ,R _i, ...) - символы предикатных переменных;

5. s ₅ = ( & , Ú , ® , Ø , ... ) - символы логических связок;

6. s ₆ = ( ",$ ) - кванторы;

7. s ₇ = (“(“,”)”) - скобки.

Определение. Множество символов s = s₁ Ès₂ Ès₃ Ès₄ называется сигнатурой.

Допустим, зафиксирована некоторая сигнатура s. Прежде, чем вводить понятие формулы, необходимо дать понятие терма.

Определение. Термом сигнатуры s является :

1)всякая предметная постоянная и константа,

2) если t₁ , ..., t_k - термы, а f - функциональная переменная, то f ( t₁ , ..., t_k ) - терм.

Терм является обобщением переменной и константы, в котором могут присутствовать функциональные перемен-ные, но нет логических функций - предикатов.

Определение. Формулу сигнатуры s введем следую-щим образом:

1. Если (t₁ , ..., t_k) - термы, (х₁ , ..., х_m) - множество переменных, входящих в них, а Р- предикатная переменная, то Р( t₁ , ..., t_k ) - назовем элементарной формулой или атомом, а (х₁ , ..., х_m ) - его свободными переменными.

2. Если А и В - формулы, то выражения вида F =А Ú В, F = А &В, F = А ®В, F =Ø А тоже являются формулами. Свободные переменные формул А и В являются свободными переменными формулы F.

3.Если А - формула со свободными переменными (х₁,...,х_m ), то выражения вида F =" х_i А(х₁ , ..., х_m ), F =$ х_i А(х₁ , ..., х_m ) - тоже являются формулами, в которых переменная х_i связана, соответственно, кванторами " и $ , а

переменные (х₁ , ..., х_m ) \ х_i -свободны в F.

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

Определение. Формула называется замкнутой, если все вхождения в неё переменных связаны.

Замечание. Одна и та же переменная может быть од-новременно свободной и связанной в одной формуле. На-пример, переменная х в формуле А(х,у)®"хВ(х,у).

Определение. Терм t свободен для переменной х_i в формуле А, если никакое свободное вхождение х_i в А не лежит в области действия никакого квантора "х_j, где х_j - переменная, входящая в t .

Примеры.

1. Терм х_j свободен для х_i в формуле Р(х_i ), но не свободен

для х_i в формуле А= "х_j Р(х_i ).

2. Терм f (x,y) свободен для х в формуле А ="у Р(x,y) ® Q(х), но не свободен в формуле B=$z"х Р(x,y)®Q(х).

Логикой предикатов (ЛП) называется расширение алгебры логики, в котором

1) логические функции (предикаты) введены на произволь-ных предметных множествах,

2) введены кванторы по переменным,

3) наряду с логическими введены и предметные функции на предметной области,

4) дано понятие формулы, учитывающее 1)-3).

Соответственно, формулы алгебры логики являются частным случаем формул ЛП.