Размещено на http://www.allbest.ru/

Московский государственный институт радиотехники, электроники и автоматики (технический университет)

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

Москва - 2000

Лекция 1. Множество. Алгебра множеств

Введем обозначения.

R - множество действительных чисел.

X e R - элемент X принадлежит множеству R.

Равные множества - множества, состоящие из одинаковых элементов.

A = B - множество А равно множеству B.

0 - пустое множество.

A<= C - Множество А является подмножеством множества С.

Если А не равно С и А <= C, то А < С. (строго).

Если A <= C и C <= А, то А = С.

Пустое множество 0 является подмножеством любого множества.

Существуют конечные и бесконечные множества. Пусть n - число элементов данного множества А. Это число называется мощностью данного множества.

У множества рациональных чисел мощность является счетной (т.е. все элементы можно пронумеровать).

У множества иррациональных чисел мощность - континиум. Обозначается (С).

Основное правило комбинаторики (показано на примере)

Пусть имеется палочка, разделенная на 3 части. Первую ее часть можно раскрасить n способами, вторую - m, третью - k. Всего способов раскраски палочки - n*m*k.

Аналогично с множествами

U = {a1,a2… an-1, an}

Пусть U = {a1, a2, a3}

Выпишем множество всех подмножеств множества U.

P(U) = {0, a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3}.

Мощность множества U равна 3, а мощность P(U) равна 8.

Методом математической индукции доказывается, что при произвольной мощности n множества U, мощность множества P(U) равна 2n.

Операции над множествами

Объединение множеств (A U B). Элемент, принадлежащий полученному множеству, принадлежит множеству А ИЛИ множеству В.

Пересечение множеств (A n B). Элемент, принадлежащий полученному множеству, принадлежит множеству А И множеству В.

Дополнение множества А. (С = А ) - не А. Все элементы, принадлежащие универсальному множеству, не принадлежат множеству А.

Свойства операций над множествами.

A U B = B U A - коммутативность

A n B = B n A

(A U B) U C = A U (B U C), A n (B n C) = (A n B) n C - ассоциативность.

(A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) - дистрибутивность.

Поглощение A U A = A, A n A = A.

Существование универсальных границ.

А U 0 = A

A n 0 = 0

A u U = U

A n U = A

6. Двойное дополнение

A = A

7. A U A = U

A n A = 0

8. Законы двойственности или закон Де - Моргана

(AUB) = A n B

(AnB) = A U B

Лекция 2. Теория булевых функций. Булева алгебра

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

Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры). Названия операций пока не введены.

X & Y = Y&X, X V Y = Y V X - коммутативность.

(X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) - ассоциативность.

(X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) - дистрибутивность.

Поглощение - X & X = X, X V X = X.

Свойства констант

X & 0 = 0

X & I = X, где I - аналог универсального множества.

Инвальтивность (X*)* = X

Дополнимость X V X* = I, X & X* = 0.

Законы двойственности - (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.

U = {a1, a2… an)

[U] = N

[P(U)] = 2n

Легко показать, что свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.

Oбъединение эквивалентно V, пересечение - &, дополнение - *, пустое множество - 0, а универсальное - I.

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

2.1 Булева алгебра характеристических векторов

Пусть A <= U, A <- P(U) ??- характеристический вектор этого подмножества.

?A = {??, ?2 ..?n)

n = [P(U)]

?i = 1, если ai <- A (принадлежит).

?i = 0, если ai не принадлежит A.

U = {1 2 3 4 5 6 7 8 9}

A = {2 4 6 8}

B = {1 2 7}

?A = {0 1 0 1 0 1 0 1 0}

?B = {1 1 0 0 0 0 1 0 0}

или

?A = 010101010 - скобки не нужны

?A= 110000100

Характеристические векторы размерностью n называются булевыми векторами.

Они располагаются в вершинах n - мерного булева куба.

Номером булевого вектора является число в двоичном представлении, которым он является

1101 - номер.

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

Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.

Булев куб размерности 1

Булев куб размерности 3

Размещено на http://www.allbest.ru/

0 - нулевой вектор.

I - вектор из одних единиц.

XY	X&Y	X V Y
00	0	0
01	0	1
10	0	1
11	1	1

Отрицание

X = 0 Y = 0

Х = 1 Y= 1

Для размерности n операции над векторами производятся покоординатно.

Логическая сумма двух векторов - вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.

Утверждение

Между множеством всех подмножеств множества U и булевым кубом Bn, где n= =[U] можно установить взаимное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения - операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному - единичный.

Следствие

Множество всех характеристических векторов является булевой алгеброй.

2.2 Булева алгебра высказываний (алгебра логики)

Высказыванием об элементах множества U называется любое утверждение об элементах множества U, которое для каждого элемента либо истинно, либо ложно.

U = {1 2 3 4 5 6 7 8 9}

A = «число четное»

B = «число, меньшее пяти»

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

SA = {2 4 6 8}

SB = {1 2 3 4}

Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным.

Высказывания, для которых множества истинности совпадают, называются тождественными или равносильными.

Равносильные высказывания объединим в один класс Р.В. и не будем их разделять, т.к. все они имеют одно и то же множество истинности.

Операции над высказываниями

Дизъюнкция высказываний (V, ИЛИ, OR)

Дизъюнкция высказываний - высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.

Конъюнкция высказываний (&, И, AND).

Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.

Отрицание высказываний (- над буквой, НЕ, NOT).

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

A B	A & B	A V B	Not A
Л Л	Л	Л	И
Л И	Л	И	И
И Л	Л	И	Л
И И	И	И	Л

Л - ложно.

И - истинно.

Утверждение (основа всей алгебры логики)

Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения.

Следствие. Множество классов эквивалентных высказываний является булевой алгеброй.

Теорема

Существуют 3 булевых алгебры:

P(U)

Bn

Множество классов эквивалентных высказываний.

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

Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел).

