Бінарні стосунки. Відношення еквівалентності, фактор-множина

Теорія множин. Основні поняття

Теорія множин є основним визначенням сучасної математики. Вона була створена Георгом Кантором у 1860-х роках. Він писав: «Багато є багато, мислиме як єдине ціле». Поняття множини належить до основних, невизначуваних понять математики. Воно не зводиться до інших, простіших понять. Тому його не можна визначити, а можна лише пояснити. Таким чином, безліч - об'єднання в одне ціле об'єктів, добре помітних нашою інтуїцією або нашою думкою; сукупність деяких об'єктів, визначених загальною ознакою.

Наприклад,

1. Безліч жителів м. Воронежа

2. Безліч точок площини

3. Безліч натуральних чисел ℕі ін.

Багато зазвичай позначаються великими латинськими літерами( A, B, Cі т.д.). Об'єкти, що становлять це безліч, називаються його елементами. Елементи множини позначаються малими латинськими літерами( a, b, cі т.д.). Якщо Х- безліч, то запис х∈Хозначає, що хє елемент множини Хабо що хналежить безлічі Х, а запис х∉Х, що елемент хне належить множині Х. Наприклад, нехай ℕ–безліч натуральних чисел. Тоді 5 ℕ , а 0,5∉ℕ .

Якщо безліч Yскладається з елементів множини Х, то кажуть, що Yє підмножиною безлічі Хі позначають Y⊂Х(або Y⊆Х). Наприклад, безліч цілих чисел ℤ є підмножиною раціональних чисел ℚ .

Якщо для двох множин Хі Yодночасно мають місце два включення Х Yі Y Х, тобто. Хє підмножина безлічі Yі Yє підмножина безлічі Х, то безлічі Хі Yскладаються з тих самих елементів. Такі множини Хі Yназивають рівними та пишуть: Х = Y.

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

Для опису множин можуть використовуватись такі способи.

Способи завдання множин

1. Перерахування об'єктів. Використовується тільки для кінцевих множин.

Наприклад, Х = (x1, x2, x3 ... x n). Запис Y ={1, 4, 7, 5} означає, що безліч складається з чотирьох чисел 1, 4, 7, 5 .

2. Вказівка ​​характеристичної властивості елементів множини.

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

Х = (х: Р (х))

(множина Хскладається з таких елементів х, для яких виконується властивість Р(х)).

Порожнє безліч можна задати, вказавши його властивості: Ø=(х: х≠х)

Побудувати нові множини можна за допомогою вже заданих, використовуючи операції над множинами.

Операції над множинами

1. Об'єднанням (сумою) називається безліч, що складається з усіх тих елементів, кожен з яких належить хоча б одному з множин Аабо У.

А∪ В = (х: х А або х).

2. Перетином (твором) називається безліч, що складається з усіх елементів, кожен з яких одночасно належить як множині А, так і безлічі У.

А∩В=(х: х А і х).

3. Різницею множин Аі Уназивається безліч, що складається з усіх тих елементів, які належать безлічі Аі не належать безлічі У.

А \ В = (х: х А і х В)

4. Якщо А- підмножина безлічі У. То безліч В\Аназивають доповненням множини Адо множини Уі позначають А’.

5. Симетричною різницею двох множин називають безліч А∆В=(А\В) (В\А)

N- множина всіх натуральних чисел;
Z- множина всіх цілих чисел;
Q- множина всіх раціональних чисел;
R- множина всіх дійсних чисел;
C- множина всіх комплексних чисел;
Z 0- множина всіх невід'ємних цілих чисел.

Властивості операцій над множинами:

1. А В=В А (комутативність об'єднання)

2. А В=В А (комутативність перетину)

3. А(У С) = (А в) С (асоціативність об'єднання)

4. А (В С) = (А в) С (асоціативність перетину)

5. А (В С) = (А в) (А С) (1 закон дистрибутивності)

6. А (В С) = (А в) (А З) (2 закон дистрибутивності)

7. А Ø=А

8. А U= U

9. А Ø= Ø

10. А U=А

11. (А В) '=А' (закон де Моргана)

12. (А В) '=А' (закон де Моргана)

13. А (А В) = А (закон поглинання)

14. А (А В) = А (закон поглинання)

Доведемо властивість №11. (А В) '=А' В’

За визначенням рівних множин, нам необхідно довести два включення 1) (А В)' ⊂А' В’;

2) А’ В'⊂(А В) '.

Для доказу першого включення розглянемо довільний елемент х∈(А В) '=Х\(А∪В).Це означає, що х∈Х, х∉ А∪В. Звідси слідує що х∉Аі х∉Втому х∈Х\Аі х∈Х\В, а значить х∈А'∩В'. Таким чином, (А В)'⊂А' В’

Назад, якщо х∈А’ В’, то ходночасно належить множинам А', В', а значить х∉Аі х∉В. З цього виходить що х∉ А Утому х∈(А В) '. Отже, А’ В'⊂(А В) '.

Отже, (А В) '=А' В’

Безліч, що складається з двох елементів, в якому визначено порядок проходження елементів, називається впорядкованою парою. Для її запису використовують круглі дужки. (х 1, х 2)- Двоелементне безліч, в якому х 1 вважається першим елементом, а х 2 - другим. Пари (х 1, х 2)і (х 2, х 1),де х 1 ≠ х 2, Вважаються різними.

Безліч, що складається з n елементів, в якому визначено порядок прямування елементів, називається впорядкованим набором n елементів.

Декартове твір - довільна безліч X 1 , X 2 ,…, X nупорядкованих наборів з n елементів, де x 1 X 1 , x 2 X 2 ,…, x n X n

Х 1 Х n

Якщо множини X 1 , X 2 ,…, X nзбігаються (X 1 = X 2 = ... = X n), то їх твір позначається Х n.

Наприклад, ℝ 2 – безліч упорядкованих пар речових чисел.

Відносини еквівалентності. Фактор-множини

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

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

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

Наприклад, відносини х=у, х≥ує бінарними відносинами на безлічі ℝ.

Бінарне відношення Rна безлічі Хназивається ставленням еквівалентності, якщо:

1. (х, х) R; х Х (властивість рефлексивності)

2. (х, у) R => (у,х) R (властивість симетричності)

3. (х, у) R, (у,z) R, то (x,z) R (властивість транзитивності)

Якщо пара (х,у)увійшла у відносини еквівалентності, то х і у називають еквівалентними (Х~у).

1.Нехай ℤ - безліч цілих чисел, m≥1- ціле число. Задамо ставлення еквівалентності Rна ℤ так щоб n~k, якщо n-kділиться на m. Перевіримо, чи виконуються властивості цьому плані.

1. Рефлексивність.

Для будь-кого n∈ℤ ℤ такого, що (p,p)∈R

р-р=0. Так як 0∈ ℤ , то (p, p)∈ℤ.

2. Симетричність.

З (n,k) ∈Rслід, що існує таке р∈ ℤ, що n-k=mp;

k-n = m(-p), -p∈ ℤ, отже (k,n) ∈R.

3. Транзитивність.

З того, що (n,k) ∈R, (k,q) ∈Rслід, що існують такі р 1і р 2 ∈ ℤ, що n-k=mp 1і k-q=mp 2. Склавши дані висловлювання, отримуємо, що n-q=m(p 1 + p 2), p 1 + p 2 =p, p∈ ℤ. Тому (n,q) ∈ ℤ.

2.Розглянемо безліч Хвсіх спрямованих відрізків простору чи площини . =(А, В). Введемо відношення еквівалентності Rна Х.

(тобто яке має такі властивості: кожен елемент безлічі еквівалентний сам собі; якщо xеквівалентно y, то yеквівалентно x; якщо xеквівалентно y, а yеквівалентно z, то xеквівалентно z ).

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

Відображення з Xу безліч класів еквівалентності називається фактор відображенням.

Приклади

p align="justify"> Факторизацію безлічі розумно застосовувати для отримання нормованих просторів з напівнормованих, просторів зі скалярним твором з просторів з майже скалярним твором і ін. Для цього вводиться відповідно норма класу, рівна нормі довільного його елемента, і скалярний добуток класів як скалярний добуток довільних елементів класів. У свою чергу відношення еквівалентності вводиться наступним чином (наприклад для утворення нормованого факторпростору): вводиться підмножина вихідного напівнормованого простору, що складається з елементів з нульовою напівнормою (до речі, воно лінійно, тобто є підпростором) і вважається, що два елементи еквівалентні належить цьому самому підпростору.

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

Приклади

Див. також

Wikimedia Foundation.

2010 .

Дивитись що таке "Фактормножина" в інших словниках:

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

Велика Радянська Енциклопедія Когомологія Галуа групи. Якщо М абелева група і група Галуа розширення, що діє на М, то когомології Галуа є групи когомології, що визначаються комплексом, складається з усіх відображень, a d комежний оператор (див. Когомології груп).

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

Конструкція, яка вперше з'явилася в теорії множин, а потім стала широко використовуватися в алгебрі, топології та інших галузях математики. Важливий окремий випадок І. п. це І. п. спрямованого сімейства однотипних математичних структур. Нехай … Когомологія Галуа групи. Якщо М абелева група і група Галуа розширення, що діє на М, то когомології Галуа є групи когомології, що визначаються комплексом, складається з усіх відображень, a d комежний оператор (див. Когомології груп).

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

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

Нехай на багатьох задано ставлення еквівалентності. Тоді безліч всіх класів еквівалентності називається фактором безліччю і позначається. Розбиття множини на класи еквівалентних елементів називається його факторизацією. Відображення з… … Вікіпедія

Під спрямованим відрізком у геометрії розуміють упорядковану пару точок, перша з яких точка A називається його початком, а друга B його кінцем. Зміст 1 Визначення … Вікіпедія

У різних розділах математики ядром відображення називається деяка множина kerf, що в певному сенсі характеризує відмінність f від ін'єктивного відображення. Конкретне визначення може відрізнятися, однак для ін'єктивного відображення f… … Вікіпедія

Чинник множини

Безліч.

Відношенням часткового порядку на множині x називається бінарне відношення, яке є антисиметричним, рефлексивним і транзитивним і позначається в
вигляді пари:

Бінарне ставлення називається толерантністю, якщо воно рефлексивне та симетричне.

Бінарне відношення називається квазіпорядком, якщо воно є іррефлексивним, антисиметричним і транзитивним (передпорядок).

Бінарне ставлення називається строгим порядком, якщо воно рефлексивне і транзитивне.

Енарною алгебраїчною операцією на множині М називається функція

- Унарна операція;

- Бінарна операція;

- Тіарна операція.

Бінарна операція алгебри –

– операція, що ставить у відповідність кожній упорядкованій парі з множини М деякі елемент множини М.

Властивості:

1) Комутативність:

2) Асоціативність:

Нейтральний елемент

Безліч М для бінарної алгебраїчної операції

Називається елемент:

• 
  Чинник безлічі– сукупність класів еквівалентності цього безлічі. Відношенням часткового порядку на безлічі x називається бінарне відношення...


• 
  Наступне питання ". Чинник безлічі. Чинник безлічі- Сукупність. Мультиплікативні та адитивні форми.


• 
  Чинник безлічі- Сукупність.
  Безліч- Сукупність певних і різних між собою об'єктів мислимих як єдине ціле.


• 
  Мультиплікативна функція – а... докладніше». Чинник безлічі. Чинник безлічі– сукупність класів еквівалентності цього безлічі.


• 
  Насправді процес виробництва протікає складніше, яке продукт результат використання безлічі факторів.


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


• 
  Оптимізація рішень щодо залучення капіталу – це процес дослідження безлічі факторів, що впливають на очікувані результати...

Нехай R – бінарне відношення на множині X. Відношення R називається рефлексивним , якщо (x, x) R для всіх x X; симетричним – якщо з (x, y) Î R випливає (y, x) Î R; транзитивним числу 23 відповідає варіант 24 якщо (x, y) R і (y, z) R тягнуть (x, z) R.

Приклад 1

Будемо говорити, що x Î X має спільне з елементом y X X, якщо безліч
x Ç y не порожньо. Відношення мати спільне буде рефлексивним та симетричним, але не транзитивним.

Відношенням еквівалентностіна X називається рефлексивне, транзитивне та симетричне відношення. Легко бачити, що R Í X ´ X буде відношенням еквівалентності тоді і тільки тоді, коли мають місце включення:

Id X IR (рефлексивність),

R -1 IR (симетричність),

R ° R Í R (транзитивність).

Насправді ці три умови рівносильні таким:

Id X R, R -1 = R, R ° R = R.

Розбиттяммножини X називається безліч А попарно непересічних підмножин a IX таких, що UA = X. З кожним розбиттям А можна пов'язати відношення еквівалентності ~ на X, вважаючи x ~ y, якщо x і y є елементами деякого a Î A.

Кожному відношенню еквівалентності ~ на X відповідає розбиття А, елементами якого є підмножини, кожне з яких складається з ~. Ці підмножини називаються класами еквівалентності . Це розбиття А називається фактор-множиною множини X по відношенню ~ і позначається: X/~.

Визначимо відношення ~ на множині w натуральних чисел, вважаючи x ~ y, якщо залишки від поділу x і y на 3 рівні між собою. Тоді w/~ складається з трьох класів еквівалентності, що відповідають залишкам 0, 1 та 2.

Відношення порядку

Бінарне відношення R на множині X називається антисиметричним , якщо з x R y та y R x випливає: x = y. Бінарне відношення R на множині X називається ставленням порядку якщо воно рефлексивне, антисиметричне і транзитивне. Легко бачити, що це рівносильно виконанню наступних умов:

1) Id X IR (рефлексивність),

2) R Ç R -1 (антисиметричність),

3) R ° R IR (транзитивність).

Упорядкована пара (X, R), що складається з множини X і відношення порядку R на X, називається частково впорядкованою безліччю .

Приклад 1

Нехай X = (0, 1, 2, 3), R = ((0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2) ), (1, 3), (2, 2), (3, 3)).

Оскільки R відповідає умовам 1 – 3, то (X, R) – частково впорядковане безліч. Для елементів x = 2, y = 3, неправильно ні x R y, ні y R x. Такі елементи називають незрівнянними . Зазвичай, відношення порядку позначають £. У наведеному прикладі 0 £ 1 і 2 £ 2, але невірно, що 2 £ 3.

Приклад 2

Нехай< – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.

Елементи x, y Î X частково впорядкованої множини (X, £) називаються порівнянними якщо x £ y або y £ x.

Частково впорядкована множина (X, £) називається лінійно упорядкованим або ланцюгом , якщо будь-які два його елементи можна порівняти. Безліч прикладу 2 буде лінійно впорядкованим, та якщо з прикладу 1 – немає.

Підмножина A Í X частково впорядкованої множини (X, £) називається обмеженим зверху якщо існує такий елемент x Î X, що a £ x для всіх a Î A. Елемент x Î X називається найбільшим у X, якщо y £ x для всіх y Î X. Елемент x Î X називається максимальним, якщо немає відмінних від x елементів y Î X, для яких x £ y. У прикладі 1 елементи 2 та 3 будуть максимальними, але не найбільшими. Аналогічно визначаються обмеження знизу підмножини, найменший та мінімальний елементи. У прикладі 1 елемент 0 буде найменшим і мінімальним. У прикладі 2 цими властивостями також має 0, але (w, £) немає ні найбільшого, ні максимального елемента.

Якщо ставлення R має властивості: рефлексивне симетричне транзитивне, тобто. є відношенням еквівалентності (~ або ≡ або Е) на множині M , то безліч класів еквівалентності називається фактор безліччю множини M щодо еквівалентності R і позначається M/R

Тут є підмножина елементів множини M еквівалентних x званих класом еквівалентності.

З визначення фактор-множини випливає, що воно є підмножиною булеану: .

Функція називається ототожненнямі визначається так:

Теорема.Фактор-алгебра F n /~ ізоморфна алгебри булевих функцій B n

Доведення.

Шуканий ізоморфізм ξ : F n / ~ → B n визначається за таким правилом: класу еквівалентності ~(φ) зіставляється функція f φ , має таблицю істинності довільної формули з множини ~(φ) . Оскільки різним класам еквівалентності відповідають різні таблиці істинності, відображення ξ ін'єктивно, а так як для будь-якої булевої функції f з В п знайдеться формула, що представляє функцію f, то відображення ξ сюр'єктивно. Збереження операцій , 0, 1 під час відображення ξ перевіряється безпосередньо. ЧТД.

По теоремі про функціональну повноту кожної функції, яка не є константою 0 , відповідає деяка СДНФ ψ , що належить класу ~(φ) = ξ -1 (f) формул, що становлять функцію f . Виникає завдання перебування у класі ~(φ) диз'юнктивної нормальної форми, що має найпростішу будову.

Кінець роботи -

Ця тема належить розділу:

Курс лекцій з дисципліни

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

Якщо Вам потрібний додатковий матеріал на цю тему, або Ви не знайшли те, що шукали, рекомендуємо скористатися пошуком по нашій базі робіт:

Що робитимемо з отриманим матеріалом:

Якщо цей матеріал виявився корисним для Вас, Ви можете зберегти його на свою сторінку в соціальних мережах:

Твітнути

Всі теми цього розділу:

Предмет дискретної математики
Предмет дискретна (фінітна, кінцева) математика – напрямок математики, що вивчає властивості дискретних структур, тоді як класична (безперервна) математика вивчає властивості об'

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

Вправи
1. Доведіть, що ізоморфне відображення завжди ізотонне, а зворотне твердження неправильне.

2. Запишіть мовою множин свою групу.
3. Запишіть мовою множин предмети, які

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

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

Як видно з наведених приклад
Потужність множини

Потужність для кінцевої множини дорівнює числу його елементів. Наприклад, потужність універсуму (A) множини A потужністю n
А1A2A3 | + … + | А1A2A3 | + … + | А1A2An | + … + | An-2An-1An | + (-1)n-1 | А1A2A3 ... An |

Кінцева множина А має потужність k, якщо вона рівномірно відрізку 1.. k;:
Підмножина, власна підмножина

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

Додавання та видалення елементів
Якщо А - множина, а х - елемент, причому, то елемент

Обмежені множини. Межі множин
Нехай на деякій множині X задана числова функція f(х).

Верхньою гранню (кордоном) функції f(х) називається таке число
Точна верхня (нижня) межа

Сукупність всіх верхніх меж Е позначається через Еs, всіх нижніх кордонів - через Еi. У випадку
Точна верхня (нижня) межа множини

Якщо елемент z належить перетину множини E і множині всіх її верхніх меж Es (відповідно нижніх г
Основні властивості верхніх та нижніх кордонів

Нехай X - частково впорядкована множина.
1. Якщо, то

Безліч з атрибутивної точки зору
Агрегатна точка зору, на відміну від атрибутивної, є логічно неспроможною в тому плані, що вона призводить до парадоксів типу Рассела і Кантора (див. нижче).

В рамках атрибутивної т
Структура

Частково впорядкована множина X називається структурою, якщо в ній будь-яка двоелементна множина
Покриття та розбиття множин

Розбиттям множини А називається сімейство Аi
Бінарні відносини

Послідовність довжини п, члени якої є а1, .... аn, будемо позначати через (а1, .... а
Властивості бінарних відносин

Бінарне відношення R на множині Холодить наступними властивостями: (а) рефлексивно, якщо хRх
Тернарні відносини

Декартовим твором XY
N-арні відносини

За аналогією з декартовим твором двох множин X,Y можна побудувати декартовий твір X
Відображення

Відображення – це зв'язки між елементами множин. Найпростішими прикладами відносин є відносини приналежності х
Відповідність

Підмножина Sдекартового твору називається n-арною відповідністю елементів множин Mi.
Формально

Функція
У всіх розділів дискретної математики лежить поняття функції.

Нехай Х -
Подання функції у термінах відносин

Функцією називається бінарне відношення f, якщо з і
Ін'єкція, сюр'єкція, бієкція

При використанні терміна «відображення» розрізняють відображення ХвY та відображення Х на Y
Зворотня функція

Для довільних, визначимо
Частково впорядковані множини

Перестановки із повтореннями
Нехай у множині A є однакові (повторювані) елементи. Перестановкою з повтореннями складу (n1, n2, …, nk

Розміщення
Кортежі довжини k (1≤k≤n), що складаються з різних елементів n-елементної множини A (кортежі відрізняються

Розміщення з повтореннями
Нехай у множині A є однакові (повторювані) елементи. Розміщеннями з повтореннями з n елементів по k нази

Упорядковане розміщення
Розмістимо п об'єктів по m ящиках так, щоб кожна ящик містив би послідовність, а не безліч, як раніше, вміщених у ньому об'єктів. Два

Поєднання
З m-елементної множини A побудуємо впорядковану множину довжини n, елементи якої є розміщеннями з одними і тими.

Поєднання з повтореннями
Отримані формули справедливі лише тоді, коли в множині A немає однакових елементів. Нехай є елементи n видів і з них складається кортеж з

Метод виконує функцій
Цей метод використовується для перерахування комбінаторних чисел та встановлення комбінаторних тотожностей.

Вихідним пунктом є послідовність (ai) комбінатор
Алгебраїчна система

Алгебраїчною системою A називається сукупність ‹M,O,R›, перша складова якої M є непорожня множина, друга компонента O – множина
Замикання та подалгебри

Підмножина називається замкненою щодо операції φ, якщо
Алгебри з однією бінарною операцією

Нехай на безлічі М задана одна бінарна операція. Розглянемо алгебри, що породжуються нею, але попередньо розглянемо деякі властивості бінарних операцій.
Бінарна про<М, f2>Групоїд

Алгебра виду
називається групоїдом. Якщо f2 - операція типу множення (<М,

Цілі числа за модулем m
Дано кільце цілих чисел .

Нагадаємо. Алгебра
Конгруенції

Конгруенцією на алгебрі A =
(Σ - сигнатура алгебри складається тільки з функціональних символів) називається таке відношення еквівалентності , що

За аналогією з декартовим твором двох множин X,Y можна побудувати декартовий твір X
Елементи теорії графів

Графи – математичні об'єкти.
Теорія графів застосовується у таких галузях, як фізика, хімія, теорія зв'язку, проектування ЕОМ, електротехніка, машинобудування, архітектура, дослідження про

Граф, вершина, ребро
Під неорієнтованим графом (або коротшим графом) розумітимемо таку довільну пару G =<и, v>, то будемо говорити, що ребро є інцидентно вірним

Зворотня відповідність
Оскільки є безліч таких вершин

Ізоморфізм графів
Два графи G1 = та G2 = ізоморфні (G

Шлях, орієнтований маршрут
Шляхом (або орієнтованим маршрутом) орієнтованого графа називається послідовність дуг, до якого

Сумежні дуги, суміжні вершини, ступінь вершини
Дуги а = (хi, хj), хi ≠ хj, що мають загальні кінцеві вершини, н

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

Теорема.
Граф зі зваженими дугами

Граф G = (N, A) називається зваженим, якщо на безлічі дуг A визначено деяку функцію l: A → R, яку на
Матриця сильної зв'язності

Матриця сильної зв'язності: по діагоналі ставимо 1; заповнюємо рядок X1 - якщо вершина досяжна з X1 та X1 д
Дерева

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

Доказ Розглянемо дерево G(V, Е). Дерево - зв'язковий граф, отже,
Теорема

Центр вільного дерева складається з однієї вершини або двох суміжних вершин: Z(G) = 0&k(G) = 1 → С(G) = К1
Орієнтовані, впорядковані та бінарні дерева

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

1. Кожна дуга входить у якийсь вузол. З п. 2 визначення 9.2.1 маємо: v
Впорядковані дерева

Багато Т1,.. ., Тk в еквівалентному визначенні ордерева є піддеревами. Якщо відносний порядок піддерев Т1,.. .,
Бінарні дерева

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

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

End for
Будь-яке вільне дерево можна орієнтувати, призначивши один із вузлів коренем. Будь-яке ордерево можна довільно впорядкувати. Для нащадків одного вузла (братів) упорядкованого ордерєва визначено одне

Основні логічні функції
Позначимо через E2 = (0, 1) - множина, що складається з двох чисел. Числа 0 і 1 є основними у дискретній маті

Бульова функція
Булевою функцією від n аргументів x1, x2, …, xn, називається функція f з n-ого ступеня множини

Двохелементна булева алгебра
Розглянемо безліч В = (0,1) і визначимо на ньому операції, згідно з таблицями іст

Таблиці булевих функцій
Булева функція від n змінних може бути задана таблицею, що складається з двох стовпців та 2n рядків. У першому стовпці перераховуються всі набори з B

F5 – повторення з y
f6 – сума за модулем 2 f7

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

Для вирішення задачі знаходження СДНФ та СКНФ, еквівалентних вихідній формулі φ, попередньо розглянемо розкладання булевої функції f(x1, х2
Друга теорема Шеннона

З принципу двоїстості для булевих алгебр справедлива Теорема 6.4.3 (друга теорема Шеннона). Будь-яка булева функція f(x1, х2,...
Функціональна повнота

Теорема (про функціональну повноту). Для будь-якої булевої функції f знайдеться формула φ, яка представляє функцію f
Алгоритм знаходження сднф

Для знаходження СДНФ цю формулу потрібно привести спочатку до ДНФ, а потім перетворити її кон'юнкти на конституенти одиниці за допомогою наступних дій: а) якщо до кон'юнкту входить деяка
Метод Квайна

Розглянемо метод Квайна для знаходження МДНФ, що представляє цю булеву функцію. Визначимо такі триоперації: - Операція повного склеювання -
Канонічне представлення логічних функцій

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

Системи булевих функцій
Нехай дані булеви функції f(g1, g2, …, gm) та g1(x1, x2, …, xn), g2(x1

Базис Жегалкіна
Розглянемо систему. Вона є повною, тому що будь-яка функція зі стандартного базису виражається.

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

Алгебра Жегалкіна
Сума по модулю 2 кон'юнкція і константи 0 і 1 утворюють функціонально повну систему, тобто. утворюють алгебру - алгебру Жегалкіна.

A =
Логіка висловлювань

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

Нехай Х1, Х2, ..., Хп довільні змінні. Ці змінні називатимемо предметними. Нехай набори змінних ви
Застосування предикатів в алгебрі

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

Булева алгебра предикатів
Оскільки до предикатів можна застосовувати логічні операції, то їм справедливі основні закони булевої алгебри.

Теорема. (Властивості логічних операцій для предикатів).
багато

F↔G=(F→G)(G→F), F→G=неFG
2. Використовувати закон нене F = F, закони де Моргана: не (F

Обчислення предикатів
Обчислення предикатів називають ще теорій першого порядку.

У обчисленні предикатів, так само як і в обчисленні висловлювань, на першому за важливістю місці стоїть проблема розв'язання
Слідування та еквіваленція