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

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

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

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

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

Моделью в логике предикатов называют множество вместе с заданной на нём совокупностью предикатов: , где - основное множество; - сигнатура модели . Например, сигнатура модели , называемой арифметикой натуральных чисел, включает предикаты суммы, произведения и равенства.

Пример 9.9.

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

1. ;

2. ;

3. ;

Решение.

1. Высказывание отражает однозначность операции умножения “для любых натуральных чисел из того, что и . Для подтверждения заключения рассмотрим наборы чисел, значения предикатов и формулы на этих наборах:

a. набор (2, 3, 6, 6): .

b. набор (2, 3, 3, 6): .

Поэтому предикатная формула ТИ на модели в силу единственности значения произведения чисел из .

2. При подстановки любой константы вместо свободной переменной формула истинна, поэтому данная формула – ТИ - формула на модели , выражающая существование натурального квадрата натурального числа .

3. Формула выполнима на модели : «существует натуральное значение квадратного корня для натурального », так как при значениях формула истинна, при значениях

Формула ложна.

Пример 9.10.

Проверить истинность заданной предикатной формулы, содержащей двуместный предикат c конечной предметной областью, обе переменные которого связаны кванторами.

Предикат задан следующей таблицей:

Определить значения высказываний (0-местных предикатов):

(1) ;

(2) ;

(3) ;

(4) ;

(5) ;

(6) .

Решение.

1. Если в заданной формуле оба квантора одинаковые, то для истинности формулы в таблице должны содержаться: для квантора - только единицы; для квантора хотя бы одна единица.

Для истинности высказывания (1) таблица должна состоять только из единиц. Поэтому высказывание (1) – ложное.

Для истинности высказывания (4) таблица должна содержать хотя бы одну единицу. Следовательно, (4) – истинное высказывание.

2. Если в заданной формуле кванторы различны, то

a. если внутренний квантор , то для истинности формулы в таблице должен существовать ряд из единиц, соответствующий переменной, связанной внешним квантором;

b. если внутренний квантор , то для истинности формулы в каждом ряду таблицы соответствующем переменной, связанной внешним квантором, должна существовать, хотя бы одна единица.

В формулах (3) и (6) внутренний квантор - . Для истинности высказывания (3) необходимо наличие строки из единиц. Поскольку такой строки нет, то .

Для истинности высказывания (6) необходимо наличие столбца из единиц. Такой столбец есть, то .

Для истинности высказывания (2) необходимо наличие хотя бы одной единицы в каждой строке. Поэтому .

Для истинности высказывания (5) необходимо наличие хотя бы одной единицы в каждом столбце. Поэтому .