Кванторы общности и существования

При изучении высказывательных форм (предикатов) был указан один из способов получения высказываний: подстановка какого-нибудь значения переменной в Р(х) из некоторого множества А. Например,

Р(х):” х - простое число”. Подставив х = 7, получим высказывание

“ 7 - простое число”. Мы познакомимся ещё с двумя логическими операциями: навешивание квантора общности и квантора существования, которые позволяют получить из высказывательных форм высказывания.

Подставим перед высказывательной формой Р(х) слово “любое”: “ любое х - простое число”. Получили ложное высказывание. Подставим перед Р(х) слово “некоторые”: “ некоторые числа х - простые”. Получили истинное высказывание.

В математике слова “любые”, “некоторые” и их синонимы называются кванторами, которые соответственно называются квантор общности (") и квантор существования ($). Квантор общности заменяется в словесных формулировках словами: любой, все, каждый, всякий и т.д. Квантор существования в словесной формулировке заменяется словами: существует, хотя бы один, какой-нибудь найдётся и т.д.

Пусть Р(х) - высказывательная форма на М. Запись

("хÎМ) Р(х)

означает: для любого элемента х (из множества М) имеет место Р(х), что уже представляет собой высказывание. Чтобы доказать, что высказывание ("х)Р(х) - истинно, надо перебрать все элементы а, b, с и т.д. из М и убедиться, что Р(а), Р(b), Р(с),... истинны, и, если невозможно перебрать элементы М, должны доказать с помощью рассуждений, что для любого а из М высказывание Р(а) истинно. Чтобы убедиться, что ("х)Р(х) ложно, достаточно найти лишь один элемент аÎМ, для которого Р(а) ложно.

ПРИМЕР. Дана высказывательная форма

В(х):” - простое число”.

В(1): 2² + 1 = 5 - простое число;

В(2): = 17 - простое число;

В(3): = 257 - простое число;

В(4): = 65537 - простое число.

Можно ли сказать, что ("х)В(х)? Это необходимо доказывать. Леонард Эйлер доказал, что В(5) - ложно, т.е. + 1 = 2³² + 1 делится на 641 и, следовательно, ("х)В(х) - ложно.

ПРИМЕР. Рассмотрим высказывание ("х)С(х), где на N задано С(х): “х³ + 5х делится на 6”.

Очевидно, С(1), С(2), С(3), С(4) истинны. Но если мы проверим даже миллион значений х всегда есть опасность, что для миллион первого значения х утверждение С(х) окажется ложным.

Доказать можно, например, так:

х³ + 5х = х³ - х + 6х = х(х² - 1) + 6х = (х - 1)х(х + 1) + 6х

Выражение (х - 1)х(х + 1) делится на 3, так как из трех последовательных натуральных чисел по крайней мере одно делится на 3; это выражение делится и на 2, так как из трех последовательных чисел одно или два числа чётны. Второе слагаемое 6х делится на 6, следовательно и вся сумма делится на 6, т.е. ("х)С(х) - истинно.

Пусть С(х) некоторая высказывательная форма. Запись

($х)С(х)

означает: существует элемент х из множества М, для которого имеет место С(х). ($х)С(х) уже высказывание. Если во множестве М можно найти элемент а, для которого С(а) истинно, то высказывание($х)С(х) - истинно. Если же в М нет ни одного элемента а, для которого С(а) истинно, высказывание ($х)С(х) - ложно.

ПРИМЕР. На множестве N задано С(х):” ”. С(1) - ложно, С(2) - ложно, С(5) - истинно. Следовательно, ($х)С(х) - истинное высказывание.

 

ПРИМЕР. На множестве N задано К(х):” х² + 2х + 3 делится на 7”. К(1) = 6, 6 не делится на 7; К(2) = 11, 11 не делится на 7 и т.д.

Гипотеза: ($х)К(х) - ложно.

Докажем это. Любое натуральное число по теореме о делении с остатком можно представить в виде n = 7q + r, где r < 7.

n² + 2n + 3 = (7q + r)² + 2(7q + r) + 3 = 7(7q² + 2qr + 2q) + r² + 2r + 3.

Итак, число n² + 2n + 3 делится на 7 тогда и только тогда, когда r² + 2r + 3 делится на 7. Остаток r Î { 0, 1, 2, 3, 4, 5, 6 }. Методом перебора убедимся, что r² + 2r + 3 не делится на 7. Итак, ($х)К(х) - ложно.

 

Как построить отрицание высказывания с квантором?

Для того чтобы построить отрицание высказывания с квантором, нужно заменить квантор общности (") на квантор существования ($) и, наоборот, квантор существования на квантор общности, а предложение, стоящее после квантора, на его отрицание, т.е.

[("x)P(x) Û ($x) P(x);

[($x)P(x) Û ("x) P(x).

Например, пусть даны два высказывания:

А: “каждое простое число нечётно”;

В: “ каждое простое число чётно”.

Будет ли В отрицанием высказывания А? Нет, так как ни одно из высказываний не является истинным. В данном случае

А: “не каждое простое число нечётно, т.е. существует чётное простое число” - истинное высказывание.

В дальнейшем считаем, что построено отрицание предложения, если не просто записано его отрицание, но и полученное предложение преобразовано к виду, где знаки отрицания стоят перед более простыми выражениями. Например, отрицанием предложения вида А Ù В будем считать не (А Ù В), а ему равносильное: А Ú В.

Пусть А(х,у) - высказывательная форма с двумя переменными.

Тогда ("х)А(х,у), ($х)А(х,у), ("х)А(х,у), ($х)А(х,у) тоже высказывательные формы но уже с одной переменной. В этом случае говорят, что квантор связывает одну переменную. Чтобы получить из высказывательной формы А(х,у) высказывание необходимо связать обе переменные. Например, ("х)($у)А(х,у) - высказывание.

Для высказывательной формы Р(х,у): “ x < y”, заданной на Z, рассмотрим все случаи получения высказывания путем добавления (навешивания) кванторов:

1) ("х)("у)Р(х,у) Û л - “ Для всякого х и для всякого у х < y”;

2) ("у)("х)(х < y) Û л - “Для всякого у и для всякого х х < y”;

3) ($x)($y) (x < y) Û и - “Существует х и существует у такие, что x < y”;

4) ($у)($х) (х < y) Û и - “Существует х и существует у такие, что x < y”;

5) ("х)($у) (x < y) Û и - “Для всякого х существует у такое, что x < y”;

6) ($у)("х) (x < y) Û л - “Существует у такое, что для всякого х х < y”;

7) ("у)($х) (х < y) Û и - “Для всякого у существует х такое, что x < y”;

8) ($х)("у) (x < y) Û л - “Существует x такое, что для всякого y х < y”.

` Обратите внимание на высказывания (1) и (2), (3) и (4). Структуры этих высказываний отличаются лишь порядком следования одноименных кванторов, но при этом не меняются смысл и значения истинности высказываний.

Высказывания (5) и (6), (7) и (8) отличаются порядком следования разноимённых кванторов, что приводит к изменению смысла и, возможно, значения истинности высказывания. Высказывание (7) утверждает о наличии в Z наименьшего числа, что ложно. (8) утверждает об отсутствии такого, что истинно.

Теоретические вопросы:

1. Понятие предиката от одного, нескольких переменных.

2. Примеры одноместных и двуместных предикатов. 3. Область истинности предиката.

4. Кванторы общности и существования. Свободные и связанные переменные. Операции над предикатами. Какова область истинности ; ; ; ? Дать геометрические интерпретации.

5. Преобразование формул логики предикатов. Определение тождественно истинного и тождественно ложного предиката, связь с областью истинности. Основные равносильности.

Упражнения

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

1. х 2, х Î N; 9. = - x, x Î R;

2. х < 1, x Î N; 10. > 0,

3. x > 6® x ³ 3, xÎZ; 11. sin x = - , xÎ R;

4. x + 3x +6 = 0, x Î R; 12. cos x = , x ÎR;

5. = 0, xÎR; 13. x ³ y, x,y Î R;

6. | x - 5 | < 2, 14. x + y < 3, x,yÎ N;

7. | 2x + 3 | ³ 2x + 3, x Î R; 15. x (y - 1) = 0, x,yÎR;

8. = x, x Î R; 16. x + y =4, x, y ÎR.

 

5.2. Найдите область истинности предикатов упражнения 5.1. Случаи 13 - 16 изобразите на координатной плоскости.

 

5.3. Найдите область истинности предикатов:

1. = 0; 7. | 3x - 2 | > 8;

2. = ; 8. | 5x - 3 | < 7;

3. - > ; 9. 2 - | x | = 1,7;

4. ; 10. | 3x - 1 | = 3x - 1;

5. < 0; 11. | 3x - 1 | = 1 - 3x;

6. > 0; 12. | 2x + 4 | ³ 2x + 4.

 

5.4. Найдите область истинности предикатов:

1. ( < x + 1,5) Ù (2x - 8 > 3 - 0,5 x);

2. ( - 4 < - 1) Ù ( x + 2 (2x- 1) < 3(x +1);

3.( - +2x<3x-3) Ù ( - 3(1-x)+2x< );

4.( - + x < 2x - 4)Ù( + 3 (x - 1)< );

5.((x+3) (x - 1) < 0) Ù (x + 4x + 6 > x (x - 5);

6.((x - 6x + 9)(2x - 10) < 0) Ù (6 + x (7 - x) < x +2x(5-x);

7.(1 + £ ) Ú (- 1 < 5x - 5)

8.( - > 2) Ú (- 3x - 1 > 2);

9.( + 6x > + 4) Ú ( - > - );

10.(0,2 (2x - 3) < x - 2) Ú (5x - 7 > x - 6).

 

5.5. Найдите область истинности предикатов:

1. sin x = ; 2. cos x = - ;

3. tg x = 1; 4. ctg x = - 1;

5. 4 - cos x = 4 sin x 6. 5 - 2 cos x=5 sin

5.6. Определите тождественную истинность и тождественную ложность предикатов:

1. x + x = 2, x Î N; 2. x + 1 = 0, x Î R;

3. 1+cos x=2 cos ; xÎR; 4. 1- cos x=2 sin , x Î R;

5. (x + x) 2, xÎZ; 6.(x 2) Ù(x = 2y +1), x,y ÎZ

7. (x 2) Ú(x=2y +1), x,yÎZ; 8.(x 2) ®(x = 2y +1), x,y ÎZ;

9. (x 9)®(x 3), x,y ÎZ.

 

5.7. Найдите значение следующих высказываний:

1. (" x Î N) (x £ 1); 2. ($ x Î N) x £ 1

3. (" x Î Z) (x + x = 2); 4. ($ xÎ Z) (x + x = 2);

5. (" x Î Z) ((x > 10) ®(x ³ 3));

6. (" x Î Z) ((x ³ 3) ® (x > 10);

7. (" x,y Î Z) (x + y = 3);

8. ($ x,y Î Z) (x + y = 3);

9. (" x,y Î R) (x < y ® x < y );

10. (" x,y Î R ) (x < y ® x < y ).

 

З А Н Я Т И Е № 6.

 

Применение предикатов.