Шпаргалка по дискретной математике

1. Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество: количество подмножеств конечного множества.

Совокупность объектов объединенных общим признаком или признаками называется множеством, и обозначается заглавными латинскими буквами (A, B). Объекты из которых состоит множество, называются элементами множества и обозначаются прописными латинскими буквами (a, b, c). Принадлежность элемента множеству записывается с помощью символа Є. Пустое множество – множество, не содержащее ни одного элемента, и обозначается Ø. Универсальное множество – множество, из которого составляются конкретные множества. Способы задания множества: перечисление, аналитический способ, графический, словесный. Теорема 1: пустое множество является подмножеством любого не пустого множества. Теорема 2: Универсальное множество содержит в себе в качестве подмножеств любые множества. Теорема 3: Множество, содержащее n элементов, имеет ровно подмножеств. Собственное множество – подмножество В, если оно не пустое и не совпадает с А (-2).

2. Диаграммы. Операции над множествами и их свойства. Декартово произведение множеств.

Объединение 2-х множеств А и В, является множество, содержащее все элементы, принадлежащие хотя бы одному множеству и обозначается АvВ. Пересечение 2-х множеств А и В является множество, состоящее из элементов, принадлежащих одновременно обоим множествам (А^В). Разность 2-х множеств А и В называется множество, состоящее из всех элементов А, не принадлежащих В, при этом не предполагается, что В подмножество А (АВ, ВА). Дополнение – если В подмножество А, то АВ называют дополнением множества В до А. Декартовым произведением множеств А и В называется множество всех упорядоченных пар вида А (а, b), где аєА, bєВ. Причем пары (a, b) и (b, a) считаются разными. Симметрическая разность – у 2-х множеств А и В называется множество, состоящее из всех элементов множества А не содержащихся в В и всех элементов множества В не содержащихся в А. Дополнение до множества – если множество В является подмножеством А, то их разность АВ называется дополнением множества В до А.

3. Понятие и характеристики высказывания.

Высказыванием называется любое повествовательное предложение, относительно которого можно сказать истинно оно или ложно. Высказывание может быть сформулировано с помощью слов, символов, специальных знаков. Виды высказываний: простые и сложные (составные). Высказывание, которое можно разложить на части называется простым (ель – хвойное дерево). Высказывание, которое можно разложить на части, каждое из которых в свою очередь будет высказыванием, называется сложным (ель – хвойное и вечнозеленое дерево). Совокупность высказываний обозначается заглавной латинской буквой. Высказывание, содержащее неизвестную величину называется неопределенным или предикатом.

4. Основные логические операции (дизъюнкция, произведение (конъюнкция), импликация, эквиваленция, отрицание). Логические операции: отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность. Отрицание — высказывание а, называется такое высказывание (не а), которое ложно, если а истина, и истинно, если а ложно. Конъюнкция – высказывание а^в (а и в), которое истинно только тогда, когда истины оба составляющих высказывания. Дизъюнкция – высказывание аvв (а или в), которое ложно только тогда, когда ложны оба составляющих высказывания. Импликация – называется такое высказывание а→в (если а, то в), которое ложно только тогда, когда а истинно, а в ложно. Эквивалентность – высказывание а↔в (ттогда), которое истинно, когда одновременно либо истинны, либо ложны оба составляющих высказывания.

5. Понятие формулы логики. Таблица истинности и методика ее построения.

Формула – логическое выражение, в котором используются символы высказываний, знаки логических операций и символы скобок, для которого можно построить таблицу истинности. Список переменных формулы – упорядоченный набор высказывательных переменных f<a, b,c>, если все переменные формулы содержатся в этом наборе. Равносильными называются 2 формулы логики высказываний А и В, если они зависят от одного и того же списка переменных и на каждой оценке списка они принимают одинаковые значения. Алгоритм построения таблицы истинности: а) определяется порядок выполнения логический операций (¯,^,v,→,↔); б) количество строк в таблице истинности вычисляется по формуле 2n+1, где n количество высказываний, 1 – заголовок; в) количество столбцов = количество переменных + количество логических операций.

