SHPORA.net :: PDA

[ Back ]

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



принимает истинные значения.

 - квантор общности (все);

 - квантор существования (существует для некоторых).

Область действия квантора входящего в формулу – это подформула, к которой он применяется.

Вхождение переменной х в формулу называется связанным если это вхождение находится в области действия квантора по этой



переменной. Иначе называется свободным.