Через обозначим кортеж переменных ; через ‑ .
Пусть φ1(),…,φn(), ψ() – формулы сигнатуры . Формула ψ называется логическим следствием формул φ1,…,φn (обозначается φ1,…,φn⊨ψ), если для любой алгебраической системы сигнатуры
⊨ (φ1() … φn()→ψ()).
Пример 9.Доказать, что
φ1()→φ2(),φ2()→φ3()⊨φ1()→φ3(), (1)
где φ1(),φ2(),φ3() – формулы сигнатуры .
Решение.Пусть = ‑ произвольная алгебраическая система сигнатуры . Необходимо показать, что
⊨ ((φ1()→φ2()) (φ2()→φ3())→(φ1()→φ3())).
Пусть и ⊨(φ1()→φ2()) (φ2()→φ3()).
Покажем, что
⊨φ1()→φ3(). (2)
Предположим, что ⊨φ1(). Так как ⊨(φ1()→φ2(), то ⊨φ2(). Так как ⊨φ2()→φ3(), то ⊨φ3(). Таким образом, (2), а, следовательно, и (1), доказано.
Формула φ(x1,…,xn) сигнатуры называется тождественно истинной, если для любой алгебраической системы сигнатуры
⊨ φ(x1,…,xn). Формула φ(x1,…,xn) сигнатуры называется тождественно ложной, если формула ¬φ(x1,…,xn) тождественно истина. Множество формул φ1,…,φn сигнатуры называется противоречивым или несовместным, если формула φ1∧…∧φn тождественно ложна.
Теорема 3.Пусть φ1,..,φm,ψ – формулы сигнатуры Следующие условия эквивалентны:
6) ;
7)
8) {φ1,..,φm,¬ψ} – противоречивое множество формул;
9) – тождественно истинная формула;
10) φ1∧..∧φm∧¬ψ – тождественно ложная формула.