Теория множеств

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

1. Множество- это нечто, состоящее из хорошо различимых объектов. 2. Это нечто мыслится как единое целое. Множества бывают конечными и бесконечными, Количество элементов в конечном множестве называется мощностью множества.…

Свойства подмножеств.

1. Рефлексивность. Множество А является подмножеством множества А: . (2) 2. Транзитивность. Если множество А является подмножеством множества В , а множество В является подмножеством…

Операции над множествами.

1. Объединением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В:

(5)

2. Пересечениеммножеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат множеству А и множеству В:

(6)

3. Разностьюмножества А и В называется множество всех тех элементов, которые принадлежат множеству А и не принадлежат множеству В:

(7)

4. Симметричной разностьюмножеств А и В называется множество , состоящее из элементов множества А , не принадлежащих множеству В, и элементов множества В, не принадлежащих множеству А:

(8)

5. Дополнениеммножества А называется множество всех тех элементов, которые не принадлежат множеству А:

(9)

Для наглядного представления операций над множествами используют диаграммы Эйлера- Венна.

 

Рис 1. Диаграмма Эйлера-Венна

где - это области 1,2,3

- это область 3;

- это область 1;

- это область 1,3

- это области 2,4.

Алгебра теории множеств.

1. Коммутативный закон (9) 2. Ассоциативный закон

Решение уравнений алгебры множеств.

Пусть дано уравнение вида: (23) где X - неизвестное множество. Необходимо определить это неизвестное множество.

Кортеж.

Кортеж длиной в две компоненты называется парой, кортеж длиной в три компоненты - тройка, длиной в n - n-ка. Проекцией кортежа на i-тую осьназывается его i-тая компонента. Проекцией кортежа на оси i1, i2, ..., iq осиназывается кортеж, состоящий из i1, i2, ... , iq компонент, где .

Проекция множества.

 

Проекция множества определена только для множеств, элементами которого являются кортежи одинаковой длины.

Проекцией множестваназывается множество проекций соответствующих кортежей.

Пример.

А={<1,2,3>;<4,5,6>;<3,3,3>}

Пр А₁={<1>;<4>;<3>}

Пр А_1,3={<1,3>;<4,6>;<3,3>}

Пр А_3,1 не определена.

 

График и свойства графика

1. перечислением: 2. описанием свойств: Пара <a,b> называетсяинверсией пары <c,d>, если a=d, b=c.

Прямое (декартовое) произведение множество.