Лекция 3. Определение и способ задания булевых функций

Булевой функцией от n аргументов называется однозначное отображение n - мерного булева куба на одномерный булев куб.

Способы задания функций

Табличный

X1 X2 X3 … XN	F(X)
0 0 0 0 0 0 0 0 0	??
…	??
1 1 1 1 1 1 1 1 1	?n

?????значение функции от данных аргументов.

Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.

Векторный

F = (??????n)

3. Геометрический

Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1.

Носителем данной функции - совокупность всех единичных векторов этой функции (Nf - носитель функции f)

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

Размещено на http://www.allbest.ru/

Nf = {001, 011, 100, 110} = [1,3,4,6] [] - указаны номера векторов.

В виде формулы.

Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают.

Будем говорить, что f зависит от переменной xi существенно, если существуют такие два набора значений, отличающихся только значением переменной xi, на которых значения функций различно.

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

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

Строим таблицу функций при n = 1.

X	0	X	X	1
0	0	0	1	1
1	0	1	0	1

Таблица всех элементарных булевых функций, применяемых в записи формул

X	Y	0	&	_____ Y?X	X	___ X?Y	Y	+	V	?	~	_ Y	X ?Y	_X	Y?X	/	1
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

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

Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание.

Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры.

Суперпозиции булевых функций

Ф = {ф1…фk}

F называется элементарной суперпозицией функции из множества Ф, если она получена одним из следующих способов.

Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента).

В одну из функций системы вместо любого аргумента ставится значение любой функции из этой системы.

Ф1 = {Y…xn}

Фi = (x1 … фj(x1…xn) … xn)

Ф(1) - множество всех элементарных суперпозиций из системы Ф.

Ф(k+1) - множество всех элементарных суперпозиций из систему Фk.

Функция g называется суперпозицией функций из системы, если ????? g??? Фn

Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции.

Конкретное выражение суперпозиции будем называть формулой над системой Ф.

G = Fф

Суперпозиция элементарных булевых функций - формула.

Для удобства записи договоримся, что отрицание - самая сильная операция. Следующая - конъюнкция, а остальные - равносильны.

X+Y = XY V XY

X ~ Y = XY V XY

X ?? Y = X V Y

X ?? Y = X Y

Лекция 4. Дизъюнктивные нормальные формы (ДНФ)

Конъюнктивные нормальные формы (КНФ)

Введем обозначения

Xа = X,

если а = 1 и X, если а = 0

Элементарной конъюнкцией (ЭК) называется выражение вида

X1a1 X2a2…Xnan

ЭК называется правильной, если все входящие в неё переменные различны.

Правильная ЭК называется полной относительно данного набора переменных, если в неё входят все эти переменные.

Для элементарных дизъюнкций (ЭД) - аналогичный набор определений.

ЭД - выражение вида

X1a1 V X2a2 V…V Xnan

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

X1 V X1X2 V X1X2X3 - ДНФ.

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

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

СКНФ - совершенная КНФ. У нее все ЭД полны.

Теорема.

Любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде СДНФ по формуле:

F(x1… xn) = V(X1a1 X2a2…Xnan)

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

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

F = G

N(f) ?? N(G) - носители функции.

????????(F) ???F(??…?n) = 1

G(??) = G(??…?n) = (????…?n?n) V (…),

где пустые скобки - оставшееся выражение.

Подставив координаты, получим:

1*1V(…) = 1 ) ??? ????(G) ??N(F) = N(G)

2. ???? N(G)

G(???..?n) = 1 - тогда, когда хотя бы одна

?????????? …?n?n = 1 ? ??? = ?? …?n = ?n ?? ?= ? ?? N(G) = N(F)

Первая часть доказана.

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

Посчитаем, сколько полных ЭК может быть

Всего - 2n = N (по перестановке комбинаций)

Число СДНФ - 2N-1 - число различных формул СДНФ.

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

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

Замечание. Единственность доказана при фиксированном числе аргументов n. Так как, вводя фиктивные переменные, мы будем менять вид формулы.

Следствие. Любая булева функция представима формулой, в которую входит только конъюнкция, дизъюнкция и отрицание.

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

F*(x1…xn) - двойственная функция,

F*(x1…xn) = F(x1…xn)

Например

(XY)* = XY = X V Y

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

Теорема. Принцип двойственности.

Если F (x1…xn) является суперпозицией функций fi (i = 1...k), то двойственная к ней функция является такой же по структуре суперпозицией, но от двойственных функций.

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

F*(x1..xn) = F(x1…xn) = f(f1…fk) = f*(f1…fk)

Следствие

f(x1..xn) = K1 V K2 V… V Kn - СДНФ

f*(x1..xn) = D1 D2 … Dn - СКНФ

Используя принцип двойственности, можно доказать следующую теорему.

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

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

Задача минимизации ДНФ.

Определения:

Рангом правильной ЭК называется число разных переменных, входящих в нее.

Рангом ДНФ называется сумма рангов всех ЭК, входящих в ДНФ.

Минимальной ДНФ или Dmin для данной функции называется ДНФ, которая равна этой функции и имеет наименьший ранг.

Задача минимизации ДНФ для данной функции состоит в нахлждении минимальной ДНФ.

Число ДНФ при фиксированном n - конечное (n - число переменных)

Тривиальный алгоритм минимизации ДНФ состоит в следующем:

Выписываем все возможные ДНФ от данного числа n в порядке возрастания их рангов.

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

Алгоритм представления функции в виде СДНФ.

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

Для каждого вектора из носителя выписываем конъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем с отрицанием, если единице - без отрицания). Это и будут все полные ЭК.

Выписываем дизъюнкцию всех этих ЭК.

Алгоритм представления функции в виде СКНФ.

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

2. Для каждого вектора из носителя выписываем дизъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем без отрицания, . если единице - с отрицанием). Это и будут все полные ЭД.

3. Выписываем конъюнкцию всех этих ЭД.

Лекция 5. Продолжение темы «ДНФ»

Носитель элементарной конъюнкции ранга R будем называть интервалом ранга R.

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

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

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

Теорема

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

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

???????f V g ? f(??) V g(??) = 1 ?? f(??) = 1 ИЛИ g(??) = 1 ?? ??????f ИЛИ ????? g

ч.т.д.

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

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

Nf = I1 V I2 V … V Ik

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

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

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

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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нет _

I1 = { 001 011} <-> П1 = x1x3 - ядровый

I2 = { 011 111} <-> П2 = x2x3

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

I3 = { 111 110} <-> П3 = x1x2

I4 = { 110 100} <-> П4 = x1x3

Dсокр. = П1 V П2 V П3 V П4

Nf = I1 U I4 U I2 (U - объединение)

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

D1= П1 V П4 V П2

Nf = I1 U I4 U I3

D2= П1 V П4 V П3

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

R1 = 6

R2 = 6

Dmin = D1 = D2

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

n = 4

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

00		0001
01	0100	0101	0111	0110
11		1101
10

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

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

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

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

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

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

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

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

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

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

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

X1X3 - покрытие X1X2X3X4

Nk1 ?? Nk2

K2 = K1K

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

X1X3 V X1X2X3X4 = X1X3 (1 V X2X4) = X1X3 - поглощение

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

Kx V Kx = K

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?????F?

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

Теорема 1.

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

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

????{ф1…фk}

??i???Е?????условие.

?f???F?? = F?2 - ч.т.д.

Мы заменили все функции суперпозицией из ????

Теорема 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

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

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

А * X1X2X3…Xn

A = {0 или 1} x1x3 - одночлен.

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

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

Теорема

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

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

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

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

Теорема.

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

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

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

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

X V Y = XY+X+Y

NOT(X) = X+1

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

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

Сосчитаем МЖ

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

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

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

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

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

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

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

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

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

Класс B будем называть замкнутым, если его замыкание совпадает с ним самим.

B = [B]

Теорема 1

Класс всех линейных функций замкнут.

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

Пусть L - класс линейных функций (так и будем обозначать в дальнейшем).

L = {a0+a1x1+a2x2+…+anxn}

Подставим вместо переменной x в одну из функций функцию y такого же вида.

Получим

L = [L].

Утверждение (теорема 2)

Необходимое условие линейности.

Если функция линейна и не равна некоторой постоянной, то на половине своих наборов она равна 1.

Если в векторе значений функции число 0 и 1 различно, то функция обязательно нелинейна, а если число нулей совпадает с числом единиц, то эта функция может быть линейной, а может быть и нелинейной. В таком случае, чтобы это проверить, нужно выписать для нее многочлен Жегалкина.

Функция называется самодвойственной, если двойственная к ней функция является самой этой функцией. F* = F.

S - класс всех самодвойственных функций.

Класс S является функционально замкнутым.

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

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

Функция называется монотонной, если из условия ??????следует, что f(??)???f(??).

Теорема.

Класс M монотонных функций замкнут.

Свойство.

У монотонных функций сокращенная ДНФ не содержит отрицаний переменных, то есть все простые импликанты не содержат отрицаний.

Другие замкнутые классы

T0 - константа 0 (класс функций, обращающихся на нулевом векторе в 0).

Т1 - константа 1? (класс функций, обращающихся на единичном векторе в 1)

Теорема

Классы Т0 и Т1 функционально замкнуты.

8.1 Лемма о несамодвойственной функции

Если функция несамодвойственна, то путем подстановки вместо аргументов переменной x или not(x) можно получить константу.

011 - нарушена самодвойственность

f(not(x),x,x) = const = 1 при любом x.

001 - нарушена самодвойственность

Если 0, то х с отрицанием, если 1, то без отрицания.

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

F ?? S ? ?? : F*(??) ?? F(??) ?? F*(??) = F(??)? F(??) = F(??) ?? F(??) = F(?)

??(x) = {x1??, x2?2, … xn?n}

??(0) = {0??, 0?2, … 0?n}

Путем подстановки получаем, что ??(x) = const.

8.2 Лемма о немонотонной функции

Путем подстановки вместо аргументов-констант и переменной х можно получить not(x).

000 ?????

F(000) = 1 F(001) = 0

F(00X) = NOT(X)

F(100) = 1

F(110) = 0

100 < 110

F(1,x,0) = NOT(X)

8.3 Лемма о нелинейной функции

Если F(X) нелинейна, то из нее путем подстановки вместо аргументов-констант переменных (x, y, not x, not y) иожно получить: конъюнкцию этих переменных, дизъюнкцию этих переменных, отрицание конъюнкции, отрицание дизъюнкции.

F = 1 + x1+x3+x1x3+x1x2x3 = x1x3(1+x2) +x3+x1+1

F(x1,0,x3) = x1x3+x3+1

F(x0y) = (xy)

Лекция 9. Доказательство леммы

F(x1…xn) = x1x2 (f1(x1…xn)) + x1f2(x1…xn) + x2f3(x1…xn) + f4(x1…xn)

Вместо x1…xn ставим константы ?1…?n, такие, что

f1(?1…?n) = 1

A = B = 0

