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

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

1. Если в области для формулы существует такая подстановка констант вместо всех переменных, что становится истинным высказыванием, то формула называется выполнимой в области М.

2. Если формула выполнима в при любых подстановках констант, то она называется тождественно истинной в . Формула, тождественно истинная в любых , называется тождественно истинной или общезначимой.

Пример. Формула тождественно истинна.

3. Если формула невыполнима в , то она называется тождественно ложной в . Если формула невыполнима ни в каких , она называется тождественно ложной или противоречивой.

Пример. Формула тождественно ложна.

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

Пример. Определить истинность, ложность или выполнимость на модели следующих формул:

Здесь – предикаты суммы, произведения и равенства.

Первая предикатная формула является тождественно истинной на модели Â ввиду единственности значения произведения чисел из . При любых подстановках констант формула истинна.

Вторая формула на модели Â выражает существование натурального квадрата натурального числа . Она также тождественно истинна на модели Â.

Третья формула выполнима на модели Â. Она читается –«существует натуральное значение квадратного корня для натурального числа из », или « – натуральное число». Очевидно, что она истинна при подстановках вместо чисел 0,1,4,9,16,… , и ложна при подстановке 2,3,5,…