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

Будем считать, что нульместная предикатная буква тоже является элемен­ тарной формулой (атомом). 0 2 / / 3 2 Примеры элементарных формул: Aj, Aj (xi,ai), Ai(fi (x)), A2(x,y,fi (a,x)). Формулы логики предикатов определяются следующим образом: а) всякая элементарная формула есть формула; б) если Л и в - формулыи х - предметная переменная, то каждое из выра­ жений (^А), (А^В), (VxA) и (ЗхА) есть формула; в) выражение является формулой только в том случае, если это следует из правил а) и б). В выражениях (VxA) и (ВхА) формула Л называется областью действия кванторов УхжВх соответственно. Примеры формул: (A^j^Aj (х,а)), (VxAj(x,f}(f}(x)))), (Vx(BxA\(a))). Придерживаясь БПФ приведенные определения терма и формулы можно записать в следующих видах. терм := х для любого хш V терм := а для любого аш А формула := элементарная формула \ {—^формула) \ {формула формула) формула := ( Ухформула) \ {Зхформула) для любого х из V Если Л и в - формулы, то договоримся, что А&В является сокращенной записью формулы (^(А ^(—В))), AwB является сокращенной записью формулы ((—А)^В), А=В - сокращенная запись для формулы (^((А^В)^ ( —i(B^A)))). Будем придерживаться тех же правил опускания скобок, которые приня­ ты в § 2 главы 1, введя дополнительно, что кванторы Vx, Зх располагаются по силе между связками связками ^,=. Например, вместо ff\/5cAJ^BJ пи­ шем \/^А^В. Договоримся также опускать скобки, в которые заключается формула А в формулах вида (Qi(Q(A))), где Qi ^ Q - любые кванторы. Например, вместо (Vx(Vy(^(Aj (x,y,z))))) пишем \/5с Vy^Aj (x,y,z). Вхождение переменной х в данную формулу называется связанным, если X является переменной входящих в эту формулу кванторов Зх или х нахо­ дится в области действия входящих в эту формулу кванторов Зс; в против­ ном случае вхождение переменной х в данную формулу называется свободным. 2 2 Например, вхождение переменной х в формулу VyAi (х,у)^А2 (у,у) является свободным, первое и второе вхождения переменной у - связанными, а третье и четвертое вхождения у в эту формулу - свободными. Таким образом, одна и та 34