Розглянемо кілька пропозицій зі змінною:

- « - просте натуральне число»; область допустимих значень цього предикату – безліч натуральних чисел;

- « - парне ціле число»; область допустимих значень цього предикату – безліч цілих чисел;

- «
- рівносторонній»;

- «
»

- «студент отримав оцінку »

- « ділиться націло на 3»

Визначення. Якщо пропозиція зі змінними при будь-якій заміні змінних допустимими значеннями перетворюється на висловлювання, така пропозиція називається предикатом.

,
,
,
- предикати від однієї змінної (одномісні предикати). Предикати від двох змінних:
,
- Двомісні предикати. Висловлювання – нульмісцеві предикати.

Квантор спільності.

Визначення. Символ називається квантором спільності.

читається: для будь-кого , для кожного , для всіх .

Нехай
- Одномісний предикат.

читається: для будь-яких
- Істина.

приклад.

- «Всі натуральні числа прості» - Помилкове висловлювання.

- «Всі цілі числа парні» - Помилкове висловлювання.

- «Всі студенти отримали оцінку - одномісний предикат. Навісили квантор на двомісний предикат, отримали одномісний предикат. Аналогічно
-n-місцевий предикат, то

- (n-1)-місцевий предикат.

- (n-2)-місцевий предикат.

У російській мові квантор спільності опускається.

Квантор існування.

Визначення.Символ називається квантором існування.

читається: існує , є , знайдеться .

Вираз
, де
- одномісний предикат, читається: існує , для котрого
істинно.

приклад.

- «Існують прості натуральні числа». (і)

- «існують цілі парні числа». (і).

- «існує студент, який отримав оцінку - одномісний предикат.

Якщо на n-місцевий предикат навісити 1 квантор, то отримаємо (n-1)-місцевий предикат, якщо навіситиnкванторів, то отримаємо нульмісцевий предикат, тобто. висловлювання.

Якщо навішувати квантори одного виду, то порядок навішування кванторів байдужий. Якщо ж на предикат навішуються різні квантори, то порядок навішування кванторов міняти не можна.

Побудова заперечення висловлювань, які містять квантори. Закони Де Морган.

Закон Де Морган.

При побудові заперечення висловлювання, що містить квантор спільності, цей квантор спільності замінюється квантор існування, а предикат замінюється своє заперечення.

Закон Де Морган.

При побудові заперечення висловлювань, що містять квантор існування, потрібно квантор існування замінити на квантор спільності, а предикат
- Його запереченням. Аналогічно будується заперечення висловлювань, що містять кілька кванторів: квантор спільності замінюється на квантор існування, квантор існування – на квантор спільності, предикат замінюється своїм запереченням.

П.2. Елементи теорій множин (інтуїтивна теорія множин). Числові множини. Безліч дійсних чисел.

Опис множини: під словом безліч розуміється сукупність об'єктів, що розглядається як одне ціле. Замість слова "множина" іноді говорять "сукупність", "клас".

Визначення. Об'єкт, що входить до множини, називається його елементом.

Запис
означає, що є елементом множини . Запис
означає, що не є елементом множини . Про будь-який об'єкт можна сказати, є він елементом множини чи ні. Запишемо це твердження за допомогою логічних символів:

Немає об'єкта, який одночасно належить безлічі і належить, тобто,

Безліч неспроможна містити однакових елементів, тобто. якщо з множини, що містить елемент видалити елемент , то вийде безліч, що не містить елемент .

Визначення.Дві множини і називаються рівними, якщо вони містять ті самі елементи.

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

Р(х): "х - просте число". Підставивши х = 7, отримаємо висловлювання

"7 - просте число". Ми познайомимося ще з двома логічними операціями: навішування квантора спільності та квантора існування, які дозволяють одержати з висловлювальних форм висловлювання.

Підставимо перед висловлювальною формою Р(х) слово "будь-яке": "будь-яке х - просте число". Отримали хибне висловлювання. Підставимо перед Р(х) слово "деякі": " деякі числа х - прості". Отримали справжнє висловлювання.

