Интервал ранга R содержит 2^N-R векторов.

N – количество рассматриваемых векторов.

Интервал – носитель элементарной конъюнкции.

Теорема

Носитель дизъюнкции двух функций равен объединению носителей этих функций.

Доказательство.

_{f V g}  f() V g() = 1  f() = 1 ИЛИ g() = 1  _f ИЛИ  _g

ч.т.д.

Носитель ДНФ является объединением интервалов.

Допустимым интервалом для данной функции называется интервал, который целиком содержится в носителе этой функции.

N_f = I₁ V I₂ V … V I_k

Интервал для данной функции является максимальным, если он не содержится целиком ни в каком другом допустимом интервале.

Элементарная конъюнкция, носителем которой является допустимый интервал, называется импликантой.

ЭК, N – максимальный интервал – простая импликанта.

Представление носителя в виде объединения максимальных интервалов будем называть покрытием носителя максимальными интервалами.

Дизъюнкция всех возможных простых импликант называется сокращенной ДНФ функции.

Покрытие носителя интервалами будем называть неприводимым, если ни один нельзя отбросить из правой части равенства, не нарушив это равенство.

ДНФ, которая соответствует неприводимому покрытию, называется тупиковой ДНФ.

Утверждение.

Минимальная ДНФ содержится среди тупиковых ДНФ.

Определение

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

Элементарная конъюнкция, соответствующая ядровому интервалу – ядровая импликанта.

Объединение всех ядровых интервалов – ядро функции.

Дизъюнкция всех ядровых импликант - ядровая ДНФ.

Ядро функции обязательно входит в любое неприводимое покрытие.

Алгоритм получения минимальной ДНФ.

1. Выделяем носитель функции.

2. Выделяем все возможные интервалы.

3. Выписываем все простые импликанты.

4. Выделяем ядровый интервал.

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

6. С реди тупиковых ДНФ выбираем минимальную.

X1	X2	X3	F
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Выделение всех возможных интервалов.

1. Для булева куба размерности 3 интервалом ранга 1 могут быть 4 вершины, лежащие в одной грани.

2. Ранга 2 – любые 2 вершины, соединенные ребром.

3. Ранга 3 – любая отдельная вершина.

1. Нет _

2. I₁ = { 001 011} <-> П₁ = x₁x₃ - ядровый

I₂ = { 011 111} <-> П₂ = x₂x₃

Если координата вектора меняет значения, то переменная не входит

I₃ = { 111 110} <-> П₃ = x₁x₂

_

I₄ = { 110 100} <-> П₄ = x₁x₃

D_сокр. = П₁ V П₂ V П₃ V П₄

N_f = I₁ U I₄ U I₂ (U – объединение)

Получили неприводимое покрытие, добавив к ядру недостающие интервалы так, чтобы все единичные вершины были задействованы.

D₁= П₁ V П₄ V П₂

N_f = I₁ U I₄ U I₃

D₂= П₁ V П₄ V П₃

Сосчитаем ранги тупиковых ДНФ

R₁ = 6

R₂ = 6

D_min = D₁ = D₂

Метод карт Карно для нахождения минимальной ДНФ

n = 4

Карта Карно – плоскостная интерпретация 4-мерного булева куба.

	00	01	11	10
00		0001
01	0100	0101	0111		0110
11		1101
10

Считаем, что левый край склеен с правым, а верхний – с нижним.

Если таблицу Карно свернуть таким образом, то получится тор (torus - геометрическая фигура, напоминающая бублик).

Правила поиска интервалов.

1. Интервалом ранга 1 могут быть 2 соседних строки (2 соседних столбца)

2. Интервалом ранга 2 может быть вся строка, весь столбец или квадрат 2х2.

3. Интервалом ранга 3 – любые 2 соседние по горизонтали и вертикали клетки.

4. Одна отдельно взятая вершина будет интервалом ранга 4.

Алгоритм – тот же самый.

Лекция 6

Метод Квайна – Мак-Клоски для нахождения минимальной ДНФ

Этот метод удобен для нахождения минимальной ДНФ функции от любого числа переменных.

Определение. Элементарная конъюнкция K₁ покрывает ЭК K₂, если каждая переменная, входящая в K₁, входит и в K₂.

__ __ __

X₁X₃ – покрытие X₁X₂X₃X₄

N_k1  N_k2

K₂ = K₁K

K – конъюнкция из других переменных.

__ _ _ __ _ _

X₁X₃ V X₁X₂X₃X₄ = X₁X₃ (1 V X₂X₄) = X₁X₃ – поглощение

Склеивание двух ЭК

_

Kx V Kx = K

Идея метода Квайна (алгоритм)

1. Выписываются все элементарные конъюнкции из СДНФ функции.

2. Проводятся все возможные склеивания между этими ЭК. Полученные новые ЭК сохраняются вместе со старыми.

3. Между ними снова проводим все возможные склеивания до тех пор, пока это возможно. В результате среди ЭК появятся все простые импликанты функции.

4. Проводим поглощение между всеми получившимися ЭК, то есть оставляем только те ЭК, которые не покрываются никакими другими.

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

Формализация Мак-Клоски.

Каждой ЭК ставим в соответствие булев вектор. (x с отрицанием – 0, без отрицания – 1).

1. Выписываем все ЭК из СДНФ функции в формализованном виде в столбец, располагая их в порядке возрастания числа единиц в векторах и разбивая на классы по числу единиц.

2. Между ЭК проводим все возможные склеивания. Результат записываем в новый столбец справа, а ЭК, участвовавшие в склеивании, помечаем звездочкой. Склеивать можно только ЭК из соседних классов.

3. Для полученного столбца еще раз применяем шаг 2.

4. Все ЭК, которые остались непомеченными звездочкой, являются простыми импликантами.

5. Строим таблицу Квайна по следующему правилу:

А) Каждой строке ставим в соответствие простую импликанту П_i.

Б) Каждому столбцу – ЭК из СДНФ K_j.

1. Если П_i.покрывает K_j , то в соответствующей клетке ставим знак +.

2. Ищем ядровые импликанты (столбец, содержащий только 1 знак +). Та строка и есть ядровая (строка, в какой этот крестик содержится).

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

4. Ядро дополняем до тупиковой ДНФ (Ищем минимальную комбинацию строк так, чтобы в каждый столбец входил хотя бы один крестик). Дизъюнкция этих строк даст тупиковые ДНФ.

5. Среди всех тупиковых ДНФ выбираем минимальную.

Лекция 7

Функционально полные системы функций

Определение. Система функций {f₁…f_n} называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из этой системы (т.е. можно представить формулой, куда входят только функции из этой системы).

F_

{V, &, NOT или отрицание - --}

Теорема 1.

Если система полна, и любая ее функция представима в виде суперпозиции функций из системы то и система также полна.

Доказательство

_{ф₁…ф_k}

_iЕ_условие.

fF = F₂ – ч.т.д.

Мы заменили все функции суперпозицией из 



Теорема 2.

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

Доказательство следует из принципа двойственности.

Основные типы функционально полных систем.

{&, V, NOT}

{&, NOT}

____

_ _

X V Y = (XY)

{/} – полна.

___

X/Y = (XY)

X/X = NOT(XX) = NOT(X)

 = {}

Система Жегалкина {+,&,1}.

NOT (X) = x+1

X V Y = xy+x+y

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

Одночленом будем называть любое выражение вида

А * X₁X₂X₃…X_n

A = {0 или 1} x₁x₃ – одночлен.

Многочленом Жегалкина называется сумма по модулю 2 различных одночленов.

А1X1+А2X2+А3X3+A4X1X2 + A5X1X3+A6X2X3+A7X1X2X3 – общий вид многочлена Жегалкина для трех переменных. Чтобы выписать общий вид многочлена Жегалкина для нужного числа переменных нужно перебрать все возможные конъюнкции переменных и сложить их по модулю 2 друг с другом, а также с переменными, входящими в функцию. Перед каждой конъюнкцией нужно расставить буквенные коэффициенты.

Теорема

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

Доказательство на лекции 8.

Поиск многочлена Жегалкина (МЖ) для любой выбранной булевой функции производится методом неопределенных коэффициентов. Для этого нужно выписать общий вид МЖ для нужного числа переменных, затем, подставив искомые значения переменных в МЖ, приравнять его к функции на нужном векторе. Таким образом получается система уравнений с неизвестными числами А. Решив ее, мы получим искомый МЖ.

Лекция 8

Продолжение темы «Многочлены Жегалкина»

Теорема.

Любая булева функция представима в виде многочлена Жегалкина (МЖ).

Доказательство

1. Существование

F = ДНФ = F{&,V, NOT}

X V Y = XY+X+Y

NOT(X) = X+1

Из этого следует, что функция представима в виде МЖ.

1. Единственность

Сосчитаем МЖ

ЭК без отрицания 2ⁿ – 1 + 1

Всего разных многочленов Жегалкина 2^N – 1, где N = 2ⁿ

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

Отсюда следует, что любой булевой функции соответствует единственный многочлен Жегалкина. Теорема доказана полностью.

Классы функций. Замкнутые и незамкнутые классы. Получение констант и элементарных булевых функций из заданной системы функций

Определение. Функция называется линейной, если ее многочлен Жегалкина не содержит ни одной конъюнкции переменных.

Замкнутые классы функций.

Определение.

Пусть дан класс функций B (т.е. конечное или бесконечное множество функций),объединенных по общему признаку. Замыканием этого класса (обозначение – [B]) будем называть множество всех суперпозиций функций из класса B.