Связанное и свободное вхождение

Переменная x имеет связанное вхождение в формулу j, если существует подформула y формулы j такое что, вхождение имеет вид

(($x)y) или (("x)y)

Пример. Пусть имеется формула j: ("x)($y)[P(x)ÚQ(x,y) ® ØR(x)]

и подформула y: ($y)[P(x)ÚQ(x,y) ® ØR(x)]

Вопрос: Как x входит в формулу j и в подформулу y ?

Основной терм – это терм, в который не входит ни одна переменная.

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

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

Подстановка – это множество пар вида

q={x₁/t₁, … , x_n/t_n}

где x_i – переменные, t_i – термы, причем равенство x_i= x_j влечет равенство t_i= t_j

Если j - атом, терм или формула, то jq - выражение, полученное в результате подстановки в j на места свободных вхождений переменных x_i соответствующих термов t_i.

Пример. Рассмотрим формулу

j(x,y,z): ($y)R(x,y) Ù ("z)(ØQ(x,z))

и подстановку q={x/f(a,b)}, где f(a,b) – основной терм. Выполнив подстановку в формулу, получим предложение

j(f(a,b),y,z): ($y)R(f(a,b),y) Ù ("z)(ØQ(f(a,b),z))

Множества формул как варианты

Пусть S={ c₁, … , c_n } – множество формул PrL, q - некоторая подстановка, тогда результатом подстановки q в S является множество формул

Sq={ c₁q, … , c_nq }

Множества формул S₁ и S₂ называются вариантами, если существуют подстановки q и y такие что

S₁= S₂q и S₂= S₁y

Пример. Являются ли следующие множества формул вариантами?

S₁={P(f(x,y)), Q(h(z),b)} и S₂={P(f(y,x)), Q(h(u),b)}

S₁= S₂q q={y/x, x/y, u/z}

S₂= S₁y y={x/y, y/x, z/u}