Белорусский государственный университет информатики и радиоэлектроники

проектирования дискретных устройств . – М.: Физматлит, 2007. – 589 c.

элементов).
2М – мощность булеана множества М.
Мощность бесконечного множества выражается через

чисел;
Z  { … , – 2, – 1, 0, 1, 2, … } – множество целых чисел
R – множество действительных чисел

множество натуральных степеней двоек.
Индуктивный способ: бесконечное множество М  {1, 2, 4, 8, 16, …} задается следующим

Пересечением множеств А и В:
А  В  {x  x  A и x  В}.

Разность множеств А

,  и  составляют булеву алгебру множеств.

=АВ;

константами ( и U):
А    А; А U  А;
А  U  U; А   ;
А А  U; АА  .
 
Закон двойного дополнения:

 А.
Принцип двойственности.

А  В С  (А  В) (А  С):

По закону дистрибутивности пересечения:
(А  В) (А  С) = АА  ВА 

{(a, b) / a  A, b  В}
Если А = {a, b, c} и B = {l, m}, то
А  В = {(a, l), (b, l), (c, l),

b – а и b находятся в отношении R.

Пример:

a R

(1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6)}.
Элемент а – проекция

R на А.

Область значений отношения R  А  В – сечение множества R

(a1, b2), (a1, b3), (a1, b5), (a2, b2), (a2, b4), (a3, b3)}.
Матричное представление Графическое представление

 R}.



M(R) =

А, В, С и R  А  В и S  В  С.
Это такое отношение

а  А.
С ним связана функция f : A  B.
Используется запись f(x) = y для

это множество совпадает с А, то f является всюду определенной.

Сюръекция

то a  b;
симметричность: если a R b, то b R a;
антисимметричность: если a R b и b R a, то a = b;
 транзитивность: если

транзитивно (равносильность формул, подобие геометрических фигур и т. п.). Классы эквивалентности.
Отношение

множество ребер – пар (vi, vj) элементов из V, т. е. vi  V,

Ориентированное ребро (дуга) a4 = (v3, v2) имеет начало v3 и конец v2

они инцидентны одному и тому же ребру.
Окрестность N(v) вершины

Е  .
Неориентированный граф полный, если любые две его вершины смежны.

Н = (W, F) – остовный подграф, если W = V.
Н = (W, F) – подграф, порожденный

цикл.
Граф связный, если любые две его вершины связаны цепью.
Компонента

могут быть связаны любым количеством ребер (допускает кратные ребра).

Взвешенный граф

их множествами вершин имеется взаимно однозначное соответствие, сохраняющее отношение смежности.

она не меняет свое значение при преобразовании Т.
а называется

полным и строгим.
Разобьем множество V вершин графа G на подмножества

граф, число ребер которого на единицу меньше числа вершин.
Дерево –

связного графа G = (V, E).
Добавление одного ребра из Е к Т приводит

циклов Матрица фундаментальных

где N(S)  .

Если

v3

v1

S – независимое множество некоторого графа G, то всякое S  S

v3

v1

вершин
графа G = (V, Е).
G1, G2, … , Gn – последовательность
порожденных подграфов: Gi = (Vi, Еi),
где Vi = {v1, v2, … , vi} (i = 1, 2, … , n).
S i = {S1i, S2i, … ,

в графе с п вершинами?

– множество В  V такое, что каждое ребро из Е инцидентно

на непересекающиеся подмножества V1, V2, … , Vk, что никакие две вершины из любого

множество еще не раскрашенных вершин;
В1, В2, … , Вk – совокупность подмножеств множества вершин

Цвет Вершины

(1736 г.)





Эйлеров цикл содержит все ребра графа.
Эйлерова

имеющий эйлеров цикл.
Алгоритм Флёри:
1. Идем из некоторой вершины

если он проходит каждую вершину графа ровно один раз.
Гамильтонова цепь

взвешены действительными положительными числами. Вес ребра e = vivj будем считать его

можно так нарисовать на этой поверхности, что никакие два ребра

Т е о р е м а П о н т р я г и н а – К у р а т о в с к о г о. Необходимым и достаточным условием непланарности графа является любое

и его двойственный граф







Раскраска граней плоского графа, при которой

подсчета – сколько конфигураций определенного вида?

Перечислительные задачи – получение всех

п предметов по т ящикам)
U(m, n) = тп.

Число перестановок
Р(n) = п · (п – 1) · … · 2 · 1 = п!.

Число размещений без повторений

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

Трудоемкость алгоритма оценивается функцией f(n), где п – натуральное число,

максимальным размером задачи, решаемой за единицу времени

за заданное время, с быстродействием вычислительной машины

обход дерева поиска.

Вершины соответствуют ситуациям, возникающим в процессе поиска, ребра

Требуется выделить

строки с максимальным числом единиц, включение ее в решение и

столбец k имеет единицы везде, где имеет единицы столбец l,

= (х1, х2, ... , хn) – n‑компонентный булев вектор.

п – длина вектора,

Более компактное задание:

Булевы векторы а = (а1, а2, … , ап) и b = (b1, b2, … , bп) находятся в отношении 

которого соответствуют наборам значений аргументов.
Функция









задается вектором (0 1 1 1 0 1 0 1).

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

число булевых функций от п переменных – это число всех

функции – функции от одной и двух переменных.
Булевы функции

алгебру логики.

аргументов может быть представлена формулой алгебры логики.
Формулу, содержащую более

f(x1, x2, x3) = 










А

и .
Основные законы булевой алгебры:

Коммутативность:
х  у  у  х; х у  у х.
 
Ассоциативность:
х  (у  z)  (x  y)  z; x (y z)  (x y) z.

Дистрибутивность:
x (y  z)  x y  x z; x  y z  (x  y) (x  z).
 
Идемпотентность:
x  x  x; x x  x.

;

можно выразить через булевы операции:
х  у = xy x y;
х ~ у =xy  x y;
х  у =x  y.

Преобразование формулы алгебры логики в булеву

U и .
Операциям  ,  и  соответствуют 

где а =  

f(x1, x2, …, xn) при любом т (1  m  n)

наборы (1, 2, … , n), на которых функция принимает значение 0, и для

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

– полная система.
a  а  1;


a  b  аb  b  а  1  1 =

х2  … хп

+

отличаются друг от друга значением только одной компоненты.
Пример: (1 0 0 1) и

одной элементарной конъюнкцией, есть интервал.
Пример: х1х3 х4 представляется троичным вектором

кодом Грея.
Длина кода п для кодирования N объектов должна быть

отношением симметрии в карте Карно.









Каждая ось имеет свою зону

элементов и обязательных интервалов.

(0 1 1 0 1 1)} – интервал булева пространства.

Интервал – характеристическое множество элементарной

Векторы и и v ортогональны по i-й компоненте, если и

Векторы и и v являются соседними, если по некоторой i-й

булевой матрице W, если каждая из строк матрицы W поглощается

строк:


Поглощение:


Обобщенное склеивание смежных строк:



Разложение строки по i-й компоненте.

если не существует троичного вектора, ортогонального каждой строке матрицы U.

со значением «–», представляет множество 2k булевых векторов. Любой из

Т удаляются столбцы, содержащие только «–».
Правило 2. Из матрицы Т

нельзя удалить ни одной элементарной конъюнкции и ни одного литерала

и D находятся в отношении формальной импликации, т. е. k  D. Функция

хk = D хk.

Литерал х в выражении хk  D является избыточным, если

ДНФ имеет минимум литералов.
Функция g имплицирует функцию f, т. е. g  f,

виде совершенной ДНФ.

Процесс минимизации состоит из двух этапов:
1) нахождение сокращенной

А = М1 и совокупность подмножеств В1, В2, … , Вт множества А в виде матриц

матрице выбрать минимальное количество строк так, чтобы каждый столбец имел

mi достаточно найти в М1 все соседние с ним элементы,

содержится ли интервал U во множестве М1, достаточно для матрицы,

0
0 1 1 1 0
1 1 0 1 0*
1 1 0 0 1
1 0 1 0 1
1 0 1 1 0
1 1 0 1 1
1 1 1 1 0
1 1 1 0 1

1 0 – 0 – – 1 1 0
0 1 1 1 0*
1 1 0 1 0*
1 1 0 0 1
1 0 1 0 1
1 0 1 1 0*
1 1 0 1 1
1 1 1 1 0*
1 1 1 0 1

1 0 – 0 – – 1 1 0 1 –

––––––– –––––––
1 1 0 0 0* – 1 0 – 0 – – 1 1 0 1

0 0 1 0 1 0 0 0 0 0 1 1
0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1
0 0 1 1 – 0 – 0 0

1 2 3 4
0 0 1 0 1 0 0 0 0* 0 0 –

преобразовать х1 х2 х3 х5  х2 х3 х4 х5 х1 в СДНФ, то получим 18 конъюнкций.
Применение обобщенного склеивания:

ядра и антиядра. Задача поиска ядра сводится к нахождению избыточных

ядра и антиядра. Для каждой строки строим минор, образованный столбцами,

получения окончательного решения к ядру

x1x2x3 x1x2x4

номеров строк матрицы U такая, что для каждого элемента множества

U2 построить матрицу U, приписав столбцы матрицы U2 к столбцам

А  В, то В удаляется из Р(U).
2. Если номер i присутствует

– области, где соответственно функция имеет значения 1, 0 и

реализует функцию f (g   f), если M1f  M1g и M0f  M0g.

Постановка

множества всех максимальных интервалов для fmax;
2) покрытие ими элементов

метода потребует формирования большого количества бесполезных интервалов.
Интервально поглощаемое множество –

интервально поглощаемых множеств.
Используется лексикографический перебор.
Для проверки, является ли M1i

интервально поглощаемых множеств.

элементов множества М1 максимальными интервально поглощаемыми множествами.

Максимальные множества: {1,

слабо определенная булева функция с помощью характеристических множеств М0 и

М1 =

в матрице Сi существует строка без единиц, то соответствующий ей

М1 =

М1 =