Построение формул

1.

1. Атомарная формула является формулой.

2. Если A и B - выражения, являющиеся формулами, то выражения вида [ A & B ], [ A Ú B ], [ A ® B ] являются формулами.

3. Если A - формула, то Ø A - формула.

4. Если y - переменная и A - формула, то выражения " y A и $ y A - формулы.

Любая подпоследовательность следующих друг за другом символов в формуле A, которая сама является формулой, называется подформулой формулы A.

Подформула формулы A, которая непосредственно следует за символами " y или $ y, где y - переменная, называется областью действия соответствующего квантора.

Вхождение переменной y называется связанным, если оно находится в области действия квантора по y, и свободным в противном случае.

Формула, не имеющая свободных вхождений переменных, называется замкнутой формулой, или предложением

Интерпретацией будем называть отображение I, заданное на σ È Var, которое:

· каждому n -местному предикатному символу P Î σ ставит в соответствие отношение P ^{( I )}Í U ⁿ;

· каждому n -местному функциональному символу f Î σ ставит в соответствие функцию f ^{( I )}: U ⁿ ® U, в частности, при n = 0 f ^{( I )} Î U и называется константой;

· каждой переменной y Î Var ставит в соответствие элемент y ^{( I )} Î U.

С помощью интерпретации I каждому терму t Î Term (σ) ставится в соответствие объект

Каждой формуле A Î Form (σ) ставится в соответствие истинностное значение A ^{( I )} Î {0,1}, при этом 0 интерпретируется как ложь, а 1 – истина.

Если A - атомарная формула вида P (t ₁, t ₂,..., t_n), то

Если А – не атомарная

Если σ состоит из символов P ₁, P ₂,..., P_k, f ₁, f ₂,..., f_n, то структуру S = I_σ на универсуме U изображают в виде набора S = I_σ = (U; P ₁^{( I )}, P ₂^{( I )},..., P_k ^{( I )}; f ₁^{( I )}, f ₂^{( I )},..., f_n ^{( I )}).

Дата добавления: 2015-08-31