3. Истинность формулы логики предикатов в алгебраической системе

Дадим индуктивное определение истинности формулы φ(x₁,…,x_n) сигнатурыΣна элементахa₁,…,a_nАв алгебраической системе= (обозначаемφ(a₁,…,a_n)).

1) ⊨t₁(a₁,…,a_n)=t₂(a₁,…,a_n), где t₁,t₂T(Σ), значения термовt₁,t₂в алгебраической системе на элементахa₁,…,a_nАсовпадают;

2) ⊨P(t₁(a₁,…,a_n),….,t_k(a₁,…,a_n)), где P^(k)Σ, t₁,…,t_kT(Σ), (t₁(a₁,…,a_n),…, t_k(a₁,…,a_n))P;

3) ⊨ψ(a₁,…,a_n)∧χ(a₁,…,a_n)⊨ψ(a₁,…,a_n) и ⊨χ(a₁,…,a_n);

4. ⊨ψ(a₁,…,a_n)∨χ(a₁,…,a_n)⊨ψ(a₁,…,a_n) или ⊨χ(a₁,…,a_n);

5. ⊨ψ(a₁,…,a_n)→χ(a₁,…,a_n) если ⊨ψ(a₁,…,a_n), то ⊨χ(a₁,…,a_n);

6. ⊨¬ψ(a₁,…,a_n)неверно, что ⊨ψ(a₁,…,a_n);

7. ⊨xψ(x,a₁,…,a_n)⊨ψ(a,a₁,…,a_n) для любого аA;

8. ⊨xψ(x,a₁,…,a_n)⊨ψ(a,a₁,…,a_n)для некоторогоаА.

Если не выполняется ⊨φ(a₁,…,a_n),то будем говорить, что формулаφ(x₁,…,x_n) сигнатурыΣложна в системена элементахa₁,…,a_nА.

Пример 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)→w₁(w=w₁z)).

Таким образом,

φ(х,у,z)uv(z=xu∧z=хy)∧w(uv(w=xu∧w=хy)→w₁(w=w₁z)).

2.3.4. Логическое следствие в логике предикатов

Через обозначим кортеж переменных; через‑.

Пусть φ₁(),…,φ_n(), ψ()– формулы сигнатуры. Формулаψ называется логическим следствием формулφ₁,…,φ_n(обозначаетсяφ₁,…,φ_n⊨ψ), если для любой алгебраической системысигнатуры

⊨(φ₁()…φ_n()→ψ()).

Пример 9. Доказать, что

φ₁()→φ₂(),φ₂()→φ₃()⊨φ₁()→φ₃(), (1)

где φ₁(),φ₂(),φ₃()– формулы сигнатуры.

Решение. Пусть=‑ произвольная алгебраическая система сигнатуры. Необходимо показать, что

⊨((φ₁()→φ₂())(φ₂()→φ₃())→(φ₁()→φ₃())).

Пусть и⊨(φ₁()→φ₂())(φ₂()→φ₃()).

Покажем, что

⊨φ₁()→φ₃(). (2)

Предположим, что ⊨φ₁(). Так как⊨(φ₁()→φ₂(), то⊨φ₂(). Так как⊨φ₂()→φ₃(), то⊨φ₃(). Таким образом, (2), а, следовательно, и (1), доказано.

Формула φ(x₁,…,x_n) сигнатуры называется тождественно истинной, если для любой алгебраической системысигнатуры

⊨φ(x₁,…,x_n). Формула φ(x₁,…,x_n) сигнатуры называется тождественно ложной, если формула ¬φ(x₁,…,x_n) тождественно истина. Множество формул φ₁,…,φ_n сигнатуры называется противоречивым или несовместным, если формула φ₁∧…∧φ_n тождественно ложна.

Теорема 3. Пусть φ₁,..,φ_m,ψ – формулы сигнатуры Следующие условия эквивалентны:

6. ;

7. 

8. {φ₁,..,φ_m,¬ψ} – противоречивое множество формул;

9. – тождественно истинная формула;

10. φ₁∧..∧φ_m∧¬ψ – тождественно ложная формула.

2.3.5. Эквивалентные формулы логики предикатов

Формулы φ и ψ сигнатурыназываются эквивалентными(обозначается φ ≡ ψ), если φψ или ψ.

Утверждение 1. В логике предикатов выполнимы все эквивалентности ИВ из теоремы 3.

Утверждение 2. Пусть φ, ψ – формулы сигнатуры переменная x не является свободной переменной формулы ψ, переменная у не является свободной переменной формулы φ. Тогда

1) ¬xφ≡x¬φ, 1΄) ¬xφ≡x¬φ,

2) x(φ∧ψ)≡xφ∧ψ, 2΄) x(φ∨ψ)≡xφ∨ψ,

3) x(φ∨ψ)≡xφ∨ψ, 3΄) x(φ∧ψ)≡xφ∧ψ,

4) xφ≡x(φ) 4΄)xφ≡x(φ)

здесь запись (φ) обозначает результат подстановки y вместо всех свободных вхождений в φ переменной x.