Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатуры Σ на элементах a1,…,an А в алгебраической системе = (обозначаем φ(a1,…,an)).
1) ⊨t1(a1,…,an)=t2(a1,…,an), где t1,t2 T(Σ), значения термов t1,t2 в алгебраической системе на элементах a1,…,an А совпадают;
2) ⊨P(t1(a1,…,an),….,tk(a1,…,an)), где P(k) Σ, t1,…,tk T(Σ), (t1(a1,…,an),…, tk(a1,…,an)) P;
3) ⊨ψ(a1,…,an)∧χ(a1,…,an) ⊨ψ(a1,…,an) и ⊨χ(a1,…,an);
4) ⊨ψ(a1,…,an)∨χ(a1,…,an) ⊨ψ(a1,…,an) или ⊨χ(a1,…,an);
5) ⊨ψ(a1,…,an)→χ(a1,…,an) если ⊨ψ(a1,…,an), то ⊨χ(a1,…,an);
6) ⊨¬ψ(a1,…,an) неверно, что ⊨ψ(a1,…,an);
7) ⊨ xψ(x,a1,…,an) ⊨ψ(a,a1,…,an) для любого а A;
8) ⊨ xψ(x,a1,…,an) ⊨ψ(a,a1,…,an) для некоторого а А.
Если не выполняется ⊨φ(a1,…,an), то будем говорить, что формула φ(x1,…,xn) сигнатуры Σ ложна в системе на элементах a1,…,an А.
Пример 7.Записать формулу φ(x), истинную в на элементе a тогда и только тогда, когда a четно.
Решение.φ(x) y(x=y+y).
Пример 8.Записать формулу φ(x,y,z), истинную в на кортеже a тогда и только тогда, когда c ‑ наименьшее общее кратное чисел a и b.
Решение.φ(x,y,z)ψ(x,y,z)∧χ(x,y,z),
где формула ψ «говорит» о том, что z делится на x и на y, а формула χ «говорит» о том, что z делит все общие кратные х и у, т. е. является наименьшим из всех общих кратных:
ψ(x,y,z) uv(z=xu∧z=хy),
χ(x,y,z) w( uv(w=xu∧w=хy)→ w1(w=w1z)).
Таким образом,
φ(х,у,z) uv(z=xu∧z=хy)∧ w( uv(w=xu∧w=хy)→ w1(w=w1z)).