При логической интерпретации формул логики предикатов возможны три основные ситуации:
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. Определить истинность, ложность либо выполнимость в области натуральных чисел следующих формул:
а) " x " y " z " u ((S (x, y, z)& S (x, y, u))® E (z, u));
б) (S (x, y, z)& S (x, y, u))® E (z, u);
в) " x " y " z " u ((П (x, y, z)& П (x, y, u))® E (z, u));
г) $ y (П (x, x, y)® S (x, x, y));
д) " x " y " z ((П (x, y, z)&Ø E (x, y))® S (x, y, z));
е) $ y ((S (x, y, z)Ú E (x, z))® Q (x, z));
ж) Q (x, z)®($ y S (x, y, z)Ú E (x, z));
з) $ x П (x, y, z)® D (z, y));
и) $ x S (x, y, y)®" x S (x, y, y));
к) $ x П (y, x, y)®" y П (y, x, y));
л) $ x S (x, x, y);
м) $ y S (x, x, y).
Примечание: S, П, E, Q, D – соответственно предикаты суммы, произведения, равенства, порядка, делимости.
2. Доказать методом от противного истинность формул:
а) " x ((P (x)® Q (x))Ú(Q (x)® P (x)));
б) " x ((P (x)® Q (x))Ú(P (x)® Q (x)));
в) " x (P (x)®(Q (x)®(P (x)& Q (x))));
г) " x ((Ø P (x)®Ø Q (x))®(Q (x)® P (x)));
д) " x ((P (x)® Q (x))Ú((P (x)®Ø Q (x))®Ø P (x)));
е) " x ((Q (x)® R (x))Ú((P (x)Ú Q (x))®(P (x)® R (x))));
ж) " x (((P (x)® Q (x))® P (x))® P (x));
з) " x (Ø P (x)®(P (x)® Q (x))).