Зубенко, Омельчук - Програмування. Поглиблений курс
.pdfРозділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ
7. Що таке терм (умовний терм, підтерм)?
8. Скільки всього підтермів у таких термах: а)
(((x y) +(x /y)) 1),
б) (f 3(x,y,x) + g2(f 3(1,x +y,g2(x,z)),2))?
9.Що таке опорна операція в термі? Проілюструвати прикла- дами.
10.У чому полягає різниця між префіксними, постфіксними та інфіксними термами?
11.Що таке ОПЗ?
12.Яка роль формул у ПЧП?
13.Які бувають логічні зв'язки та квантори?
14.Що таке пропозиційна змінна та пропозиційна формула?
15.Дати визначення тавтології. Навести приклади тавтологій.
16.Що таке рівносильні пропозиційні формули?
17. |
Чи можна |
усунути |
дужки у формулах: а) P (Q R) ; |
|
б) (P Q) R ; в) ←(P & Q) ; г) P (Q R)? |
||
18. |
Відновити |
дужки у |
формулах: а) P ←(Q & R) P ↔ R ; |
б) P Q R ↔ ←Q P .
19.Розглянемо систему аксіом:
1)P (Q P );
2)(P (Q R)) ((P Q) (P R)) ;
3)(←Q ←P ) ((←Q P ) Q)
і правило виведення MP (лат. – modus ponens): із формул- засновків P , P Q виводиться формула-висновок Q . Пока-
зати, що: а) усі аксіоми 1)–3) є тавтологіями для будь-яких фор- мул P,Q,R , б) якщо у правилі МР засновки P , P Q – тав-
тології, то й висновок Q – тавтологія, в) ** система аксіом є по-
вною, тобто в ній виводяться усі тавтології [84].
20. Довести рівносильність пропозиційних форм 1)-6):
1)x x & y x; 2)x &(y x) x; 3)x x & y x y;
4)←x x & y ←x y; 5)x &(y x) x & y; 6)←x &(y x) ←x & y.
21.Відновити дужки у формулі y z x(P 1(x) P2(y)& ←P1(z)).
22.З'ясувати, які входження змінних x,y,z є вільними та зв'я-
заними у формулі y(P 2(x,y) z xP1(y,x,z)) P 2(z,y)) . 23. Записати засобами ПЧП натуральної арифметики такі твер-
дження:
а) для будь-яких двох чисел існує найбільший спільний дільник; б) найбільший спільний дільник двох чисел ділиться на будь- який їхній спільний дільник.
31
ПРОГРАМУВАННЯ
24. Студент написав твердження: x(Dv(x) ³ä(x)), де універ- сумом є академічна група, ³ä(x) інтерпретується як " x – відмінник", Dv(x) – як " x має заборгованості". Чи може воно
бути істинним?
25. Ввести необхідну сигнатуру й переформулювати твердження у вигляді формул відповідних ПЧП:
а) тільки судді в захваті від суддів; б) існують судді, від яких не в захваті жоден правопорушник;
в) кожна жінка-адвокат у захваті від якогось судді-чоловіка; г) деякі програми можна зрозуміти; д) деякі лекції не можна зрозуміти;
е) є замки, які не відкриваються, але зачиняються; є) кожна програма містить помилки; ж) усі чесні програмісти поважають один одного.
26 * . Спростити формули ПЧП, де p,q,r – унарні предикатні символи, x,y,z – предметні змінні:
p(x)& q(y)& r(z) p(x)& q(y)& ←r(z) а) p(x)& ←q(y)& r(z) ←p(x)& q(y)& r(z);
б) x y z(p(x) p(x)& q(y) q(y)& r(z) ←p(x)& r(z));
в) x y( ( p(x) q(y))&
&( ←p(x)& ←q(y) r(z)) ←r(z) (p(x) q(y))& (u(z ) v(z ))) .
1.2. Множини
¾Поняття множини
¾Алгебра множин
¾Індексовані множини
¾Бінарні відношення
¾Еквівалентності й порядки
Ключові слова: множина, характеристична функція, індексована множина, пряма сума множин, перетин множин, об'єднання множин, різниця множин, доповнення множини, закони булевої алгебри множин, діаграма Ейлера – Венна, кортеж, вектор, декартів добуток множин, відношення, відповідність, відображення, множення та обернення відношень, рефлективність, симетричність, транзитивність, транзитивне замикання бінарного відношення, антисиметричність, частковий порядок, лінійний
32
Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ
порядок, діаграма Гессе, монотонне й неперервне відображення, нерухома точка, структура, повна структура, еквівалентність, фактор-множина, індекс еквівалентності, факторизація.
У цьому підрозділі розглядаються фундаментальні з погляду дескрип- тології математичні поняття – множина, індексована множина й відно- шення, а також деякі похідні від них поняття, важливі для застосувань.
1.2.1. ПОНЯТТЯ МНОЖИНИ
Сукупність матеріальних чи абстрактних об'єктів, об'єднаних будь- якою спільною властивістю, називається множиною. Об'єкти й понят- тя, що складають множину, називаються її елементами. Будемо по- значати множини великими, а їхні елементи – малими літерами ла- тинської або грецької абеток. Твердження, що елемент a є елементом множини А, подається формулою a A . Бінарний предикат нази- вається предикатом приналежності. Його заперечення записується як , тобто формула a A означає, що об'єкт a не належить А. Еле- ментами множини можуть бути й самі множини. Наприклад, студе- нтські академічні групи утворюють курс певного року навчання й самі є множинами, що складаються з відповідних студентів. Дві мно- жини А та В називаються рівними (А=В), якщо вони складаються з одних і тих самих елементів. Засобами ПЧП цей предикат коротко можна було б визначити так:
def
A = B = x(x A ↔ x B ).
Для того, щоб задати множину, достатньо перерахувати всі її еле- менти в довільному порядку. Такий перерахунок записується зазви-
чай усередині фігурних дужок. Наприклад, запис {2,0,7} означає множину M , що складається із чисел 2, 0 та 7. Ця множина збігаєть- ся з множинами {0,2,7} та {2,0,0,7}. В останньому випадку елемент 0 поданий двічі, а це не суттєво для означення множини. Розрізняти- мемо елемент a , множину {a}, множину {{a}}, єдиним елементом
якої є множина {a} тощо. Розглядають також порожню множину ,
яка не містить жодного елемента. Множина В називається підмножи- ною множини A , а множина A , у свою чергу, – надмножиною мно- жини B (записується B A ), якщо кожний елемент B є елементом
def
A , тобто B A = x(x B → x A).
33
ПРОГРАМУВАННЯ
Підмножина В називається власною ( B A ), якщо B ≠ A . Нехай A – певна множина, P – деяка властивість елементів з A . Нехай формула
P (x ) означає, що елемент x має властивість P , тобто P (x ) =1. Тоді за- пис P(A) означає підмножину {x A : P (x )} тих елементів A , які мають
властивість P . Як уже зазначалось, P називається характеристичною властивістю (функцією) цієї підмножини. Якщо х є типізованою змінною
типу T , то замість виразу вигляду {x A : P (x )} пишуть просто {x : P (x )}. Так, у прикл. 1.5 змінна n вважається натуральною.
Приклад 1.5. Характеристичні властивості множин.
{x N : x < 0} = ,
{x N : 0 < x < 4}={1,2,3},
{x N : x =a1 K x =an } ={a1,K,an }.
{n : n%2 = 0} збігається з множиною парних натуральних чисел.
Тут символ " % " позначає операцію взяття залишку від ділення ці- лих чисел ■
1.2.2. АЛГЕБРА МНОЖИН
У зв'язку з поняттям множини цілком природно виникає питання: чим є сукупність (універсум) усіх можливих множин U ? Як з'ясувало- ся, сам універсум U не може належати до множин. Це першим зафі- ксував Б. Рассел (парадокс Рассела). Дійсно, якщо універсум визнати
def
множиною, то має існувати й множина M = {x U : x x}. Припус-
тимо, що M M . Тоді за означенням M M . Нехай тепер M M . Тоді за означенням M M . В обох випадках маємо протиріччя. Отже, або універсум U не є множиною, або необхідно відмовитись від визна- чень підмножин за допомогою властивостей. Математики обрали пе- рший шлях і вилучили з теорії універсум усіх множин. Один зі спосо- бів уникнути парадоксів, подібних парадоксу Рассела, запропонував сам Рассел у теорії типів. За цією теорією кожній константі та змінній приписується певний тип, сукупність типів має строгу ієрархічну бу- дову, а предикат x M має сенс тільки у випадку, коли тип M є на- ступним у ієрархії за типом x . Якщо це не так, то значення предика- та вважається беззмістовним. Теорія типів мала певний вплив на ро- збудову основ математики. Однак не менше, а можливо, і ширше,
34
Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ
своє застосування вона знайшла при створенні штучних формальних мов різного призначення, у тому числі – мов програмування (див. принцип типізації, підрозд. 2.2.2). Принциповим у зв'язку із цим є те, що поняття типу унеможливлює появу заздалегідь помилкових мов- них виразів, і перевірити виконання типових вимог можна суто фор- мально, не звертаючи увагу на значення виразів. Визначимо тепер
основні операції на множинах:
def
A B = {x : x A x B} – об'єднання множин A та B ,
def
A ∩ B = {x : x A & x B} – перетин множин A та B ,
def
A \ B = {x : x A & x B} – різниця множин A та B ,
def
A = {x : x A}– доповнення множини A ,
def
B (A) = {X : X A} – булеан множини A ,
def
A = – потужність множини A .
Булеан множини A також позначають 2A .
Нехай A – довільна множина. Сигнатуру Ω2 булевої алгебри мно-
жин Β(A) = {2A ; ,∩,\, , } над A складають:
1) сорти σ,ρ та λ , що подають відповідно базову множину A , буле- ан 2A і множину істиннісних значень Bool = {1,0,#};
2) сукупність ΩC – константа типу ρ, що інтерпретується як по-
рожня підмножина; 3) індексована сукупність змінних
ΩV = {x : σ,x1 : σ,K,y : σ,y1 : σ,K,X : ρ,X1 : ρ,K,Y : ρ,Y1 : ρ,...};
4) бінарні функціональні символи ,∩,\ : ρ×ρ → ρ і унарний символ
: ρ → ρ , що інтерпретуються відповідно як операції об'єднання, пе-
ретину, різниці й доповнення множин;
5) предикатні символи : ρ×ρ → Bool та : σ×ρ → Bool , що інтер- претуються як предикати включення й приналежності.
Покладемо τ = ρ×ρ → ρ , ν = ρ → ρ, |
ς = ρ×ρ → Bool,μ = σ×ρ → Bool . |
Типом сигнатури Ω2 є = (ρ;τ,τ,τ,ν;ς,μ) . |
|
35
ПРОГРАМУВАННЯ
Для операцій об'єднання, перетину й доповнення виконуються за- кони булевої алгебри, перші два з яких проілюструємо за допомогою діаграм Ейлера –Венна:
1) комутативності: A B = B A , A ∩ B = B ∩ A (рис. 1.1);
A B
– перетин
– об’єднання
Рис. 1.1
2) асоціативності об'єднання й перетину множин:
A (B C )= (A B ) C , A ∩ (B ∩C )= (A ∩ B )∩C (рис. 1.2);
A B
C
–об’єднання множин A, B, C
–перетин множин A, B
Рис. 1.2
3) дистрибутивності:
а) перетину відносно об'єднання:
A ∩ (B C )= (A ∩ B ) (A ∩C );
36
Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ
б) об'єднання відносно перетину:
A (B ∩C ) = (A B )∩ (A C );
4)ідемпотентності: A A = A , A ∩ A = A ;
5)дії з універсальною й порожньою множинами:
A = A , A ∩ = , A U =U , A ∩U = A , A A =U , A ∩ A = ;
6) де Моргана:
а) A ∩ B = A B ;
б) A B = A ∩ B ;
7) подвійного доповнення: A = A .
Наведені закони дозволяють за допомогою тотожних перетворень спрощувати складні вирази над множинами.
Приклад 1.6. Спростимо вираз, скориставшись законом булевої алгебри підмножин над множиною Α :
(A ∩ B ∩C ) (A ∩ B ∩C ) (B C ) = [(A A)∩ B ∩C] (B C) = = [Α ∩ B ∩C] B ∩C = B ∩C B ∩C = Α ■
1.2.3. ІНДЕКСОВАНІ МНОЖИНИ
Розглянемо загальні засоби структурування елементів множин. Пер- шим і найфундаментальнішим є індексування (ми його вже застосову- вали в підрозд. 1.1). Нехай I та M – довільні множини. Елементи I бу- демо називати індексами. Проіндексувати множину M означає поста- вити у відповідність усім або деяким її елементам певний індекс. При цьому можливі два варіанти: 1) різні елементи отримають обов'язково різні індекси (сильна індексація); 2) індекси різних елементів можуть збі- гатися (слабка індексація). В обох випадках зворотне не вимагається, тобто елемент може мати кілька індексів. Якщо i – індекс елемента a , то індексований елемент записується ai . Важливо, що, приписуючи ін-
декс елементу, ми тільки вводимо для нього нове ім'я, а сам елемент при цьому не змінюється. Проіндексовані елементи збігаються тільки тоді, коли вони однакові й у них збігаються індекси. Отже, якщо ai = bj , то
a = b та i = j . Зокрема, ai ≠ a j для будь-якого a та i ≠ j . Слабка індек-
сація використовується, наприклад, для побудови прямих сум множин. При звичайному об'єднанні однакові елементи в операндах "склеюють- ся" в один екземпляр. Цього можна уникнути, якщо перед об'єднанням
37
ПРОГРАМУВАННЯ
множини спочатку проіндексувати. Щоб побудувати пряму суму мно- жин A B , проіндексуємо всі елементи множин A та B відповідно ін- дексами 1 та 2 і покладемо
def
A B = {a1 : a A } {b2 : b B } .
У прямій сумі множин індекс кожного елемента свідчить про приналеж- ність його до першого чи другого операнда й саме за цим показником
однакові |
елементи можуть різнитися. Наприклад, для |
A = {a,b,c } , |
B = {b,c } |
пряма сума A B = {a1,b1,c1,b2.c2 } , тоді як |
об'єднання |
A B = A . Значення елементів b1 і b2 та c1 і c2 однакові (відповідно b
та c ), але як індексовані елементи вони різні й тому не "склеюються" в сумі. Надалі під індексацією будемо розуміти сильний її варіант.
У математиці як індекси найчастіше використовують натуральні числа (усі або початкові їхні відрізки). Нехай M – довільна множина. Сильно проіндексовані натуральними числами множини називаються послідовностями на множині M , але не всі, а тільки ті, у яких для ін- дексації елементів використані всі без винятку натуральні числа (або всі числа їхнього початкового відрізка). Кількість елементів у послідо- вності називається її довжиною. Наприклад, для множини A = {a,b,c }
послідовностями будуть {a1} (довжиною 1), {a1,b2} (довжиною 2), {ci : i ≥ 0} (нескінченна послідовність), а сукупності {a1,b1} та {a1,b3} –
ні. У першому випадку індексація несильна, у другому – пропущено елемент з індексом 2. У другому випадку індексована сукупність на- зивається підпослідовністю. Таким чином, на відміну від послідовнос- тей, у підпослідовності можуть бути пропущені ті чи інші індекси.
Індексація дозволяє переносити бінарні операції на випадок індексо- ваних сімей множин. Наприклад, нехай P1,...,Pn та A1,...,An – довільні
проіндексовані формули й множини, а {Bi :i I } |
– індексована сім'я |
||
def |
|
def |
{1,K,n}, |
множин. Домовимось про такі позначення: 0...n = |
{0,K,n}, 1...n = |
вирази 1 ≤ i ≤ n та 1 ≤ i ≤ n замінюють обмежені квантори i 1...n таi 1...n . Тоді вже відомі нам операції можна узагальнити:
n |
|
def |
|
≤ nP ; |
|
n |
|
def |
≤ i ≤ nP ; |
|
|
& P |
= 1 ≤ i |
|
P |
= |
1 |
|
|||||
i =1 |
i |
|
|
i |
|
i =1 |
i |
|
|
i |
|
n |
|
def |
{x :1 |
≤ i ≤ n x A |
}; |
n |
|
def |
{x :1 ≤ i ≤ n x A |
}; |
|
A |
= |
∩ A |
= |
||||||||
i =1 |
i |
|
|
i |
|
i =1 |
i |
|
|
i |
|
38
|
def |
{x : i I x A |
}; |
||||
A = |
|||||||
i I |
i |
|
|
|
|
i |
|
n |
def |
n |
{a |
|
: a A |
}; |
|
A = |
I |
|
|
||||
i =1 |
i |
i =1 |
|
i |
i |
|
|
n
∑ai = a1 +... +a n ;
i =1
Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ
|
def |
{x : i I x Bi }; |
||||
∩ Bi = |
||||||
i I |
|
|
|
|
|
|
|
def |
|
{a |
|
: a A |
}; |
A = |
U |
|
||||
i I |
i |
i I |
|
i |
i |
|
n
∏ai = a1 ×...×a n .
i =1
Подібні узагальнені операції розглядаються, наприклад, у [62, 105] і мають численні застосування у програмуванні. Скінченні послідовності отримали окрему назву кортежів. Індекси елементів кортежу називають-
ся їхніми порядковими номерами, або координатами. Кортежі запису-
ються у вигляді [a0,....,an−1], [a1,....,an ]. Кортеж довжиною 0 є порожньою
сукупністю й записується []. На відміну від множин, елементи в кортежі можуть повторюватись, але координати при цьому в них будуть різні.
Сукупність усіх кортежів з елементами з A позначається A* . Два кортежі рівні, якщо вони мають однакову довжину й рівні покоординатно:
|
|
|
|
|
|
|
def |
n −1 |
|
|
|
|
[a0,....,an −1] = [b0,....,bm −1] n |
= m & & ai = bi . |
|||||
Визначимо деякі операції на кортежах: |
i =0 |
||||||||
|
|
||||||||
|
|
|
def |
|
|
|
|
|
|
1) |
|
x |
= довжина кортежу x ; |
|
|
||||
|
|
|
|
|
def |
|
|
|
|
2) |
i 1..n pri [a1,....,an ] |
= |
ai – проекція кортежу за i -ю компонентою; |
||||||
|
|
|
|
|
def |
[a1,....,an , b1,....,bm] – конкатенація кортежів; |
|||
3) |
[a1,....,an ] o [b1,....,bm] |
= |
|||||||
|
|
|
|
def |
|
|
|
|
|
4) |
|
pre(a,[a1,....,an ]) |
= |
[a,a1,....,an ] – додавання компоненти в поча- |
|||||
ток кортежу; |
|
def |
|
|
|
||||
|
|
app([a1,....,an ],a ) |
|
|
|
||||
5) |
|
= |
[a1,....,an ,a] – додавання компоненти в кі- |
||||||
нець кортежу. |
|
|
|
|
|
|
|||
Кортежі x та z – це відповідно префікс (x < y) |
і закінчення (y > x ) |
||||||||
кортежу y , якщо |
існують такі кортежі |
v та |
w , що y = x ow та |
||||||
y = v oz . Кортеж z |
є cуфіксом кортежу y |
(x y), якщо існують такі |
непорожні кортежі v та w , що y = v oz ow .
Індексація є основним інструментом структурування даних у програ- муванні. Тут як індекси використовуються спеціальні імена – l-вирази15.
15 Найпростіші з них – ідентифікатори (див. 3.1.2).
39
ПРОГРАМУВАННЯ
1.2.4. БІНАРНІ ВІДНОШЕННЯ
Кортежі фіксованої довжини n ≥ 0 називаються векторами. Вони позначаються (a1,....,an ). Елементи вектора називаються компонен-
тами. Декартовим добутком сукупності множин A1,...,An назива-
n |
def |
{(a1,K,an ): i 1Kn ai Ai }. |
ється множина ∏ Ai |
= |
|
i =1 |
n |
співмножників A називається декартовим |
Декартів добуток |
степенем A й позначається An . За означенням A1 =A , A0 ={[]}, де []
– порожній кортеж. Якщо принаймні одна з координат добутку Ai по-
n |
=A0 . Відношенням між множинами A ,...,A назива- |
||
рожня, то ∏ A |
|||
i |
|
1 |
n |
i =1 |
|
n |
|
ється довільна підмножина декартового добутку R |
|
||
∏ Ai . Якщо век- |
|||
тор (a1,....,an ) R , то кажуть, що елементи a1,....,an |
i =1 |
|
|
задовольняють |
відношення R, і записують R(a1,....,an ). У протилежному випадку ка-
жуть, що дані елементи не задовольняють R, і записують ←R(a1,....,an ) . Відношення зручно задавати предикатами. Предикат
n
p : ∏ Ai → Bool називається характеристичною властивістю відно-
i =1
шення R , якщо R(a1,....,an ) p (a1,....,an ) =1.
Вектори довжиною 2 називаються упорядкованими парами й по- значаються (a1,a2 ) . Елементи a1 та a2 називаються відповідно пер-
шою й другою компонентами пари.
Бінарним відношенням, або відповідністю між множинами A та B ,
називається довільна підмножина декартового добутку R A B . Серед бінарних відношень особлива роль належить відображенням.
Це такі відношення F A B , для яких x A 1y B (x,y) F . По-
няття відображення є центральним у більшості розділів математики – математичному й функціональному аналізах, алгебрі, теорії диферен- ційних рівнянь тощо. Ми повернемося до них у підрозд. 1.4.
Відношення вигляду R A A називається бінарним відношенням на множині A . Серед усіх бінарних відношень на A виділяють: по-
рожнє ε , тотальне A A та одиничне (рівність) iA ={(a,a ): a A}.
40