Материал: discrete_mathematics
Вираз x читають також як усі x; для кожного x; для довільного x; для будь-якого x; а вираз x – як деякий x; для деякого x; знайдеться такий x тощо.
Зазначимо, що, крім уведених символічних позначень кванторів, використовують також інші позначення. Наприклад, за-
мість x іноді пишуть (x), (x) або x, а замість x – відповідно
(x), (Ex) або x.
Приклад 1.19.
1. Розглянемо два бінарні предикати на множині натуральних чисел N: предикат x менше y та предикат x ділить y. Перший із них записуватиме у традиційній формі x < y, а другий – у вигляді x | y. Тоді неважко переконатись, що висловлення:
x y(x < y) та x y(x | y) є істинними,y x(x < y) та y x(x | y) є хибними.
Істинними будуть, наприклад, висловлення
x(0 < x2 – x + 1),x((x | 1) (← (1 < x))),
x((x < 1) → (x < 2)),
x(((2 | x) (3 | x)) → (6 | x)),
а хибними –
x(2| x), x(x2 < 0), x((3 | x) → (6 | x)).
2.Записати формулою логіки предикатів такі твердження: (а) Існує таке x, що P(x) – хибне;
(б) Існує таке x, що P(x) – хибне. (а) x(← P(x)); (б) ← xP(x).
3.У цій вправі предметна область є множиною R дійсних чисел. Визначити, чи є даний вираз висловленням або пропозиційною формою. У першому випадку вказати, істинним чи хибним
євисловлення; у другому – здійснити квантифікацію так, щоб одержати істинне висловлення:
(а) y (x < y); (б) x y z (xy = z).
Розглянемо (а). Це пропозиційна форма. Перетворити її на істинне висловлення можна, наприклад, так:
x y (x < y) (або x y (x < y)).
Розглянемо (б). Це істинне висловлення. У ньому виражено твердження, що для будь-яких дійсних чисел x та y існує дійсне число z, яке є їхнім добутком. ◄
62
Важливу роль у логіці предикатів відіграє поняття області дії квантора у заданій формулі, під якою розумітимемо той вираз (підформулу), до якого належить квантор. Область дії квантора позначають за допомогою дужок. Ліва дужка, що відповідає початку області дії, записується безпосередньо після кванторної змінної даного квантора, а відповідна до неї права дужка означає закінчення області дії цього квантора. Там, де це не викликає невизначеності, дужки можна опускати й замість x(P(x)) або x(P(x)) писати відповідно xP(x) або xP(x). Це означає, що операції квантифікації мають більший пріоритет, ніж логічні операції.
Приклад 1.20. В усіх нижченаведених кванторних виразах область дії квантора підкреслено:
x((3 | x) → (6 | x)), x(3 | x) → (6 | x),x((x2 < 9) → (x < 3)), x(x2 < 9) → (x < 3).
Перший і другий вирази з останнього прикладу, а також третій і четвертий відрізняються не лише областю дії квантора. Відмінність між ними істотніша, і про це слід сказати окремо.
Розглянемо на універсальній множині R дійсних чисел вирази: x2 < 10 та x(x2 < 10).
Перший із них є предикатом, що залежить від змінної x. Замість x до нього можна підставляти різні дійсні значення й отримувати певні висловлення (істинні чи хибні). Та сама предметна змінна x входить до другого виразу інакше. Якщо замість неї підставити будь-яке дійсне значення, то дістанемо беззмістовний вираз.
Нехай P(x) – деякий предикат на M. Перехід від P(x) доxP(x) або xP(x) називають зв'язуванням змінної x. Інші назви
– навішування квантора на змінну x у предикаті P(x) (або на предикат P(x)), квантифікацією змінної x. Змінну x, на яку навішено квантор, називають зв'язаною, інакше змінну x назива-
ють вільною.
Зауважимо, що така ситуація не виняткова й доволі часто зустрічається в інших розділах математики. Наприклад, у виразах
b |
|
n |
|
∫ f (x)dx, lim xn та |
|||
∑ f ( j) |
|||
a |
x→c |
j=k |
|
|
63 |
|
|
параметри a, b, c, k і n – це змінні, замість яких можна підставляти певні значення, а параметри x та j – зв'язані змінні, підстановка замість яких будь-яких значень не має жодного сенсу.
Навішувати квантори можна й на багатомісні предикати. Наприклад, застосовуючи квантори і до змінних x та y двомісного предиката A(x, y), отримаємо чотири різні одномісні предикати:
xA(x, y), xA(x, y), yA(x, y) і yA(x, y).
У перших двох змінна x є зв'язаною, а змінна y – вільною, а у двох останніх – навпаки.
Вираз xA(x, y) (читають як для всіх x A від x та y) є одномісним предикатом B(y). Він є істинним для тих і тільки тих b M, для яких одномісний предикат A(x, b) є істинним для всіх x із M.
Приклад 1.20. Розглянемо двомісний предикат A(x, y), означений на множині M = {a1, a2, a3, a4} за допомогою табл. 1.4. Значенням предиката A(ai, aj) є елемент на перетині рядка, що відповідає ai, та стовпчика, що відповідає aj.
x \ y |
a1 |
a2 |
a3 |
a4 |
Таблиця 1.4 |
a1 |
0 |
1 |
1 |
0 |
|
a2 |
0 |
1 |
1 |
1 |
|
a3 |
0 |
0 |
1 |
1 |
|
a4 |
0 |
0 |
1 |
0 |
|
Таблиці істинності для чотирьох відповідних одномісних предикатів, отримуваних з A(x, y) навішуванням одного квантора, наведено у табл. 1.5.
|
|
|
|
|
yA(x, y) |
|
Таблиця 1.5 |
|
y |
xA(x, y) |
y |
xA(x, y) |
x |
x |
yA(x, y) |
|
|
a1 |
0 |
a1 |
0 |
a1 |
0 |
a1 |
1 |
|
a2 |
0 |
a2 |
1 |
a2 |
0 |
a2 |
1 |
|
a3 |
1 |
a3 |
1 |
a3 |
0 |
a3 |
1 |
|
a4 |
0 |
a4 |
1 |
a4 |
0 |
a4 |
1 |
|
Увсіх чотирьох випадках до вільної змінної, що залишилася, можна застосовувати один із кванторів і, зв'язавши таким чином обидві змінні, перетворити відповідні предикати на висловлення.
Урезультаті отримаємо такі висловлення:
x( yA(x, y)) = 0,x( yA(x, y)) = 0,y( xA(x, y)) = 0,
y( xA(x, y)) = 0, |
y( xA(x, y)) = 1, |
x( yA(x, y)) = 1, |
y( xA(x, y)) = 1, |
x( yA(x, y)) = 1. |
|
64
Неважко переконатися, що перестановка однакових кванторів зумовлює рівносильні висловлення. Дійсно, обидва висловлення x( yA(x, y)) і y( xA(x, y)) істинні тоді й тільки тоді, коли предикат A(x, y) набуває значення 1 на всіх кортежах значень (a, b) з M 2. Висловлення x( y A(x, y)) і y( x A(x, y)) істинні тоді й тільки тоді, коли існує принаймні одна пара (a, b) така,
що A(a, b) = 1.
Водночас усі чотири висловлення з різнойменними кванторами є нерівносильними. Особливо слід наголосити, що суттєвим є порядок слідування різнойменних кванторів.
Висловлення x( yA(x, y)) і y( xA(x, y)) нерівносильні. Наприклад, у термінах табличного задання предиката A(x, y) істинність першого висловлення x( yA(x, y)) означає, що кожен рядок таблиці істинності містить принаймні одну одиницю. Друге ж висловлення y( xA(x, y)) істинне тоді й лише тоді, коли в таблиці є стовпчик, що складається тільки з одиниць. ◄
Неважко поширити всі наведені вище міркування й висновки на предикати більшої арності. Навішування одного квантора завжди зменшує кількість вільних змінних і арність предиката на одиницю. Застосування кванторів до всіх змінних предиката перетворює його на висловлення (іноді таку предикатну формулу називають замкненою).
Зауваження. Треба звернути увагу на те, що термін "предикат" має різні тлумачення в лінгвістичному та математичному контекстах. У лінгвістичному (синтаксичному) контексті він тлумачиться як присудок-властивість у певному реченні; математичне (семантичне) тлумачення (яке є абстракцією від лінгвістичного) полягає в тому, що термін предикат визначається як функція в множину булевих значень, яка задана на множині предметних значень (це питання буде розглянуто детальніше в останньому розділі посібника).
Завдання для самостійної роботи
1. Записати формулою логіки предикатів таке твердження:
Для кожного x P(x) – хибне; P(x) – хибне для кожного x.
65
2. Указати вільні та зв'язані змінні у виразі. Для кожної зв'я- заної змінної визначити, яким саме квантором її зв'язано:
(а) P(x) → y (Q(y) z P(z) ~ ← P(y));
(б) x (P(y) → P(x) z(Q(z) ~ y(Q(y) Q(x))) x(P(x) → ← ( y Q(y)));
(в) x (x2y > 0 → y > 0); (г) x > 3 x y (xy2 > 0); (д) x y (x < y → z (x < z z < y)).
3. Предметна область – це множина R дійсних чисел. Визначити, є вираз висловленням чи пропозиційною формою. У першому випадку вказати, істинним чи хибним є висловлення, у другому – навісити квантори так, щоб дістати істинне вислов-
лення: |
|
(а) y x(xz = xy); |
(б) p x(x2 + px + q > 0); |
(в) x y z(xy = z); |
(г) y x(xy > 0) → z(z2 < 0). |
4. Нехай предметною областю є множина N натуральних чисел. Проаналізувати область дії кванторів і знайти значення висловлення:
(а) x y( z (z > x z < y) ~ x < y); (б) x y z((z > x z < y) ~ x < y).
5.Навести приклади тверджень як математичного, так і нематематичного змісту, у яких є кванторні вирази для кожного та існує, значення яких змінюються при зміні порядку слідування цих виразів.
6.Порівняти області дії квантора йзначення істинності виразів
x(x > 3) → (2 > 3) та x((x > 3) → (2 > 3)).
1.8. Формули логіки предикатів. Рівносильність формул. Пренексні формули. Тотожно істинні формули
Наведемо індуктивне означення поняття формули логіки предикатів (предикатної формули, або просто формули).
1. Якшо P – символ елементарного n-місного предиката, x1, x2, …, xn – предметні змінні, то вираз
P(x1, x2, …, xn)
– формула. Такі формули називають елементарними, або ато марними.
66