Дискретна математика

01 - знаходячись у стані d0 автомат під впливом першого символу цього слова перейде в стан d1, а зі стану d1 автомат під впливом другого й останнього символу цього слова перейде знову в стан d1, що і буде ознакою розпізнавання;

011 - знаходячись у стані d0 автомат під впливом першого символу цього слова перейде в стан d1, зі стану d1 автомат під впливом другого символу цього слова перейде знову в стан d1, зі стану d1 автомат під впливом третього й останнього символу цього слова перейде знову в стан d1, що і буде ознакою розпізнавання.

Очевидно, що в такий же спосіб автомат розпізнає всі слова мови {0, 01, 011, 0111, ...}, визначеної вище за допомогою граматики G1. Легко переконатися також, що автомат не розпізнає ніяких інших слів, крім слів мови {0, 01, 011, 0111, ...}. Таким чином, даний автомат визначає способом розпізнавання мову {0, 01, 011, 0111, ...}, визначену породженням за допомогою граматики G1.

Важливість вибору стану, з якого автомат починає розпізнавання (початкового стану) і станів, що сигналізують про те, що переглянуте слово розпізнане (заключних станів) продемонструємо на прикладі того ж автомата. Якби автомат знаходився в стані d1 на момент подачі першого символу, то вхідна послідовність, що вводиться, 01 не була б переглянута і, отже, розпізнана автоматом, тому що він не може реагувати в стані d1 на вхідний символ 0. У цьому випадку він не може далі переглядати вхідне слово і, отже, не можна розглядати його стан d1 як заключний тому що не завершений перегляд вхідного слова. З іншого боку, якщо автомат знаходиться в стані d0 на момент подачі першого символу вхідної послідовності 010, то він не перегляне ланцюжок 010 і, хоча буде знаходитися в стані d1 під впливом її підслова 01, це не буде ознакою розпізнавання, тому що вхідне слово не переглянуте.

Звідси, щоб однозн чно визн чити ті слов , що втом том розпізн ються, необхідно:

1) чітко обумовити ст н втом т , у якому він повинен почин ти перегляд вхідних прогр м (поч тковий ст н);

2) обмовити ст ни, в один з яких повинен перейти втом т після з кінчення вхідного слов

0

Тут d0 і d1 – стани, 0 – вхідний символ, перехід зі стану d0 у стан d1 здійснюється при вхідному символі 0 на вході автомата, а перехід зі стану d1 у стан d0 здійснюється при вхідному символі 1 на вході автомата. Стан d0 – початковий і заключний.

Наведений автомат розпізнає наступні слова:

ε – знаходячись у стані d0, автомат знаходиться в заключному стані d0, що і буде ознакою розпізнавання, тому що вхідне слово не містить символи вхідної мови і, отже, уже переглянуте;

00 - знаходячись у стані d0, автомат під впливом першого символу цього слова перейде у стан d1, а зі стану d1 автомат під впливом другого й останнього символу цього слова перейде знову у стан d0, що і буде ознакою розпізнавання;

0000 - знаходячись у стані d0, автомат під впливом першого символу цього слова перейде у стан d1, зі стану d1 автомат під впливом другого символу цього слова перейде знову у стан d0, зі стану d0 автомат під впливом третього символу цього слова перейде знову у стан d1, зі стану d1 автомат під впливом четвертого й останнього символу цього слова перейде знову у стан d0, що і буде ознакою розпізнавання.

Очевидно, що в такий же спосіб автомат розпізнає всі слова мови {ε, 00, 0000, 000000, ...}, визначеної вище за допомогою граматики G2. Легко переконатися також, що автомат не розпізнає ніяких інших слів, крім слів мови {ε, 00, 0000, 000000,...}. Таким чином, даний автомат визначає способом розпізнавання мову {ε, 00, 0000, 000000,...}, визначену породженням за допомогою граматики G2.

1.2.Ідея операційного способу полягає у визначенні мови в алфавіті як результату виконання скінченого числа операцій над деякою початковою множиною «простих» мов. Звичайно під простими мовами маються на увазі мови, слова яких складаються не більш ніж з одного символу алфавіту. Цей спосіб розглянемо на прикладі важливого класу формальних мов.

19. Регулярні множини і вир зи

Тепер уведемо формальні означення для того щоб уточнити викладене інтуїтивне уявлення про операційний спосіб.

Визначення. Визначимо регулярні множини в алфавіті Е в такий спосіб:

21

1)– регулярна множина;

2){ } - регулярна множина;

3){ei}, де ei Е, - регулярна множина;

