41. Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов.

Пусть G=<M,R> - неорграф, имеющий n вершин, m ребер и c компонент связности, Т – остов графа G, имеет υ^*(G)=n-c ветвей и υ(G)=m-n+c хорд. Если к лесу T добавить произвольную хорду υ_i, то в полученном графе найдется ровно один цикл C_i, который называется фундаментальным циклом графа G, хорды υ_i и остова T. Множество {C₁,..,C_m-n+c} называется фундаментальным множеством циклов. Мощность этого множества равна цикломатическому числу υ(G)=m-n+c.

Фундаментальное множество циклов можно задать с помощью матрицы фундаментальных циклов С=(a_ij), где . Пусть G=<M,R> - неорграф, m={M₁,M₂} – разбиение множества М. Разрезом графа G по разбиению m называется множество всех ребер, соединяющих вершины из M₁ c вершинными из M₂. В связном графе любой разрез непуст.

Непустой разрез К неорграфа G называется простым разрезом или коциклом, если любое непустое собственное подмножество не является разрезом ни по какому разбиению.

Теорема: В связном неорграфе остовное дерево имеет по крайней мере одно общее ребро с любым из разрезов графа.

Теорема: В связном неорграфе любой цикл имеет любым разрезом четное число общих ребер.

Множество {K₁,…,K_n-c} называется фундаментальным множество коциклов. Мощность этого множества равна корангу υ^*(G)=n-c. Фундаментальное множество коциклов можно задать матрицей K=(b_ij), где .

18.Минимизация днф: метод Квайна

Рассмотрим метод Квайна для нахождения МДНФ:

1. операция полного склеивания

2. операция неполного склеивания

3. операция элементарного поглощения

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

В силу принципа двойственности для булевых алгебр все рассуждения можно применить для нахождения МКНФ.

13. Булевы функции, способы их задания. Представления булевых функций формулами.

Функцией алгебры логики (ФАЛ) от n переменных x₁,…,x_n называется любая функция f:{0,1}ⁿ→{0,1}, т.е. функция, которая произвольному набору {δ₁,…,δ_n} нулей и единиц ставит в соответствие значение f(δ₁,…,δ_n) из {0,1}.

ФАЛ называются также булевыми функциями, двоичными функциями или переключательными функциями.

Булева функция f(x₁,…,x_n) полностью задается своей таблицей истинности. В каждой строке таблицы задается сначала набор значений переменных (δ₁,…,δ_n), а затем значение функции на этом наборе.

Если булева функция f и формула φ имеют одну и ту же таблицу истинности, то говорят, что формула φ представляет функцию f.

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

Поскольку всего имеется 2ⁿ наборов нулей единиц, то существует ровно булевых функций от n переменных.

Функция f называется суперпозицией функций g(y₁,..,y_n) и h₁(x₁,…,x_n),…,h_m(x₁,…,x_n), если f(x₁,…,x_n)=g(h₁(x₁,…,x_n),…,h_m(x₁,…,x_n)).

Булева функция, принимающая значения 1 (соответственно 0) на всех наборах нулей и единиц, называется константой 1 (константой 0).

Опишем булеву алгебру β_n функцией алгебры логики от n переменных. В качестве носителя рассмотрим множество . Отношение ≤ на множестве B_n определим по следующему правилу: для любого набора значений X=(δ₁,…,δ_n). Пересечением называется такая функция h , что h(X)=min{f(X),g(X)} на любом наборе X=(δ₁,…,δ_n). Объединением называется такая функция h, чтоh=max{f(X),g(X)} на любом наборе X. Дополнение функции f определяется следующим образом: . Система образует булеву алгебру функций от n переменных (алгебру булевых функций).