F(x1x2…?3…?n) = x1x2 + C = {x1x2, если с = 0 и NOT(x1x2, если с = 1)

Аналогично получаем дизъюнкцию и ее отрицание.

Теорема Поста.

Система функций полна тогда и только тогда, когда она не находится ни в одном из пяти важнейших замкнутых классов, а именно S, M, L, T0, T1.

Необходимо.

Дана полная система функций. Отсюда следует, что она не принадлежит никакому замкнутому классу (см. выше).

Доказательство следует из того факта, что по определению и по тому, что мы доказали, что все важнейшие классы замкнуты. Если предположить, что система целиком входит в один из замкнутых классов, то

[?] = [B] = B

Но ????множество всех булевых функций, а B - не всех.

Получили противоречие.

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

Дано

????{S, M, L, T0, T1}

Каждая функция (f с индексами 1…5) не принадлежит каждому соответствующему ей важнейшему замкнутому классу.

Получение констант.

F1(00…0) = 1

F(111) = 1

F(111) = 0

F(xxxx) = 1

F2(111) = 0

Получение отрицаний

Из F4 по лемме 2 мы можем получить отрицание.

Используя F5 по лемме 3 получаем xy, x V y, not(xy), not(x V y)

Лекция 10. Функциональные элементы. Схемы

Функциональный элемент с n упорядоченными входами и одним выходом

При подаче на выходы любой комбинации двоичных сигналов, на выходе также возникает сигнал.

Каждый вход - аргумент функции.

Выход - булева функция от аргументов.

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

Два и более входов можно отождествлять.

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

Полный набор булевых функций, который мы будем использовать для построения логических сетей (схем) в какой-нибудь задаче, мы назовем базисом из функциональных элементов.

Число функциональных переменных считаем сколь угодно большим.

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

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

Пример полного базиса.

- Конъюнктор

Дизъюнктор

- Инвертор

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

Найти минимальную ДНФ.

Для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя.

10.1 Сумматор n-разрядных двоичных чисел

Составить элементы с 2n входами и n+1 выходом, реализующих сложение n-разрядных двоичных чисел вида

X = XnXn-1…X1

Y = YnYn-1…Y1

Z = x+y = Zn+1Zn…Z1

X+Y - сумма чисел.

Для решения такой задачи вводим qi - единица переноса из одного разряда в другой.

Формулы сумматора

Zi = Xi + Yi + Qi - сумма по модулю 2

Qi+1 = XiYi V XiQi V QiYi

Лекция 11. Графы

Графом (G) будем называть тройку объектов (V, X, ??)

V - множество n вершин.

X - конечное множество ребер.

??- функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.

??задана на множестве X.

Если в значении функции инцидентности допускается перестановка вершин, то граф называется неориентированным. В противном случае граф называется ориентированным (Орграф).

Vj - начало ребра

Vk - его конец

??xi) = (Vj, Vk) - ребро инцидентно в вершине Vj и в вершине Vk.

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

Если на ребре xi0

??(x0) = (Vj0, Vj0),

то ребро называется петлей.

Способы задания графов

Аналитический

Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной.

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

В конце выписываются все изолированные вершины.

Геометрический

Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин - кривой.

Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.

С помощью матрицы инцидентности

A(m*n)

m = [V] - число вершин

n = [X}- число ребер

а) Неориентированные графы

Aij = {0, если Vi не инцидентно xj, 1, если Vi инцидентно xj)

б) Орграфы

Aij = {0, если Vi не инцидентно xj, -1, если Vi - начало xj, 1, если Vi - конец xj)

Для петель нужны дополнительные предположения.

Матрица смежности (задается одинаково для всех графов)

B(m*m) m = [V]

Bij равно числу ребер, инцидентных паре вершин (oi, oj)

Если граф не ориентирован, то матрица симметрична.

Граф, в котором нет кратных ребер и петель, называется простым.

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

Дальше все о неориентированных графах.

K1 - полный граф с одной вершиной

K2 - с двумя

K3 - с тремя

K4 - полный граф с четырьмя вершинами

K5 - полный пятивершинник

Граф называется двудольным, если множество вершин разбивается на 2 непересекающихся подмножества, такие, что ребра соединяют вершины из разных подмножеств.

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

Полный двудольный граф.

Маршруты, циклы, связности.

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

Будем говорить, что этот маршрут соединяет первую и последнюю вершину. Если существует маршрут, то последняя вершина называется достижимой из первой вершины.

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

Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью.

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

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

Эти части называются компонентами связности.

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

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

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

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

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

Свойства деревьев.

Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

Лекция 12. Эйлеровы графы

Дан граф. Требуется найти в нем маршрут, проходящий по каждому ребру ровно один раз. Начало и конец - в одной вершине.

Такой маршрут называется Эйлеровым циклом, а граф, в котором он существует, называется Эйлеровым графом.

Степень вершины в графе - это число ребер, инцидентных этой вершине.

Критерий эйлеровости графа.

Для того, чтобы связный граф без петель был Эйлеровым, необходимо и достаточно, чтобы степень его вершины была четным числом.

Планарные графы.

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

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

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

Любой граф можно изобразить в трехмерном пространстве без пересечения ребер.

Для любого графа xi, соединяющего 2 вершины проводим новую плоскость, содержащую эту прямую, а ребро рисуем на плоскости.

Граф будет планарным, если существует его укладка на сфере.

Размещено на http://www.allbest.ru/

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

Следствие. Граф любого выпуклого многогранника планарен.

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

Теорема Эйлера о плоских графах.

Формула Эйлера.

Для плоского графа справедливо соотношение.

M - N + P = 2.

Докажем индукцией по числу граней

P = 1

Если P = 1, то граф - дерево. В нем нет ни одного цикла. У дерева число вершин больше числа ребер на 1.

M = N + 1

N + 1 - N + 1 = 2 - справедливо.

Пусть p = k, и утверждение верно.

