Примеры. Одной из задач логики предикатов является поиск областей истинности предикатов – множества значений аргументов

Одной из задач логики предикатов является поиск областей истинности предикатов – множества значений аргументов, на которых предикат принимает истинные значения. Пусть, к примеру, даны предикаты: P (x): «x – четное число» и Q (x): «x кратно 3», определенные на множестве натуральных чисел N. Областями истинности P (x) и Q (x) соответственно являются I_P = {2, 4, 6, …, 2 n …}, I_Q = {3, 6, 9, …, 3 n …}. Найдем области истинности для следующих предикатов:

1. P (x) Ù Q (x): множеством истинности конъюнкции будет пересечение множеств истинности конъюнктов – I_{P Ù Q} = I_P Ç I_Q = {6, 12, …, 6 n …}
2. P (x) Ú Q (x): множеством истинности дизъюнкции будет объединение множеств истинности дизъюнктов – I_{P Ú Q} = I_P È I_Q = {2, 3, 4, 6, …, 2 n, 3 n …}
3. Ø P (x): множеством истинности отрицания будет исключение множества истинности предиката из множества его определения – I _{Ø P} = N \ I_P = {1, 3, 5, …, 2 n - 1,…}
4. P (x) ® Q (x): множеством истинности импликации (логического следствия) будет объединение множества истинности отрицания первого дизъюнкта и множества истинности второго дизъюнкта (так как a ® b = Ø a Ú b) – I_{P ® Q} = I _{Ø P} È I_Q = {1, 3, 5, …, 2 n - 1,…} È {3, 6, 9, …, 3 n …}

Следующий пример показывает, как с помощью логики предикатов можно отыскать утверждение, противоположное заданному, или, иначе говоря, отрицание заданной формулы. Найдем отрицание формулы "(x) $(y) R (x, y) ® L (x, y):

Ø ("(x) $(y) R (x, y) ® L (x, y)) = $(x) Ø ($(y) R (x, y) ® L (x, y)) =

= $(x) "(y) Ø(R (x, y) ® L (x, y)) = $(x) "(y) Ø(Ø R (x, y) Ú L (x, y)) =

= $(x) "(y) (R (x, y) Ù Ø L (x, y)).

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

Докажем общезначимость формулы A = "(x) (P (x) ® Ø Q (x)) ® Ø $(x) (P (x) Ù "(x) Q (x)).

Считая, что формула A определена на любой области определения проведем равносильные преобразования:

A = "(x) (P (x) ® Ø Q (x)) ® Ø$(x) (P (x) Ù "(x) Q (x)) =

во второй части импликации изменяем квантор

в соответствии с законами взаимосвязи между кванторами

= "(x) (P (x) ® Ø Q (x)) ® "(x) Ø (P (x) Ù "(x) Q (x)) =

переносим квантор общности в начало формулы,

т.к. квантор одинаково связывает обе части импликации

= "(x) [(P (x) ® Ø Q (x)) ® Ø (P (x) Ù "(x) Q (x))] =

на основании закона x ® y = Ø x Ú y

= "(x) [Ø (P (x) ® Ø Q (x)) Ú Ø (P (x) Ù "(x) Q (x))] =

= "(x) [Ø (Ø P (x) Ú Ø Q (x)) Ú Ø (P (x) Ù "(x) Q (x))] =

вносим отрицание «под скобки»,

применяя законы Де Моргана

= "(x) [(P (x) Ù Q (x)) Ú Ø P (x) Ú Ø"(x) Q (x)] =

= "(x) [(P (x) Ù Q (x)) Ú Ø P (x) Ú $(x) Ø Q (x)] =

применяем дистрибутивный закон

и закон x Ú Ø x = 1

= "(x) [(P (x) Ú Ø P (x)) Ù (Q (x) Ú Ø P (x)) Ú $(x) Ø Q (x)] =

= "(x) [(1 Ù (Q (x) Ú Ø P (x))) Ú $(x) Ø Q (x)] =

на основании закона x Ù 1 = x

= "(x) [ Q (x) Ú Ø P (x) Ú $(x) Ø Q (x)] =

= "(x) [ Q (x) Ú $(x) Ø Q (x) Ú Ø P (x)] =

= "(x) [$(x) (Q (x) Ú Ø Q (x)) Ú Ø P (x)] =

наконец, по закону x Ú 1 = 1, имеем

= "(x) [ 1 Ú Ø P (x)] = 1.