logo search
практикум по мат

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

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

Пусть φ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,ψ – формулы сигнатуры Следующие условия эквивалентны:

  1. ;

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

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

  5. φ1∧..∧φm∧¬ψ – тождественно ложная формула.