Тогда оно верно и при P= k+1

Берем ребро графа, отделяющее бесконечную грань от внутренних и удаляем это ребро из графа. Т.к. оно циклическое, то в новом графе g1 (он также будет связным) число вершин M останется прежним.

N1 = N - 1

P1 = P - 1

M = M

k + 1-1 = k

Для g1 справедливо предположение индукции.

M1 + N1 + P1 = 2

M - N - 1 + K = 2

M - N + K - 1 = 2

M - N + P = 2

Что и требовалось доказать.

Следствие 1.

Для плоского связного простого графа справедливо соотношение

n <= 3*(m-2)

Следствие 2.

Для плоского связного простого графа без треугольных граней справедливо соотношение

n <= 2*(m-2)

Следствие 3.

Граф K5 - непланарен.

Размещено на http://www.allbest.ru/

m > 2 И если бы он был плоским, то для него было бы справедливо следствие1.

N <= 3*(m-2)

10 <= 9 - неверно.

Противоречие. Значит, он не может быть нарисован плоским.

Следствие 4.

Граф K3-3 непланарен.

Нет треугольных граней.

Если бы он был плоским, то для него было бы справедливо следствие 2.

9 <= 2*(6-2)

9 <= 8 - неверно.

Противоречие из предположения, что он не может быть плоским.

Операцией разбиения ребра графа называется следующая процедура:

Ребро удаляется из графа, и в граф добавляется новая вершина, соединенная новыми ребрами с концами данного ребра.

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

Теорема Понтрягина - Куратовского.

Чтобы граф был планарным, необходимо и достаточно, чтобы он не содержал гомеоморфных подграфов.

Лекция 13. Сети. Пути в орграфах. Остовы минимальной длины

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

Размещено на http://www.allbest.ru/

Двуполюсная сеть называется сильно связанной (связной), если через любое ребро проходит простая цепь, соединяющая полюса. В ней нет повторяющихся вершин.

Параллельная сеть - сеть вида

Размещено на http://www.allbest.ru/

Последовательная сеть - сеть вида

Размещено на http://www.allbest.ru/

П (пи) сети - последовательно-параллельные сети

Примеры П-сетей

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Такая сеть называется мостиковой.

Контактными схемами называются сильносвязные двуполюсные сети, каждому ребру которой поставлено в соответствие x или NOT(x).

Размещено на http://www.allbest.ru/

X Not Y

Z Not X

Любой контактной схеме (КС) можно поставить в соответствие булеву функцию (функцию проводимости) по правилу:

Для любой простой цепи, соединяющей полюса, записываем ЭК тех переменных, которыми помечены ребра этой цепи.

Затем берем дизъюнкцию всех ЭК. Получим искомую функцию проводимости.

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

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

Чтобы построить минимальную КС, надо выписать минимальную ДНФ для данной функции, упростить путем вынесения за скобки, нарисовать П-сеть, реализующую КС для функции и постараться найти мостиковые соединения.

Минимальные пути в графах

Путем в графе (в орграфе) называется маршрут, движение по которому любого ребра проходит в соответствии с направлением этого ребра.

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

Орграф, в котором нет ни одного контура, называется бесконтурным.

Первая задача о минимальном пути.

Дан граф. Выделено две вершины. Найти путь из одной вершины в другую, состоящий из наименьшего числа ребер.

Введем обозначения

Г(V) - множество вершин, в которые можно попасть из вершины V, пройдя только по одному ребру в его направлении.

Г-1(V) - множество вершин, из которых можно попасть в вершину V, пройдя только по одному ребру.

Алгоритм.

Исходной вершине A присваиваем метку 0.

Любому Г(А), которые еще не имели меток, присваиваем метку М = 1.

Для любой V, принадлежащей Г(А) находим Г(V) и любой V, принадлежащему Г(V), если она не имела метку, даем метку 2.

И так далее до тех пор, пока конечная вершина не получит метку.

Выбираем путь по Г-1(V).

Может произойти такое, что пути из А в В нет вообще.

Тогда на некотором шаге при обратном ходе нужной вершины нет.

Вторая задача.

Если каждому ребру поставить в соответствие некоторое целое положительное число, называемое его длиной и требуется найти путь из А в В, такой, что i = minimum. (r или l - длина ребра)

Алгоритм будет следующий.

Метка для ребра А ??????

Для Vi ?i = +(бесконечность) - очень большое число, большее суммы всех длин ребер всего графа.

L(Vi, Vj) - длина ребра, идущего из вершины Vi в Vj. Направление важно.

Для любого ребра из графа проверяем выполнение неравенства.

