Логика предикатов

Предикатом R(x₁, x₂,..., x_n) называется функция, аргументы x₁, x₂,..., x_n которой принимают значения из некоторого множества M, а сама функция – значения 0 («ложь») или 1 («истина»).

Предикат R(x₁, x₂,..., x_n) называется:

- тождественно-истинным, если для любого набора значений аргументов x₁, x₂,..., x_n значение предиката истинно;

- тождественно-ложным, если для любого набора значений аргументов значение предиката ложно;

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

Для предикатов вводятся две новые операции – квантор общности " и квантор существования $.

Под выражением "x P(x) будем подразумевать высказывание истинное, когда P(x) истинно для каждого элемента x из множества M, и ложное в противном случае.

Под выражением $x P(x) будем понимать высказывание истинное, когда существует элемент x из множества M, для которого P(x) истинно, и ложное в противном случае.

Пример 1.5. Найти предикат равносильный данному, не содержащий кванторов, на множестве M = {a, b}:

"x P(x,y) + $y Q(x,y).

Решение. Квантор общности равносилен конъюнкции на конечном множестве, а квантор существования – дизъюнкции.

(P(a,y) × P(b,y)) + (Q(x,a) + Q(x,b)).

В случае наличия двух или более кванторов перед предикатом, раскрытие кванторов начинается с самого левого.

Пример 1.6. Даны предикаты: P(x) – «Объект x – высокий», R(x) – «Объект x – узкий».

Решение. Выражение P(x) × можно прочитать как «Объект x – высокий и не узкий».

Под простой формулой будем понимать предикат, значение которого не зависит от значений других предикатов.

Под формулой в логике предикатов будем понимать:

- простые формулы;

- если A(x) и B(x) – формулы, то (A(x)B(x)), (A(x)+B(x)), (A(x)®B(x)), (A(x)~B(x)) – формулы;

- если A(x) – формула, то – формула.

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

Перенос квантора через отрицание:

= P(x) = $x . (1.24)

= P(x) = "x . (1.25)

Дистрибутивность:

"x (P(x)×Q(x)) = "x P(x)×"x Q(x). (1.26)

$x (P(x) + Q(x)) = $x P(x) + $x Q(x). (1.27)

$x (P(x)×Q(x)) ® $x P(x)×$x Q(x). (1.28)

"x P(x) + "x Q(x) ® "x (P(x) + Q(x)). (1.29)

Перестановка одноименных кванторов:

"x"y P(x,y) = "y"x P(x,y). (1.30)

$x$y P(x,y) = $y$x P(x,y). (1.31)

Переименование связанных переменных:

"x P(x) = "t P(t). (1.32)

$x P(x) = $t P(t). (1.33)

Предикат, не зависящий от квантора:

"x P = P. (1.34)

$x P = P. (1.35)

Вынос квантора за скобки:

"x P(x)×Q = "x(P(x)×Q). (1.36)

"x P(x) + Q = "x(P(x) + Q). (1.37)

$x P(x)×Q = $x(P(x)×Q). (1.38)

$x P(x) + Q = $x(P(x) + Q). (1.39)

Следует отметить, что в равносильных формулах (1.28) и (1.29) равенство справедливо лишь в одну сторону (указано стрелкой).

Порядок выполнения логических операций с предикатами тот же, что и в логике высказываний. Однако кванторы связывают сильнее, чем другие операции, и поэтому выполняются в последнюю очередь.

Пример 1.7. Записать на языке предикатов следующее высказывание: «Каждое положительное действительное число является квадратом другого».

Решение. Определим следующие предикаты:

P(x) = (x > 0);

D(x) = (x – действительное число);

Q(x,y,z) = (x Ä×y = z),

где «Ä» – операция арифметического умножения.

Тогда высказывание запишем следующим образом:

"x ((P(x)×D(x)) ® $y Q(y,y,x)).

Предикат Q(x,y,z) истинен, если произведение x и y будет равно z. Следовательно, предикат Q(y,y,x) истинен, если справедливо равенство: y Ä y = y² = x.

