При вивченні висказивательной форм (предикатів) був зазначений один із способів отримання висловлювань: підстановка якогось значення змінної в Р (х) з деякого безлічі А. Наприклад,
Р (х): "х - просте число". Підставивши х = 7, отримаємо висловлювання
"7 - просте число". Ми познайомимося ще з двома логічними операціями: навішування квантора спільності і квантора існування, які дозволяють отримати з висказивательной форм висловлювання.
Підставами перед висказивательной формою Р (х) слово "будь-яке": "будь-х - просте число". Отримали хибне висловлювання. Підставами перед Р (х) слово "деякі": "деякі числа х - прості". Отримали справжнє висловлювання.
В математиці слова "будь-які", "деякі" і їх синоніми називаються кванторами, які відповідно називаються квантор спільності ( ") і квантор існування ($). Квантор спільності замінюється в словесних формулюваннях словами: будь-який, все, кожен, всякий і т.д . Квантор існування в словесному формулюванні замінюється словами: існує, хоча б один, який-небудь знайдеться і т.д.
Нехай Р (х) - висказивательной форма на М. Запис
означає: для будь-якого елемента х (з безлічі М) має місце Р (х), що вже є висловлювання. Щоб довести, що висловлювання ( "х) Р (х) - істинно, треба перебрати всі елементи а, b, с і т.д. з М і переконатися, що Р (а), Р (b), Р (с) . істинні, і, якщо неможливо перебрати елементи М, повинні довести за допомогою міркувань, що для будь-якого а з М висловлювання Р (а) істинно. Щоб переконатися, що ( "х) Р (х) помилково, досить знайти лише один елемент аÎМ, для якого Р (а) помилково.
ПРИКЛАД. Дана висказивательной форма
В (х): "- просте число".
В (1): 2 + 2 + 1 = 5 - просте число;
В (2): = 17 - просте число;
В (3): = 257 - просте число;
В (4): = 65537 - просте число.
Чи можна сказати, що ( "х) В (х). Це необхідно доводити. Леонард Ейлер довів, що В (5) - помилково, тобто + 1 = 2 32 + 1 ділиться на 641 і, отже, (" х) В (х) - помилково.
ПРИКЛАД. Розглянемо висловлювання ( "х) С (х), де на N задано С (х):" х 3 + 5х ділиться на 6 ".
Очевидно, С (1), С (2), С (3), С (4) істинними. Але якщо ми перевіримо навіть мільйон значень х завжди є небезпека, що для мільйон першого значення х твердження С (х) виявиться помилковим.
Довести можна, наприклад, так:
х 3 + 5х = х 3 - х + 6х = х (х 2 - 1) + 6х = (х - 1) х (х + 1) + 6х
Вираз (х - 1) х (х + 1) ділиться на 3, так як з трьох послідовних натуральних чисел принаймні одне ділиться на 3; це вираз ділиться і на 2, так як з трьох послідовних чисел одне або два числа парні. Другий доданок 6х ділиться на 6, отже і вся сума ділиться на 6, тобто ( "Х) С (х) - істинно.
Нехай С (х) деяка висказивательной форма. запис
означає: існує елемент х з безлічі М, для якого має місце С (х). ($ Х) С (х) вже висловлювання. Якщо в безлічі М можна знайти елемент а, для якого С (а) істинно, то висловлювання ($ х) С (х) - істинно. Якщо ж в М немає жодного елемента а, для якого С (а) істинно, висловлювання ($ х) С (х) - помилково.
ПРИКЛАД. На множествеN задано С (х): "". З (1) - помилково, С (2) - помилково, С (5) - істинно. Отже, ($ х) С (х) - справжнє висловлювання.
ПРИКЛАД. На безлічі N задано К (х): "х 2 + 2х + 3 ділиться на 7". К (1) = 6, 6 не ділиться на 7; К (2) = 11, 11 не ділиться на 7 і т.д.
Гіпотеза: ($ х) К (х) - помилково.
Доведемо це. Будь-яке натуральне число по теоремі про розподіл із залишком можна представити у вигляді n = 7q + r, де r <7.
n 2 + 2n + 3 = (7q + r) 2 + 2 (7q + r) + 3 = 7 (7q 2 + 2qr + 2q) + r 2 + 2r + 3.
Отже, число n 2 + 2n + 3 ділиться на 7 тоді і тільки тоді, коли r 2 + 2r + 3 ділиться на 7. Залишок r Î <0, 1, 2, 3, 4, 5, 6>. Методом перебору переконаємося, що r 2 + 2r + 3 не ділиться на 7. Отже, ($ х) К (х) - помилково.
Як побудувати заперечення висловлювання з квантором?
Для того щоб побудувати заперечення висловлювання з квантором, потрібно замінити квантор спільності ( ") на квантор існування ($) і, навпаки, квантор існування на квантор спільності, а пропозиція. Стоїть після квантора, на його заперечення, тобто
[( "X) P (x) Û ($ X) P (x);
[($ X) P (x) Û ( "X) P (x).
Наприклад, нехай дано два висловлювання:
А: "кожне просте число непарній";
В: "кожне просте число парне".
Чи буде У запереченням висловлювання А? Ні, тому що жодне з висловлювань не є істинним. В даному випадку
А: "не кожне просте число непарній, тобто існує парне просте число "- справжнє висловлювання.
Надалі вважаємо, що побудовано заперечення пропозиції, якщо не просто записано його заперечення, а й отриману пропозицію перетворено до виду, де знаки заперечення стоять перед більш простими виразами. Наприклад, запереченням пропозиції виду А Ù В будемо вважати ні (А Ù В), а йому рівносильне: А Ú В.
Нехай А (х, у) - висказивательной форма з двома змінними.
Тоді ( "х) А (х, у), ($ х) А (х, у), (" х) А (х, у), ($ х) А (х, у) теж висказивательной форми але вже з однієї змінної. У цьому випадку говорять, що квантор пов'язує одну змінну. Щоб отримати з висказивательной форми А (х, у) висловлювання необхідно пов'язати обидві змінні. Наприклад, ( "х) ($ y) А (х, у) - висловлювання.
Для висказивательной форми Р (х, у): "x 1) ( "х) (" у) Р (х, у) Û л - "Для будь-якого х і для будь-якого у х 2) ( "у) (" х) (х 3) ($ x) ($ y) (x 4) ($ y) ($ х) (х 5) ( "х) ($ y) (x 6) ($ y) ( "х) (x 7) ( "у) ($ х) (х 8) ($ х) ( "у) (x `Зверніть увагу на висловлювання (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. ( 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 ) 7. (1 + £) Ú (- 1 <5x - 5) 8. (-> 2) Ú (- 3x - 1> 2); 9. (+ 6x> + 4) Ú (-> -); 10. (0,2 (2x - 3) 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 10. ( "x, y Î R) (x Схожі статті