Математическая логика и теория алгоритмов
|
       Чтобы
наглядно показать чем отличаются термы и формулы, рассмотрим
следующий пример.
       Пусть
имеется предикат
на множестве натуральных чисел N .
Определим две функции
и
следующим образом:
       
       
       Функция f (x, y)
определяет истинностное значение предиката при определенных значениях
предметных переменных x и y .
Значение функции g (x, y)
принадлежит той де предметной области, что и предметные переменные x и y. Для записи функций типа
функции f (x, y)
используются формулы, а для записи функций типа функции g (x, y)
– термы.
       Дадим
точные определения формулы и терма в исчислении предикатов. Сначала
определим алфавит формул и термов. В алфавит входят:
- Предметные переменные
;
- Функциональные переменные
– арность (местность);
- Предикатные переменные
– арность (местность);
- Логические символы
(дополнительные
);
- Служебные символы (,).
       Последовательность символов в исчислении
предикатов называется термом, если она удовлетворяет
следующему определению:
- любая предметная переменная, любая нульарная функциональная переменная является термом;
- если
– термы, то 
–терм;
- других термов нет.
Пример. Выражение
является термом, а выражение
не является термом.
       Придадим
теперь функциональным символам следующие значения:
- умножение двух чисел,
- возведение в степень,
– сложение двух чисел.
       Тогда терм выглядит так:
.
Полагая
, получаем, что терм равен 9. Таким образом, если заданы значения всех
функциональных и предметных переменных, входящих в терм, то чтобы
получить значение терма следует выполнить все операции сопоставленные
переменным.
       Дадим
теперь определение формулы исчисления предикатов. Последовательность
символов в исчислении предикатов называется формулой, если она
удовлетворяет следующему определению:
- Каждый предикатный символ арности нуль является формулой;
- Eсли
– n-арный предикатный символ и
– термы, то
– формула. Все входящие в эту формулу предметные переменные – свободные;
- Eсли
– формулы, то
- формулы. Свободные вхождения переменных в
остаются свободными в формулах
;
- Если переменная x – свободная в F , то
– формула. Вхождения других переменных (отличных от x ) остаются свободными в формуле
;
- других формул нет.
       Одна и та
же переменная может иметь в одной и той же формуле как свободные, так
и связанные вхождения. Формула, не содержащая свободных вхождений
переменных, называется замкнутой. Квантор существования
вводится определением
.