, (29) ПРИМЕР. Пусть заданыи : , . Тогда прямое (декартовое) произведение этих множеств может быть представлено графически:X={x |…

Соответствия.

Соответствием называется тройка вида . При этом - область отправления (определения), - область прибытия (значений), - график соответствия.   ПРИМЕР.

Отношения.

Отношением называется пара вида такая, что ФÍM2 (M2=MM),где Ф - график отношения, М - это множество, между элементами которого существует…   ПРИМЕР.

Основные свойства отношений.

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

Отношение называется рефлексивным, если для всех x выполняется условие: xjx или DMÍF.

Антирефлексивность.

Отношение называется антирефлексивным, если для всех x выполняется условие: ùxjx (символ “ù“ означает “не выполняется”) или .

3. Симметричность.

Отношение называетсясимметричным , если для всех x выполняется условие: xjy Þ yjx или Ф=Ф^-1.

Антисимметричность.

Отношение называется антисимметричным, если для всех x выполняется условие: xjy и x¹y Þù yjx или ÍDM.

Асимметричность.

Отношение называется асимметричным, если для всех x выполняется условие: xjy Þù yjx или =Æ.

Связность (полнота).

Отношение называется связным (полным), если для всех x выполняется условие: x¹y Þ xjy или yjx или М²DMÍ.

Транзитивность.

  ПРИМЕР  

Решетки.

Диаграммы Хассе.

j=<F,M>, где … Графически данное отношение можно изобразить следующим образом:

Алгебраическое представление решеток.

1. Коммутативный: ab=ba ab=ba 2. Ассоциативный:

Математическая логика

Высказывания и операции над высказываниями.

 

Высказыванием называется повествовательное предложение, о котором можно сказать истинно оно или ложно.

1. Москва - столица России.

2. Если студент учится на отлично, то он получит красный диплом.

3. Осадки - это снег или дождь.

4. Курица – не птица.

5. Пейте томатный сок.

6. Я лгу.

7. 23<5

Высказываниями являются 1, 2, 3,4 и 7 предложения. Предложение 5 не является высказыванием, так как про него нельзя сказать истинно оно или ложно. Предложение 6 является логическим парадоксом.

Элементарным высказыванием называется высказывание, которое содержит одно утверждение (предложения 1,7).

Сложное (составное) высказывание состоит из элементарных высказываний связанных с помощью следующих предлогов и частиц: И, НЕ, ИЛИ, ЕСЛИ - ТО, ТОГДА И ТОЛЬКО ТОГДА и другие. Предложения 2,3,4 являются сложными высказываниями.

 

Операции над высказываниями.

Отрицанием высказывания х называется новое высказывание, которое истинно, если высказывание ложное и наоборот. Таблица истинности операции отрицания имеет вид:

Дизъюнкцией двух высказываний x и y(логическое «или»)называется новое высказывание, которое будет истинным тогда когда, когда хотя бы одно из высказываний будет истинным.

 

Конъюнкцией двух высказываний x и y(логическое «и»)называется новое высказывание, которое будет истинным тогда когда, когда оба высказывания истины. Обозначение операции конъюнкция - &(

 

 

Импликацией двух высказываний x и y(«если – то») называется новое высказывание, которое ложно тогда, когда х(предпосылка)- истинно, а у(следствие)- ложно.

 

 

Эквивалентностью двух высказываний x и y(«тогда и только тогда») называется новое высказывание, которое будет истинно , если высказывания х и у будут одновременно истинны или ложны.

 

 

Неодназночностью (суммой по модулю два) двух высказываний x и y(«тогда и только тогда») называется новое высказывание, которое будет истинно тогда когда одно из высказываний х или у истинно, а другое ложно.

 

 

Штрих Шеффера (логическое «и - не») высказываний x и y - это новое высказывание, которое будет ложно тогда и только тогда когда оба высказывания истинны.

 

 

Стрелка Пирса (логическое «или - не») высказываний x и y - это новое высказывание, которое будет истинно тогда и только тогда когда оба высказывания ложны.

 

 

Для операций справедливы следующие приоритеты: ù, &, Ú, ®, «.

Формулы математической логики.

 

Формулой математической логики называется сложное высказывание, которое получено из элементарных высказываний с использованием логических операций.

Две формулы равносильны, если они принимают одинаковые логические значения на любом наборе значений входящих в формулу элементарных высказываний. Равносильность формул обозначается - A º B.

 

Формулы равносильности.

АVВ º ВVА А&В º В&А   2) Ассоциативность

Различные формы представления высказываний

Литерой - называется элемент высказывания x или её отрицание. Элементарной дизъюнкцией называется выражение следующего вида: , (2.2)

Выполнимость формулы алгебры логики

1. тождественно истинные или тавтологии: 2. тождественно ложные или противоречия; 3. выполнимые.

Применение математической логики.

Спомощью алгебры логики можно: · решать логические задачи; · реализация технических устройств.

Минимизация сложных высказываний.

Существует несколько способов минимизации сложных высказываний. Рассмотрим самые распространенные:

· метод Квайна;

· карты Вейча;

· минимизирующие карты.

 

Метод Квайна.

Алгоритм метода Квайна включает в себя следующие этапы: 1. Любая формула приводится к СДНФ. 2. СДНФ приводится к сокращенной ДНФ (СкДНФ). При получении СкДНФ используются следующие формулы равносильности:

Метод минимизирующих карт.

1. Любая формула приводится к СДНФ. 2. Составляется таблица всевозможных сочетаний переменных. 3. Из таблицы вычеркиваются те строки, которые не содержат конституенты СДНФ. Конъюнкции этих строк вычеркиваются в…

Метод минимизации с помощью карт Вейча.

Алгоритм метода карт Вейча включает в себя следующие этапы: 1. Любая формула приводится к СДНФ. 2. Составляется карта Вейча. Карта Вейча – это таблица всех возможных комбинаций значений переменных. В…

Булевые функции и их свойства.

Булевой функцией называется функция n переменных, которая принимает значение 1 или 0, а так же ее аргументы тоже принимают значение 1 или 0. Булевая функция имеет следующие свойства: 1. Свойство сохранения нуля . Булевая функция сохраняет нуль, если функция при нулевых значениях аргумента принимает…

Функциональная полнота. Теорема Поста.

Функциональный набор логических функций - это такой набор функций, который позволяет любую функцию математической логики описать с помощью функций… Теорема Поста. Для того чтобы набор функций {f1,f2,……fn} был функционально… Полноту набора удобно определять по таблице Поста, в клетках которой ставится знак «+» или «-» в зависимости от того,…

Логика предикат.

Предикат - это сложное высказывание, в котором аргументы принимают значение из некоторой вещественной области , а значение самого высказывания… ПРИМЕР

Логические операции над предикатами.

Для предикатов выполнимы следующие операции:

Конъюнкция -этоновый предикат, который принимает значение истинно при тех и только тех значениях из вещественной области , при которых оба предиката и истинны одновременно, и ложно во всех других случаях.

Дизъюнкция -этоновый предикат, который принимает значение ложно при тех и только тех значениях из вещественной области , при которых оба предиката и ложны одновременно, и истинно во всех других случаях.

Отрицание предиката - это новый предикат, который принимает значение истинно при всех из вещественной области , при которых предикат принимает значение ложно и наоборот.

 

Квантовые операции.

 

Для предикатов кроме логических операций применимы кванторные операции: всеобщности и существования.

Пусть - предикат, определенный на множестве . Тогда - означает «для всякого (любого) истинно ». Символ называется квантором всеобщности.

Переменную в предикате называют свободной ( ей можно придавать различные значения из М), в высказывании переменную называют связанной квантором всеобщности.

Пусть - предикат, определенный на множестве . Тогда - означает «существует , для которого истинно ». Символ называется квантором существования.

 

ПРИМЕР

Пусть на множестве натуральных чисел задан предикат -«число кратно 3». Используя кванторы, из данного предиката можно получить высказывания:

- «все натуральные числа кратны 3»;

- «существуют натуральные числа, кратные 3».

Очевидно, что первое из данных высказываний ложно, а второе – истинно.

Кванторные операции применяются и к многоместным предикатам. Пусть на множестве задан двухместный предикат . К данному предикату могут применяться кванторные операции как по одной, так и по двум переменным.

 

ПРИМЕР

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

1. - «для любого и для любого справедливо, что делится на без остатка.

2. - «для любого существует , который является делителем без остатка.

Нетрудно заметить, что первое высказывание является ложным, а второе – истинным.

 

Для многоместных предикатов, связанных по одной переменной справедливы следующие формулы:

,

где

,

где

 

Равносильные формулы логики предикатов.

Две формулы логики предикатов и называются равносильными на области, если они принимают одинаковые логические значения при всех значениях входящих в… Две формулы логики предикатов и называются равносильными, если они равносильны… Очевидно, что все формулы равносильности алгебры высказываний будут верны, если в них вместо переменных подставить…

ТЕОРИЯ ГРАФОВ

Начало теории графов как математической дисциплине было положено Леонардом Эйлером в его знаменитом решении задачи о Кенигсбергских мостах в 1736 году. План города Кенигсберга представлен на рис. 3.1. Задача о Кенигсбергских мостах сводилась к тому, чтобы построить маршрут своей воскресной прогулки так, чтобы, начиная в любой точке суши (A, B, C или D) пройти по всем мостам строго по одному разу и вернуться в исходную точку (начало маршрута).

 

A

 

 

B

Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах.

 

Такую задачу не предоставляется возможным решить классическими методами математики. Для решения такой задачи был предложен качественно новый аппарат – аппарат теории графов.

 

Основные понятия теории графов

Графом называется пара следующего вида:

, (3.1)

где - график ;

- множество вершин.

Иными словами, граф представляет совокупность множества вершин и дуг.

 

 

Рис. 3.2. Граф

Граф, представленный на рис. 3. 2, состоит из множества вершин и множество дуг

Графическое изображение графа является самым наглядным, но не единственным способом задания графа. Кроме того граф может быть задан:

1. перечислением:

2. множеством образов:

,

где - образ вершины- множество вершин, в которые исходят дуги из данной вершины.

Матрицей инцидентности

Дуга инцидентна вершине, если эта дуга исходит или заходит в данную вершину. Вершина инцидентна дуге, если в эту вершину заходит или исходит данная дуга. … В матрице инцидентности в первом столбце расположены вершины, в первой строке – дуги. Остальные ячейки матрицы…

Матрицей смежности

Смежные вершины – вершины, инцидентные одной дуге. Матрица смежности - это матрица смежных вершин. Матрица смежности заполняется по следующему правилу:, если из i-той вершины исходит дуга в j – тую вершину; во всех…

Эйлеров граф.

Эйлеровым циклом называется эйлеровая цепь, начинающаяся и заканчивающаяся в одной вершине. Эйлеровым графом называется граф, содержащий Эйлеров цикл.  

А

 

 

С D

 

 

B

Рис. 3.5 Граф «Кенигсбергские мосты»

 

Вершины графа (A, B, C, D) имеют степени:

(3.3)

Тогда в соответствии с теоремой Эйлера данный граф не является Эйлеровым. А это означает, что нельзя обойти все мосты г. Кенигсберга строго по одному разу, начав и закончив путь в одной точке суши.

 

Следствие из ТЕОРЕМЫ: Для того чтобы граф содержал Эйлеровую цепь, необходимо и достаточно, чтобы две вершины имели нечетную степень. При этом в одной из вершин цепь будет начинаться, в другой – заканчиваться.

 

Множество внутренней устойчивости графа

Множество внутренней устойчивости графа – это множество несмежных вершин. Пусть дан граф . Тогда для множества внутренней устойчивости справедливо… (3.4)

Алгоритм Магу для определения множества внутренней устойчивости графа

Введем булевую переменную , которая определяется следующим образом: , если вершина принадлежит множеству внутренней устойчивости ; , если вершина не принадлежит множеству внутренней устойчивости ;

Множество внешней устойчивости графа

Множество внешней устойчивости – множество вершин, для которых выполняется одно из следующих правил: 1). Любая вершина входит в это множество 2) Либо вершина не входит в это множество, но из этой вершины есть дуга в данное множество.

Алгоритм Магу для определения множества внешней устойчивости.

Вводятся булевые переменные и по тому же правилу, что и для алгоритма Магу для определения множества внутренней устойчивости. Тогда определение множества внешней устойчивости (3.12) запишется следующим… (3.13)

Множество путей в графе

По матрице смежности можно определить, сколько различных путей существует между i-той и j- той вершинами длиной в к единиц. Для этого необходимо… Если элемент матрицы : - между i-той и j- той вершины не существует пути длиной в к единиц;

Алгоритм фронта волны. Поиск минимального пути в графе.

Одной из самых распространенных задач в теории графов является задача поиска минимального пути в графе. Рассмотрим некоторые свойства минимальных путей 1. Любой минимальный путь является простым путем.

Ярусно-параллельная форма графов

Количество вершин в ярусе определяет ширину яруса. Наибольшая ширина яруса определяет ширину графа в ярусно-параллельной форме. Количество ярусов…  

Алгоритм приведения графа к ярусно-параллельной форме.

2. Матрица смежности просматривается в поисках нулевых столбцов. Вершины, которым соответствуют нулевые столбцы, помещаются в нулевой ярус. 3. Из матрицы смежности столбцы и строки, соответствующие вершинам нулевого… 4. Повторяется п.2 данного алгоритма до тех пор, пока не будут охвачены все вершины.