4)якщо R і S – регулярні множини в алфавіті Е, то R S, RS, R* - також регулярні множини;

5)Т - регулярна множина в алфавіті Е тоді і тільки тоді, коли це випливає з пунктів 1) – 4) даного означення.

Коли ми говоримо про означення такого типу, ми розуміємо, що вони задають обумовлений об'єкт індуктивним чином, тобто задають шлях його побудови. Таким чином, множина регулярна в алфавіті Е, тоді

ітільки тоді, коли або вона порожня, або містить тільки порожнє слово , або містить тільки слово, що складається з будь-якого одного символу алфавіту Е, або може бути отримана з цих множин застосуванням скінченого числа операцій об'єднання, конкатенації й ітерації. Таким чином, усі скінчені множини регулярні.

Приклади регулярних множин в алфавіті Е. а)

б) { }; б') {0}; б‖) {1}; в) {0,1} – як {0} {1};

г) {00, 01, 10, 11} - як {0}{0} {0}{1} {1}{0} {1}{1}; д) { , 01, 0101, 010101,…} - як 0 1 ;

е) - { , 0, 00, 000, } - як 0 ;

ж) { , 000111, 000111000111, 000111000111000111,…} - як 0 0 0 1 1 1 ;

з) { , 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 101, 110, 111,…} - як 0 1 .

Виникає таке враження, що довільна нескінченна множина, елементами якої є ланцюжки елементів 0,1 також є регулярною множиною. Однак, це не так. Розглянемо наступний

Приклад 1. Розглянемо нескінчену множину { , 01, 0011, 000111,...}.

Ця множина не є регулярною. Зверніть увагу на те, що потрібен повтор однакової кількості 0 і 1, а ця побудова регулярної множини не забезпечується за скінчене число кроків. Дійсно, ми можемо, використовуючи конкатенацію, одержати будь-яке слово з однаковою кількістю 0 і 1, але тоді для нескінченної мови потрібно явно використовувати нескінченне число конкатенацій. Одна ітерація змогла б породити будь-яку послідовність однакових елементів або 0, або 1. Однак, ітерація дає довільне число елементів у слові і тому конкатенація двох ітерацій не забезпечить рівне число 0 і 1 у слові.

Аналогічно не є регулярними множини:

{011, 00111, 000011111,...};

{010, 001100, 000111000,...} і інші.

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

Варто зазначити, що під T, R, S ми розуміємо множини. Ми вже говорили про те, яке значення має в інформатиці символьне оброблення, можливість виконання перетворень над символьним записом перед виконанням операцій. У теорії мов регулярні множини звичайно позначають за допомогою їх же елементів шляхом використання регулярних виразів.

Визначення регулярних виразів:

1)– регулярний вираз, що позначає регулярну множину ;

2)- регулярннй вираз, що позначає регулярну множину { };

3)ei - регулярний вираз, що позначає регулярну множину {ei}, якщо ei Е;

4)якщо r і s - регулярні вирази, що позначають регулярні множини R і S, то (r + s), (rs), (r)* -

регулярні вирази, що позначають відповідно регулярні множини R S, RS, R*;

5) t – регулярний вираз тоді і тільки тоді, коли це є наслідком застосування пунктів 1) - 4) цього означення.

Приклад 2. Наведемо регулярні вирази для регулярних множин: (01) позначає {01}; (010) позначає {010};

(0+1)* позначає {0,1}*;

(e1 + e2) (e1 + e2 + e3 + e4) позначає множину слів з e1, e2, e3, e4, що розпочинаються на e1 чи e2.

Далі будемо позбавлятися від дужок, увівши пріоритет операцій. Розташуємо операції в порядку збільшення їх пріоритету в такому порядку: ітерація; конкатенація; об'єднання. Домовимося, якщо при бездужковому записі декілька операцій претендують на виконання одночасно, першою будемо виконувати

операцію з найменшим пріоритетом. У такий спосіб вираз 10 1 0 можна записати у вигляді

10 10 . Але вже вираз 1 0 без дужок без втрати значення записати не можна.

22

Таким чином, якщо ми в прикладі візьмемо будь-який регулярний вираз, то по ньому можна побудувати регулярну множину. Тому що при цьому застосовується однозначна процедура породження слів шляхом виконання операцій об'єднання, конкатенації й ітерації, то цей висновок можна поширити на будьякий регулярний вираз.

