шпоры 2 (шпоры в ворде на печать)

Вопрос №17

Вопрос №18

Вопрос №19

Вопрос №20

Полиномом Жегалкина называется выражение вида:  _i1…is x_i1,…x_is (_i1…is B), где суммирование производится по различным наборам 1<1<…<i_s, и среди слагаемых имеется константа ₀ B, отвечающая пустому множеству.

Теорема: Любая б.ф. реализуется подходящим полиномом Жегалкина.

Доказательство: Учитывая, что тождества в булевом кольце дают возможность свободного обращения с выражениями, содержащими сложение и умножение и то, что х=х1, получим:

Последнее выражение после раскрытия дает полином Жегалкина.

Полиномом Жегалкина называется выражение вида:  _i1…is x_i1,…x_is (_i1…is B), где суммирование производится по различным наборам 1<1<…<i_s, и среди слагаемых имеется константа ₀ B, отвечающая пустому множеству.

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

Теорема: всякую функцию можно реализовать единственным полиномом Жегалкина, т.е. ПЖ однозначно определяет БФ.

Доказательство: Поскольку число наборов переменных х1, х2, …, хn совпадает с числом подмножеств множества { х1, х2, …, хn} и равно 2ⁿ и каждый коэффициент полинома Жегалкина равен 0 или 1, то число полиномов от переменных совпадает с числом характеристических функций на множестве указанных наборов. Т. образом число полиномов в точности равно числу булевых функций от n переменных. Поскольку каждая функция реализуется полиномом (т.к. через полином могут быть получены функции стандартного базиса, через который реализуется любая б.ф. что легко показать), теорема доказана.

Полиномом Жегалкина называется выражение вида:  _i1…is x_i1,…x_is (_i1…is B), где суммирование производится по различным наборам 1<1<…<i_s, и среди слагаемых имеется константа ₀ B, отвечающая пустому множеству. Функция f(x₁,…,x_i-1,x_i,x_i+1,…,x_n) из P₂ зависит существенным образом от аргумента x_i, если существуют такие значения ₁,… _i-1, _i, _i+1,… _n, переменных x₁,…,x_i-1,x_i,x_i+1,…,x_n, что

f(₁,… _i-1,0, _i+1,… _n)f(₁,…_i-1,1, _i+1,… _n). В этом случае переменная x_i называется существенной. Переменная, не являющаяся существенной, называется несущественной, или фиктивной.Теорема: Пусть реализуемая полиномом Жегалкина функция f(x₁,x₂,…,x_n) зависит только от переменных, входящих в полином. Тогда все переменные функции f существенны. Доказательство: От противного. Пусть х_i – фиктивная переменная. Группируя все слагаемые полинома, содержащие х_i, представим функцию f в виде: f(x₁,x₂,…,x_n)=x_i g(x₁,…,x_i-1,x_i+1,…x_n) h(x₁,…,x_i-1,x_i+1,…x_n), где g и h – полиномы Жегалкина. Так как функция g не равна тождественно нулю, существует набор (₁,… _I-1, _I+1,…,_m) на котором она принимает значение 1, из чего следует, что f существенно зависит от xi, что противоречит условию. Следствие: равные функции реализуются одним и тем же полиномом Жегалкина.

ДНФ от переменных x₁,…,x_n – это формула вида K₁…K_m, где K_i –элементарная конъюнкция, содержащая некоторые из литералов из x₁,…,x_n. Когда в каждую конъюнкцию K_i входит в точности один из литералов x_j (x_j ), ДНФ называется СДНФ. Задача о минимизации ДНФ сводится к отысканию такой формы, которая содержит наименьшее число литералов (функций х или х) по сравнению с другими эквивалентными ей ДНФ.

Алгоритм Блейка является одним из методов склейки исходной функции и состоит в том, что к любой ДНФ, представляющей функцию применяются следующие тождества:

• Правило обобщенного склеивания: х К₁х К₂= хК₁ х К₂  К₁ К₂

• Правило поглощения: К₁  К₁ К₂ = К₁

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

Вопрос №21

Вопрос №22

Вопрос №23

Вопрос №24

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

Функция f называется импликантой g, если для любых наборов значений переменных из f=1 g=1, но не наоборот. ДНФ называется тупиковой, если удаление любой простой импликанты нарушает эквивалентность этой ДНФ исходной. Простую импликанту называют ядровой, если она покрывает некоторую импликату исходной СДНФ, не покрываемую никакими другими импликатами, т.е. на карте Карно, если мы ее удалим, возникнет непокрытая единица.ТДНФ – ДНФ без избыточных импликант, т.е. содержащая только ядровые импликаты.

Для определения МДНФ от 3 или 4 переменных можно использовать карту Карно, которая является одной из форм таблицы истинности. Процесс склейки выглядит так: на карте Карно 2, 4 или 8 соседних единиц обводятся прямоугольником, который обозначает склейку. Таким образом, мы получаем все простые импликанты исходной функции. Карты Карно для 3 и 4 переменных:

Задача о минимизации ДНФ сводится к отысканию такой формы, которая содержит наименьшее число литералов( функций х или х) по сравнению с другими эквивалентными ей ДНФ. Алгоритм Квайна-Мак-Клоски. 1. Операция склейки: Пусть К1 и К2 – две элементарные конъюнкции, входящие в исходную СДНФ, причем К₁=хК , К₂=хК, где К – некоторая элементарная конъюнкция. Тогда К₁К₂=хК(хК)=(хх)К=К. Процесс склейки можно выполнить, используя карты Карно, которая является одной из форм таблицы истинности. Процесс склейки выглядит так: на карте Карно 2, 4 или 8 соседних единиц обводятся прямоугольником, который обозначает склейку. Поучаем сокр. ДНФ. 2. Определение ядра. Простую импликанту называют ядровой, если она покрывает некоторую импликату исходной СДНФ, не покрываемую никакими другими импликатами. 3. Перечисление тупиковых ДНФ. ДНФ называется тупиковой, если удаление любой простой импликанты нарушает эквивалентность этой ДНФ исходной (т.е. ДНФ содержит все ядровые импликанты и не содержит ни одной избыточной). Получить ТДНФ можно, используя КНФ функцию Патрика К1… Kn. Раскрывая скобки в КНФ и применяя правило поглощения, получим ДНФ, элементарные конъюнкци которой определяют ТДНФ. 4. Отыскания среди ТДНФ минимальных ДНФ. Операцию получения сокр. ДНФ можно провести по алгоритму Блейка. Он состоит в том, что к любой ДНФ, представляющей функцию применяются следующие тождества: правило обобщенного склеивания: х К₁х К₂= хК₁ х К₂  К₁ К₂ правило поглощения: К₁  К₁ К₂ = К₁ Сам алгоритм следующий: сначала к ДНФ применяют правило обобщенного склеивания до тех пор, пока не перестанут появляться новые элементарные конъюнкции, а затем, применяют правило поглощения. В результате получаем сокращенную ДНФ.

Пусть F – некоторое множество булевых функций. Замыканием [F] множества F называется совокупность всех функций из P, реализуемых формулами над F.

Множество F булевых функций называется функционально замкнутым классом, если [F]=F.

T0 – класс всех функций, сохраняющих константу 0, т.е. f(0,0,…,0)=0;

T1 – класс всех функций, сохраняющих константу 1, т.е. f(1,1,…,1)=1;

S – класс всех самодвойственных функций, т.е. f (x₁,x₂,…,x_n ) = f (x₁,x₂,…,x_n). Например, x иx.

Лемма о несамодвойственной функции: если f(х₁,…,х_n), то, подставляя на места ее переменных х иx, можно получить константу.

Доказательство: т.к. fS, то найдется набор (₁, ₂,…, _n) такой, что f(₁, ₂,…, _n)= f(₁, ₂,…, _n).

Положим _i (х)=х^i , i = 1,…,n, и (х)=f(₁ (х),… _n (х)). Т.е имеем: (0)= f(0^i,…, 0^i) = f(₁, ₂,…, _n) = f(₁, ₂,…, _n)= f(1^i,…, 1^i)= (1). Следовательно (х) – константа. Лемма доказана.

Пусть F – некоторое множество булевых функций. Замыканием [F] множества F называется совокупность всех функций из P, реализуемых формулами над F. Множество F булевых функций называется функционально замкнутым классом, если [F]=F. Функция называется монотонной, если для любых двух наборов  и  f(А₁,А₂,…,А_n)  f(В₁,В₂,…,В_n), при А В (А  В если А₁  В₁, …, А_n  В_n ). Пример: f = 0; f = 1; f = х; f = х₁х_2ъ. Класс монотонных функций обозначается через M. Доказательство замкнутости: если f(х₁,…,х_n)М и g(х₁,…,х_n)М, то f(g(х₁,…,х_n),х₂,…,х_n ) М. Пусть АВ, тогда g(А) g(В)  (g(А),a₂,…,a_n )  (g(В),b₂,…,b_n )  f(g(А),а₂,…,а_n )  f(g(B),b₂,…,b_n ) что и требовалось доказать. К классу лин. ф-ций L относят ф-ции, реализ. полиномом Жегалкина вида: ₀  ₁х₁  … _nх_n (_iB). Лемма о немонотонной функции: из любой немонотонной функции путем подстановки в нее констант и х можно получить отрицание. Доказательство: возьмем два набора А  В для которых f(А)  f(В) и которые различаются K компонентами. Меняя последовательно в наборе А 0 на 1 мы будем приближаться к В и на j замене получим, что f(А₁,…,А_j-1,0, А_j+1,…,А_n)> f(А₁,…,А_j-1,1, А_j+1,…,А_n). Положим (х)= f(А₁,…,А_j-1,х, А_j+1,…,А_n), которая и будет функцией отрицания. Лемма о нелинейной функции: из любой нелинейной функции путем подстановки в нее констант и использования отрицания можно получить конъюнкцию. Доказательство: Пусть f нелинейна, тогда она содержит хотя бы одну конъюнкцию. Пусть К=х_i1 … x_is , s>1 – самая короткая из них. Положим х_i3 … x_is = 1, а для всех х_j, не входящим в К положим х_j =0. Поэтому f примет вид: (х_i1, х_i2) = х_i1 х_i2   х_i1   х_i2  , где  ,  и  - константы, равные 0 или 1. Положим теперь (х_i1 ,х_i2 ) = (х_i1   ,х_i2  )     . При раскрытии (х_i1 ,х_i2 ) получим (х_i1 ,х_i2 )= х_i1  х_i2. Лемма доказана.

Вопрос №25

Вопрос №26

Вопрос №27

Вопрос №28

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

Система F={f₁, f₂, …,f_n} полна тогда и только тогда, когда она целиком не содержится ни в одном из пяти замкнутых классов: T₀, T₁, S, M, L .

Доказательство: 1) Пусть F полна, т.е. [F]= F. Предположим, что F содержится в одном из пяти классов – обозначим его через Q, т.е. F Q. Тогда в силу свойства замыкания и замкнутости Q, получим P₂=[F] Q = Q. С другой стороны замкнутые классы T₀, T₁, S, M и L попарно различны и отличны от P₂ (P₂ – стандартный набор из И, ИЛИ и НЕ). Таким образом P₂  Q. Полученное противоречие доказывает необходимость. (Также можно показать, что существуют функции, не лежащие ни в одном классе Поста (например, штрих Шеффера), а из [F] Q следует, что всякая суперпозиция над F также лежит в Q).

2) Пусть F не содержится целиком ни в одном из 5 классов. Это значит, что в системе есть 5 функции _I, _j, _k, _l и _m, не принадлежащие этим классам. Такая подсистема будет полна:

• Пусть _I T₀T_1.Тогда мы получим либо константу 1, либо отрицание. В последнем случае возьмем несамодвойств. функцию _k S и в силу леммы о несамодв. ф-ции получим константу, а используя отрицание, получим и другую.

• Теперь, на основе леммы о немонотонной функции, мы можем получить отрицание, подставляя в _l M константы и х.

• На основе леммы о нелинейной функции мы можем получить конъюнкцию, подставляя в константы, х и отрицание в _m  L.

Таким образом, мы получили полную систему из И и НЕ. Следовательно, теорема доказана.

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

Система F={f₁, f₂, …,f_n} полна тогда и только тогда, когда она целиком не содержится ни в одном из пяти замкнутых классов: T₀, T₁, S, M, L .

Пусть F не содержится целиком ни в одном из 5 классов. Это значит, что в системе есть 5 функции _I, _j, _k, _l и _m, не принадлежащие этим классам. Такая подсистема будет полна.

-Пусть _I T₀T_1.Тогда мы получим либо константу 1, либо отрицание.

-В последнем случае возьмем несамодвойств. функцию _k S и в силу леммы о несамодв. ф-ции получим константу, а используя отрицание, получим и другую.

-В первом случае на основе леммы о немонотонной функции, мы можем получить отрицание, подставляя в _l M константы и х.

-На основе леммы о нелинейной функции мы можем получить конъюнкцию, подставляя в константы, х и отрицание в _m  L.

Таким образом, мы получили полную систему из И и НЕ, т.е. стандартный базис {, , }, из которого можно получить любую заданную функцию.

Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Для неориентированных графов степенью вершины v называют число dg(v) всех инцидентных (ребро инцидентно вершине, если она является одним из его концов) ей ребер. Для ориентированных графов полустепенью захода вершины  называется число dg^-(v) заходящих в нее дуг, а полустепенью исхода  - число dg⁺(v) исходящих из нее дуг. Степень вершины (ориентированный граф) v - это сумма полустепеней захода и исхода. Дуга называется инцидентной вершине , если она или заходит в  или исходит из . Лемма о рукопожатиях. Сумма степеней всех вершин графа равна удвоенному числу ребер. Доказательство. Будем доказывать по индукции. Лемма выполняется для графа с числом вершин равным числу ребер и равным 0. Теперь предположим, что лемма выполняется для некоторого графа G, т.е. S_G (сумма степеней всех вершин) равно 2*N_G (N_G – сумма всех ребер). Докажем теперь, что лемма верна для графа G^|, получаемому из графа G путем добавления к нему одной вершины или одного ребра. В случае добавления вершины доказательство тривиально (S_G'=S_G=2*N_G=2*N_G’). В случае добавления ребра S_G’=S_G+2=2*N_G+2=2*(N_G+1)=2*N_G’. Теорема доказана.

Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Граф (неориентированный или ориентированный) G₁=<V₁,E₁> называют подграфом графа G=<V,E> (соответственно, неориентированного или ориентированного), если V₁V и E₁E. Если V₁=V₂, то G₁ называется остовным подграфом графа G. Отображение h:V₁V₂ множества вершин графа G₁=<V₁,p₁> в множество вершин графа G₂=<V₂,p₂> называют изоморфизмом графа G₁ в G₂, если любые две вершины смежны в первом графе тогда и только тогда, когда их образы смежны во втором графе, т.е. если (u,vV₁)(up₁vh(u)p₂h(v)). Цепь в неориентированном (путь в ориентированном) графе G – это последовательность вершин v₁,v₂,…,v_n,…, такая, что для любого i v_i-()v_i+1. Простая цепь (все входящие в нее ребра попарно различны и все входящие в нее вершины, кроме, быть может, первой и последней, попарно различны) неориентированного(ориентированного) графа ненулевой длины с совпадающими концами называется циклом(контуром). Неориентированный (ориентированный) граф называют связным, если любые две его вершины соединены цепью (для любых его двух вершин u,v вершина u достижима из v или v достижима из u: u*v или v*u). Компонента неориентированного (ориентированного) графа G – это его максимальный связный подграф. Диаметр графа D(G) – это расстояние между двумя наиболее удаленными друг от друга вершинами.

Вопрос №29

Вопрос №30

Вопрос №31

Вопрос №32

Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Граф (неориентированный и ориентированный) может быть представлен в виде следующей матрицы, называемой матрицей инциденции размера nm, где n – число вершин, а m – число ребер (или дуг): a_ij={^{1, если j-ое ребро инцидентно i-й вершине,}_{0, иначе.} (неориентированный граф); a_ij={^{1, если j-я дуга выходит из I-й вершины,}_{-1, если j-я дуга заходит в i-ю вершину,}^{0, иначе} (ориентированный граф). Матрица смежности вершин – это квадратная матрица B n-го порядка, элементы которой определяются для неориентированного графа следующим образом: b_ij={^{1, если i-я и j-я вершины соединены ребром,}_{0, иначе}. Для орграфа – аналогично. Для неорграфа матрица смежности вершин симметрична. Матрица Кирхгоффа – B_a=(b_{i j})={^{degVi, i=j}_{-1, {Vi,Vj}E}^{0, иначе}. B_a=B_a^T _ib_ij=_jb_ij=0. Теорема. d(G)rkG.

d(G)=max_(u,v) p(u,v) = p(u₀,v_o). u₀=v₁v₂…v_d+1=v₀. v={v₁,…v_d+1,…} v₁ v_d+1

0 1 0 0 0 * rkAd

1 0 1 0 0 *

0 1 0 1 0 *

v_d+1 0 0 1 0 1 *

и т.д. * * * * …

0

Теорема. G=(V,E); |V|=n; |E|=m 1. Граф G – дерево 2. Граф G – связан и m=n-1 |E|=|V|-1. 3. Граф G – ацикличен (не содержит цикла) и |E|=|V|-1. 4.  две различные вершины V₁ и V₂  V соединяют единственный простой путь в G. 5. G – ацикличен;  V₁, V₂ (не смежные) {V₁V₂}E. Все эти утверждения эквивалентны и могут служить определением дерева. 1.2. Индукция по количеству вершин n=|V| n=1  m=0. G=(V,E) с n вершинами. Рассмотрим eE G’=(V₁E\{e}) – состоит из 2-х связанных компонент, а сам не связан. Т.к. цикла нет, то при исключении e получится не связный граф. G’=T₁T₂ n_i – количество вершин в T_i m_i – количество ребер в T_i  m_i=n_i-1 (по предположению индукции). G: |V|=n₁+n₂ |E|=m₁+m₂+1=n₁-1+n₂-1+1=n₁+n₂-1=n-1 ч.т.д. 2.3. Пусть G содержит цикл, тогда если из этого цикла выбросим ребро, то получим связанный граф, у которого |V|=n, |E|=n-2. Докажем, что такого не бывает. Лемма: k – количество компонент связанности графа G=(V,E), тогда |E||V|-k. Проведем индукцию по количеству ребер m. m=0 k=|V|00 – верно. Рассмотрим граф с |E|=n. Выбросим из него ребро G\{e}. У него или k – компонент, или k+1 компонент связанности, а количество ребер n-1. m-1|V|-k, тогда m|V|-k+1|V|-k; m-1|V|-k-1m|V|-k. ч.т.д. 2.3. G – цикл m=n-1. Предположим, что G состоит из k компонент связности. G=T₁..T_k – каждая из них – дерево. n_i – количество вершин T_i, m_i – количество ребер m_i=n_i-1. ^k_i=1m_i=^k_i=1(m_i-1)-1=^k_i=1n_i-1=^k_i=1m_i=^k_i=1n_i-1; (^k_i=1n_i)-kk=1. Есть хотя бы один путь. И такой путь один, иначе был бы узел. ч.т.д.

Матрица Кирхгоффа – B_a=(b_ij)={^{degVi, i=j}_{-1, {Vi,Vj}E}^{0, иначе}. B_a=B_a^T _ib_ij=_jb_ij=0. Теорема Кирхгоффа. G – связный граф, |V_G|2. Количество остовов в G равно алгебраическому дополнению  элемента матрицы B_G.

Схема доказательства: 1. Переберем все подграфы с (n-1) ребром. 2. Проверка дерево или не дерево этот подграф. Доказательство: Лемма: H=(V_n,E_n); |V_n|_=m+1=|E_n|+1. G – матрица ориентированной идентичности. H – дерево (mn) – минор =1; 1).H – не дерево, то минор =0. Вычеркиваем строку, соответствующую вершине и рассмотрим минор (рис.1). H – не дерево  H - не связан  количество компонент связанности больше 1. H=^k_i=1H_i k>1. Рис.2 – блочная матрица. C_j – матрица ориентира инцидентности компонента H_j. aC₁. строк матрицы C₁=0 (рис.3)rkC\{0}<mdet=0. 2). Пусть H - дерево. Мы доказали лемму, что  дерево содержащего не менее двух вершин степени 1V: degV=1 Va; V₁=V. e₁ – единственное ребро в H₁ инцидентное V₁. H\V₁ – дерево (снова).  (вершина), deg_H1=1; a. V₂=, e₂=единственное ребро в H₁, инцидентное  H₂=H₁. В конце концов останется вершина V_min=a (рис.4). Нужный минор – a равен 1. C*C^T=B(G). Рис.5.

B_nn=_e11…e1n-1{^{1. e11…et2, дерево}_0, не дерево. ч.т.д.

Полный граф - граф, у которого каждая пара вершин соединена ребром.

Количество остовов в полном графе. B(P_n)_nn=(n-1 -1 -1….....) ( 1 1 1…….1) (1 1…..….1)

( -1………….….) ( -1 n-1…….…-1) ( 0 n 0……0)

( -1…………….) ( -1 -1 n-1…...-1)( 0 0 n 0…0 )

( …………….….) ( ………………….) (.……………. )

( ..……….…n-1) (-1……………….) (...…………n)

Количество остовов растет как n^n-2.



Но есть способ лучше – алгоритм Крускапа.