6. Типы формул.

Все формулы логики высказываний можно разбить на 3 класса: а) все формулы, которые на всех оценках списки переменных принимают значение только истины, называются тождественные (тавтология); б) все формулы, которые на всех оценках списка переменных принимают значение только лжи, называются невозможные; в) Все формулы, которые на всех оценках списка переменных принимают значения истины или лжи, называются выполнимые.

7. Понятие элементарных конъюнкции и дизъюнкции. Понятие нормальных форм формул.

Элементарная конъюнкция – формула, если она содержит переменные, отрицание переменных и операцию конъюнкции. Элементарная дизъюнкция – формула, если она содержит переменные, отрицание переменных и операцию дизъюнкции. Дизъюнктивно-нормальная форма (ДНФ) – формула, если она является дизъюнкцией элементарных конъюнкций. Конъюнктивно-нормальная форма (КНФ) – формула, если она является конъюнкцией элементарных дизъюнкций. Теорема: для любой формулы А, можно найти формулу В, находящиеся в КНФ или ДНФ, для которой будет справедливо утверждение АΞВ. Формула находится в СДНФ, относительно списка формулы А, если выполняются условия: 1) формула находится в ДНФ; 2) каждый дизъюнктивный член формулы А, является k-членной конъюнкцией, причем на любом месте, этой конъюнкции, находится либо высказывательная переменная, либо ее отрицание; 3)все дизъюнктивные члены А попарно различны. Формула находится в СКНФ, относительно списка формулы А, если выполняются условия: 1) формула находится в КНФ; 2) каждый конъюнктивный член формулы А, является k-членной дизъюнкцией, причем на любом месте, этой дизъюнкции, находится либо высказывательная переменная, либо ее отрицание; 3)все конъюнктивные члены А попарно различны.

8. Равносильные формулы. Законы логики. Методика упрощения формул логики с помощью равносильных преобразований.

Две формулы логики высказываний А и В называются равносильными, если они зависят от одного и того же списка переменных < х1, х2,… хn> и на каждой оценке списка переменных они принимают одинаковые значения. Обозначается равносильность: А≡В – А равносильна В, А(перечеркнутая)≡В – А не равносильна В. С помощью основных равносильностей логики высказываний можно преобразовывать формулы логики определять их названия, доказывать равносильности и упрощать их. Под упрощением формулы понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.

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

Булевой функцией f(x1, x2, …, xn), называется произвольная n-местная функция, аргумента которой {x1, x2, …, xn} є {0,1} и сама функция принимает значения f= {0,1}, где 0 – ложь, 1 – истина. Булеву функцию можно задать одним из следующих способов: А) аналитический – с помощью формулы. Для булевых функций сохраняются логические операции таблицы истинности логических операций и основные равносильности логики высказываний. Поэтому любую формулу логики можно считать и булевой функцией. Булева функция может быть задана таблицей в которой указываются оценки списка переменных и значения функции. Б) графический – можно изобразить одноместные, 2-местные, 3-местные булевы функции. В) Представление БФ формулой логики.

10. Проблема представления булевой функции в виде формулы логики.

Представление БФ формулой логики. Теорема: пусть f<x1, x2, …, xk> — k-местная БФ (k=>1). Если (f≠0), не равна тождественно 0, то существует такая формула логики f(x1,x2, …,xk) и находящаяся в СДНФ относительно списка переменных, что F выражает f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов. Теорема2: Пусть f(x1,x2, …,xk) – k-местная БФ, если f≠1, то существует такая формула логики зависящая от того же списка переменных и находится в СКНФ, относительно этого списка, что F выражает f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.

11. Многочлен Жегалкина.

