Xreferat.com » Рефераты по информатике и программированию » Доведення теоретико-математичних тотожностей і тверджень

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

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

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


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


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

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

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) для п=к+1, тобто доведемо, що: Доведення теоретико-математичних тотожностей і тверджень,звідси Доведення теоретико-математичних тотожностей і тверджень =Доведення теоретико-математичних тотожностей і тверджень

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

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


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


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

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

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

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

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

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

- перерахунком елементів: М={a1,a2,…,ak};

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

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

Розглянемо множини Y всіх множин, що не містять себе як елементу: Доведення теоретико-математичних тотожностей і тверджень

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

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

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

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

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


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


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

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


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


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


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

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

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

Перетин

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

Різність

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

Симетрична різність

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

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

Заперечення

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

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

Назва властивості

Варіант №1

Варіант №2

Іденпотентність

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

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

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

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

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

Асоціативність

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

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

Дистрибутивність

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


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

Поглинання

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

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

Властивість нуля

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

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

Властивість одиниці

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

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

Інволюнтивність

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


Закон де Моргана

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

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

Властивість доповнення

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

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

Властивість для різності

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



Завдання 2.1


Розробити алгоритм та написати програму обчислення множини: Доведення теоретико-математичних тотожностей і тверджень


Проектування рішення задачі

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

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


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


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


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

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


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


Мал.1.Принципова блок-схема обчислення множин


Примітка: При розробці алгоритму даної задачі ми вводимо множини А, В, D вже в упорядкованому вигляді, але ми нижче приводимо опис методу впорядкування множин методом простого включення.


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


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

Представимо структуру програми у вигляді наступної блок-схеми (для програми обрано модульний принцип організації програми):

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


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


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


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

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

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


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

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


Мал.2.Принципова блок-схема програми


У програмі вирішення даної задачі ми використовуємо наступні процедури:

SYS- призначена для сортування цілих додаткових чисел;

ОBED- призначена для організації виконання операцій об’єднання двох відсортуваних множин;

PERET- призначена для організації виконання операцій перетину двох відсортуваних множин;

RIZ- призначена для організації виконання операцій різниці двох відсортуваних множин.


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


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

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

Задана послідовність чисел A = {aі, а2, а3, … ,аn }.

Необхідно упорядкувати її елементи по зростанню, тобто створити послідовність чисел В={Доведення теоретико-математичних тотожностей і тверджень}, такий, щоб Доведення теоретико-математичних тотожностей і тверджень, Доведення теоретико-математичних тотожностей і тверджень.

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


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

Як математичну модель представимо логічну схему роботи методом простого включення. Описуємо суть методу.

Побудуємо таблицю з 3 стовбців:

1-й стовбець предначений для вказування ітерацій методу.

2-й —для несортованої послідовності (А).

3-й —для відсортованої послідовності (В).

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


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

і

Невідсортований список,

(А)

Відсортований список,

(В)

0 7, 2, 21, 17, 6, 1, 13, 5, 8.
1 2, 21, 17, 6, 1, 13, 5, 8. 7
2 21, 17, 6, 1, 13, 5, 8. 2, 7
3 17, 6, 1, 13, 5, 8. 2, 7, 21
4 6, 1, 13, 5, 8. 2, 7, 17, 21
5 1, 13, 5, 8. 2, 6, 7, 17, 21
6 13, 5, 8. 1, 2, 6, 7, 17, 21
7 5, 8. 1, 2, 6, 7,13, 17, 21
8 8. 1, 2, 5, 6, 7,13, 17, 21
9
1, 2, 5, 6, 7, 8, 13, 17, 21

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

Алгоритм процедури SYS.

Алгоритм призначений для впорядкування чисел методом простого виключення.

Вхід: А- масив невідсортуваних даних;

n- кількість елементів масиву.

Вихід: В- масив відсортуваних даних.

Трудоємність алгоритма Доведення теоретико-математичних тотожностей і тверджень.

Крок 1: Визначити перші два елемента масива В.

Крок 2: Організувати цикл по Доведення теоретико-математичних тотожностей і тверджень, Доведення теоретико-математичних тотожностей і тверджень.

Крок 3: Провірити умови Доведення теоретико-математичних тотожностей і тверджень Якщо умова виконується, то Доведення теоретико-математичних тотожностей і тверджень.

Перехід на крок 6.

Крок 4: Організувати цикл по Доведення теоретико-математичних тотожностей і тверджень, де Доведення теоретико-математичних тотожностей і тверджень (для індексації решти елементів масива В).

Крок 5: Провірити умови Доведення теоретико-математичних тотожностей і тверджень. Якщо вона виконується, то елементи масива В зміщуються на один розряд вправо з Доведення теоретико-математичних тотожностей і тверджень до Доведення теоретико-математичних тотожностей і тверджень. Присвоїти Доведення теоретико-математичних тотожностей і тверджень.

Крок 6: Завершення циклу по Доведення теоретико-математичних тотожностей і тверджень.

Крок 7: Кінець.

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


так

ні


так


Мал.3. Блок-схема процедури SYS.

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

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

Задані дві множини A={аДоведення теоретико-математичних тотожностей і твердженьДоведення теоретико-математичних тотожностей і тверджень,..,аДоведення теоретико-математичних тотожностей і тверджень}, В={bДоведення теоретико-математичних тотожностей і тверджень,bДоведення теоретико-математичних тотожностей і тверджень,..,bДоведення теоретико-математичних тотожностей і тверджень}.

Потрібно отримати множину С=А Доведення теоретико-математичних тотожностей і твердженьВ.


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

Об’єднання визначається наступним чином Доведення теоретико-математичних тотожностей і тверджень.


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

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


1

2


3


4


Блок 1:використовуємо Procedure SYS ,яка описана в лабораторній pоботі №1.

Блок 2,3: не відсортовані масиви; відсортовані масиви.

Блок 4: алгоритм OBED

Алгоритм OBED:

Призначений для об’єднання двох відсортованих множин А і В з використанням методу злиття.

Крок 1. Присвоїти Доведення теоретико-математичних тотожностей і тверджень, j=1,Доведення теоретико-математичних тотожностей і тверджень;

Крок 2. Перевірити умову Доведення теоретико-математичних тотожностей і тверджень: якщо так, то: к=к+1,сДоведення теоретико-математичних тотожностей і тверджень=Доведення теоретико-математичних тотожностей і тверджень ,і=і+1;

Крок 3. Перевірити умову Доведення теоретико-математичних тотожностей і тверджень; якщо так, то перехід на крок 2;

інакше: записати в кінці масиву С елементи масиву В,

які залишились нерозглянуті; кінець.

Якщо Доведення теоретико-математичних тотожностей і тверджень ,то перехід на крок 4;

Крок 4. Перевірити

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: