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

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

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

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

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

Моделью M в логике предикатов называют множество M вместе с заданной на нем совокупностью предикатов å={ ,..., }:

M = (M; ,..., ),

где M – основное множество модели M; å={ ,..., } – сигнатура модели M. Например, сигнатура модели N = { N; S, П, E }, называемой арифметикой натуральных чисел, включает предикаты суммы S, произведения П и равенства Е. Аналогично предыдущему определяются формулы, выполнимые на модели M, тождественно истинные (ТИ-формулы) и тождественно ложные (ТЛ-формулы) на модели M.

Пример 1. Определить истинность, ложность либо выполнимость на модели N = { N; S, П, E } следующих формул:

1. (П (x, y, z)& П (x, y, u))® E (z, u);

2. $ y П (x, x, y);

3. $ x П (x, x, y).

1. Предикатная формула (П (x, y, z)& П (x, y, u))® E (z, u) – ТИ-формула на модели N в силу единственности значения произведения чисел из N. Действительно, для любых подстановок констант вместо переменных x, y, z, u, например, a, b, c, d Î N, формула (П (a, b, c)& П (a, b, d))® E (c, d) имеет значение “истинно” (см. поясняющие примеры различных подстановок констант вместо переменных x, y, z, u в примере 2 §2.2.)

2. Формула $ y П (x, x, y) – ТИ-формула на модели N, выражающая существование натурального квадрата натурального числа x. Действительно, при подстановке любой константы вместо свободной переменной x формула $ y П (x, x, y) истинна.

3. Формула $ x П (x, x, y) выполнима на модели N: “существует натуральное значение квадратного корня для натурального y из N ” или “ – натуральное число”. Очевидно, формула истинна при подстановках вместо свободной переменной y чисел 0, 1, 4, 9, 16,... и ложна при подстановке 2, 3, 5, 6, 7, 8, 10,...; например, $ x П (x, x,4) – истинна, а $ x П (x, x,5) – ложна.

Пример 2. Доказать истинность формулы:

" x ((P (x)& Q (x))® P (x)).

Предположим противное. Пусть формула ложна, т.е. не для всех x (P (x)& Q (x))® P (x) истинно. Тогда существует константа a Î M, подстановка которой в формулу сделает ее ложной, т.е. (P (a)& Q (a))® P (a)=0.

Это возможно лишь тогда, когда P (a)=0 (правая часть импликации), а P (a)& Q (a)=1 (левая часть), но последнее требует, чтобы P (a)=1 и Q (a)=1.

Таким образом, требуется, чтобы существовала константа a в области M такая, что P (a)=0 и P (a)=1, что невозможно.

Принятое предположение относительно ложности формулы привело к противоречию, поэтому оно неверно и, следовательно, формула " x ((P (x)& Q (x))® P (x)) – истинна.

Вопросы для самопроверки и упражнения.

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