Квантори

Квантор загальності, квантор існування, зв'язана та вільна змінна, зменшення порядку п-місних предикатів

При визначенні істиннісного значення предиката неабиякий інтерес становить питання: чи є він істинним при будь-якому значенні предметної змінної або чи існує хоча б одне значення змінної, при якому цей предикат істинний. Наприклад, твердження «Всі прості числа мають два дільника» можна формалізувати за допомогою предиката МАТИ_ДВА_ДІЛЬНИКА(х), який є істинним для всіх х у предметній області простих чисел. Твердження «Існують натуральні числа, які не діляться на 2» означає, що предикат ДІЛИТЬСЯ_НА_2(х) істинний не для всіх х у предметній області натуральних чисел.

Визначення

Нехай Р(х)— предикат, визначений на М. Висловлення «для всіх х Î М, Р(х) істинне» позначається "х Р(х). Знак " називається квантором загальності.

Квантори керують областю значення змінної, наступної за символом квантора. Якщо застосовується квантор загальності, то ми говоримо, що висловлення істинне для всіх х з деякої множини.

Визначення

Висловлення «існує таке х Î М, що Р(х) істинне» позначається $х Р(х),де знак $ називається квантором існування.

Квантор існування застосовується, коли треба вказати, що існує хоча б одне значення змінної, для якого істинне це висловлення.

В логіці предикатів (або першого порядку) існує таке обмеження: не можна застосовувати квантори до предикатів. Наприклад, не можна записати "P Р(х). Однак такі операції здійсненні у логіках більш високих порядків.

Визначення

Перехід від Р(х) до "x P(x) або $х Р(х)називається зв'язуванням змінної х, а сама змінна х у цьому випадку — зв'язаною.

Визначення

Змінна, не зв'язана ніяким квантором, називається вільною.

Від того, чи є змінна зв'язаною або вільною, залежить значення предиката. Вільна змінна — це предметна змінна, яка може приймати різні значення з множини М,і значення предиката Р (х) залежить від значення змінної х. Навпаки, вираз "x Р(х) не залежить від змінної х і при заданих Р і М має визначене значення; тут х — зв'язана змінна.

Зв'язані змінні зустрічаються не тільки у логіці. Наприклад, у виразах або змінна х зв'язана і дані вирази при фіксованих а, b і f мають визначені значення, не залежні від будь-якого значення х.

Приклад. Записати у вигляді предикатів з кванторами такі висловлення: «Всі студенти складають іспити», «Деякі студенти складають іспити на відмінно».

Розв'язок. Введемо предикати: Р — «складати іспити» і Q—«складати іспити на відмінно». Предметна область да­них предикатів являє множину студентів. Тоді вихідні вирази набудуть вигляду:

"(x) Р(х) і $(х) Q(x).

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

«Для всіх х правильно, що (х - 1)² = х² - 2х + 1»;

«Існує число, квадрат якого дорівнює 4».

Розв'язок. Введемо предикат ДОРІВНЮЄ(х, у),який істинний у тому випадку, якщо значення змінної х дорівнює значенню у. Тоді, використовуючи квантори, можна записати:

"x ДОРІВНЮЄ((х - 1)², (х² - 2х + 1));

$х ДОРІВНЮЄ(x², 4).

Застосування кванторів до багатомісних предикатів зменшує кількість вільних змінних, від яких залежить цей предикат. Нехай А(х, у)— деякий двомісний предикат, визначений на довільній множині М. Квантор загальності і квантор існування можна застосувати до неї як для змінної х, так і для змінної у:

; ; ; .

Всі чотири наведені вирази є записами одномісних предикатів від відповідної вільної змінної. Так, — одномісний предикат від змінної у: . Предикат F істинний точно для такихелементів b Î М, для якихпредикат А(х, b) істинний на всіх значеннях аргументу х. Якщо зобразити множину значень істинності предиката А(х, у)у вигляді матриці, то предикат F(y) = "x A(x, у)істинний для таких у = b, для яких стовпчик аргументу у = b містить виключно букву I. Для ілюстрації нижче наведено матрицю предиката (таблиця 5.6), що визначений на множині М з п'яти елементів a₁, а₂, а₃, а₄, а₅,і матриці одномісних предикатів (таблиці 5.7-5.10), що одержані з вихідного за допомогою застосування кванторів.