У математиці слова "будь-які", "деякі" та їх синоніми називаються кванторами, які відповідно називаються квантор спільності (") і квантор існування ($). Квантор спільності замінюється в словесних формулюваннях словами: будь-який, всі, кожен, всякий і т.д. Квантор існування в словесному формулюванні замінюється словами: існує, хоча б один, який-небудь знайдеться і т.д.

Нехай Р(х) - висловлювальна форма на М.

("хІМ) Р(х)

означає: для будь-якого елемента х (з множини М) має місце Р(х), що вже являє собою висловлювання. Щоб довести, що висловлювання ("х)Р(х) - істинно, треба перебрати всі елементи а, b, с і т.д. з М і переконатися, що Р(а), Р(b), Р(с) ,... істинні, і, якщо неможливо перебрати елементи М, повинні довести за допомогою міркувань, що для будь-якого а з М висловлювання Р(а) істинно. один елемент αМ, для якого Р(а) хибно.

ПРИКЛАД. Дано висловлювальну форму

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

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

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

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

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

Чи можна сказати, що ("х)В(х)? Це необхідно доводити. Леонард Ейлер довів, що В(5) - хибно, тобто + 1 = 232 + 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). p align="justify"> Методом перебору переконаємося, що r 2 + 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) Ú (-> -);

Оператор, за допомогою якого про к.-л. окремому об'єкті перетворюється на висловлювання про сукупність (безліч) таких об'єктів.
У логіці використовується два основних До.: До. спільності, «V», і До. існування, «Е». У природній мові віддаленими смисловими аналогами До. спільності є слова "все", "будь-який", "кожен"; смисловими аналогами До. існування - слова «деякі», «існують». За допомогою даних До. будь-яке атрибутивне висловлювання виду Р(х) про те, що об'єкту х властиве Р, може бути перетворено на відповідне кванторне висловлювання виду VхР(х) та виду ЗхР(х). Змістовно сама кванторна формула "VxP(x)" читається як "для всіх х має Р(х)", а формула "ЕхР(х)" - як "для деяких х має місце Р(х)". Висловлювання виду VxP(x) істинно, якщо будь-х володіє властивістю Р; і хибно, якщо хоча б один х не має властивість Р. Аналогічним чином, висловлювання виду ЗхР(х) істинно, якщо хоча б один х має властивість Р; і хибно, якщо жоден х не має властивості Р.
На основі елементарних кванторних формул "VxP(x)", "ЕхР(х)" можуть бути побудовані ін, більш складні кванторні формули. Логічні взаємозв'язки між такими формулами вивчаються у логіці предикатів. Зокрема, формула «ЗхР(х)» логічно еквівалентна формулі «) VxКВАНТОР| P(x)», а формула «VхР(х)» еквівалентна формулі «) Ех) Р(х)», де «)» - заперечення.
У неявній формі К. використовувалися вже Аристотелем, однак у строгому змістовному та формальному сенсі вони вперше були введені у логіку Г. Фреге.

Філософія: Енциклопедичний словник. - М: Гардаріки. За редакцією А.А. Івіна. 2004 .

(від лат. quantum - скільки), оператор логіки предикатів, застосування крого до формул, що містять лише одну вільну змінну, дає (висловлювання). Розрізняють До. спільності, що позначається символом (від англ. all - все), та К. існування (від exist - існувати): хР(х) інтерпретується (див.Інтерпретація)як «для всіх х має місце властивість Р», а хР(х) - як «існує х такий, що має місце властивість?(х)». Якщо (Універсум)кінцева, то хР(х) рівносильно кон'юнкції всіх формул Р (а)де а - елемент предметної області. Аналогічно, хР(х) рівносильно диз'юнкції всіх формул виду? (а). Якщо ж предметна область нескінченна, то xP (x)і хР(х) можуть бути витлумачені відповідно як нескінченні та диз'юнкції. Введення К. у логіці багатомісних предикатів (тобто.неодномісних)обумовлює нерозв'язність обчислення предикатів. Різні співвідношення між К. спільності та існування та логічними зв'язками логіки висловлювань формалізуються у обчисленні предикатів.

Філософський енциклопедичний словник. - М: Радянська енциклопедія. Гол. редакція: Л. Ф. Іллічов, П. Н. Федосєєв, С. М. Ковальов, В. Г. Панов. 1983 .

(від лат. quantum – скільки) – логіч. оператор, що застосовується до логіч. виразам і дає кількості. характеристику області предметів (а іноді і області предикатів), до якої відноситься одержуване в результаті застосування К. . У те, як логіч. засобів логіки висловлювань недостатньо для висловлювання форм загальних, приватних і поодиноких суджень, у логіці предикатів, одержуваної у вигляді розширення логіки висловлювань з допомогою запровадження До., такі судження виразні. Так, напр., чотири осн. форми суджень традиц. логіки "Всі А суть В", "Жодне А не є В", "Нек-рі А суть В" і "Нек-рі А не суть В" можуть бути записані (якщо відволіктися від передбачуваного аристотелевою логікою вимоги непустоти А в загальних судженнях) за допомогою символіки нижче: ) & В (х)) та ∃ (х) (А (х) & B (x)). Введення До. дає записувати на формалізованому логіч. мові висловлення єств. мови, що містять кільк. Показники к.-л. предметних чи предикатних областей. Природ. мовами носіями таких характеристик є т.з. кванторні слова, до яких належать, зокрема, кількостей. чисельні, займенники "все", "кожен", "нек-рий", дієслово "існує", прикметники "будь-який", "всякий", "єдиний", прислівники "нескінченно багато" і т.п. Виявляється, що висловлювання всіх згаданих кванторних слів у формаліз. мовами та логіч. обчислення досить двох найбільш вживе. К.: К. спільності (або в с в о щ н о с т і), що позначається зазвичай символом ∀(перевернута літера А – початкова літера англ. слова "all", нім. "alle" та ін), і К. с іс т в о в а н і я, що позначається зазвичай символом ∃ (перевернута літера E – початкова літера англ. слова "exist", нім. "existieren" та ін); за знаками ∀ і ∃ в позначенні К. слід буква деякого алфавіту, звана кванторною змінною, к-рую розглядають зазвичай як частина позначення К.: ∀х, ∀у, ∀F, ∃х, ∃α і т.п. Для До. спільності використовують також позначення:

для К. існування:

Знак До. ставиться перед виразом, до якого застосовується До. (операцію застосування До. часто називають квантифікацією); цей вислів полягає в дужки (які часто опускають, якщо це не призводить до двозначності). Вираз ∀x (А(х)), що містить К. спільності, читається як "Для всіх x вірно, що А(х)", або "Для кожного x вірно А(х)"; що містить До. існування вираз ∃х (А(х)) читається як "Існує x такий, що А(х)", або "Для деякого x вірно А(х)". В обох цих випадках не передбачається, взагалі кажучи, що вираз A (х) насправді залежить від змінної x (може і взагалі не містити жодних змінних, тобто може позначати деяке висловлювання; в цьому випадку не змінює сенсу цього висловлювання) ). Проте осн. призначення К. - висловлювань з виразу, що залежить від кванторної змінної, або хоча б зменшення числа змінних, від яких брало це вираз, будучи незамкнутою (відкритою) формулою (див. Замкнена формула), залежить. Напр., вираз (y>0&z>0&x=у-z) містить три змінні (х, y та z) і стає висловлюванням (істинним або хибним) при к.-л. визна. заміщення цих змінних іменами деяких предметів з області їх значень. Вираз ∃ z(y>0&z>0&x = y-z) залежить вже лише від двох змінних (х і у), a ∃y∃z (y>0&z>0& &х = у –z) - від однієї х. Остання формула виражає, т.ч., деяку властивість (одномісний). Нарешті, формула ∃х∃у∃z (y>0&z>0&x=y–z) висловлює цілком визна. висловлювання.

Др. приклади формул, що містять К.: 1) ∀х(х>0); 2) ∃х(х>0); 3) ∀х (2+2=5); 4) ∃x (2+2=4); 5) ∀х (х = х)&(х+2=у); 6) ∀х∃у (∀z (x = z⊃x ≠ 0) & (x дія к.-л. К., наз. областю дії цього К. Так, у формулі 6) областями дії К. ∀х і ∃y є частиною формули, що стоять праворуч від них, а область дії К. ∀z - формула (x = z⊃x ≠ 0).Входження к.-л. , названим пов'язаним входженням змінної у формулу.В інших випадках входження змінної назви з в о д н н м. Одна і та ж може входити в к.-л.формулу в одному місці у зв'язаному вигляді, а в ін. місці - у вільному.Така, напр., формула 5): перші три (вважаючи ліворуч) входження до неї змінної x - пов'язані, останнє ж - вільне. Іноді кажуть, що змінна пов'язана у цій формулі, якщо всі її входження до цієї формули – пов'язані. У математиці та логіці будь-яке вираз, що містить вільну змінну, може розглядатися (при неформальному підході) як її в тому звичайному значенні цього слова, що воно (вираз) залежить від різних значень цієї змінної; надаючи цій змінній різні значення(Тобто заміщаючи всі її вільні входження ім'ям к.-л. предмета, що належить до області значень цієї змінної), ми отримуємо різні (власне кажучи) значення цього виразу, що залежать від значення змінної, тобто. від підставленої замість неї константи. Що ж до пов'язаних змінних, то їхні висловлювання насправді від них не залежать. Напр., вираз ∃х(х = 2у), що залежить від у (що входить до нього вільно), еквівалентно виразам ∃z(z = 2y), ∃u(u = 2у) тощо. Ця логіч. виразів від що входять у яких пов'язаних змінних знаходить у т. зв. правилі перейменування з зв'язаних перемінних, постулюваному або виведеному в разл. логіч. обчисленнях (див. Змінна , Предикатів обчислення).