Формула, равносильная данной и не содержащая других операций логики высказываний, кроме отрицания, конъюнкции и дизъюнкции, в которой отрицание относится только к простым формулам и кванторы вынесены в начало, называется предваренной нормальной формой (ПНФ) и имеет вид:

K₁u₁ K₂u₂ … K_mu_m A,

где K_i (1 £ i £ m) – квантор " или $; u₁, u₂, …, u_m – переменные; а A – формула.

Порядок приведения к ПНФ:

1) избавление от операций импликации и эквивалентности;

2) продвижение знака отрицания до простой формулы;

3) разделение переменных и их переименование;

4) вынос кванторов в начало формулы.

Пример 1.8. Привести к ПНФ формулу .

Решение. В соответствии с порядком приведения к ПНФ:

1) избавляемся от импликации

= ;

2) продвигаем знак отрицания до простой формулы

= "x R(x)× Q(x,y) = "x R(x)×"y ;

3) разделяем переменные и их переименовываем

"x R(x)×"y = "x₁ R(x₁)×"y₂ ;

4) выносим кванторы в начало формулы

"x₁ R(x₁)×"y₂ = "x₁ "y₂(R(x₁)× ).

Упражнения

а) Записать на языке предикатов следующие высказывания.

1. Если произведение двух действительных чисел меньше нуля, то один из множителей отрицателен.

2. Натуральное число, которое делится на 9, разделится на 3.

3. Для любого натурального числа есть превосходящее его натуральное число.

4. Не существует натурального числа, которое меньше единицы.

б) Записать высказывания 2-4 из предыдущего задания с помощью предикатов S(x,y) = (x > y) и R(x,y,z) = (x/y = z) на множестве натуральных чисел.

в) Даны предикаты: P(x) – «Объект x – высокий», R(x) – «Объект x – узкий», Q(x) – «Объект x – широкий», S(x) – «Объект x – низкий» на множестве некоторых объектов. Перевести на обычный язык следующие высказывания:

1) P(x) × R(x);

2) Q(x) + S(x);

3) P(x) ® ;

4) P(x) × ();

5) P(x) ® ();

6) ( ® Q(x)) × ;

7) ~ Q(y).

г) Найти предикат равносильный данному, не содержащий кванторов, на множестве M = {a, b}:

1) "x $y R(x,y);

2) $x "y R(x,y);

3) $x $y R(x,y);

4) "x "y R(x,y);

5) $x $y (R(x,y) + Q(y,z));

6) $x "y (Q(x,z)×Q(x,y)).

д) Являются ли выполнимыми формулы на множестве натуральных чисел:

1) $x R(x);

2) "x R(x);

3) "x $y R(x,y);

4) $x "y R(x,y);

5) $x "y (R(x,x)× ;

6) $x $y (R(x)× );

7) $y "x R(x,y)®$y "x ;

8) $x "y R(x,y)®"y $x R(y,x);

9) $x "y R(x,y)×$y "x R(x,y).

е) На множестве натуральных чисел подобрать только выполнимые предикаты R(x,y) и Q(x,y), такие что:

1) R(x,y) + – выполнимый, но не тождественно-истинный;

2) R(x,y) + Q(x,y) – тождественно-истинный;

3) R(x,y) × Q(x,y) – тождественно-ложный;

4) R(x,y) × Q(x,y) – тождественно-истинный.

ж) Найти ПНФ следующих формул:

1) R(x) + ;

2) R(x) + $x Q(x,y);

3) ;

4) ;

5) $x (R(x) + $y Q(x,y))×"y S(x,y);

6) "x P(x,y) × R(y,x) ® $y S(y);

7) "x R(x,y) ~ "x "y ;

8) "x $y ~ "y $x Q(x,y);

9) $x "y R(x,y) ~ $x ;

10) "x "y ~ $y Q(x,y);

11) "x R(x,y) ~ $x $y ;

12) $x "y ~ Q(x,y);

13) "y R(x,y) ~ $y "x ;

14) $x $y ~ "x Q(x,y);

15) "x R(x,y) ~ "x "y ;

16) $x "y ~ $y

17) $y R(x,y) ~ $x "y ;

18) ~ $x "y Q(x,y);

19) $x R(x,y) ~ $y $x ;

20) "x ~ $x "y Q(x,y).