Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

же переменная в одной и той же формуле может иметь как связанные, так и свободные вхождения. Переменная называется свободной {связанной) переменной в данной фор­ муле, если существуют свободные (связанные) ее вхождения в эту формулу. Формула называется замкнутой, если она не содержит никаких свобод­ ных переменных, т.е. либо все ее переменные связанные, либо переменных нет совсем. Замкнутую формулу называют предложением. Например, формула 2 2 2 Vx{VyAj (х,у)^А2 (х,х)) - замкнутая, т.е. предложение, а формула VxAj (х,у) - незамкнутая, ибо содержит свободную переменную у. Замыканием формулы А называется формула, полученная из А приписы­ ванием перед нею кванторов всеобщности по всем ее свободным переменным, при этом кванторы приписываются следующим образом: сначала записываем кванторы общности по всем свободным переменным х (если они есть) в поряд­ ке возрастания их индексов, затем по свободным переменным у (если они есть) в порядке возрастания их индексов и т.д. Так, замыканием формулы A j (х^ ,xj ,У2) будет формула: \/Х] \/Хз \/y2Aj (Хз,Х],У2), 3 2 а замыканием для формулы VyiBxsAi (х1,у1,Хз)^A j (хз,х2) будет формула: \/Х] \/Х2 \/Хз(\/у]ЗСзА2 (Х],у],Хз)^А2 (Хз,Х2)). в формуле VxA(x)^ В(х) вхождение х в AfxJ является связанным, а вхож­ дение X в BfxJ - свободным вхождением. Замыканием этой формулы будет Vx(VxA(x)^ В(х)). Для того чтобы не перепутать области действия кванторов, было бы удобнее записывать разные переменные, но это мы сделаем в даль­ нейшем. Отметим, что таким же образом поступают и в программировании, на­ пример, в языке Паскаль можно записать следующую программу [38]. program Main; var X: Integer; procedure A; var X: Integer; begin X:=l; writeln(X) end; procedure begin writeln(X) end; X:=5;A; В begin end. 35