Доведення теоретико-математичних тотожностей і тверджень (стр. 1 из 5)

Курсова робота

з дисципліни дискретний аналіз

Доведення теоретико-математичних тотожностей і тверджень

Зміст

алгоритм програма множина графи

1. Доведення рівностей методом математичної індукції

2. Розробка алгоритму та написання програми обчислення множин

2.1. Теоретичні відомості

2.2. Проект обчислення

2.3. Організація структури програми

2.4. Вихідний текст програми

2.5.Опис процедур

2.5.1. Опис процедури SYS

2.5.1.1. Постановка задачі

2.5.1.2. Математична модель

2.5.1.3. Алгоритм рішення задачі

2.5.1.4. Блок-схема

2.5.2 Опис процедури OBED

2.5.3 Опис процедури PERET

2.5.4 Опис процедури RIZ

2.6. Результат

3. Доведення теоретико-математичних тотожностей і тверджень

4. Побудува таблиці істинності висловлень

4.1. Теоретичні відомості

4.2. Рішення

5. Побудова диз’юнктивної нормальної форми (ДНФ)

5.1. Теоретичні відомості

5.2. Рішення

6. Побудова досконалої диз’юнктивної нормальної форми (ДДНФ)

6.1. Теоретичні відомості

6.2.Рішення

7. Розробка алгоритму та написання програми знаходження множини елементарних циклів у графі

7.1. Теоретичні відомості

7.2. Алгоритм рішення задачі

7.3. Блок-схема програми

7.4. Вихідний текст програми

7.5. Результат роботи програми

Список літератури

1.Доведення рівностей методом математичної індукції

Теоретичні відомості

ТЕОРЕМА. Нехай властивість Р вірна для п =1 і нехай з істинності Р для п = к випливає його істинність для п = к+1. Тоді властивість Р вірна для кожного

.

ТЕОРЕМА.Нехай множина

має такі властивості.

1.

.

2. Для кожного

, якщо , то .

Тоді

.

ТЕОРЕМА(Зворотний метод математичної індукції). Нехай властивістьр(n) виконується дляn=1. з того, що вона вірна для кожного

випливає, щор(n) вірна дляn. Значитьр(n) вірна для будь-якого натуральногоn.

Зауваження. У загальному випадку індуктивний процес не зобов'язаний починатися з 1. Базисом індукції може бути будь-як ціле число a.

ТЕОРЕМА. Нехай властивістьр(n) виконується дляn= a. З цього для кожного

випливає істинність дляk+1. Значитьр(n) істинно для будь-якого цілого

.

Завдання 1: Довести, що для будь-якого

(1)

Розв‘язок:

1. Базиси індукції. Перевіримо рівність для п =1. Ліва частина =

, права частина = . Тобто базис індукції виконується.

2. Індуктивне припущення. Вважаємо рівність (1) вірною для п = к, тобто припустимо, що:

(2)

3. Індуктивний перехід. Доведемо рівність (1) для п=к+1, тобто доведемо, що:

,звідси =

Таким чином на підставі методу математичної індукції рівність (1) вірна для кожного п.

2. Розробка алгоритму та написання програми обчислення множин

2.1. Теоретичні відомості

Множина – це будь-яка певна сукупність об'єктів. Об‘єкти з яких складається множина, називаються його елементами.

Множина, що не містить елементів, називається порожньою.

Множини, як об’єкти, можуть бути елементами інших множин. Множини, елементи яких є множини, іноді називають сімейством.

Сукупність об'єктів, які не є множиною, називають класом.

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

Щоб задати множину, потрібно вказати, які елементи йому належать. Це можна зробити різними способами:

- перерахунком елементів: М={a₁,a₂,…,a_k};

- характеристичним предикатом: М={x| P(x)};

- породжуючою процедурою:M={x | x= f}.

Розглянемо множини Y всіх множин, що не містять себе як елементу:

Якщо множина Yіснує, то ми повинні відповісти на наступне питання: Y

Y ? Хай Y Y, тоді Y Y. Хай Y Y, тоді Y Y. Виходить неусувна логічна суперечність, яка відома як парадокс Рассела. Ось три способи уникнути цього конкретного парадоксу.

1. Обмежити використання характеристичні предикати вигляду:

, де А – відома, явно існуюча множина (універсум). Звичайно при цьому використовується позначення . Для Y універсум не вказаний, а тому Y множиною не може бути.

2. Територія типів. Об‘єкти мають типи 0, множина елементів типу 0 мають тип 1, множина елементівтипу 0 та 1 – типу 2 і т. д. Y не має типу і тому не може юути множиною.

3. Явна заборона приналежності множини самої собі:

- неприпустимий предикат. Відповідна аксіома називається аксіомою регулярності.

Множина А міститься у множині В якщо кожний елемент А є елементом В:

В цьому видатку А називається підмножиною В, В – над множиною А. З означенням

Дві множини рівні, якщо вони є підмножинами один одного:

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

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

Назва операції	Математичне представлення операції
Об‘єднання
Перетин
Різність
Симетрична різність
Заперечення

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

Назва властивості	Варіант №1	Варіант №2
Іденпотентність
Комутативність
Асоціативність
Дистрибутивність
Поглинання
Властивість нуля
Властивість одиниці
Інволюнтивність
Закон де Моргана
Властивість доповнення
Властивість для різності

Завдання 2.1