Подібним чином "y А(х, у)= С(х) — одномісний предикат від х, що істинний для таких а Î М,для яких рядок аргументу х = а містить тільки букву І. Предикат $х А(х, у) = =Н(у)істинний для таких а Î М, для яких відповідний стовпчик у = b містить, щонайменше, один раз букву I. Нарешті, предикат $y А(х, у)істинний для таких х = а Î М, для яких у відповідному рядку х = а зустрічається буква І.

Таким чином, застосування квантора за однією із змінних двомісного предиката перетворює його на одномісний. У випадку трьохмісних предикатів застосування квантора призводить до двомісного предикату. Аналогічно, для n-місних предикатів застосування квантора за будь-якою змінною перетворює предикат на(n - 1)-місний, тобто зменшує його порядок на одиницю.

Квантор загальності можна інтерпретувати як узагальнення кон'юнкції, а квантор існування — як узагальнення диз'юнкції. Насправді, якщо область визначення М предиката Р скінченна, наприклад, М = {а₁, а₂, ..., а_п}, то висловлення "х Р(х)еквівалентне кон'юнкції Р(a₁) Ù Р(а₂)Ù ... Ù Р(а_п),а висловлення $х Р(х)— диз'юнкції Р(a₁) Ú Р(а₂)Ú ... Ú Р(а_п).

Як приклад розглянемо предикат Р(х), який означає «х — непарне число» і визначений на області М = {а, b, с}.Висловлення "х Р(х)означає: «а — непарне число, і b — непарне число, і с— непарне число»; а висловлення $х Р(х)означає те ж, що і диз'юнкція «а — непарне число, або b— непарне число, або с— непарне число».

Запитання

1. Що розуміють під квантором загальності?

2. Дайте визначення поняттю квантор існування.

3. Які змінні називаються зв'язаними, а які — вільними?

4. Поясніть на прикладах призначення зв'язаних змінних.

5. До яких наслідків призводить застосування квантора за однією із змінних n‑місного предиката?

6. Скількома різними способами може бути застосований квантор існування до n‑місного предикату?

7. Коли предикат "х А(х, у) приймає значення «Істина»?

Завдання

1. Запишіть такі висловлення, використовуючи знаки кванторів:

а) існує число х таке, що х + 1 = 5;

б) яким би не було число у, у + 0 = у;

в) будь-яке число або додатне, або від'ємне, або дорівнює нулю.

2. Вкажіть вільні та зв'язані входження кожної із змінних у таких формулах:

а) "x Р(х, у) Ù "y Q(y);

б) "x (Р(х) ® Р(.у));

в) "x (Р(х) ® Q(y))Ú $у R (х, у);

г) "x [(Р(x) ® Q(y)) Ú $y R (х, у)].

3. Нехай х і у— будь-які люди, Q(x, у)означає «х батько у».Наведені висловлення сформулюйте природною мовою, визначивши їх значення істинності:

а) "х $у Q(x, у);

б) $х "y Q(x, у);

в) "y $х Q(x, у);

г) $у "x Q(x, у);

д) "х "y Q(x, у);

e) $x $у Q(x, у).

4. Нехай N(x) — «х — натуральне число», С(х) — «х — ціле число», Р(х) — «х — просте число», Е(х)— «х — парне число», О(х)— «х— непарне число», D(x, у)— «у ділиться на х». Сформулюйте природною мовою наведені висловлення, встановивши їх значення істинності:

а) P(z);

б) E(2) Ù Р(2);

в) "x (D(2, х) ® E(х));

г) $х (E(х) Ù D(x, 6));

д) "x [P(x) ® $у (E(y) Ù D(x, y))];

е) "x (N(x) ® C(x));

ж) $х (N(x) ® C(x));

з) "x (C(x) ® N(x));

і) "x "y [O(x) ® (Р(у) ® D(х, у))];

к) "x [С(х) ® (Е(х)Ú ØE(х))];

л) $х "y [(С(х) Ù C(y)) ® D(x, у)];

м) "x "y [(E(x) Ù O(x)) ® ØD(x, y)

5. Предикат Р(х, у) задано в предметній області D = {а, b} такою матрицею:

Яка з нижченаведених формул визначає цей предикат?

а) "x Р(х, а);

б) "y Р(а, у);

в) $у "x Р(х, у);

г) "y "x P(x, у);

д) "y "x ØР(х, у).