Многочлен Жегалкина называется многочлен, являющийся суммой постоянных величин 0 или 1, и различных одночленов, в которой все переменные входят 1-ой степени. Алгоритм представления БФ многочленом Жегалкина: а) упрощение БФ с помощью основных равносильностей логики высказываний; б) представление полученной упрощенной формулы в СДНФ; в) замена логических операций, операциями математики; г) приведение полученного выражения к форме многочлена Жегалкина. 2 способ: а) построить таблицу истинности для заданной БФ; б) выбрать из таблицы строки, где функция принимает 1; в) Построить СДНФ; г) заменить логические операции математическими и упростить полученное выражение.

12. Полнота множества функций. Замыкание множества функций.

Все булевы функции можно условно разделить на функции принадлежащие к замечательным классам и не принадлежащие к ним. Всего существует 5 замечательных классов БФ: 1) Класс функции, сохраняющий константу const=0, Обозначается Т0. БФ – принадлежит классу Т0, если для нее выполняется условие f(0,0,…,0)=0. 2) Класс функции, сохраняющий const=1 – Т1. Функция относится к классу Т1, если для нее выполняется условие f(1,1,…,1)=1. 3) Класс линейных функций обозначается L. БФ называется линейной, если ее можно представить многочленом Жегалкина. 4) Класс двойственных БФ, обозначается S. Пусть f(x1,x2,…,xn) – БФ f(¯x1,¯x2,…,¯xn) называется двойственной заданной функцией f если выполняются следующие условия, т. е. на противоположных наборах значения двойственными являются функции f(x)=x и F(x)=¯x. 5) БФ называется монотонной, если для любых двух оценок списка переменных, таких что <x1,x2,…,xn> < <x1,x2,…,xn> выполняются условия f (x1,x2,…,xn) < f (x1,x2,…,xn). Сравнивать можно только сопоставимые оценки списка переменных.

14. Понятие предиката. Область определения и область истинности предиката.

Предикатом P(x1, x2, … ,xn) – называется функция, переменные которой определены на некотором множестве М, а сама она принимает значение Истины или Лжи, при этом Р – называется предикатный символ, x1, x2, … ,xn – предметные переменные, М – предметная область (область определения предикатов), {И, Л} – область значений. Подмножество Ip<=М предметной области предиката, на элементах которого предикат принимает значение Истины, называется областью истинности предиката.

15. Обычные логические операции над предикатами. Кванторные операции над предикатами.

Над предикатами на множестве М можно проводить логические операции (¯,^,v,→,↔). В результате проведения логических операций появляются новые более сложные предикаты. При определении их значений необходимо пользоваться таблицами истинности логических операций. Определены в логике предикатов 2 специфические операции, называемые навешиванием квантором или связывание кванторами. Квантор общности: «для всех Х выполняется P(x)» — ∀xP(x). Квантор существования: «существуют х, для которых выполняется Р(х)» — ∃хР(х).

16. Понятие предикатной формулы: свободные и связанные переменные. Построение отрицаний к предикатам, содержащим кванторные операции.

Переменная, на которую навешан квантор, называется связанной, остальные переменные свободные. Область действия квантора – выражение, на которое навешан квантор. Формулой логики предикатов называется выражение, удовлетворяющее следующим требованиям: 1) если Р-символ предиката, (x1, x2, … ,xn) – предметные переменные, то выражение Р(x1, x2, … ,xn) – формула атомарная. 2) если А — формула, то (не)¯А – тоже формула. Свободные и связанные переменные формулы А остаются такими же после проведения операции отрицания. 3) Пусть А и В – формулы, причем нет таких предметных переменных, которые были бы связанными в одной формуле и свободными в другой. 4) Пусть А формула содержащая свободную переменную Х. Тогда выражение ∃хА(х) и ∀хА(х) – формулы, но переменные в них уже связаны.

29. Понятие неориентированного графа, орграфа. Способы задания графа.

Графом называется двухосновная модель <V, E; i >, где i – бинарное отношение множеств V и E, такое, что каждый элемент e О E находится в отношении i либо ровно с одним, либо ровно с двумя элементами множества V. При этом элементы множества V называются вершинами графа, элементы множества E называются рёбрами графа, а отношение i – отношением инцидентности. Вершины, инцидентные одному и тому же ребру, называются смежными. Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра – линиями, соединяющими те точки, соответствующим вершинам которых ребра инцидентны. Если ребро инцидентно только одной вершине, его называют петлей. Рёбра называются кратными, если они инцидентны одним и тем же вершинам. Если в наборе Х встречаются кратные ребра и петли, то про множество V и набор X будем говорить, что они задают псевдограф. Псевдограф без петель – мультиграф. Если в наборе Х ни одна пара не встретилась более 1-го раза, то такая структура называется графом. Если пары в наборе Х являются упорядоченными х=(Vi, Vj), где Vi – начало, Vj – конец ребра, то граф называется ориентированным или орграфом. Изображение графа на плоскости в виде рисунка, называется геометрической интерпретацией. Геометрическая интерпретация является произвольной, главное чтобы были реализованы элементы из множества V и набора X.

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

Матрица смежности графа G, называется квадратная матрица A(G)=[aij] порядка n, у которой элементы aij равны. aij равна: 1, если (ViVj)єx; 0, если (ViVj)∉x; k, если (ViVj)єx – k раз.

31. Путь в графе. Цикл в графе. Связный граф.

Пусть дан не ориентированный граф G (V, X). Последовательность V1x1V2x2,…,xkVk+1 (k=>1), в которой чередуются вершины и ребра, называется маршрутом, соединяющим вершины V1 и Vk+1, причем V1 – начальная, Vk+1 – конечная, а V2 … Vk – внутренние. Одна и та же вершина в маршруте может быть одновременно начальной, конечной и внутренней. Количество ребер в маршруте называется длиной маршрута. Все маршруты можно разделить на 2 группы: не замкнутые, у которых начальные и конечная вершина совпадают. Замечание: в любом графе G можно указать минимум один замкнутый маршрут. Не замкнутый маршрут, в котором все ребра попарно различны, называются цепью. Цепь, в которой все вершины попарно различны, называются простой цепью. Замкнутый маршрут, в котором все ребра попарно различны, называется циклом. Цикл в котором все вершины попарно различны, называется простым циклом. Утверждение: если в графе можно задать цикл, то одновременно можно указать и простой цикл. В любом псевдографе можно указать цикл. Пусть дан ориентированный граф G (V, X). Последовательность V1x1V2x2,…,xkVk+1 (k=>1), в которой чередуются вершины и ребра, называется путем, соединяющим вершины V1 и Vk+1. Все пути делятся на замкнутые и незамкнутые. Не замкнутый путь, в котором все дуги попарно различны, называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью. Замкнутый путь, в котором все дуги попарно различны, называется контуром. Контур, в котором все вершины попарно различны, называется простым. Граф G называется связным, если для любых его 2-х вершин Vi и Vj существует маршрут их соединяющий. Граф, не являющийся связным, называется несвязным.

32. Компоненты связности графа. Степень вершины. Теорема о сумме степеней вершин графа.

Пусть дан граф D(V, X). Говорят, что вершина Vj орграфа D достижима из вершины Vi, если Vj=Vi или существует путь из Vi в Vj. Замечание: если все вершины орграфа соединены контуром или простым контуром, то все его вершины являются достижимыми. Орграф D называется сильносвязным, если для любых 2-х его вершин существует путь из одной в другую. Орграф называется односторонне связным, если для любых его 2-х вершин, по крайней мере одна достижима из другой. Компонента сильной связности орграфа D называется его сильносвязным подграфом, не является собственным подграфом, никакого другого сильносвязного подграфа D. Компонента связности связным графе G получается путём удаления последовательного удаления в графе по одному ребру не нарушающему связность графа. Степенью вершины v графа называется число дельта(v) ребер инцидентных вершине v. Замечание. В случае не ориентированного псевдографа вклад каждой петли в степень вершины равен 2. Полустепенью исхода вершины v орграфа D называется число дельта+(v) дуг исходящий из вершины v. Полустепенью захода вершины v орграфа D называется число дельта-(v) дуг заходящих в вершину v. Замечание. В случае ориентированного псевдографа вклад каждой петли равен 1 и в полустепень исхода и в полустепень захода.

34. Методика выделения компонент связности в графе. Расстояние между вершинами в графе: определение, свойства, методика нахождения. Радиус и диаметр в графа. Центральные вершины.

Граф G называется связным, если для любых его 2-х вершин Vi и Vj существует маршрут их соединяющий. Граф, не являющийся связным, называется несвязным. Компонента связности в связном графе G получается путём последовательного удаления в графе по одному ребру не нарушающему связность графа. Пусть дан граф G(v, x). Если граф связный, то любые его две вершины можно соединить маршрутом, и если таких маршрутов несколько, то среди них всегда можно указать минимальный маршрут, соединяющий вершины vi и vj. Обозначим длину минимального маршрута через d(vi vj) и договоримся, что кратчайшее расстояние d(vi vi)=0.
d(vi vj)=бесконечность, когда нет маршрута соединяющего данные вершины.
Расстояние между вершинами графа vi и vj будем называть величину d(vi vj) конечную или бесконечную. Величина d(G)=max d(vi vj) является конечной и называется диаметром графа G. Величина vi€V ч(vi)=max d(vi vj) называется максимальным удаление от вершины vi в графе G. Радиусом графа G называется величина ч(G)=min ч(vi). Любая вершина графа G для которой выполняется условие ч(G)=ч(v) называется центром графа.

35. Двудольные графы. Методика проверки графа на двудольность.

Двудольный граф – это граф, множество вершин которого можно разбить на 2 не пересекающихся множества V1 и V2 (V1^V2=Ø; V1vV2=V), так что каждое ребро соединяет некоторую вершину из множества V1 с некоторой вершиной множества V2. Для того чтобы граф являлся двудольным необходимо выполнение 2х условий: 1) граф должен быть связным; 2) все его простые циклы должны иметь четную длину.

36. Изоморфные графы. Методика проверки графов на изоморфность.

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

37. Эйлеровы графы. Теорема Эйлера (критерий эйлеровости графа). Методика нахождения эйлерова цикла в эйлеровом графе.

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

38. Гамильтоновы графы.

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

39. Деревья и их свойства.

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

40. Понятие ориентированного графа (орграфа). Способы задания орграфа.

Если пара в наборе х является упорядоченными x=(ViVj),Vi — начало, Vj — конец ребра, то граф называется ориентированным или орграфом. Для ориентированных графов справедливо утверждение (ViVj)≠(VjVi).

41. Матрица смежности для орграфа. Степень входа и степень выхода вершины.

Матрицей смежности орграфа D, называется квадратная матрица А(D)=[aij] порядка n, у которой элементы aij равны. Степенью вершины v графа называется число дельта(v) ребер инцидентных вершине v. Замечание. В случае не ориентированного псевдографа вклад каждой петли в степень вершины равен 2. Полустепенью исхода вершины v орграфа D называется число дельта+(v) дуг исходящий из вершины v. Полустепенью захода вершины v орграфа D называется число дельта-(v) дуг заходящих в вершину v. Замечание. В случае ориентированного псевдографа вклад каждой петли равен 1 и в полустепень исхода и в полустепень захода.

42. Ориентированный путь. Ориентированный цикл (контур).

Пусть дан ориентированный граф G (V, X). Последовательность V1x1V2x2,…,xkVk+1 (k=>1), в которой чередуются вершины и ребра, называется путем, соединяющим вершины V1 и Vk+1. Все пути делятся на замкнутые и незамкнутые. Не замкнутый путь, в котором все дуги попарно различны, называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью. Замкнутый путь, в котором все дуги попарно различны, называется контуром. Контур, в котором все вершины попарно различны, называется простым.

44. Матрица достижимости. Эквивалентность (взаимодостижимость) вершин в орграфе.

Матрицей достижимости орграфа D называется квадратная матрица T(D)=[tij] порядка n, у которой tij равно: 1, если Vj достижима из Vi; 0, если Vj не достижима из Vi.