Тепер подивимося навпаки. Нехай регулярна множина містить слова e1 і e2, тобто R = {e1} {e2}. Регулярний вираз, що позначає її, має вигляд (e1 + e2). Але і (e2 + e1) також позначає ту ж множину. Чи розглянемо множину слів довільної довжини із символів e1 і e2, тобто регулярну множину ({e1} {e2})*. Її також позначають (e1 + e2)* чи (e2 + e1)*. Таким чином, для кожної регулярної множини може існувати множина регулярних виразів, що позначають її .

На множинах природно визначається відношення рівності. Скористаємося цим і визначимо відношення рівності регулярних виразів.

Визначення. Регулярні вирази r і s рівні (будемо позначати цей факт r = s), якщо вони позначають рівні множини.

Природно, що ми використовуємо уже введене нами раніше визначення рівних множин. Теорема 5. Якщо r, s, t – регулярні вирази, то справедливі такі рівності:

r + s = s + r ;

r = r = ; r + = r .

Доведення. Нехай r позначає регулярну множину R, а s - регулярну множину S. Але тоді, тому що

S R R S , то r s s r .

Аналогічно доводяться інші рівності. Теорема доведена.

20. Поняття лгебри

Поняття алгебри. Ми вже говорили, що математиці властиве формування складних об'єктів шляхом узагальнення. Одним з найбільш яскравих і корисних понять, отриманих у такий спосіб, є поняття алгебри.

Вище ми ввели поняття операції, функції і відношення, що дозволяють від дослідження окремих об'єктів переходити до дослідження комбінацій об'єктів. Одним з важливих понять, пов'язаних з n-місними відношеннями, є поняття предиката. В попередньому розділі ми вже використовували зв‘язок між предикатами і відношеннями. Тепер розглянемо ще один аспект застосування предикатів. Нехай A – деяка непорожня множина. Ми домовилися називати n-місним відношенням будь-яку підмножину множини An. Це відношення можна розглядати як функцію : {0,1}, яка звичайно називається n-місним предикатом і набуває значення 1 тільки на n-ках відношення . І навпаки, будь-якому n-місному предикату можна співставити n-місне відношення , графік якого формують n-ки, значенням предиката для яких буде 1. Варто зазначити, що n-ки відношення часто називають кортежами, особливо коли це стосується застосування теорії відношень для формалізації процесів оброблення даних в базах даних.

Визначення. Під алгебраїчною системою будемо розуміти упорядковану трійку A, F, , що складається з деякої непорожньої множини A і заданих на ній операцій, скажімо, F = { f1n1 , f2n2 ,... }, і

відношень, скажімо, = { 1m1 , 2m2 ,... }.

Відзначимо, що тут: для кожної операції верхній індекс ni означає місність операції, а для кожного відношення верхній індекс mi означає місність відношення. Звичайно множина A називається носієм або основною множиною алгебраїчної системи.

Визначення. Послідовність n1,n2,…;m1,m2,… називається типом алгебраїчної системи. Дві алгебраїчні системи однотипні, якщо їхні типи збігаються.

Завдячуючи тому, що між множинами n-місних відношень і n-місних предикатів існує взаємно однозначна відповідність, множину відношень алгебраїчної системи можна замінити множиною n- місних предикатів. Звичайно, множини предикатів і операцій алгебраїчної системи поєднують, позначають F і називають сигнатурою алгебраїчної системи.

Визначення. Алгеброю (універсальною алгеброю) будемо називати алгебраїчну систему A, F, , множина відношень якої є порожньою.

23

Визначення. Моделлю (реляційною системою) будемо називати алгебраїчну систему A, F, , множина операцій F якої є порожньою.

Розглянута вище термінологія переноситься на алгебри і моделі з очевидними застереженнями. Визначення. Класом алгебр назвемо довільну систему однотипних алгебр. Далі алгебру з носієм A і

сигнатурою { f1n1 , f2n2 ,... } будемо позначати A, f1n1 , f2n2 ,... .

Те, що операція f ini задана на множині A, означає її визначеність для будь-яких ni елементів з

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

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

21. Алгебри з однією опер цією

Варто зазначити, що найбільш поширені алгебри з бінарними операціями типу додавання чи множення. Не є виключенням і алгебри з однією операцією.

Визначення. Алгебра A, з бінарною операцією , що задовольняє властивість асоціативності x (y z) = (x y) z для будь-яких x, y, z A, називається напівгрупою.

Приклади напівгруп: N, , N, + .

Можна недооцінювати роль асоціативності, але не можна забувати, що операції типу додавання і множення, щонайменше, на числових множинах асоціативні. Важливість асоціативності підкреслює той факт, що вже операція віднімання на множини Z не асоціативна:

(5 - 3) - 1 5 - (3 - 1), тому що 1 3.

Далі операції типу у напівтрупі N, і + у напівтрупі N, + назвемо, відповідно, мультиплікативними й адитивними.

Визначення. Якщо існує елемент 1 A такий, що для кожного елемента x R має місце рівність x1 = 1 x = x, то елемент 1 називається одиницею.

Якщо існує елемент 0 A такий, що для кожного елемента x A має місце рівність x 0 = 0 x = 0, то елемент 0 називається нулем.

Зауваження. Спробуйте установити відношення між нулем і одиницею для адитивних і мультиплікативних операцій.

Визначення. Алгебра (A, , 1 з бінарною асоціативною операцією й одиницею називається моноїдом.

Якщо існує елемент a A такий, що для елемента x A моноїда має місце рівність x a = 1, то елемент x називається оборотним справа. Елемент a тут називають правим оберненим.

Якщо існує елемент a A такий, що для елемента y A моноїда має місце рівність a y = 1, то елемент y називається оборотним зліва. Елемент a тут називають лівим оберненим.

Оборотний зліва і справа елемент x A називається оборотним, а якщо його лівий обернений співпадає з правим оберненим, то елемент x має обернений елемент..Далі скрізь для елемента x A обернений елемент будемо позначати x -1.

Визначення. Група A, , 1, -1 - це моноід A, , 1 , у якому кожен елемент, крім нуля, обернений. Визначення. Якщо операція на носієві A комутативна, то група A, , 1, -1 називається абелевою. Отже, в аксіоматичній теорії абелевих груп розглядаються множина A, операція , одиниця 1,

обернення -1, а аксіомами є властивості операції над елементами множини A, одиницею, оберненими елементами:

1)x y = y x;

2)x (y z) = (x y) z;

3)x 1 = 1 x = x;

4)x x -1 = x -1 x = 1.

Приклад. Алгебра Z, +, 0, - - абелева група.

Тепер можна доводити теореми про співвідношення між об'єктами визначеної теорії, наприклад: Теорема 2. Якщо x, y, a A, то справедливі такі співвідношення:

а) з a x = a y випливає x = y; б) з x a = y a випливає x = y.

Доведення. Доведемо спочатку пункт а): x = 1 x - аксіома 3;

1 x = (a a -1) x - аксіома 4;

(a a -1) x = (a-1 a) x - аксіома 1; (a-1 a) x = a-1 (a x) - аксіома 2;

a-1 (a x) = a-1 (a y) - умови теореми;

24

a-1 (a y) = (a-1 a) y - аксіома 2; (a-1 a) y = 1 y - аксіома 4;

1 y = y - аксіома 3.

Аналогічно доводиться і пункт б). Теорема доведена.

22. Алгебри з двом опер ціями

