Основные понятия и методы теории формальных систем. Волохович А.В. - 17 стр.

      a 1 , a 2 , …, a n , … – предметные константы;
      A 1 1 , A 2 2 , …, A l m , P 1 1 ,… – предикатные буквы;
      f 1 1 , f 2 2 , …, f l k ,… – функциональные буквы.
      Верхний индекс предикатной или функциональной буквы
указывает число аргументов, а нижний служит для различения букв
с одним и тем же числом аргументов.
      Правила конструирования термов:
      1) всякая предметная переменная или предметная константа есть
терм;
      2) если f n i – функцнональная буква и t 1 , t 2 , …, t n – термы, то f n i (t 1 ,
t 2 , …, t n ) есть терм;
      3) других правил образования термов нет.
      Например, х, у и 1 – термы; mult и plus – двухместные
функциональные символы, тогда plus(у, 1) и mult(х, plus(у, 1)) –
также термы.
      Правила образования атомов (атомарных формул):
      1) всякое переменное высказывание есть атом;
      2) если A n i – предикатная буква, а t 1 , t 2 , …, t n – термы, то A n i (t 1 ,
t 2 , …, t n ) есть атом;
      3) других правил образования атомов нет.
      Формулы исчисления предикатов конструируются по следующим
правилам:
      1) всякий атом есть формула;
      2) если А и В – формулы и х – предметная переменная, то каждое
из выражений ¬ А, А → В, А ~ В, А & В, А ∨ В, что ∃ xА, ∀ х А есть
формула;
      3) других правил образования формул нет.
      Как и раньше будем употреблять скобки только в тех случаях,
которые               исключают          двусмысленности.   Кроме  того,  всегда
предполагаем, что свободные и связанные переменные обозначены
разными буквами и если один квантор находится в области действия
другого, то переменные, связанные этими кванторами, также
обозначены разными буквами.
      Пример. Пусть Р(х) и N(х) обозначают соответственно «х есть
положительное целое число» и «х есть натуральное число». Тогда
утверждение «Всякое положительное целое число есть натуральное
число. Число 5 есть положительное целое число. Следовательно, 5
есть натуральное число» будет записано на языке                       исчисления
предикатов следующим образом:

                    ∀ х(Р(х)) → N(х),
                          Р(5),
                          N(5).




17