Викладене вище тлумачення сенсу К. ставилося до складу л ь ні м логіч. теоріям. Що ж до обчислень у прив. сенсі (т.зв. формальних систем), то них взагалі немає сенсу говорити про " значення " тієї чи іншої До., що є тут просто деяким символом обчислення. Питання про значення (сенсі) К. відноситься цілком до галузі інтерпретації обчислення. У застосуванні до К. можна говорити принаймні про три інтерпретації: класичну, інтуїціоністську та конструктивну, що відповідають різним концепціям існування та загальності в логіці та математиці (див. Інтуїціонізм, Конструктивна логіка). Як у класич., Так і в інтуїціоністському (конструктивному) обчисленні предикатів способи виведення у випадках, коли вихідні або доводять формули містять До., описуються одними і тими ж т. н. постулатами квантифікації, напр. постулатами Бернайсу.

До. спільності та існування не вичерпуються вживані в логіці види До. Великий До. є т.з. обмежені К. виду ?P(x)А(х) або ?xQ(x)A(x), в яких брало область зміни кванторної змінної x "обмежена" деяким спец. предикатом Р(х) (або Q(x)). Обмежені До. зводяться до До. спільності та існування за допомогою слід. еквівалентностей: ∀xP(x)A(x) КВАНТОР∀x(P(x) ⊃A(x)) та ∃xQ(x)A(x) КВАНТОР ∃x(Q(x)&A(x)). Часто вживаний До. єдиності ∃!хА(х) ("є єдине x таке, що А(х)") також виражається через До. спільності та існування, напр. так: xA(x) КВАНТОР ∃xA(x)& ∀y∀z(A(y)&A(z)⊃y=z).

