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

18.Введем определение классов Поста.   Класс P 0 — это класс булевых функций, сохраняющих нуль, т. е. функций f(x1,..., х_n), для которых f(0,0,... , 0) = 0: P0 = {f | f(0,0, ...,0) =0}. Класс P1 — это класс булевых функций, сохраняющих единицу, т. е. функций f(x1,...xn), для которых f(1,1,..., 1) = 1: P1 ={f|f(1,1..,1) = 1}. Класс S-это класс самодвойственных функций: s{f|f — самодвойственная функция}.  Класс М-это класс монотонных функций. Булева функция f(x1,..xn) называется монотонной, если для любых наборов нулей и единиц (α1,.., αn) и (β1,.., βn) из условий α1≤ β1, αn≤ βn следует (α1,.., αn) ≤(β1,.., βn)  Таким образом, М = {f | f — монотонная функция}. Класс L — это класс линейных функций. Булева функция f(x1,...,x_n) называется линейной, если в булевом кольце ({0,1}, ,) функция f представима в виде f(x1,..., xn) = C0 , где C0,C1,C2,…Cn{0,1}.

19.Суть метода сводится к тому, чтобы преобразовать СДНФ в МДНФ. Задачи минимизации по методу Квайна состоит в попарном сравнении импликант, входящих в СДНФ с целью выявления возможности склеивания по какой-то переменной так: FxiFxi=F= F. Таким образом, можно понизить ранг термов. Процедура производится до тех пор, пока не остается ни одного терма, допускающего склейки с другим. Причем склеивающиеся термы помечаются Определение: Непомеченные термы называются первичными импликантами. Полученное логическое выражение не всегда оказывается минимальным, поэтому исследуется возможность дальнейшего упрощения. Для этого:1. Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.2. Клетки этой таблицы отмечаются в том случае, если первичная импликанта входит в состав какого-нибудь первичного терма.3. Задача упрощения сводится к нахождению такого минимального количества импликант, которые покрывают все столбцы. Алгоритм метода Квайна (шаги): 1. Нахождение первичных импликант. Исходные термы из ДНФ записывают в столбик и склеиваю сверху вниз. Непомеченные импликанты переходят в функции на этом шаге.2. Расстановка меток избыточности. Составляем таблицу, в которой строки – первичные импликанты, столбцы – исходные термы. Если некоторый min-терм содержит первичный импликант, то на пересечении строки и столбца ставим метку.3. Нахождение существенных импликант. Если в каком-либо столбце есть только одна метка, то первичный импликант соответствующей строки является существенным.4. Строка, содержащая существенный импликант и соответствующие столбцы вычеркиваются.Если в результате вычеркивания столбцов появятся строки первичных импликант, которые не содержат метки или содержат одинаковые метки в строках, то такие первичные импликанты вычеркиваются. В последнем случае оставляем одну меньшего ранга. 5. Выбор минимального покрытия. Из таблицы, полученной на шаге 3 выбирают такую совокупность первичных импликант, которая включает метки во всех столбцах по крайней мере по одной метке в каждом. При нескольких возможных вариантах отдается предпочтение покрытию с минимальным суммарным числом элементов в импликантах, образующих покрытие. 6. Далее результат записывается в виде функции.

20.Кольцо — структура с двумя бинарными операциями: абелева группа по сложению, моноид по умножению, выполняется закон дистрибутивности:  a∙ (b+c)=a∙b+a∙c, (a+b) ∙c=a∙c+b∙c. Дистрибутивность (далее Д) (от лат. distributivus - распределительный), распределительность, распределительный закон, свойство умножения, выражаемое тождествами с (a + b) = са + cb и (а + b)c = ас + bc. В более общем смысле говорят о Д оператора (x) относительно некоторого действия х * у как о свойстве, выражаемом равенством (x * у) = (x) * (y). Например, равенство (ab)n = anbnпоказывает, что оператор возведения в степень дистрибутивен относительно операции умножения (но не относительно операции сложения, т. к., вообще говоря, (a + b) n ¹ an + bn).

21.Теорема Поста. Система F булевых функций тогда и только тогда является полной, когда для каждого из классов Ро, P1, S, М, L  в системе F найдется функция, не принадлежащая этому классу. В силу теоремы Поста функция х|у образует полную систему; т. е. с помощью штриха Шеффера можно получить любую булеву функцию. В частности, , xy~(x(x|y)~(x|y)|(x|y). Система булевых функций называется базисом, если оная полна, а удаление любой функции из этой системы делает ей неполной. Теорема..Каждый базис содержит не более четырех булевых функций. Док-во. Предположим, что существует базис f состоящий более чем из четырех функций. По теореме Поста тогда получаем, что f состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f - функция из f, не принадлежащая классу Р0. Тогда, с одной стороны, f(0,0,.... 0) = 1, а, с другой — из  следует что f(1,1,... ,1) = 1. Это означает, что f не является самодвойственной функцией, что противоречит предположению

22.Алгебраической системой U = (А,∑) сигнатуры ∑ называется непустое множество А, где каждому n-местному предикатному (функциональному) символу из ∑ поставлен в соответствие п-местный предикат (соответственно операция), определенный на множестве А. Множество А называется носителем или универсумом алгебраической системы (А,∑). Предикаты и функции, соответствующие символам из ∑, называется их интерпретациями. Интерпретация любого константного символа является некоторый элемент (константа) из А. Мощностью алгебраической системы U называется мощность ее носителя А. Сигнатура ∑ называется функциональной, если она не содержит предикатных символов. Система U называется алгеброй, если ее сигнатура функциональна.

23.Под множеством понимают совокупность некоторых объектов, объединенных по какому-либо признаку. Объекты, из которых состоит множество, называются его элементами. Если элемент х принадлежит множеству X, то записывают х ÎX; запись хÏХ или х ÎX означает, что элемент х не принадлежит множеству X. Множество, не содержащее ни одного элемента, называется пустым, обозначается символом Ø. Множество А называется подмножеством множества В, если каждый элемент множества А является элементом множества В.. Объединением (или суммой) множеств A и В называется множество, состоящее из элементов, каждый из которых принадлежит хотя бы одному из этих множеств. Объединение (сумму) множеств обозначают AUВ (или А+В). Кратко можно записать АUВ={х:хєА или хєВ}.Пересечением (или произведением) множеств А и В называется множество, состоящее из элементов, каждый из которых принадлежит множеству А и множеству В. Пересечение множеств обозначают А∩В (или А*В). Кратко можно записать А∩В={х:хєА и хєВ}. М.И.Если предложение А(n), зависящее от натурального числа n, истинно для n=1 и из того, что оно истинно для n=k (где k-любое натуральное число), следует, что оно истинно и для следующего числа n=k+1, то предположение А(n) истинно для любого натурального числа n. Если предложение А(n) истинно при n=p и если А(k)ÞА(k+1) для любого k>p, то предложение А(n) истинно для любого n>p.

24. 1) Для  любых бинарных отношений P,Q, R выполняются следующие свойства: 1) (Р-1)-1 = Р; 2) ; 3) ) (P o Q) o R= P o (Q o R) (ассоциативность композиции). Док-во: По определению обратного отношения условие (x,y) P равносильно условию (y,x) , что в свою очередь выполняется тогда и только тогда, когда (x,y) , P=. Отношение  называется функцией или отображением из множества А в множество B, если , pf и из (x,y1) f, (x,y2) f следует y1=y2. Если вместо = A выполняется     , то f называется частичной функцией. Функция f называется разнозначной, инъективной (инъекцией) или 1-1-функцией, если отношение является частичной функцией, т. е. для любых элементов x1,x2 следует f(x1) f(x2) .Если f — инъекция, то пишем f: A. Функция f: A называется функцией А на В или сюръективной функцией (сюръекцией), если pf=B. Если f-сюръекция, то будем писать f: AB. Функция f называется взаимно однозначным соответствием между множествами А и В или биективной функцией, если она инъективна и сюръективна Биекция f:A A называется подстановкой множества А.

25.Отношение R на множестве  называется отношением порядка, если оно обладает следующими свойствами:   (x,x) ∈ R для всех x ∈ A (рефлексивность);  Если (x,y) ∈ R   и(y,x) ∈ R  , то x=y (антисимметричность); Если (x,y) ∈ R  и (y,z) ∈ R , то (x,z) ∈ R (транзитивность) Обычно отношение порядка обозначают знаком . Если для двух элементов x и y выполняется xy, то говорят, что x "предшествует" y. Если xx для всех xA (рефлексивность) Если x≤y  и y≤x  ,то x=y (антисимметричность) Если x≤y   и y≤z  , то x≤z (транзитивность).Для любых чисел x и y выполняется либо x≤y   , либо y≤x  , т.е. любые два числа сравнимы между собой. Такие отношения называются отношениями полного порядка.

26. Отношение Р называется отношением эквивалентности (эквивалентностью), если Р рефлексивно, симметрично и транзитивно. Эквивалентности часто обозначают символами Е и ~ (тильда): x E y, x ~ y. Пусть Е- эквивалентность на множестве А . Классом эквивалентности элемента x A называется множество E(x) = {y|xEy}. Классы эквивалентности E будут так же называться фактор-множеством множества А по отношению Е. О-ие. Пусть p — некоторое бинарное отношение  на множестве А . Будем говорить, что p — отношение эквивалентности, если оно одновременно удовлетворяет свойствам рефлексивности: (x,x) для всех x ; симметричности: (x,y)   для всех  x,y; транзитивности ((x,y)  для всех x, y, z A. В этом случае вместо (x,y)  употребляется запись x~y , где x,y  .

27.  Т1.Из всякого бесконечного множества А можно выделить счетное множество.  Док-во: Пусть А – бесконечное множество. Возьмем произвольный элемент а₁ОА. тогда множество А\{а₁} будет по-прежнему бесконечным. Из множества А\{а₁} возьмем произвольный элемент а₂ОА\{а₁}. Множество А а₂ОА\{а₁, a₂} будет по-прежнему бесконечным. Из множества А\{а₁, a₂} возьмем произвольный элемент а₃О А\{а₁,a₂}. Множество А а₂ОА\{а₁, a₂, а₃} будет по-прежнему бесконечным. Продолжая этот процесс до бесконечности, мы получим счетное множество В={a₁, a₂, a₃,…}, для которого очевидно, что ВА, т.е. В является подмножеством А. Т2. Всякое бесконечное подмножество счетного множества тоже счетно. Пусть А – счетное множество и ВМА также содержит бесконечное число элементов. Представим А в форме последовательности: А={a₁, a₂, a₃,…}. Будем рассматривать элементы множества А по порядку, т.е. а₁, затем а₂,а₃ и т.д. При этом мы иногда будем “наталкиваться” на элементы подмножества В. Будем ставить этим элементам множества В в соответствие “номер встречи с ним”. Тем самым, будет установлено взаимно-однозначное соответствие между В и N, что и говорит о счетности В. Т3. Сумма конечного числа счетных множеств есть также счетное множество. Пусть для простоты имеются два счетных множества А и В; А={a₁, a₂, a₃,…}; В={b₁, b₂, b₃,…}. Представим их сумму в виде АИВ={a₁, b₁, a₂, b₂, a₃, b₃,…}. →АИВ есть счетное множество. Т3. Сумма счетного числа конечных множеств есть конечное или счетное множество.

28. Для описания логики функционирования аппаратных и программных средств ЭВМ используется алгебра логики или, как ее часто называют, булева алгебра. Булева алгебра оперирует с логическими переменными, которые могут принимать только два значения: истина или ложь, обозначаемые соответственно 1 и 0.Как ранее отмечалось, основной системой счисления ЭВМ является двоичная СС, в которой также используются только две цифры: 1 и 0. Таким образом, одни и те же цифровые устройства ЭВМ могут применяться для обработки как числовой информации в двоичной СС, так и логических переменных. Это обуславливает универсальность (однотипность) схемной реализации процесса обработки информации в ЭВМ. Совокупность значений логических переменных x1, x2, ..., xn называется набором переменных. Логической функцией от набора логических переменных (аргументов) F(x1, x2, ..., xn ) называется функция, которая может принимать только два значения: истина или ложь (1 или 0). Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются возможные наборы аргументов, а в правой — соответствующие им значения функции. Логическую функцию порой называют функцией алгебры логики (ФАЛ). В случае большого числа аргументов табличный способ задания функции алгебры логики становится громоздким, поэтому ФАЛ удобно выражать через другие, более простые ФАЛ. Общее число ФАЛ n переменных определяется возведением числа 4 в степень n, т. е. 4n. В алгебре логики рассматриваются переменные, которые могут принимать только два значения: 0 и 1. Базируется алгебра логики на отношении эквивалентности и трех упомянутых ранее операциях: дизъюнкции (синонимы — логическое сложение, операция ИЛИ), конъюнкции (логическое умножение, операция И) и отрицании (инверсия, операция НЕ).

30. СДНФ, формулы алгебры логики, называется формула представляющая  данную функцию и имеющая вид дизъюнкции полной конъюнкции, которые формируются для набора переменных при которых значение функции равно 1. Для любой логической функции существует единственное представление её в виде СДНФ. Существует несколько алгоритмов построения СДНФ функции. Для случаев простых функций, удобно использовать табличный метод: составляется таблица истинностей, для данной функции, рассматриваются только те строки в которых принимает значение равное 1 берется без инверсий, а аргумент со значением 0 с инверсией. Затем выполняется дизъюнкция полных конъюнкций. Н-Р:  xy+xz приведем к сднф, учитывая z+=1 b и на 1 можно домножить xy(x+ )+x=xy(x+-x). СКНФ формулы алгебры логики называется формула представляющая данную функцию и имеющая вид конъюнкция полной дизъюнкции, которая формируется для набора переменных, при которых функция =0. Для любой логической функции, существует единственное представление её в виде СКНФ.  f(x1,x2,x3)=(x1+x2+x3)(x1++x3)(,x2,)(

31. Первая теорема  Шеннона. Любая булева функция f(x1,x2…xn) представима в виде разложения Шеннона: f(x1,x2..,xk,xk+1,…,xn)= ()f(. Док-во: =1 xi=. Подставим произвольно вместо k переменных их значения: x1=, x2=, xk= . Тогда левая часть доказываемой формулы равна f(,,.., xk+1,.., xn). Правая часть представляет собой дизъюнкцию конъюнкций вида f( которые разбиваются на 2 класса. К первому относится конъюнкция , у которой набор () совпадает с набором (,,..): … f(,,.., xk+1,.., xn)=11(,,.., xk+1,.., xn)= f(,,.., xk+1,.., xn). Эта конъюнкция равна левой части формулы. Ко второму классу относится конъюнкций, у каждой из которых хотя бы в 1 переменной xi, {1,2,…k} выполнимо условие каждая равна 0. Используя з-н a⋁0=a, получаем, что левая и правая части равны при любой подстановке переменных x1,x2,…xn.

32(11). Удаление вершины или ребра - это пример операций, уменьшающих число элементов графа. Рассмотрим теперь операции над графами, увеличивающими число вершин или ребер. Такова, например, операция добавления ребра е = uv, если вершины u и v графа G не являются смежными. В результате получается граф G + е, у которого эти вершины уже соединены ребром.Граф H называется объединением (или наложением) графов F и G, если VH = VFVG и ЕН = EFEG . В этой ситуации пишут H=FG Объединение FG называется дизъюнктным, если VF VG = Ø. Пусть Gi m (Vi, Ei) (i = 1, 2)- два графа. Произведением G1 G2 = G называется граф, для которого VG = V1 V2 - декартово произведение множеств вершин исходных графов, a EG определяется следующим образом: вершины (и1 , и2) и (w1 , w2) смежны в графе G тогда и только тогда, когда или и1=w1 , а и2  и w2 смежны в G2 , или и2=w2 , а и1  и w1 смежны в G1.Очевидно, что |G1 G2 | = |G1| |G2 |, |E(G1 G2 )| = |G1 | |EG2 | + |G2 | |EG1 |С помощью операции произведения вводится рекуррентным образом важный класс графов – п-мерные кубы Qn: Q1=K2;   Qn=K2Qn-1(n>l). Граф Qn имеет порядок 2п, вершины его можно представить (0,1)-векторами длины п таким образом, что две вершины будут смежны тогда и только тогда , когда соответствующие векторы различаются ровно в одной координате.

34.Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Сам такой цикл также называется гамильтоновым. Гамильтоновой называется и простая цепь, содержащая все вершины графа. Очевидно, что любой граф, ребра которого образуют простой цикл, является гамильтоновым. Известны следующие достаточные условия существования гамильтоновых циклов в связном неорграфе G без петель, имеющем п3 вершин:Теор..Если для любых двух различных несмежных вершин a иb графа G выполняется условие deg a+deg b n, то существует гамильтонов цикл. Следствие: Если для любой вершины а графа G выполнено условие deg a/2, то существует гамильтонов цикл.

37. Маршрутом (путем) для графа G(V, Е) называется последовательность v₁e₁v₂e₂v₃…e_kv_k+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути). Любой отрезок конечного или бесконечного маршрута  M вида M’(em,…en), где 1≤m,n≤k+1 также является маршрутом и называется участком маршрута M. Определим алгоритм Форда- Беллмана. Зададим строку =(,…), пологая =,. В этой строке () есть вес дуги (), если () существует и =, если (,) R. Определим строку =(,…), пологая =min ,+}k=1,..,n.-минимальный из весов ()-маршрутов, состоящих не более чем из 2 дуг (рис.1). =(,…), пологая =min ,+}k=1,..,n. Строка w-расстояний получается из s=n-1:=pw(ai,aj). Работу завершим на шаге k, если = Пример: В качестве источника выберем вершину 1. Тогда =(0,1,,,3), =(0,1,4,4,3), (0,1,4,4,-1), =(0,1,4,3,-1). Т.о. , =4, (1,4)=3,(1,5)=-1