Математическая логика и теория алгоритмов

Примеры формул: (=> (х,а)), (Vx А^^ (х,//(//(х)))), (Vx(3xAl(a))). Если А и В - формулы, то договоримся, что А&В является сокращенной записью формулы (1 (А =5'(1 В))), AvB - сокращенной записью формулы (("U)=>.8), А=В - сокращенной записью формулы (1(В=>Л)))). Будем придерживаться тех же правил опускания скобок, которые приняты в §3 гл. 1, введя дополнительно, что кванторы Vx, Зх располагаются по силе между связками 1, &, v и связками =>, =. Например, вместо ((Vx/4)=>5) пишем Договоримся та1сже опускать скобки, в которые заключа­ ется формула А в формулах вида {Q\{QiA))), где Qi VL Q — любые кванторы. Например, вместо (Ух(\/Х3г( (х,^,^))))) пишем VxV3;3z А^ {x,y,z). Вхождение переменной х в данную формулу называется связан­ ным, если X является переменной входящих в эту формулу кванторов Vx, Зх или находится в области действия входящих в эту формулу кванторов Vx, Зх; в противном случае вхождение переменной х в дан­ ную формулу называется свободным. Например, вхождение перемен­ ной X в формулу \/yAf(x,y)=>Al(y,y) является свободным, первое и второе вхождение переменной - связанным, а третье и четвертое вхождение у в эту формулу - свободным. Таким образом, одна и та же переменная в одной и той же фор­ муле может иметь как связанные, так и свободные вхождения. Переменная называется свободной (связанной) переменной в данной формуле, если существуют свободные (связанные) ее вхолс- дения в эту формулу. Формула называется замкнутой, если она не содержит никаких свободных переменных, т.е. либо все ее переменные связанные, либо переменных нет совсем. Например, формула Vx(Vy Af (xj')=> (x^)) - замкнутая, a формула Vx Af {x,y) - незамкнутая, ибо содержит свобод­ ную переменную у. 55