?j - ?i > L(Vi, Vj) *

Если это неравенство выполняется, то меняем метку ?j на новую.

?j = ?i + L(Vi, Vj) и так до тех пор, пока выполняется *.

Если * нигде не выполняется, то та метка, которая будет стоять у вершины В и будет равна длине минимального пути из А в В, а сам путь строится движением назад из В в А.

Г-1(В) Существует такое ребро Vi1, для которого выполнено равенство.

?b - ?i1 = L(Vi1,B)

Затем Г-1(V1) Существует V2, где ??V1) - ??V2) = L(V1, V2) и т.д. пока не вернемся в вершину А.

Путь минимальной длины найден.

Остов графа минимальной длины.

Остов - дерево, содержащее все вершины графа и какие-то из его ребер.

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

Алгоритм

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

Просматриваем ребра, начиная с первого. Если x1 не является петлей, мы его включаем в остов и переходим к следующему ребру. Если оно не является петлей и не образует с уже имеющимися ребрами цикла, мы его включаем в остов. И так до тех пор, пока не рассмотрим все ребра.

Остов минимальной длины найден.

Лекция 14. Парное сочетание (паросочетание) двудольных графов

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

Паросочетанием в двудольном графе называется любое множество попарно несмежных ребер (у них нет общих вершин).

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

Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c.

Для любого подмножества S через ф(S) обозначим те вершины из множества w, которые соединяются ребрами с вершинами подмножества S.

Теорема Холла (без доказательства)

Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [ф(S)].

Венгерский алгоритм нахождения максимального паросочетания.

Дан двудольный граф. Все определения для графа справедливы.

Полным паросочетанием называется паросочетание (ПС), к которому нельзя добавить ни одного ребра графа, не нарушив условие несмежности ребер.

Перебираем все ребра в любом порядке. Все несмежные ребра включаем в паросочетание.

Ребра, входящие в полное паросочетание, будем называть толстыми. Остальные ребра считаем тонкими.

Вершины, которые соединены толстыми ребрами - насыщенные. Остальные - ненасыщенные.

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

Тонкой чередующейся цепью называется чередующаяся цепь, соединяющая 2 ненасыщенные вершины (В ней тонких ребер на 1 больше, чем толстых).

Находим полное паросочетание.

Для этого паросочетания ищем тонкую цепь. Если ее нет, то данное паросочетание максимально и алгоритм закончен.

Если же она существует, то проводим перекраску ребер.

Толстые ребра тонкой цепи делаем тонкими, а тонкие - толстыми.

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

Переходим на шаг 2.

Количество ребер в новом паросочетании увеличится на 1.

Максимальное паросочетание (МПС) найдено.

Совершенное ПС - МПС обязательно.

Матрицы смежности двудольных графов.

A(M,N)

[V] = M

[W] = N

Aij = 1, если есть ребро ViWj

Если его нет, то Aij = 0.

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

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

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

Алгоритм оптимального назначения

Есть m работников и m работ.

Каждый из работников выполняет каждую работу с определенной эффективностью.

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

A = (aij) - матрица эффективности.

А(М*М)

А =

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

Дан двудольный полный граф с V = M, W = M

Даны длины ребер.

Задача состоит в нахождении совершенного паросочетания, сумма длин всех ребер которого максимальна.

Алгоритм.

Подобные документы

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

  Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
  
  учебное пособие [1,3 M], добавлен 20.08.2014
  

• Функционально полные системы логических функций. Алгебраический подход

  Основная функционально полная система логических функций. Законы алгебры логики в основной функционально полной системе и их следствия. Переместительный и распределительный законы. Закон инверсии (правило Де Моргана). Системы логических функций.
  
  реферат [40,5 K], добавлен 17.11.2008
  

• Полные системы булевых функций

  Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
  
  курсовая работа [278,1 K], добавлен 21.02.2009
  

• Изучение функций в курсе математики

  Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.
  
  контрольная работа [133,5 K], добавлен 08.06.2010
  

• Основы дискретной математики

  Минимизация заданного выражения алгебры множеств на основании известных свойств. Анализ заданного бинарного отношения в общем виде. Вывод формул булевых функций для каждого элемента и схемы в целом. Преобразование формулы булевой функции логической схемы.
  
  контрольная работа [286,7 K], добавлен 28.02.2009
  

• Исследование возможностей основных соотношений булевой алгебры для решения практических задач

  Логический синтез устройства с использованием соотношений булевой алгебры. Составление таблицы истинности. Основные соотношения булевой алгебры. Логическая функция в смысловой, словесной, вербальной, табличной и аналитической математической формах.
  
  лабораторная работа [83,6 K], добавлен 26.11.2011
  

