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

1.10 Термы и формулы в исчислении предикатов

назад | оглавление | вперёд

 

       Чтобы наглядно показать чем отличаются термы и формулы, рассмотрим следующий пример.
       Пусть имеется предикат на множестве натуральных чисел N . Определим две функции и следующим образом:
       
       

       Функция f (x, y) определяет истинностное значение предиката при определенных значениях предметных переменных x и y . Значение функции g (x, y) принадлежит той де предметной области, что и предметные переменные x и y. Для записи функций типа функции f (x, y) используются формулы, а для записи функций типа функции g (x, y)термы.

       Дадим точные определения формулы и терма в исчислении предикатов. Сначала определим алфавит формул и термов. В алфавит входят:

  1. Предметные переменные ;
  2. Функциональные переменные – арность (местность);
  3. Предикатные переменные – арность (местность);
  4. Логические символы (дополнительные );
  5. Служебные символы (,).
       Последовательность символов в исчислении предикатов называется термом, если она удовлетворяет следующему определению:
  1. любая предметная переменная, любая нульарная функциональная переменная является термом;
  2. если – термы, то –терм;
  3. других термов нет.
Пример. Выражение является термом, а выражение не является термом.
       Придадим теперь функциональным символам следующие значения:        Тогда терм выглядит так: . Полагая , получаем, что терм равен 9. Таким образом, если заданы значения всех функциональных и предметных переменных, входящих в терм, то чтобы получить значение терма следует выполнить все операции сопоставленные переменным.

       Дадим теперь определение формулы исчисления предикатов. Последовательность символов в исчислении предикатов называется формулой, если она удовлетворяет следующему определению:

  1. Каждый предикатный символ арности нуль является формулой;
  2. Eсли n-арный предикатный символ и – термы, то – формула. Все входящие в эту формулу предметные переменные – свободные;
  3. Eсли – формулы, то - формулы. Свободные вхождения переменных в остаются свободными в формулах ;
  4. Если переменная x – свободная в F , то – формула. Вхождения других переменных (отличных от x ) остаются свободными в формуле ;
  5. других формул нет.
       Одна и та же переменная может иметь в одной и той же формуле как свободные, так и связанные вхождения. Формула, не содержащая свободных вхождений переменных, называется замкнутой. Квантор существования вводится определением .


назад | оглавление | вперёд