Формулой логики предикатов называется
1. атом (атомарная формула);
2. если F и G формулы, то G<*>F, G -дизъ- F – формулы и т.д.;
3. если F формула и х свободная переменная, то (х)F и (х)F – формулы;
Формулы должны быть конечны.
Если P – n-местный предикатный символ и t1, t2, …, tn - термы, то P(t1, t2, …, tn) атом.
На интерпретации формула логики предикатов получает конкретное значение И или Л (то есть это значение вычисляется).
Формулу G назовем непротиворечивой (выполнимой), если существует такая интерпретация I, что G имеет значение И (истина) на I.
Такую интерпретацию I (на которой G(I)º И) назовем моделью формулы G. Будем говорить, что интерпретация I удовлетворяет G.
Формулу G назовем противоречивой (невыполнимой) тогда и только тогда, когда не существует интерпретация, которая
удовлетворяет G (то есть не существует модели для G).
Формулу G назовем общезначимой (тождественно истинной) тогда и только тогда, когда для любой интерпретации I, формула G
принимает истинные значения.
- квантор общности (все);
- квантор существования (существует для некоторых).
Область действия квантора входящего в формулу – это подформула, к которой он применяется.
Вхождение переменной х в формулу называется связанным если это вхождение находится в области действия квантора по этой
переменной. Иначе называется свободным.