Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

58 формулах – свободные. 3. Если A – формула, а x – свободная переменная в A , то (  x)A и (  x)A – формулы. Пример 11.1. Приведем пример формулы и с названиями ее компонент.           , x P x Q f x a   Терм   Атом      Область действия квантора  Рис. 11.1. Формула и ее компоненты. Все вхождения переменной x – связанные. Интерпретация формул Определение. Интерпретация I формулы F исчисления предикатов состоит из непустой предметной области D и указания значения всех констант, функциональных и предикатных символов, входящих в F . При этом: 1. каждой константе ставится в соответствие некоторый элемент из D ; 2. каждому n –местному функциональному символу ставится в соответствие функция D n  D ; 3. каждому n – местному предикатному символу ставится в соответствие n –местный предикат D n  B . Если задана интерпретация I , то значение формулы определяется по следующим правилам: а) если заданы значения формул G и H , то значения формул G G H H G H G    , , , можно определить по таблицам;