Вживані та ін. види До., що не покриваються поняттям обмеженого До. Такі "числові" До. виду ∃хnА(х) ("існує в точності n різних x таких, що А(х)"), що вживається в інтуїціоністській логіці До. "квазііснування" ∃ хА(х), або ("невірно, що не існує такого х, що А(х)"); з т. зр. класич. логіки К. "квазііснування" нічим не відрізняється від К. існування, в інтуїціоністській ж логіці пропозиція ∃xA(x), що нічого не говорить про існування алгоритму для знаходження такого х, що А(х), справді стверджує лише "квазі" такого x і К. нескінченності ∃x∞A(x) ("існує нескінченно багато таких х, що А(х)"). Вирази, що містять До. нескінченності та числові До., також можуть бути записані за допомогою До. спільності та існування. У розширеному обчисленні предикатів К. беруться не лише за предметними, але й за предикатними змінними, тобто. розглядаються формули виду ∃F∀xF(x), ∀Ф∃у(Ф(y)) тощо.

Літ.:Гільберт Д. та Аккерман Ст, Основи теоретичної логіки, пров. з англ., М., 1947, с. 81-108; Тарський А., Введення в логіку та методологію дедуктивних наук, пров. з англ., М., 1948, о. 36-42, 100-102, 120-23; Кліні С. К., Введення в метаматематику, пров. з англ., М., 1957, с. 72-80, 130-38; Черч А., Введення в математичну логіку, пров. з англ., т. 1, с. 42-48; Кузнєцов А. Ст, Логічні контури алгоритму, перекладу зі стандартизованої російської мови на інформаційно-логічну, в сб.: Тези доповідей на конференції з обробки інформації, машинного перекладу та автоматичного читання тексту, М., 1961; Mostowski A., On a generalization of quantifiers, " Fundam. math. " , 1957, t. 44, No 1, p. 12–36; Hailperin T., Теорія з обмеженою quantification, I-II, "J. Symb. Logic", 1957, v. 22, No 1, p. 19-35, No 2, p. 113–29.

Ю. Гастєв. Москва.

Філософська енциклопедія. У 5-х т. – М.: Радянська енциклопедія. За редакцією Ф. В. Константинова. 1960-1970 .

Синоніми:

Дивитися що таке "КВАНТОР" в інших словниках:

Сущ., кіл у синонімів: 1 оператор (24) Словник синонімів ASIS. В.М. Трішин. 2013 … Словник синонімів

квантор- - Тематики електрозв'язок, основні поняття EN quantifier... Довідник технічного перекладача

Квантор загальна назва для логічних операцій, що обмежують область істинності якогось предикату і створюють висловлювання. Найчастіше згадують: Квантор загальності (позначення: , Читається: «для всіх…», «для кожного…» або «кожен…» … Вікіпедія

Загальна назва для логічних операцій, які за предикатом Р(х) будують висловлювання, що характеризує область істинності предикату Р(х). У математич. логіці найбільш уживані квантор загальності та квантор існування Висловлювання означає,… Математична енциклопедія

Квантор- (від лат. quantum скільки) символ, який використовується для позначення деяких операцій математичної логіки, одночасно логічна операція, що дає кількісну характеристикуобласті предметів, яких відноситься вираз, одержуваний в… … Початки сучасного природознавства

Крім відомих нам логічних операцій для предикатів запроваджуються дві нові: операція навішування кванторів існування та спільності.

"для всіх х» (для будь-якого х, для кожного х) називається квантором спільностіі позначається х.

Висловлювання «існує х" (для деяких х, хоча б для одного х,знайдеться таке х) називається квантором існуванняі позначається х.

Висловлювання «існує одне і тільки одне х»(для єдиного значення х) називається квантором єдиності : ! х.

Наприклад: "Всі чагарники є рослинами". Цей вислів містить квантор спільності («все»). Висловлювання «існують числа, кратні 5 » містить квантор існування («існують»).

Щоб отримати висловлювання з багатомісного предикату, треба зв'язати кванторами кожну змінну. Наприклад,якщо Р(х; у)- двомісний предикат, то (хХ) (уY) Р(х; у)- Висловлювання.

Якщо кожна змінна пов'язується квантором, то виходить не висловлювання, а предикат, залежить від зміною, яка пов'язана квантором. Так, якщо перед предикатом Р(х; у)поставити квантор у,то отримаємо предикат (уY) Р(х; у), що залежить від змінної х.

З'ясуємо, які з наступних речень є висловлюваннями, а які предикатами: а) знайдеться таке х,що х+ у = 2;

b) для будь-яких хі умає місце рівність х + у = у + х.

Рішення: Виявимо логічну структуру даних речень.

а) Пропозиція «Знайдеться таке х,що х + у = 2» можна записати у вигляді (хR) х + у = 2.Так як квантор пов'язана тільки змінна х, то пропозиція з двома змінними є предикатом.

b) Пропозиція «для будь-яких хі умає місце х + у = у + х» можна записати у вигляді : (хR) (уR) х + у = у + х,де обидві змінні є пов'язаними. Отже, ця пропозиція є висловлюванням.

Якщо якесь предметне змінне у формулі не пов'язане квантором, то його називають вільним змінним.

Наприклад: (х) ху = ух.Тут змінне уне пов'язано будь-яким квантором, тому воно вільне. Від нього залежить істинність цього висловлювання.

