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

 

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

1. Формула F1, х2, ..., хп) называется выполнимой в области М, если в этой области для формулы F существует такая подстановка констант a1, a2, ...,aп вместо переменных х1, х2, ..., хп, что F(a1, a2, ...,aп) становится истинным высказыванием.

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

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

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

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

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

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

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

Пример 5.

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