• Полином Жегалкина

  Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
  
  курсовая работа [701,9 K], добавлен 27.04.2011
  

• Вычисление характеристических многочленов, собственных значений и собственных векторов

  Нахождение собственных значений и собственных векторов матриц. Нетривиальное решение однородной системы линейных алгебраических уравнений. Метод нахождения характеристического многочлена, предложенный А.М. Данилевским. Получение формы Жордано: form.exe.
  
  курсовая работа [53,4 K], добавлен 29.08.2010
  

• Булева алгебра и логические схемы для коньюнктора, дезъюнктора, инвентора, равнозначности и неравнозначности с положительной и отрицательной логикой

  История возникновения булевой алгебры, разработка системы исчисления высказываний. Методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Дизъюнкция, конъюнкция и отрицание, таблицы истинности.
  
  презентация [1,9 M], добавлен 22.02.2014
  

• Решение практических заданий по дискретной математике

  Представление с помощью кругов Эйлера множественного выражения. Законы и свойства алгебры множеств, упрощение выражений. Система функций, ее возможные базисы. Минимизирование булевой функции. Метод Квайна – Мак-Класки. Определение хроматического числа.
  
  контрольная работа [375,6 K], добавлен 17.01.2011
  

• Полиномы Жегалкина для логических операций

  Свойства алгебры Жегалкина. Действия с логическими константами (нулём и единицей). Свойства элементарных булевых функций, задаваемых логическими операциями. Способы построения полиномов с помощью таблиц истинности (метод неопределенных коэффициентов).
  
  курсовая работа [467,2 K], добавлен 28.11.2014
  

• Применение аппарата алгебры логики к решению содержательных задач

  Операции над логическими высказываниями: булевы функции и выражение одних таких зависимостей через другие. Пропозициональные формулы и некоторые законы логики высказываний. Перевод выражений естественного языка на символическую речь алгебры логики.
  
  контрольная работа [83,3 K], добавлен 26.04.2011
  

• Размещения и их свойства

  Возникновение комбинаторики как раздела математики. Исследование на практических примерах особенностей чисел размещений с повторениями и без них. Анализ задач, решение которых опирается на правила комбинаторики и относящиеся к ней вычислительные формулы.
  
  курсовая работа [175,3 K], добавлен 05.01.2018
  

• Булевы функции

  Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
  
  контрольная работа [178,2 K], добавлен 20.01.2011
  

• Элементы комбинаторики

  Решение задач по факультативному курсу комбинаторики, подготовка сообщений и докладов. Комбинаторика как ветвь математики, изучающая комбинации и перестановки предметов. Основные правила суммы и правило произведения. Поиск числа сочетаний с повторениями.
  
  дипломная работа [508,5 K], добавлен 26.01.2011
  

• Дискретная математика в задачах

  Свойства операций над множествами. Формулы алгебры высказываний. Функции алгебры логики. Существенные и фиктивные переменные. Проверка правильности рассуждений. Алгебра высказываний и релейно-контактные схемы. Способы задания графа. Матрицы для графов.
  
  учебное пособие [1,5 M], добавлен 27.10.2013
  

• Математическая логика и теория алгоритмов

  Основные определения математической логики, булевы и эквивалентные функции. Общие понятия булевой алгебры. Алгебра Жегалкина: высказывания и предикаты. Определение формальной теории. Элементы теории алгоритмов, рекурсивные функции, машина Тьюринга.
  
  курс лекций [651,0 K], добавлен 08.08.2011
  

• Элементы векторной алгебры и аналитической геометрии

  Линейные операции над векторами. Скалярное произведение двух векторов. Векторное произведение векторов. Графическое решение систем неравенств. Построение графиков функций с помощью геометрических преобразований. Простейшие геометрические преобразования.
  
  методичка [2,0 M], добавлен 15.06.2015
  

• Элементы математической логики. Исчисление высказываний

  Определение формулы исчисления высказываний, основные цели математической логики. Построение формул алгебры высказываний. Равносильность формул исчисления высказываний, конъюнктивная и дизъюнктивная нормальная форма. Постановка проблемы разрешимости.
  
  контрольная работа [34,3 K], добавлен 12.08.2010
  

• Применение методов дискретной математики в экономике

  Нахождение полинома Жегалкина методом неопределенных коэффициентов. Практическое применение жадного алгоритма. Венгерский метод решения задачи коммивояжера. Применение теории нечетких множеств для решения экономических задач в условиях неопределённости.
  
  курсовая работа [644,4 K], добавлен 16.05.2010
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам