Лекции по "Дискретная математика"

1.Всякая булева функция f(x1,... ,х_п) представима полиномом Жегалкина, т.е. в виде f(x1... х_п) = х_i1хi2 ... x_ik с, где в каждом, наборе (i1,.ik) все ij различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых. Полином Жегалкина называется нелинейным (линейным), если он (не) содержит произведения переменных. Т.О, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.

2.Алгебраической  системой U = {А,∑) сигнатуры ∑ называется непустое множество А, где каждому n-местному предикатному (функциональному) символу из ∑ поставлен в соответствие п-местный предикат (соответственно операция), определенный на множестве А.Пусть A = <A;f1,...,fk;r1,...,rl> и B = <B;g1,...,gk;p1,...,pl> – алгебраические системы одного типа <m1,...,mk; n1,...,nl>. Отображение   A  B называется гомоморфизмом алгебраической системы A в B, если выполняются следующие условия: 1) (fi(x1,...,xmi)) = gi( (x1),..., (xmi)), 2)(x1,...,xnj)  rj  ( (x1),..., (xnj))  pj для любых x1, x2, ...  A, для любых i : 1 ≤ i ≤ k, для любых j : 1 ≤ j ≤l. Если гомоморфизм является биекцией и обратное отображение тоже – гомоморфизм, то такой гомоморфизм называется изоморфизмом. Алгебраические системы, для которых существует изоморфизм, называются изоморфными. Иначе говоря, изоморфизм алгебраических систем A = <A;f1,...,fk; r1,...,rl> и B = <B;g1,...,gk;p1,...,pl> одного типа <m1,...,mk; n1,...,nl> – это взаимно-однозначное отображение  множества A на B, такое что выполняются условия: 1) (fi(x1,...,xmi)) = gi( (x1),..., (xmi)), 2)(x1,...,xnj) О rj  (j(x1),...,j(xnj)  pj Изоморфизм алгебраической системы на себя называется автоморфизмом. Автоморфизм, являющийся тождественным отображением называется тривиальным.

3. Под множеством М понимается совокупность некоторых объектов, которые будут называться элементами множества М. Тот факт, что x является элементом множества М, обозначают через x M, в противном случае x M. Элементы множества сами могут являться множествами . Множество можно задать перечислением принадлежащих ему элементов (то есть писать M={x1, x2,..., xn}) или указанием свойств, которым элементы множества должны удовлетворять, то есть, если имеется свойство P, которым могут обладать элементы некоторого множества A, то будем обозначать {x A | x обладает свойством P} или {x | P(x)}, если из контекста ясно, о каком множестве А идет речь.Множество A называется подмножеством множества B , если все элементы множества А принадлежат В:  ABx(xAxB). Совокупность всех подмножеств множества А называется его булеаном или множеством-степени и обозначается через P(A)={B|BA}.  Ассоциативность операций A()=(AB)C; Коммутативность операций A=B; З-ны идемпотентности A=A; З-ны дистрибутивности A(B C)=(AB)(AC); З-ны поглащения A(A)=A; З-ны де Моргана =; З-ны 0 и 1:  положим 0=, 1=U, тогда A0=A, A; Закон двойного отрицания =A

4.Пусть G = (M,R) – неорграф M = {М\,М2} – разбиение множества М. Разрезом графа G (по разбиению M) называет множество всех ребер, соединяющих вершины из М1 с вершинами из М2. Отметим, что в связном графе любой разрез непуст. Непустой разрез К неорграфа G называется простым разрезом или конциклом, если любое непустое собственное подмножество К≠ К не является разрезом ни по какому разбиению. Другими словами из К нельзя удалить ни одно ребро с тем, чтобы полученное множество было непустым разрезом. Т. В конечном неорграфе G=(M,R), имеющем с компонентом, когда граф (M,R\K) имеет (с+1) компонент связанности   

5.Размещением с повторением из n элементов по m или упорядоченной (n,m)-выборкой с возвращениями называется любой кортеж (a1..am) элементов множества М, для которого |М| = п. Поскольку в кортеж (a1,a2… аm.) на каждое место может претендовать любой из п элементов множества М, число размещений с повторениями Р(п,т) равно n*n*n…*n=      P(n.m)=  Сочетанием с повторением из n элементов по m или неупорядоченной (n,m)- выборки с возвращениями называется любой класс эквивалентности по отношению ~ множества размещений с повтор. из n элементов по m. Число сочетаний с повт. из n элементов по m С(m,n)== 
 
6.Графом, называется алгебраическая система G = (M,R), где R — двухместный предикатный символ. Элементы носителя М называются вершинами графа G, а элементы бинарного отношения R — дугами. Таким образом, дугами являются пары вершин (a, b) R. При этом дуга (а, b) называется исходящей из вершины, а, И заходящей в вершину b. Изображение графа G = (М, R) получается путем расположения различных точек на плоскости для каждой вершины a, М, причем если (a,b) R, то проводится стрелка (дуга) из вершины а к вершине b. Граф называется ориентированным если найдеться дуга (a,b) R , такая что (b,a) R

7.Сочетанием из n элементов по m или неупорядоченной (n,m) выборкой называется любое подмножество подмножества М, состоящее из m  элементов. Н-Р: если М= {a,b,c}, то {a,b}, {a,c},{b,c} все сочетания из 3 по 2. Число сочетаний из n по m обозначается через ,) или С(n,m).  = для любых a,bR, nω(Бином Ньютона). Числа называют биномиальными коэффициентами.

8.ФАЛ от переменных x1, x2…xn называется любая функция f:→{0,1} т.е. функция, которая произвольному набору (δ1,δ2..δn) нулей и единиц ставит в соответствие значение f (δ1,δ2..δn) {0.1}. ФАЛ называют также булевыми функциями, двоичными функциями и переключательными функциями. Преобразование логических функций с целью упрощенияих аналитического представления называются минимизацией. Определение. Неполностью определенной функцией является такая переключательная функция, значения которой на некоторых наборах аргументов могут быть произвольными (т.е. равными "0" или "1"). Определение. Пусть функция f(x1,x2,...xn) не определена на "р" наборах аргументов. Тогда полностью определенную функцию (x1,x2,...xn) будем считать эквивалентной к f(x1,x2,...xn), если ее значения на тех наборах, на которых f(x1,x2,...xn) определена, совпадают. Очевидно, существует 2р различных функций, эквивалентных f(x1,x2,...xn). Задача минимизации f(x1,x2,...xn) состоит в выборе такой эквивалентной (x1,x2,...xn), которая имеет простейшую форму. Введем две вспомогательные эквивалентные функции 0(x1,x2,...xn), 1(x1,x2,...xn), которые принимают на запрещенных наборах аргументов значения 0 и 1 соответственно.

9.Под минимизацией ФАЛ понимается преобразование ее алгебраического выражения с целью наиболее простого представления функции. При использовании метода карт Карно производится накрытие с помощью правильных конфигураций содержащих нули или единицы. Правильными конфигурациями на карте Карно для ФАЛ от n переменных являются все прямоугольники (горизонтальные, вертикальные, квадраты), имеющие площадь 2^n-i (i = 0, 1, 2, … , n).При накрытии ФАЛ стремятся, чтобы число накрытий на карте было минимально, а площадь, накрываемая каждой правильной конфигурацией – максимальна. Конфигурации могут перекрываться, накладываться друг на друга. При выборе накрытия возможно объединение крайних полей, расположенных на противоположных сторонах карты, в горизонтальном и вертикальном направлениях. Принцип минимизации заключается в объединении соседних полей карты в пределах правильных конфигураций. При нахождении минимальной формы ФАЛ, выписываются переменные не изменяющие своего значения в пределах правильной конфигурации. При объединении полей в которых записаны единицы, ФАЛ выписывается в ДНФ, т.е. в виде дизъюнкции произведений переменных неизменных в пределах каждой конфигурации накрытия. При объединении полей содержащих нули, ФАЛ записывается в КНФ, т.е. в виде произведений дизъюнкций инверсных значений переменных, не меняющихся при переходе с одного поля конфигурации на другое

10.Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Граф G называется связным, если соответствующий ему неорграф F(G) тоже: является связным. Граф G называется сильно связным, если для каждой пары различных вершин а и b существуют (а, b)-маршрут и (b, а)-маршрут. Аналогично определяются понятия связности и сильной связности для мультиграфов. Всякий максимальный по включению (сильно) связный подграф данного графа называется его (сильной) связной компонентой или (сильной) компонентой связности. Любой граф представляется в виде объединения непересекающихся связных (сильных) компонент. Разложение графа на связные (сильные) компоненты определяете однозначно. Таким образом, множества вершин связных компонент, а также сильных компонент образуют разбиение множества вершин графа, а число c(G) связных компонент графа G определяется однозначно.

11.Граф Н называется подграфом графа G, если множество вершин графа Н есть подмножество вершин графа G, и множество ребер графа Н есть подмножество ребер графа G: V_H ÍV_G E_H ÍE_G .  1. добавление ребра x=(Vi,Vj) в графе G. H=G+x, V_H=V_G, E_H=E_GÈ{x}= E_GÈ{(Vi,Vj)}. Замечание: ребра добавляются только между несмежными вершинами, иначе получим мультиграф. 2. удаление ребра H=G-(Vi,Vj). V_H=V_G, E_H=E_G/{(Vi,Vj)}. 3. удаление вершины H=G-Vi, V_H=V_G/{Vi},  E_H=E_G/{x| x – ребра, инцидентные Vi)}. 4. объединение графов GÈH, V_HÈV_G, E_HÈE_G. Обычно полагают, что множества вершин и ребер не пересекаются. В противном случае операция объединения сводится к наложению графов друг на друга. 5. пересечение графов GÇH. Эта операция полагает, что пересечение вершин – не пустое множество. Тогда получаем граф, у которого пересекаются вершины и пересекаются ребра. V_HÇV_G, E_HÇE_G 6. сложение графов G+H, V_HÈV_G, E_HÈE_GÈ{x=(u,v)|uÎV_G, vÎV_H}, т.е. из каждой вершины первого графа строим ребра к каждой вершине второго графа.

12.Определение: Преобразование логических функций с целью упрощения их аналитического представления называются минимизацией. 
Существуют два направления минимизации: 
1. Кратчайшая форма записи (цель - минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ. 
2. Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу). 
При этом следует учесть, что ни один из способов минимизации не универсален! 
Существуют различные методы минимизации: 
1. Метод непосредственных преобразований логических функций. При применении данного метода: 
а) Записываются ДСНФ логических функций 
б) Форма преобразуется и упрощается с использованием аксиом алгебры логики. При этом, в частности, выявляются в исходном ДСНФ так называемые соседние min-термы, в которых есть по одной не совпадающей переменной. 

13.Если ребра не имеют ориентации, граф называется неориентированным. Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути. Маршрут в графе путь, ориентацией дуг которого можно пренебречь.  
Цепь маршрут, в котором все ребра попарно различны. Цикл замкнутый маршрут, являющийся цепью.Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом. Свойства: 1) Всякий незамкнутый (u, v)-маршрут, содержит в себе простую (u, v)-цепь. В частности, любая (u, v)-цепь, содержит в себе простую (u, v)-цепь. Причем, если (u, v)-маршрут содержит в себе вершину w (w?u и w?v), то в общем случае, простая (u, v)-цепь может не содержать в себе вершину w.2) Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.3) Всякая непростая (u, v)-цепь, может быть разбита на простую (u, v)-цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.4) Для любых трех вершин u, w, v из существования (u, w)-цепи их и (w, v)-цепи, следует существование (u, v)-цепи. Причем может не существовать (u, v)-цепи, содержащей вершину w.5) Объединение двух несовпадающих простых (u, v)-цепей содержит простой цикл. 6) Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.

14.Бинарным отношением между множествами А и В называется любое подмножество p прямого произведения A X B. Часто чтобы обозначить принадлежность упорядоченной пары (x,y)  к бинарному отношению p вместо записи(x,y) p  используют обозначения p(x,y) или xpy. При этом говорят, что x находится в отношении p к y. Если A=B, то говорят, что p задано на множестве A. Пример A={a,b,c,d,e,f,g,h} и B={1,2,3,4,5,6,7,8} тогда подмножество {(a,2),(c,3),(d,5)} в A*B является бинарным отношением между множествами А и В

15.Фундаментальные циклы графа. О. Рассмотрим каркас Т графа G. e1…es — все ребра графа G, которые не входят в каркас T. При добавлении ei образуется простой цикл Ci. Семейство циклов C1…Cs называется фундаментальными циклами графа G относительно каркаса T. Теорема: Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис циклического пространства этого графа. Док-во: Рассмотрим каркас T графа G и фундаментальные циклы C1..Cs относительно каркаса T. В каждом цикле есть ребро e1, которое принадлежит ровно одному из C1..Cs. Поэтому сумма различных фундаментальных циклов относительно каркаса T не является пустым графом, из чего следует, что C1…Cs линейно независимы.Докажем, что любой цикл из циклического пространства графа G является суммой фундаментальных циклов. Пусть Z — цикл циклического пространства графа G, e1…ek ребра принадлежащие Z и не принадлежащие T. Рассмотрим граф F=Z C1…Ck. Каждое из ребер et, t=1…k  встречается ровно в двух слагаемых — Z и Ck. Значит F содержит только ребра из T. Так как C1…Ck  простые циклы, то степени всех их вершин четны, степени вершин Z тоже четны по лемме, значит степени всех вершин F четны. Если Fнепустой граф, то в F есть цикл, значит цикл есть и в T. Значит F пустой граф, откуда следует что Z= C1…Ck

16.Перестановки. Имеются предметы n различных видов а1, а2..аn. Из них составляют всевозможные расстановки длины k. Две расстановки считаются различными, если они отличаются друг от друга порядком этих предметов. Такие расстановки называются перестановками из n элементов по k. Их количество обозначается символом Рn.Теорема: число различных перестановок из n элементов Рn=n! Доказательство: число перестановок n элементов равно числу размещений без повторений из n элементов по n элементов, поэтому: Рn=Аn\n= n!/0!= n! РАЗМЕЩЕНИЯ  Имеются предметы n различных видов а1, а2..аn. Из них составляют всевозможные расстановки длины k. Две расстановки считаются различными, если они отличаются друг от друга или видом входящих в них предметов, или порядком этих предметов. Такие расстановки называются размещением с повторениями из n элементов по k (элементы одного вида могут повторятся).k,n - любые натуральные числа. k может быть больше n, элементы в расстановке могут повторяться. Пример: расстановке длиной 6, k=6: a3,a1,a1,a2,a1,a3. Телефонные номера - есть размещения с повторениями. Теорема: число различных размещений с повторениями из n элементов по k: N= n^k (n в степени k)Доказательство: введем множества х1,..хk такие, что х1=х2...={а1...аn}. Тогда все размещения с повторением составят множество х1 х .. х xk. По правилу произведения общее число размещений с повторениями из n по k равно |х1..хk|= n*n...n= n^k.

17.Переменная x называется булевой, если она способна принимать только два значения 0 и 1. В качестве примера интерпретации такого рода переменных может выступать обычный настенный выключатель света на два положения. Здесь 1 соответствует положению переключателя вверх и 0 — положению вниз. 
Определение. Функция f(x1,x2,…,xn) называется булевой (или логической, или функцией алгебры логики, или переключательной), если все ее аргументы x[i] являются булевыми, а сама функция также может принимать только два значения 0 и 1. Множество всех булевых функций от переменных x1,x2,…,xn обозначают через P2. Свойства xy=y- коммутативность;  x=(x- ассоциативность; – дистрибутивность