Визначення. Алгебра (A, +, називається кільцем, якщо операція + визначає на A структуру абелевой адитивної групи, операція визначає на A структуру мультиплікативного моноїду й операції + і пов'язані властивістю дистрибутивності:

a (b + c) = (a b) + (a c); (b + c) a = (b a) + (c a).

Приклад кільця: Z, +, .

Якщо операція кільця - комутативна, то кільце називається комутативним.

Визначення. Алгебра A, +, називається областю цілісності, якщо вона є комутативним кільцем, у якому виконується правило скорочення:

якщо a b = a c і a 0, то b = c.

Визначення. Комутативне кільце (A, +, , у якому ненульові елементи утворюють групу щодо операції , називається полем.

Приклад поля: Q, +, , де Q - множина усіх раціональних чисел.

Використання алгебр із двома операціями характерне для розв‘язання рівнянь. Теорія алгебр узагалі бере свій початок від алгебраїчних рівнянь.

Теорема 3. Нехай x, a, b, c A. Виконується ax + b = c тоді і тільки тоді, коли x = (c + (-b)) a-1. Доведення. Пряме. Воно побудоване на застосуванні аксіом теорії до результату підстановки значення

х у рівняння:

a ((c + (-b)) a-1) + b = (a a-1) (c + (-b)) + b – аксіоми комутативності й асоціативності операції ; (a a-1) (c + (-b)) + b = c + ((-b) + b) - аксіоми оберненого елемента й одиниці операції і

асоціативності операції +;

c + ((-b) + b) = c + 0 - аксіома оберненого елемента операції +; c + 0 = c - аксіома одиниці операції + .

Обернене. Якщо x a = c + (-b) (*), то: x = x 1 – аксіома одиниці операції ;

x 1 = x (a a-1) – аксіома оберненого елемента операції ; x (a a-1) = (x a) a-1 – аксіома асоціативності операції ; (x a) a-1 = (c + (-b)) a-1 – з умови (*).

Теорема доведена

23. Абстр ктні опер ції т лгебри

Фізичні процеси як і процеси іншої природи в найбільш загальному вигляді описуються в термінах операцій (спостережень, експериментів), що зв'язують фізичні об'єкти. Складність власне фізичних процесів вимагає спрощених їхніх описів за допомогою вербальних, символьних і навіть інших фізичних моделей.

Потрібно тільки щоб моделі «абстрагували» придатним чином обрані «істотні» властивості фізичних об'єктів і процесів.

Математиці властиво розробляти і досліджувати символьні моделі, що узагальнюються у вигляді математичних моделей, що охоплюють класи невизначуваних (абстрактних, символьних) математичних об'єктів і відношень між ними. Більшість відношень можуть бути представлені у вигляді математичних операцій, що зв'язують один чи кілька об'єктів (операндів) з іншим об'єктом чи з їх множиною (результатом). Абстрактна модель може включати об'єкти будь-якої природи, їхні відношення й операції і визначається несуперечливим набором правил, що мають вигляд визначальних аксіом, що вводять операції, якими можна користуватися, і загальні відношення, що встановлюються між їхніми результатами, у вигляді властивостей.

Наприклад, аксіоматичному визначенню кільця відповідають деякі числові множини з операціями додавання і множення. Прикладом кільця також є множина багаточленів від однієї змінної з коефіцієнтами з числового кільця.

Розглянемо множину усіх функцій дійсної змінної x, скрізь визначеної і такої, що приймає значення на множині дійсних чисел. Визначивши природним чином суму (функція, значення якої для будь-якого x = x0 дорівнює f(x0) + g(x0)) і добуток (функція, значення якої для будь-якого x = x0 дорівнює f(x0) g(x0)) функцій f(x) і g(x), ми можемо переконатися в тому, що щодо них виконуються аксіоми кільця. Таким

25

чином, множина усіх функцій дійсної змінної x, скрізь визначених і приймаючих значення на множині дійсних чисел, разом з операціями додавання і множення функцій утворює кільце.

Тоді всі результати, отримані для числового кільця з використанням тільки аксіом кільця будуть мати місце і для кільця усіх функцій дійсної змінної x, усюди визначених і приймаючих значення на множині дійсних чисел. Зокрема, це відноситься і до закону дистрибутивності множення щодо віднімання. Віднімання є операцією оберненою додаванню.

Визначення. Для операції додавання, визначеної на множини A, існує обернена операція – віднімання, якщо для будь-якої пари елементів a, b множини A існує в A такий елемент d, притому єдиний, котрий задовольняє рівняння b + x = a. Елемент d називається тоді різницею елементів a і b і позначається a

– b.

Теорема 4. В усякім кільці виконується закон дистрибутивності множення щодо віднімання (a – b) c = a c – b c.

Доведення. Воно побудоване на використанні аксіом кільця до результату визначення різниці елементів a – b як елементу, що задовольняє рівняння:

b + (a – b) = a.

Тоді множення обох частин отриманої рівності на c з наступним застосуванням аксіоми дистрибутивності приводить до рівності:

b c + (a – b) c = a c.

А звідси згідно того ж означення різниці елемент (a – b) c є різницею елементів a c і b c, тобто

(a – b) c = a c – b c.

Теорема доведена.

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

Так для кільця чисел можна вивести також властивість єдиності одиниці по додаванню, показати виконання рівностей a (-b) = - (a b), (-a) (-b) = a b і інших, а потім поширити їх на інші кільця.

Не варто, однак, думати, що будь-які властивості додавання і множення на множині чисел зберігаються в будь-якому кільці. Зокрема, множення чисел має наступну властивість: якщо добуток двох чисел дорівнює нулю, то хоча б один із множників дорівнює нулю (*). Однак, можна привести приклади кілець, у яких існують такі пари елементів a 0, b 0, що a b = 0 (ці елементи a, b називаються дільниками нуля). Зокрема, кільце усіх функцій дійсної змінної x, скрізь визначених і приймаючих значення на множині дійсних чисел, містить наступні функції:

f(x) = 0 при x 0, f(x) = x при x 0; g(x) = x при x 0, g(x) = 0 при x 0.

Обидві ці функції відмінні від нуля, тому що не при всіх значеннях x дорівнюють нулю їх значення, а їх добуток дорівнює нулю.

Очевидно, що в цьому випадку згадана вище властивість (*) для чисел в загальному випадку встановлюється за допомогою властивостей, що додатково характеризують числові множини і таких, що не належать аксіоматизованим властивостям кільця чи доведеним з їхньою допомогою.

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

24. Решітк як лгебр їчн систем

Спочатку покажемо, що деякі відомі нам об'єкти можна визначити як алгебраїчні системи. Введемо ще одне означення решітки.

Визначення. Решіткою будемо називати алгебраїчну систему А, , , сигнатура якої включає дві бінарні операції, що мають такі властивості:

1) ідемпотентність: aj aj = aj,

aj aj = aj; 2) комутативність: aj aj = aj ai,

ai aj=aj ai;

3) асоціативність: (ai aj) ak = ai (aj ak),

(ai aj) ak = ai (aj ak); 4) поглинання: ai (ai aj) = ai,

ai (ai aj) = ai.

Тут - операція взяття найменшої верхньої границі (верхньої грані) елементів; - операція узяття найбільшої нижньої границі (нижньої грані) елементів.

26

У попередньому розділі ми ввели означення решітки, використовуючи поняття частково упорядкованої множини. Нагадаємо його.

Решіткою називається упорядкована множина A, , будь-які два елементи ai, aj якої мають нижню грань (перетин ai aj) і верхню грань (об'єднання ai aj).

Продемонструємо рівносильність обох визначень поняття решітки.

Припустимо спочатку, що задана решітка, визначена як частково впорядкована множина. Тоді виконання властивостей ідемпотентності і комутативності очевидне (дійсно, варто тільки згадати означення верхньої і нижньої граней і застосувати його для пар елементів). Перевіримо, чи виконується властивість асоціативності, наприклад, для об'єднання . Тому що - верхня грань, то виконуються наступні співвідношення:

(ai aj) ak ai aj ai, (ai aj) ak ai aj aj,

(ai aj) ak ak.

Звідси, виходячи з того ж означення верхньої грані, одержуємо:

(ai aj) ak aj ak.

Таким чином, маємо:

(ai aj) ak ai (aj ak).

Аналогічно можемо одержати:

ai (aj ak) (a i ai) ak.

З двох останніх нерівностей випливає властивість асоціативності.

Зовсім аналогічно доводиться властивість асоціативності для перетину .

Залишається продемонструвати справедливість властивості поглинання. Почнемо з першої тотожності властивості поглинання. Тому що - верхня грань, а - нижня грань, то виконується наступне співвідношення:

З нерівностей (*) і (**) випливає властивість поглинання. Зовсім аналогічно доводиться друга тотожність властивості поглинання.

Нехай тепер решітка визначена як алгебра з операціями і , що задовольняють властивостям

одночасно можуть виконуватися або не виконуватися. Дійсно, якщо ai aj = ai, то відповідно до властивості поглинання

ai aj = (ai aj) aj = aj.

Якщо ж ai aj = aj, то відповідно до властивості поглинання

ai aj = ai (ai aj) = ai.

Якщо для елементів mi і mj мають місце рівності (***), то приймемо ai aj. Таким чином, на множині A визначене відношення часткового порядку. Дійсно, відповідно до властивості ідемпотентності виконується рефлексивність ai ai введеного відношення.

Покажемо його транзитивність, прийнявши ai aj і aj ak. Але тоді за означенням відношення виконуються

ai aj = ai, aj ak = aj,

звідки, відповідно до властивості асоціативності, одержимо

ai ak = (ai aj) ak= ai (aj ak) = ai aj = ai,

іншими словами ai ak.

Покажемо антисиметричність відношення , прийнявши ai aj і aj ai. Але тоді за означенням відношення виконуються

ai aj = ai, aj ai = aj,

звідки, відповідно до властивості комутативності, одержимо ai = aj.

Тепер покажемо, що виконується умова нижньої грані. З рівності (ai aj) ai = ai (ai aj) = (ai ai)

aj = ai aj випливає, що ai aj aj.

Якщо ж у A взяти довільний елемент aq, що задовольняє умовам aq ai, aq aj, тобто aq ai = aq, aq aj=

aq, то aq (ai aj) = (aq ai) ai=aq aj = aq, звідки aq ai aj. Отже, елемент ai aj є нижньою гранню. Зовсім аналогічно доводиться, що виконується умова верхньої грані для елемента ai aj.

25. Ускл днення м тем тичних об'єктів

27

Раніше ми розглянули деякі важливі об'єкти дискретної математики, насамперед числа, множини, функції, операції, відношення, познайомилися з його методом. Тепер розглянемо з цих позицій ще деякі риси дискретної математики, що мають принципове значення для її викладання і розвитку.

Математика має властивість, використовуючи узагальнення, від простих об'єктів переходити до більш складних. Так здійснюється, ми бачили, перехід від об'єктів до множин об'єктів, далі до функцій і перетворень об'єктів на базі введених операцій. Ми одержуємо цілі системи, що самі є математичними об'єктами, далі розглядаються їхні множини, а потім знову переходимо до функцій і перетворень уже на цих множинах об'єктів і т.д.

Як приклад розглянемо введення функцій на множині алгебраїчних систем. Розпочнемо з алгебр з однією операцією.

Нехай A, , S, - напівгрупи.

Визначення. Морфізмом напівгруп називається відображення чи функція : A S напівгрупи A, у напівгрупу S, , що переводить операцію на множині A в операцію на множині S, тобто (ai aj) = (ai)

(aj), ai, aj A (*).

Якщо A, , S, – моноїди, то функція : A S називається морфізмом моноїдов, якщо виконується умова (*) і, крім того, умова

(1A) = 1S.

Якщо морфізм сюр‘ективний, то він називається епіморфізмом. Якщо морфізм ін‘єктивний, то він називається мономорфізмом. Якщо морфізм бієктивний то він називається ізоморфізмом.

Приклад. Наведемо ізоморфізм, який добре відомий усім читачам зі шкільних часів. Нехай задані

моноїди Q1, ,1 і Q2,+,0 , де Q1 = Q2 = {x Q : 0 x }.

Тоді функція lnx = y, x Q1, y Q2, відома нам як логарифмічна, становить собою ізоморфізм

моноїдів Q1, , 1 і Q2, +, 0 . Дійсно, ln(x1 x2) = y1 + y2, де y1 = ln(x1), y2 = ln(x2), і ln(1) = 0.

Поняття морфізма розповсюджується і на інші алгебраїчні системи. У загальному значенні морфізм є відображенням, що зберігає одну або кілька операцій.

Визначення. Нехай A, +, і S, +, - дві алгебраїчні системи, кожна з бінарними операціями додавання і множення. Функція : A S називається морфізмом (щодо цих операцій), якщо для будь-яких

ai, aj A виконується

(ai + aj) = (ai) + (aj), (ai aj) = (ai) (aj).

Якщо морфізм алгебр є бієкцією, то його називають ізоморфізмом, а дані алгебри – ізоморфними. Природним чином поняття ізоморфізму можна поширити і на інші алгебраїчні системи. У наступних лекціях ми розглянемо приклади ізоморфізму деяких важливих класів алгебр.

26.Векторний простір

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

Визначення. Упорядковану систему n чисел = (a1, a2,…,an) назвемо n-вимірним вектором, а числа ai, i = 1,2,…,n – компонентами вектора .

Зокрема, прикладами векторів будуть: 1) вектори, що виходять з початку координат при фіксованій системі координат; 2) коефіцієнти будь-якого лінійного рівняння з n невідомими; 3) кожний розв‘язок будьякої системи лінійних рівнянь з n невідомими.

На множині введених у такий спосіб n-вимірних векторів визначимо природним чином (через покомпонентну рівність) рівність векторів, що становить відношення еквівалентності на множини n- вимірних векторів.

Аналогічно через покомпонентне додавання визначимо суму n-вимірних векторів = (a1, a2,…,an) і= (b1, b2,…,bn) як + = (a1 + b1, a2 + b2,…,an+bn). Очевидно, що додавання n-вимірних векторів комутативне, асоціативне (в силу аналогічних властивостей додавання чисел), має одиницю (нульовий вектор) 0 = (0, 0,…,0) і обернений елемент (протилежний вектор) - = (-a1, -a2,…,-an) для довільного вектора

= (a1, a2,…,an).

Варто зазначити, що введене додавання векторів виникло на основі геометричного додавання векторів за правилом паралелограма.

Крім того, визначимо множення вектора = (a1, a2,…,an) на скаляр (число) k як вектор k = (ka1,ka2,…,kan). Очевидно, що множення вектора на скаляр замкнуте на множини векторів, дистрибутивне щодо додавання векторів (і додавання скалярів), асоціативне, множення вектора на число 1 не змінює вектор.

Визначення. Нехай A, +, - комутативне кільце, кожен елемент a носія якого називається скаляром. На множини A визначимо множину об'єктів L, елементи якої назвемо векторами, і визначимо операції + - векторне додавання і - множення вектора на скаляр. Тоді L, +, називається лінійним векторним простором над кільцем A, якщо:

28

1.L - абелева група щодо операції +;

2.Якщо L, a A то a L;

3.Якщо a, b A, L, то (a b) = a (b );

4.Якщо , L, a, b A то a ( + ) = a + ;

(a + b) = a + b ;

5.1 = .

У векторному просторі виконуються такі співвідношення:

0 = 0, де 0 – адитивна одиниця щодо векторного додавання (нульовий вектор);

(-1) = - , де - – адитивний обернений до елемент;

(-a) = -(a ).

Легко показати, використовуючи властивості операцій:

1)єдиність одиниці по додаванню векторів: якщо 01 і 02 - дві одиниці, те 01 + 02 = 01 і 01 + 02 = 02 + 01 = 02, звідки 01 = 02;

2)єдиність оберненого елемента по додаванню векторів: якщо (- )1 і (- )2 - два зворотних елементи для вектора , те (- )1 + [ + (- )2] = (- )1 + 0 = (- )1 і [(- )1 + ] + (- )2 = 0 + (- )2 = (-)2, звідки (- )1 = (- )2;

3)існування і єдиність різниці - (довести самостійно) і інші.

Визначення. Два лінійних векторних простори L і L‘ над полем дійсних чисел назвемо ізоморфними, якщо існує бієктивна функція : L L‘ така, що ( + ) = ( ) + ( ) і (a ) = a ( ).

Визначення. Систему векторів 1, 2,…, r назвемо лінійно залежною, якщо існують такі числа k1, k2,…,kr,хоча б одне з яких відмінне від нуля, що виконується умова

k1 1 + k2 2 +…+kr r=0...

Наприклад, система векторів 1 = (5,2,1), 2 = (-1,3,3), 3 = (9,7,5), 4 = (3,8,7) лінійно залежна, тому

що 4 1 - 2 -3 3 + 2 4 = 0.

Теорема 6. Система одиничних векторів n-мірного векторного простору

1 = (1,0,0,…,0)2 = (0,1,0,…,0)

…

n = (0,0,0,…,1)

лінійно незалежна.

Доведення. Від супротивного. Нехай k1 1 + k2 2 +…+kn n= 0. Але через те, що ліва частина цієї рівності дорівнює вектору (k1, k2,…,kn), то (k1, k2,…,kn) = 0. Іншими словами, ki = 0, i = 1,2,…,n в силу визначення рівності векторів. Теорема доведена.

Визначення. Лінійно незалежну систему векторів 1, 2,…, r n-вимірного векторного простору назвемо максимальною лінійно незалежною або базою, якщо додавання до цієї системи будь-якого n- вимірного вектора перетворює її в лінійно залежну.

Визначення. Лінійний векторний простір L над полем дійсних чисел назвемо скінченовимірним, якщо в ньому можна знайти скінченну максимальну лінійно незалежну систему. Усяку таку систему векторів назвемо базою простору L.

27. Лінійні перетворення (опер тори)

Загальна теорія систем лінійних рівнянь вимагає введення ще ряду фундаментальних понять, що дозволяють характеризувати умови існування розв‘язків системи лінійних рівнянь, отримання розв‘язків, перетворення одних розв‘язків в інші.

Існування ненульових розв‘язків системи лінійних рівнянь від n змінних у значній мірі визначається лінійною незалежністю векторів, складених з коефіцієнтів рівнянь. Тому важливо досліджувати умови незалежності.

Приведемо без доведення найважливіші результати, отримані в теорії систем лінійних рівнянь:

1)усякі r векторів n-вимірного векторного простору лінійно залежні, якщо r > n;

2)у n-вимірному векторному просторі всяка лінійно незалежна система з n векторів буде максимальною лінійно незалежною;

3)у n-вимірному векторному просторі існує нескінченно багато максимальних лінійно незалежних систем векторів;

4)у n-вимірному векторному просторі всяка максимально лінійно незалежна система векторів складається з n векторів.

В плані обґрунтування перелічених результатів важливим є поняття лінійного вираження векторів через систему векторів.

Визначення. Вектор лінійно виражається через систему векторів 1, 2,…, r, якщо є лінійною комбінацією векторів 1, 2,…, r, тобто існують такі числа l1, l2,…,ln, що l1 1 + l2 2 +…+lr r = . Система векторів 1, 2,…, s лінійно виражається через систему векторів 1, 2,…, r, якщо кожен вектор i , i = 1,…,s, є лінійною комбінацією векторів 1, 2,…, r.

29