Квантори та квантифікація предикатів

Існує інший спосіб перетворення предиката у формулу – квантифікація. Для цього використовуються спеціальні символи – квантори:

1. квантор загальності – " («для всіх»);

2. квантор існування – $ («існує»);

3. квантор існування і єдності – $! («існує єдиний»).

Якщо D ={ a₁, a₂,..., a_n } – скінченна предметна область змінної x у предикаті P(x), то можна скористатися логічними еквівалентностями " xP (x)= P (a₁)Ù P (a₂)Ù...Ù P (a_n) та $ xP (x)= P (a₁)Ú P (a₂) Ú...Ú P (a_n). У такому разі заперечення квантифікованої формули дає той самий результат, що й застосування відповідного закону де Моргана. Це випливає з того, що

Ø(" xP (x))=Ø(P (a₁)Ù P (a₂)Ù...Ù P (a_n))= , а це у свою чергу, еквівалентне $ x= .

Аналогічно,

Ø($ xP (x))=Ø(P (a₁)Ú P (a₂)Ú...Ú P (a_n))= ,

що еквівалентно .

Приклад 5.3. Нехай х – змінна, визначена на множині людей (D), а Р (х) – предикат «x – смертна». Задати словесне формулювання предикатної формули " хР (х).

Формула" хР (х)означає «всі люди смертні». Вона не залежить від змінної х, а лише характеризує всіх людей в цілому. ▲

Приклад 5.4. Нехай х – змінна, визначена на множині натуральних чисел (D), а Р (х) – предикат «x – парне число». Задати словесне формулювання предикатної формули $ хР (х) та визначити його істинність.

Формула$ хР (х)означає «в множині натуральних чисел існує парне число». Множина натуральних чисел містить парні, тому дане висловлювання істинне. ▲

Приклад 5.5. Нехай Р (х,у) – предикат «х любить у» на множині людей (D). Розглянути всі варіанти використання кванторів для обох змінних. Задати словесну інтерпретацію отриманим висловлюванням.

Випадок 1. " х $ у Р (х,у). Дане висловлювання означає, що «для будь-якої людини х існує людина у,яку вона любить»або «будь-яка людина когось любить»(рис.5.1).

Рис.5.1. "х$у Р(х,у)

Випадок 2. $ у " х Р (х,у). Дане висловлювання означає, що «існує людина у,яку любить будь-яка людина х»(рис.5.2).

Рис 5.2. $ у " х Р (х,у).

Випадок 3. " х " у Р (х,у). Дане висловлювання означає, що «всі люди х люблять всіх людей у»(рис.5.3).

Рис.5.3. "х"у Р(х,у).

Випадок 4. $ х $ у Р (х,у). Дане висловлювання означає, що «існує людина х, яка любить людину у»(рис.5.5).

Рис.5.4. $ х $ у Р (х,у).

Випадок 5. $ х " у Р (х,у). Дане висловлювання означає, що «існує людина х, яка любить всіх людей у»(рис.5.5).

Рис.5.5.$ х " у Р (х,у).

Випадок 6. " у $ х Р (х,у). Дане висловлювання означає, що «для будь-якої людини у існує людина х, яка її любить» або «кожну людину хтось любить»(рис.5.6).

Рис.5.6. " у $ х Р (х,у).

Із даного прикладу видно, що від перестановки кванторів загальності та існування змінюється суть висловлювання. ▲

Приклад 5.6. Позначимо речення «x – просте число» як P (x), «x –раціональне число” – як Q (x), «x – дійсне число» — як R (x) та „ x менше y ” – як МЕНШЕ(x, y). Розглянемо такі істинні твердження:

1. Кожне раціональне число дійсне.

2. Існує просте число.

3. Для кожного числа x існує таке число y, що x < y.

Наведені речення можна записати такими формулами.

1. " x (Q (x) → R (x)).

2. $ x P (x).

3. " x $ y МЕНШЕ(x,y). ▲

Означення 5.6. Перехід від P (x) до " xP (x) або $ xP (x) називають зв’язуванням предметної змінної x, а саму змінну x – зв’язаною. Незв’язану змінну називають вільною. У виразах " xP (x) та $ xP (x) предикат P (x) належить області дії відповідного квантора.

Приклад 5.7. Запишемо речення «Кожний студент групи вивчав дискретну математику» за допомогою предикатів і кванторів. Спочатку перепишемо речення так, щоб було зрозуміло, як краще розставити квантори: «Про кожного студента групи відомо, що цей студент вивчав дискретну математику». Тепер уведемо змінну x і речення набере вигляду: «Про кожного студента x групи відомо, що x вивчав дискретну математику». Уведемо предикат C (x): «x вивчав дискретну математику». Якщо предметна область змінної x – усі студенти групи, то можна записати задане речення як " xС (x). Є й інші коректні подання з різними предметними областями та предикатами. Зокрема, можна вважати, що нас цікавлять інші групи людей, окрім тих, які вчаться в одній академічній групі. Узявши як предметну область усіх людей, можна записати задане речення так: «Для кожної особи x, якщо ця особа x – студент групи, то x вивчав дискретну математику». Якщо предикат S (x) має вигляд «Особа x вчиться в групі», то задане речення треба записати у вигляді " x (S (x)→ C (x)). Зауважимо, що задане речення не можна записати як " x (S (x)Ù C (x)), бо тоді це означало б, що всі особи з предметної області вчаться в групі та вивчали дискретну математику. ▲

Приклад 5.8. Запишемо речення «Хтось зі студентів групи відвідав Париж» за допомогою предикатів і кванторів. Це речення аналогічне реченню «У групі є студенти(принаймі один), які відвідали Париж». Якщо ввести змінну x, то задане речення можна переписати так: «У групі є такий студент x, що x відвідав Париж». Уведемо предикат M (x), який відповідає реченню «x відвідав Париж». Якщо предметна область змінної x складається тільки зі студентів певної групи, то можна записати це речення як $ xM (x).

Якщо ж нас цікавлять інші особи, окрім студентів зазначеної групи, то перше із запропонованих речень матиме інший вигляд: «Є така особа x, що x – студент групи й x відвідав Париж». У такому разі предметна область складається з усіх можливих людей. Нехай S (x): «x – студент групи». Тоді речення має такий вигляд: $ x (S (x)Ù M (x)), бо воно містить повідомлення про те, що хтось – студент групи та відвідав Париж. Це речення не можна подати формулою $ x (S (x)→ M (x)), оскільки вона істинна навіть тоді, коли особа x – не студент групи. ▲

Приклад 5.9. Подамо формулу " x (C (x)Ú$ y (C (y)Ù F (x,y))) словами, якщо C (x) означає «x має комп’ютер», F (x,y) – «x та y – друзі», а предметна область для x і для y – усі студенти певного курсу. Зміст формули можна записати так: «Кожний студент курсу має комп’ютер або друга, у якого є комп’ютер». ▲

Приклад 5.10. Запишемо формулою логіки предикатів речення «Сума двох додатних чисел – додатнє число». Спочатку перепишемо це речення так: «Два довільні додатні числа дають у сумі додатнє число». Уведемо змінні x та y і отримаємо речення: «Будь-які додатні числа x та y утворюють суму x + y, яка являє собою додатнє число». Запишемо його формулою " x " у (((x >0)Ù(y >0))→(x + y >0)). Тут предметна область кожної змінної – усі дійсні числа. ▲

Поиск по сайту: