13. Предикаты и области истинности

Кроме высказываний, рассматриваются также высказывания с переменными, т.е. буквами, вместо которых можно подставлять определенные значения (например, числа). Если вместо всех переменных подставить их значения, то высказывание с переменными превратится в обычное высказывание.

Например, рассмотрим высказывание с переменной x^2+y^2=25.

    [x=3, y=-4]

3^2+(-4)^2=25 — истинное высказывание,

    [x=2, y=3]

2^2+3^2=25 — ложное высказывание.

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

Определение. Предикат — это высказывание с переменными.

Пример. Область истинности предиката x^2=4{-2;2};
предиката x^3>27(3;+infty);
предиката x=y — на рис. 1:

Рис. 1

Область истинности предиката exists z: x^2+y^2=z, где
x,y — свободные переменные, z — связанная переменная, изображена на следующие рис. 2:

Рис. 2

Область истинности предиката xy>0 изображена на рис. 3 (оси координат не включаем):

Рис. 3

Область истинности предиката exists z: x+y=z^2 изображена на рис. 4:

Рис. 4

Если в предикаты P и Q входят одни и те же переменные, то область истинности предиката P& Q есть пересечение, а область истинности предиката Pvee Q — объединение областей истинности данных предикатов.

Задачи.

1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности:

1) x+5=1;

2) при x=2 выполняется равенство x^2-1=0;

3) x^2-2x+1=0;

4) Существует такое число x, что x^2-2x+1=0;

5) x+2<3x+4;

6) однозначное число x кратно 3;

7) (x+2)-(3x-4);

8 ) x^2+y^2>0.

2. Пусть даны предикаты: P(x): x — четное число и Q(x): x кратно 3, определенные на множестве натуральных чисел. Найти области истинности предикатов

1) P(x)& Q(x);

2) P(x)vee Q(x);

3) daleth P(x);

4) P(x)to Q(x).

3. Даны предикаты

    [P(x): x^2+x+1>0, Q(x): x^2-4x+3=0,]

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

1) forall x P(x);

2) exists x P(x);

3) forall x Q(x);

4) exists x Q(x).

4. Пусть предикат Q(x,y): xvdots y. Показать, что высказывания

    [forall yexists x Q(x,y), exists xforall y Q(x,y)]

имеют разные логические значения.

Пусть даны два предиката P(x) и Q(x). Предикат Q(x) является следствием предиката P(x) (P(x)to Q(x)), если область истинности P(x) содержится в области истинности Q(x). Предикаты P(x) и Q(x) равносильны, если их области истинности совпадают.

Задачи.

1. Будут ли следующие предикаты равносильны или один из них является следствием другого?

1) sqrt{x}sqrt{y}=15 и sqrt{xy}=15;

2) x+y=z и (x+y)(x-z)=-zy;

3) x^3+y^3=0 и x^2-y^2=0.

2. Изобразите на плоскости области истинности предикатов:

1) x+3y=3;

2) x-y^2ge0;

3) (x-2)^2+(y+3)^2=0.

3. На множестве M={1,2,3,dots,20} заданы предикаты

A(x): x не делится на 5;

B(x): x — четное число;

C(x): x — число простое;

D(x): x кратно 3.

Найдите множества истинности предикатов

1) A(x)& B(x);

2) C(x)& B(x);

3) daleth B(x)& D(x);

4) C(x)vee D(x);

5) A(x)vee B(x)vee D(x);

6) C(x)to A(x);

7) A(x)& B(x)& D(x).

4. Изобразите на координатной плоскости области истинности предикатов:

1) daleth(x>2)&(x<y);

2) (xle y)vee (|x|le1);

3) ((x>2)&(yge1))&((x<-1)vee(y<-2)).

5. Будет ли истинно высказывание

    [forall x(P(x)& Q(x)to R(x)),]

если P(x): число x делится на 3, Q(x): число x делится на 4, R(x): число x делится на 2?

6. Найти отрицание формул:

1) forall x(P(x)& Q(x));

2) exists x(P(x)vee Q(x));

3) forall xexists y(R(x,y)to L(x,y)).

7. Пусть предикат P(x,y): x<y. Какие из следующих предложений истинны, а какие ложны:

1) exists xforall y P(x,y);

2) forall xexists y P(x,y);

3) forall yexists x P(x,y);

4) forall xforall y P(x,y);

5) forall yforall x P(x,y);

6) exists yforall x P(x,y);

7) exists xexists y P(x,y);

8 ) exists yexists x P(x,y).

8. Найти отрицания формул:

1) exists x(A(x)& B(x)& C(x));

2) forall x(A(x)toforall y B(y));

3) forall x(A(x)veeexists y B(y));

4) forall (A(x)to B(x))&exists x(S(x)&daleth R(x));

5) forall xexists yforall z(P(x,y,z)to Q(x,y,z)).

Ссылка на основную публикацию