Деревья и леса

Неотделенными называются вершины, между которыми существует путь. Подграфом графа называется граф вида: (3.19)

Алгоритм получения дерева из графа

1. Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1). 2. Если i = k, то дерево построено. 3. Если i ¹ k, то выбирается любая незадействованная вершина и ребро, соединяющее данную вершину с любой из…

ТЕОРИЯ АЛГОРИТМОВ

Алгоритм обладает следующими характеристиками: 1. Дискретность. Алгоритм – это процесс последовательного построения величин… 2. Детерминированность. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой…

Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в машине. Впервые это было сделано Тьюрингом, который предложил общую и вместе с тем самую простую концепцию вычислительной машины. Ее описание было дано Тьюрингом в 1937 г. А это направление в теории алгоритмов получило название - машина Тьюринга.

3. Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. х Нормальные алгоритмы Маркова. Это направление получило название нормальные алгоритмы Маркова.

 

Рекурсивная функция

Основные понятия: элементарные функции, правила образования новых функций.

Простейшие функции:

1. Функция сохранения нуля (нуль-функция)

(4.1)

Функция сдвига

(4.2)

Функция-проекция

Правила преобразования функций   1. Правило подстановки (суперпозиции)

Правило примитивной рекурсии

Основывается на простейших или выведенных из простейших функциях g и h:

Пусть

Тогда новая функция может быть выведена по правилу:

(4.6)

Следует отметить, что функция зависит от аргументов, функция зависит от аргументов, функция зависит от аргументов. Иначе говоря, правило примитивной рекурсии позволяет получить n + 1-местную функцию из n-местной и n + 2 - местной функций.

ПРИМЕР

 

Пусть некоторая функция задана правилом рекурсии

Нетрудно заметить, что функция , функция

Вычислим значение функции при .

Нетрудно заметить, что функция выполняет сложение двух чисел и .

3. m - оператор (оператор нахождения наименьшего корня у)

Оператор определяет наименьшее значение у, при котором при фиксированном значении. Принято обозначение

(4.7)

(Читается: «наименьшее такое, что »). Аналогично определяется функция многих переменных :

(4.8)

Для вычисления функции существует следующий алгоритм:

1. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу.

2. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу. И т. д.

Если окажется, что для всех функция , то функция считается неопределенной.

 

ПРИМЕР

Дана функция . Необходимо определить при

Таким образом,

 

Функция называется частично рекурсивной, если она получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии или m - оператора.

Функция называется примитивно рекурсивной, если она может быть получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии.

Функция называется общерекурсивной, если она частично рекурсивная и всюдуопределенная.

 

Тезис А. Черча. Если функция является общерекурсивной, то она выполнима, т.е. имеет алгоритм решения.

 

Машина Тьюринга

Машина Тьюринга включает в себя: 1. Внешний алфавит - конечное множество символов . В этом алфавите в виде… 2. Внутренний алфавит - конечное множество символов . Для любой машины число состояний фиксировано. Два состояния…

Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой.

Таким образом, машина Тьюринга может быть представлена в виде четверки: (4.9) Работа машины Тьюринга:

Нормальные алгоритмы Маркова

, (4.10) где - слова из символов входного алфавита - оператор подстановки, при этом :

Законы функционирования автоматов.

1. Автоматы первого рода, или автоматы Мили: (5.2) 2. Автоматы второго рода

Задание автоматов

 

Автоматы могут быть заданы следующими способами:

1. В виде графа

 

 

 

 

РИС. 5.1. Автомат Мили

 

РИС. 5.2. Автомат Мура.

При построении автомата Мили каждая дуга, соединяющая вершины и , имеет обозначение . Это означает следующее: находясь, в состоянии автомат, отрабатывая входной сигнал , выдает выходной сигнал и переходит в состояние .

Так как в автомате Мура выходной сигнал зависит только от текущего состояния , то каждая дуга, соединяющая вершины и , имеет обозначение .

2. В виде таблиц перехода и выхода (автомат Мили); отмеченной таблицы перехода (автомат Мура).

Автомат Мили описывается с помощью двух таблиц: таблицы перехода и таблицы выхода:

 

Таблица переходов (ТП) Таблица выходов (ТВ)

 

Автомат Мура описывается с помощью отмеченной таблицы перехода:

Таблица переходов (ТП)

ПРИМЕР.

Синтезировать автомат, на вход которого подаются монеты номинальной стоимостью 1, 2 и 3 копейки, а на выходе автомат выдает билет, если сумма набранных монет составляет 3 копейки, если сумма меньше 3 копеек, то автомат ничего не выдает, если сумма больше 3 копеек, то автомат возвращает деньги.

Определим входной, выходной алфавиты и множество внутренних состояний:

· входной алфавит - монеты номинальной стоимостью 1, 2 и 3 копейки

· выходной алфавит - на выходе возможны выходные символы: - ничего;- билет;- возврат.

· множество внутренних состояний ,

где - начальное состояние автомата « в автомате ничего нет»;

- «в автомате 1 копейка»;

- «в автомате 1 копейка»;

- «в автомате 2 копейки»;

- «в автомате 3 копейки».

Граф автомата имеет вид:

 

 

РИС. 5.3. Автомат Мили

Таблицы перехода и выхода представлены в виде:

Таблица переходов (ТП) Таблица выходов (ТВ)

							Н	Н	Б	Н
							Н	Б	В	Н
							Б	В	В	Б

 

Неопределенным состоянием называется несуществующее состояние.

Частичным автоматом называется автомат, в котором некоторые состояния в таблице перехода не определены. Для дальнейшего исследования неопределенное состояние некоторым образом доопределяют.

 

Минимизация автоматов

Выходным словом называются совокупность сигналов на выходе. Два автомата называются эквивалентными, если они имеют одинаковый входной и… Два состояния одноэквивалентными, если на одинаковое входное слово выдается одинаковый выходной сигнал.

Алгоритм минимизации автомата Мили

2. По таблице перехода определяются классы двухэквивалентных состояний: для любого класса выделяется состояние, которое на одинаковый входной… 3. Алгоритм выполняется, пока в классах k-эквивалентных состояний не… 4. Вводятся новые состояния, соответствующие классам эквивалентных состояний.

Особенности минимизации автомата Мура.

:

Автомат Мура минимизируется аналогично минимизации автомата Мили за исключением первого шага. Выделение класса одноэквивалентных состояний осуществляется по строке выходов отмеченной таблицы переходов автомата Мура.

 

Минимизация частичных автоматов.

Для того, чтобы провести минимизацию частичных автоматов неопределенное состояние доопределяется самостоятельно. Далее минимизация автоматов осуществляется по вышеизложенному алгоритму.

 

Переход от автомата Мили к автомату Мура

Автомат Мили: (5.5) Автомат Мура:

Переход от автомата Мура к автомату Мили

Переход от автомата Мура к автомату Мили заключается в построении таблицы выходов. Построение состоит в подстановке выходных сигналов, отмечающих… А таблица переходов автомата Мили получается из отмеченной таблицы переходов…