Квантори (х) (х) називаються двоїстимиодин одному.

Одноіменні квантори можна міняти місцями, що впливає істинність висловлювання.

Наприклад: (у) (х) х + у = 5.Це твердження має той самий сенс, що і (х) (у) х + у = 5.

Для різноїменних кванторів зміна порядку може призвести до зміни істинності висловлювання.

Наприклад: (х) (у) х<у , тобто. для кожного числа хіснує більша кількість у- Справжнє висловлювання.

Поміняємо місцями квантори: (х) (у) x існує число убільше будь-якого числа х- хибне висловлювання.

У зв'язку із запровадженням кванторов необхідно врахувати таке:

1. Формула логіки предикатів не може містити те саме предметне змінне, яке було б пов'язане в одній частині формули і вільно в іншій.

2. Одне й те змінне неспроможна перебувати у сфері двоїстих один одному кванторов.

Порушення цих умов називають колізією змінних.

Як встановлюється значення істинності висловлювання із квантором?

Для доказу затвердження із квантором спільності необхідно переконатися в тому, що при підстановці кожного значення ху предикат Р(х)останній звертається до справжнього висловлювання. Якщо безліч Х звичайно, це можна зробити шляхом перебору всіх випадків; якщо ж безліч Х нескінченно, необхідно провести міркування в загальному вигляді.

Висловлювання (х) Р(х)помилково, якщо можна вказати таке значення аХ, за якого Р(х)звертається у хибне висловлювання Р(а).Тому, для спростування висловлювання з квантором спільності Досить навести приклад.

Висловлювання (х) Р(х)істинно, якщо можна вказати таке значення аХ, за якого Р(х)звертається до справжнього висловлювання Р(а). Тому, щоб переконатися у істинності висловлювання з квантором існування , достатньо навести приклад і в такий спосіб довести.

Для того щоб переконатися у хибності висловлювання з квантором існування (х) Р(х),необхідно переконатися у хибності кожного Р(х), Р(х), …, Р(х). Якщо безліч Хзвичайно, це можна зробити перебором. Якщо ж безліч Хнескінченно, необхідно провести міркування у загальному вигляді.

Приклади.

1. Знайти значення істинності «средичисел 1, 2, 3, 4 знайдеться просте число».

Рішення:Вислів містить квантор існування і тому може бути представлений у вигляді диз'юнкції висловлювань: « 1 - просте число» або « 2 - просте число» або « 3 - просте число» або « 4 - просте число". Для доказу істинності диз'юнкції достатньо істинності хоча б одного висловлювання, наприклад, « 3 - просте число», яке є істинним. Отже, істинне та вихідне висловлювання.

2. Доведемо, що будь-який квадрат є прямокутником.

Рішення:Вислів містить квантор спільності. Тому воно може бути представлене у вигляді кон'юнкції: «квадрат – прямокутник» та «квадрат – прямокутник» і «квадрат – прямокутник» і т.д. Оскільки всі ці висловлювання істинні, то істинна кон'юнкція цих висловлювань, отже, істинна і вихідна пропозиція.

3. «Будь-який трикутник рівнобедрений». Це хибне висловлювання. Щоб переконатися в цьому, достатньо накреслити трикутник, що не є рівнобедреним.

Для побудови заперечення висловлювання з кванторамитреба:

1) квантор спільності замінити квантором існування, а квантор існування – квантором спільності;

2) предикат замінити його запереченням.

приклад. Сформулюємо заперечення для наступних висловлювань:

а) всі елементи множини Zпарні; b) деякі дієслова відповідають питанням «що робити?».

Рішення:а) Замінимо квантор спільності квантором існування, а висловлювання його запереченням: деякі елементи множини Zнепарні.

b) Замінимо квантор існування квантором спільності, а вираз його запереченням: всі дієслова не відповідають питанням «що робити?».

Функціональна природа предикату спричиняє запровадження ще одного поняття – квантора. (quantum - від лат. "скільки") Кванторні операції можна розглядати як узагальнення операцій кон'юнкції та диз'юнкції у разі кінцевих та нескінченних областей.

Квантор спільності (все, кожен, кожен, кожен (all – «всякий»)). Відповідні йому словесний вираз звучить так:

«Для всякого x Р(x) істинно». Входження змінної у формулу може бути пов'язаним, якщо змінна розташована безпосередньо після знака квантора, або в області дії квантора, після якого стоїть змінна. Всі інші входження – вільні, перехід від P(x) до x(Px) або (Px) називається зв'язуванням змінної x або навішуванням квантора на змінну x (або предикат P) або квантифікацією змінної х. Змінна, на яку навішується квантор, називається пов'язаною, незв'язана квантування змінна називається вільною.

Наприклад, змінна x у предикаті Р(x) називається вільною (x – будь-яке з М), у висловлюванні Р(x) змінну x називають пов'язаною змінною.

Справедлива рівносильність P(x1)P(x2)…P(xn),

P(x) – предикат, визначений на множині М=(х 1 ,х 2 ...х 4 )

Квантор існування(exist - "існувати"). Словове вираз, відповідне йому, звучить так: “Існує x, у якому Р(x) істинно”. Висловлювання xР(x) не залежить від x, змінна x пов'язана квантором .

Справедлива рівносильність:

xP(x) = P(x1)P(x2)…P(xn), де

P(x) - предикат, визначений на множині М = (x 1, x 2 ... x n).

Квантор спільності та квантор існування називають двоїстими, іноді використовується позначення квантора ! – «існує, і до того ж, тільки один».

Зрозуміло, що висловлювання xP(x) істинно лише тому випадку, коли Р(x) - тотожно істинний предикат, а висловлювання хибно лише тоді, коли Р(x) - тотожно помилковий предикат.

Кванторні операції застосовуються і до багатомісних предикатів. Застосування кванторної операції до предикату P(x,y) по змінній x ставить у відповідність двомісному предикату P(x,y) одномісний предикат xP(x,y) або xP(x,y), що залежить від у і не залежить від х.

До двомісного предикату можна застосувати кванторні операції з обох змінних. Тоді отримаємо вісім висловлювань:

1. P(x,y); 2. P(x,y);

3. P(x,y); 4. P(x,y);

5. P(x,y); 6. P(x,y);

7. P(x,y); 8. P(x,y)

Приклад 3.Розглянути можливі варіанти навішування кванторів на предикат P(x,y) – “xділиться на y”, визначений на безлічі натуральних чисел (без нуля) N. Дати словесні формулювання отриманих висловлювань та визначити їхню істинність.

Операція навішування кванторів призводить до наступних формул:

Висловлювання "для будь-яких двох натуральних чисел має місце ділимість одного на інше" (або 1) всі натуральні числа поділяються на будь-яке натуральне число; 2) будь-яке натуральне число є дільником для будь-якого натурального числа) хибні;

Висловлювання “існують такі два натуральні числа, що перше ділиться на друге” (1. «існує таке натуральне число x, яке ділиться на якесь число y»; 2. «існує таке натуральне число y, яке є дільником якогось натурального числа числа x») істинні;

Висловлювання "існує натуральне число, яке ділиться на будь-яке натуральне", хибне;

Висловлювання "для будь-якого натурального числа знайдеться таке натуральне, яке ділиться на перше" (або для будь-якого натурального числа знайдеться своє ділене), істинне;

Вислів “для будь-якого натурального x існує таке натуральне число y, на яке воно ділиться” (або “для будь-якого натурального числа знайдеться свій дільник”), дійсне;

Висловлювання "існує натуральне число, яке є дільником будь-якого натурального числа", істинне (таким дільником є ​​одиниця).

У випадку зміна порядку проходження кванторов змінює сенс висловлювання та її логічне значення, тобто. наприклад, висловлювання P(x,y) та P(x,y) різні.

Нехай предикат P(x,y) означає, що x є матір'ю для y, тоді P(x,y) означає, що кожна людина має матір – справжнє твердження. P(x,y) означає, що є мати всіх людей. Істинність цього твердження залежить від безлічі значень, які можуть набувати y: якщо це безліч братів і сестер, то воно істинне, інакше воно хибне. Таким чином, перестановка кванторов загальності та існування може змінити сам сенс та значення виразу.

а) замінити початковий знак (або ) на протилежний

б) поставити знак перед рештою предикату