Визначення

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

Від того, чи є змінна зв'язаною або вільною, залежить значення предиката. Вільна змінна — це предметна змінна, яка може приймати різні значення з множини М,і значення предиката Р (х) залежить від значення змінної х. Навпаки, вираз "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 А(х, у)істинний для таких х = а Î М, для яких у відповідному рядку х = а зустрічається буква І.

Таблиця 5.6. Предикат А(х, у)		Таблиця 5.7. Предикат "x A(x, у)
Y X	a₁	a₂	a₃	a₄	a₅	y	" x A (x, y)
a₁	I	I	X	I	X	a₁	X
a₂	X	I	X	I	X	a₂	I
a₃	I	I	X	I	I	a₃	X
a₄	X	I	X	I	X	a₄	I
a₅	I	I	X	I	I	a₅	X

Таблиця 5.8 Предикат $ x A (x, y)		Таблиця 5.9. Предикат " y A (x, y)		Таблиця 5.10. Предикат $ y A (x, y)
y	$ x A (x, y)		x	" y A (x, y)	x
a₁	I		a₁	X	a₁	I
a₂	I		a₂	X	a₂	I
a₃	X		a₃	X	a₃	I
a₄	I		a₄	X	a₄	I
a₅	I		a₅	X	a₅	I

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

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

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Визначення	\|	Визначення

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.