Ця тема належить розділу:
Об'єднанням множин А і В називається множина складається з усіх тих і тільки тих елементів які належать хоча б одній з множин А. Пересеченіеммножеств А і В називається множина складається з тих і тільки тих елементів які належать.
Що будемо робити з отриманим матеріалом:
Всі теми даного розділу:
Теорія множин.
Безліччю Sназивается об'єднання в одне ціле об'єктів, добре помітних нашою думкою або інтуїцією. Ці об'єкти називається елементами
Властивості підмножин.
1. Рефлексивність. Безліч А є підмножиною множини А:
Алгебра теорії множин.
Для будь-яких множин А, В і С здійсненні наступні тотожності: 1. комутативну закон
Кортеж.
Кортеж це упорядкований набір елементів. Кортеж характеризується елементами і їх порядком розташування. Елементи кортежу називаються компонентамі.Компон
Графік і властивості графіка
Графіком називається безліч пар. Графіки можуть задаватися. 1. перерахуванням:
Відповідності.
Відповідністю називається трійка виду. При цьому
Відносини.
Ставленням називається пара виду така, що ФÍM
Транзитивність.
Відношення називається транзитивним, якщо для всіх x виконується умова: xjy і yjz Þ xjz або Ф
Формули равносильности.
1) Комутативність АVВ º ВVА АВ º ВА 2) асоціативність АV (ВVС) º (АVВ) VС А (ВС) º (АВ) З
Різні форми представлення висловлювань
Літерою - називається елемент висловлювання x або її заперечення. Елементарної диз'юнкція називається вираз такого вигляду:
Застосування математичної логіки.
Спомощью алгебри логіки можна: · вирішувати логічні завдання; · Реалізація технічних пристроїв. Спомощью алгебри логіки м
Метод Квайна.
Алгоритм методу Квайна включає в себе наступні етапи: 1. Будь-яка формула
Метод мінімізують карт.
Алгоритм методу мінімізують карт включає в себе наступні етапи: 1. Будь-яка формула приводиться до СДНФ. 2. Складається таблиця всіляких поєднань змінних. 3. З
Метод мінімізації за допомогою карт Вейча.
Алгоритм методу карт Вейча включає в себе наступні етапи: 1. Будь-яка формула приводиться до СДНФ. 2. Складається карта Вейча. Карта Вейча - це таблиця всіх возможн
Булеві функції та їх властивості.
Булевой функцією називається функція n змінних, яка приймає значення 1 або 0, а так само її аргументи теж приймають значення 1 або 0. Булевой фу
Функціональна повнота. Теорема Поста.
Функціональний набір логічних функцій - це такий набір функцій, який дозволяє будь-яку функцію математичної логіки описати за допомогою функцій даного набір
Логіка предикат.
Предикат - це складне висловлювання, в якому аргументи приймають значення і
матрицею інцидентності
Матриця інцидентності - це матриця вершин і інцідентних їм дуг. Дуга инцидентна вершині, якщо ця дуга виходить або заходить в цю вір
матрицею суміжності
Суміжні дуги - це дуги інцідентние одній вершині. Суміжні вершини - вершини, інцидентні одній дузі. Матриця суміжності -
Ейлеров граф.
Ейлеровой ланцюгом називається ланцюг, що проходить по всіх ребрах графа. Ейлеровим циклом називається ейлерову ланцюг, що починається і заканчівающаяс
Безліч внутрішньої стійкості графа
Безліч внутрішньої стійкості графа - це безліч несуміжних вершин. Нехай дано граф
Безліч зовнішньої стійкості графа
Безліч зовнішньої стійкості - безліч вершин, для яких виконується одна з наступних правил: 1). Будь-яка вершина входить в це безліч
Безліч шляхів у графі
По матриці суміжності можна визначити, скільки різних шляхів існує між i-тій і j- тій вершинами довжиною в до
Алгоритм фронту хвилі. Пошук мінімального шляху в графі.
Однією з найпоширеніших завдань в теорії графів є завдання пошуку мінімального шляху в графі. Розглянемо деякі властивості мінімальних шляхів 1. Будь-який ми
Ярусно-паралельна форма графів
Граф, що не має контурів, може бути представлений в ярусно-паралельній формі. Ярусно-паралельна форма - це такий вид графа, у якого в верхній нульовий ярус примі
Алгоритм приведення графа до ярусно-паралельній формі.
1. Складається матриця суміжності графа. 2. Матриця суміжності проглядається в пошуках нульових стовпців. Вершини, яким відповідають нульові стовпці, поміщаються в нульовий ярус.
Дерева і ліси
Відокремленими називаються вершини, для яких не існує з'єднує ці вершини шляху. Неотделеннимі називаються вершини, між якими суті
Алгоритм отримання дерева з графа
1. Вибирається будь-яка вершина. Лічильник i приймаємо рівним 1 (i = 1). 2. Якщо i = k, то дерево побудовано. 3. Якщо i ¹ k, то вибирається
ТЕОРІЯ АЛГОРИТМІВ
Алгоритм - це точне, зрозуміле розпорядження про те, які дії і в якому порядку повинні бути виконані, щоб вирішити будь-яке завдання з класу однотипних задач.
Функція-проекція
(4.3) Правила перетворення функцій 1. Правило
машина Тьюринга
Якщо для вирішення деякої масової проблеми відомий алгоритм, то для його реалізації необхідно лише чітке виконання приписів цього алгоритму. Автоматизм, необхідний при реалізації алгоритму
Нормальні алгоритми Маркова
Нормальний алгоритм Маркова являє собою систему підстановок. (4.10)
Закони функціонування автоматів.
Залежно від законів функціонування розрізняють 3 види автоматів: 1. Автомати першого роду, або автомати Мілі:
мінімізація автоматів
Вхідним словом називається сукупність сигналів, що надходять на вхід. Вихідним словом називаються сукупність сигналів на виході.
Алгоритм мінімізації автомата Мілі
1. По таблиці виходу знаходяться стану з однаковими вихідними сигналами. Дані стану об'єднуються в клас одноеквівалентних станів. Проводиться перекодування. 2. По таблиці перех
Перехід від автомата Мілі до автомата Мура
Автомати Мілі та автомати Мура відрізняються функцією виходу. Автомат Мілі: (
Перехід від автомата Мура до автомата Мілі
Перехід від автомата Мура до автомату Мілі полягає в побудові таблиці виходів. Побудова полягає в підстановці вихідних сигналів, які відзначають стану в зазначеній таблиці пере