Зміст
Введення
Завдання 1
Уявити за допомогою кіл Ейлера множинне вираз
Використовуючи закони та властивості алгебри множин, спростити заданий вираз
Завдання 2
Задані безлічі кортежів
Показати, що ці множини являють собою відповідності між множинами N 1 і N 2 , якщо N 1 = N 2 =. Дати повну характеристику цих відповідностей
Завдання 3
Частково впорядкована множина М задано безліччю впорядкованих пар
Побудувати діаграму і визначити, чи є дане безліч гратами. Якщо заданий безліч є гратами, то визначити, чи є грати дедекіндовой, дистрибутивної ...
Завдання 4
Чи є повною система булевих функцій ? Якщо система функцій повна, то виписати всі можливі базиси
Завдання 5
Мінімізувати булеву функцію за методом Квайна - Мак-Класки
Завдання 6
Для неорієнтованого графа, у якого,
а) обчислити числа;
б) визначити хроматичне число ...
Завдання 7
Для заданої мережі:
а) знайти величину мінімального шляху і сам шлях від вершини до вершини за алгоритмом Дейкстри;
б) використовуючи алгоритм Форда-Фалкерсона, визначити максимальний потік (v 1 - вхід, v 6 - вихід мережі) і вказати мінімальний розріз, що відокремлює v 1 від v 6 , якщо задана матриця ваг (довжин, пропускних спроможностей) Р ...
Література
Введення
Проблеми, пов'язані з поняттями нескінченності, дискретності і безперервності, розглядалися в математиці, як і у філософії, давньогрецькими мислителями, починаючи з 6 століття до нашої ери. Під впливом творів Арістотеля вони широко обговорювалися середньовічними вченими і філософами в країнах Європи та Азії. Через всю історію математики проходить ідея подолання між актуальною і потенційною нескінченністю, з одного боку, між дискретним характером числа і безперервної природою геометричних величин - з іншого. Вперше проблема математичної нескінченності і пов'язаних з нею понять була широко поставлена ​​в найбільш загальному вигляді в теорії множин, основи якої були розроблені в останній чверті 19 століття Георгом Кантором.
Мета контрольної роботи - ознайомиться з основними поняттями та методами вирішення по дискретній математиці, вміти застосувати отримані знання при вирішенні практичного завдання.
Завдання 1
Уявити за допомогою кіл Ейлера множинне вираз
.
Використовуючи закони і властивості алгебри множин, спростити заданий вираз.
Рішення:
Використовуючи круги Ейлера і, враховуючи, що операція перетину виконується раніше операції об'єднання, отримаємо наступні малюнки:
Об'єднуючи заштриховані області, отримаємо шукане безліч:
Спростимо задане вираз:
=
.
Завдання 2
Задані безлічі кортежів:
.
Показати, що ці безлічі являють собою відповідності між множинами N 1 і N 2 , якщо N 1 = N 2 =. Дати повну характеристику цих відповідностей
Рішення:
Знайдемо декартів твір:
Видно, що задані безлічі є підмножинами цього пря-мого твору. Отже, дані безлічі тобто відповідності.
а).
Область визначення:. Отже, відповідність є частково певним.
Область значень:. Отже, відповідність є сюр'ектівним.
Образом елемента є два елемента. Значить відповідність не є функціональним. З цього випливає, що відповідність не є функцією, відображенням.
б).
Область визначення:. Отже, відповідність є частково певним.
Область значень:. Отже, відповідність не є сюр'ектівним.
Образом будь-якого елементу з є єдиний елемент з. Отже, відповідність є функціональним, функци-їй. Відповідність є частково визначеним. Це означає, що функція є частково визначеною і не є відображенням.
в).
Область визначення:. Отже, відповідність усюди визначено.
Область значень:. Отже, відповідність не є сюр'ектівним.
Образом будь-якого елементу з є єдиний елемент з. Отже, відповідність є функціональним, функцією. Так як відповідність усюди визначено, то маємо повністю певну функцію, тобто маємо відображення N 1 в N 2 .
г).
Область визначення:. Значить, відповідність повністю визначено.
Область значень:. Значить, відповідність сюр'ектівно.
Образом будь-якого елементу з N 1 є єдиний елемент з N 2 . Отже, відповідність є функціональним, функцією.
Так як відповідність всюди визначено, сюр'ектівно, функціонально і прообразом будь-якого елементу з є єдиний елемент з, то відповідність є взаємно однозначним.
Так як функція повністю визначена і відповідність сюр'ектівно, то маємо відображення N 1 на N 2 .
Так як для будь-яких двох різних елементів з N 1 їх образи з N 2 також різні, то відображення є ін'ектівним.
Так як відображення є одночасно сюр'ектівним і ін'ектівним, то маємо биективное відображення (взаємно однозначне відображення).
Завдання 3
Частково впорядкована безліч М задано безліччю впорядкованих пар
.
Побудувати діаграму і визначити, чи є дане безліч гратами. Якщо заданий безліч є гратами, то визначити, чи є грати дедекіндовой, дистрибутивної.
Рішення:
Побудуємо діаграму:
Побудуємо таблицю:
Пари
елементів
Н.Г.
В.Г.
Н.Н.Г.
Н.В.Г.
1,2
1
2,5
1
2
1,3
1
3,4,5
1
3
1,4
1
4,5
1
4
1,5
1
5
1
5
1,6
1
6,2,5
1
6
2,3
1
5
1
5
2,4
1
5
1
5
2,5
2,6,1
5
2
5
2,6
6,1
2,5
6
2
3,4
3,1
4,5
3
4
3,5
3,1
5
3
5
3,6
1
5
1
5
4,5
4,3,1
5
4
5
4,6
1
5
1
5
|
