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

вить. Например, вместо А^^(х,у) будем писать А](х,у) и, если нет дру­ гих двухаргументных (двуместных) предикатных букв А, вместо Ai(x,y) будем писать просто кроме того иногда будем использо­ вать буквы Р, Q, R, S для обозначения предикатных букв А" . Определение терма: а) всякая предметная постоянная или предметная переменная есть терм; б) если //' - функциональная буква и - термы, то f,"{luh,-..tn) есть терм; в) выражение является термом только в том случае, если это следует из правил а) и б). Примеры термов: а, х,, fi{x,d), (а, f\ О)). Предикатные буквы, примененные к термам, порождают элементарные формулы или точнее: если - предикатная буква, а 1хЛъ --Лп — термы, то А" - элементарная формула. Будем считать, что нульместная предикатная буква тоже является элементарной формулой. Примеры элементарных формул: А°, А^ (Х],А)), AL(//(X)), А2 (х,у, (а,х)). Формулы логики предикатов определяются следующим образом: а) всякая элементарная формула есть формула; б) если Л W В - формулыи х - предметная переменная, то каждое из выражений ("U), ( у4=>В ), (УХА) и (Зх/4) есть формула; в) выражение является формулой только в том случае, если это следует из правил а) и б). В выражениях (Vx4) и (Зх/1) формула А называется областью действия кванторов Vx и Зх соответственно. 54