Выполнимость и истинность

 

При логической интерпретации формул логики предикатов возможны три основные ситуации:

1. Формула F(х_1, х_2, ..., х_п) называется выполнимой в области М, если в этой области для формулы F существует такая подстановка констант a_1, a_2, ...,a_п вместо переменных х_1, х_2, ..., х_п, что F(a_1, a_2, ...,a_п) становится истинным высказыванием.

Формула называется просто выполнимой, если существует область М, где F выполнима.

2. Формула F(х_1, х_2, ..., х_п) называется тождественно истинной в области М, если F выполнима в М при любых подстановках констант.

3. Формула F(х_1, х_2, ..., х_п) называется тождественно истинной (ТИ) или общезначимой, если она тождественно истинна в любых М.

Формула F(х_1, х_2, ..., х_п) называется тождественно ложной в области М, если F невыполнима в М.

Формула F(х_1, х_2, ..., х_п) называется тождественно ложной (ТЛ) или противоречивой, если F невыполнима ни в каких М.

Моделью МО в логике предикатов называют множество М вместе с заданной на нем совокупностью предикатов

где М - основное множество модели МО; -сигнатура модели МО.

Пример 5.

Сигнатура модели - арифметика натуральных чисел, включает предикаты суммы S, произведения П и равенства Е.