ДИСКРА 2 СЕМЕСТР ЛЕКЦИИ Flashcards
(110 cards)
1
Q
Л1 КОЛЬЦО ВЫЧЕТА
A
МН-ВО КЛАССОВ ЭКВИВАЛЕНТНОСТИ ПО ДЕЛИМОСТИ НА ЗАДАННОЕ N. С ОПРЕДЕЛЕННЫМ НА НЕМ ОПЕРАЦИЯМИ(СЛОЖЕНИЕ, УМНОЖЕНИЕ ЛИБО ОБА )
2
Q
Л1 ПОРЯДОК ЭЛЕМЕНТА В КОЛЬЦЕ ВЫЧЕТА
A
СКОЛЬКО РАЗ(НАИМЕНЬШЕЕ ИЗ ВОЗМОЖНЫХ) НУЖНО ПРИМЕНИТЬ ОПЕРАЦИЮ К ЭЛЕМЕНТУ ЧТОБЫ ОН ПРЕОБРАЗОВАЛСЯ В НЕЙТРАЛЬНЫЙ ЭЛЕМЕНТ
3
Q
Л1 ПОРЯДОК ЭЛЕМЕНТА ПО СЛОЖЕНИЮ
A
ЕСЛИ ЭЛЕМЕНТ ВЗАИМНО ПРОСТ С ОСНОВАНИЕМ, ЗНАЧИТ ПОРЯДОК ЭЛЕМЕНТА N. ЕСЛИ ИМЕЕТ ОБЩИЕ ДЕЛИТЕЛИ, ЗНАЧИТ ПОРЯДОК N/НОД(А, N)
4
Q
Л1 КРИТЕРИЙ НАЛИЧИЯ ПОРЯДКА ПО УМНОЖЕНИЮ
A
ЕСТЬ ПОРЯДОК <=> ЭЛЕМЕНТ ВЗАИМНО ПРОСТ С ОСНОВАНИЕМ(ЭЛЕМЕНТ ОБРАТИМ)
5
Q
Л1 МН-ВО ОБРАТИМЫХ ОСТАТКОВ(ОБОЗНАЧЕНИЕ)
A
Zn*
6
Q
Л1 Т О ДЕЛИМОСТИ ПОРЯДКА ЭЛЕМЕНТА ПО УМНОЖЕНИЮ
A
ПОРЯДОК ЭЛЕМЕНТА ПО УМНОЖЕНИЮ - ДЕЛИТЕЛЬ КОЛЛИЧЕСТВА ЭЛЕМЕНТОВ В МН-ВЕ ОБРАТИМЫХ
7
Q
Л1 Ф-Я ЭЙЛЕРА
A
Ф-Я РАВНАЯ КОЛЛИЧЕСТВУ ЭЛЕМЕНТОВ В МН-ВЕ ОБРАТИМЫХ
Ф(р^k) = р^k - p^(k-1), р - ПРОСТОЕ
ф(аб) = Ф(а) * Ф(б) <=> а,б - ВЗАИМНО ПРОСТЫ
8
Q
Л1 Т ЭЙЛЕРА
A
ЕСЛИ а ЛЕЖИТ В Zn* => a^Ф(n) == 1
ИЛИ
ЕСЛИ НОД(а, n) = 1 => a^Ф(n) == 1
9
Q
Л1 Т О ДЕЛИМОСТИ СТЕПЕНИ ЭЕЛЕМЕНТА НА ЕГО ПОРЯДОК
A
ЕСЛИ М - ПОРЯДОК А, А П -СТЕПЕНЬ В КОТОРОЙ А ОБРАЩАЕТСЯ В ЕДИНИЦУ => П - ДЕЛИТСЯ НА М.
Д-ВО
Л1: 14:00
ЭТО И ЛЕЖИВ В ОСНОВЕ ТОГО ЧТО ПОРЯДОК ЭЛЕМЕНТА ДЕЛИТЕЛЬ Ф-ИИ ЭЙЛЕРА
10
Q
Л1 ЕСТЬ ЛИ ЭЛЕМЕНТ С ПЕРИОДОМ РОВНО Ф-ИИ ЭЙЛЕРА?
A
ВР:22:20
11
Q
Л1 ТЕОРЕМА ВИЛЬСОНА
A
В КОЛЬЦЕ ВЫЧЕТОВ ПО ОСНОВАНИЮ Р-ПРОСТОЕ, ВЕРНО УТВЕРЖДЕНИЕ
(Р-1)! == -1 mod P
12
Q
Л1 ОПРЕДЕЛЕНИЕ КОЛЬЦА = ПРИМЕРЫ
A
ОПР:
ПРИМЕРЫ: КОЛЬЦО ВЫЧЕТОВ - КОНЕЧНОЕ КОЛЬЦО
ВР:~39:00
13
Q
Л1 ПРИМЕР ПОЧЕМУ МОЖЕТ НЕ СУЩЕСТВОВАТЬ ИЗОМОРФИЗМ М\У КОЛЬЦАМИ(Z4 <-X-> Z2xZ2)
A
Л1 ВР: ~47:00
14
Q
Л1 ПОРЯДОК ПО СЛОЖЕНИЮ В ДЕКАРТОВОМ ПР-ИИ КОЛЕЦ ВЫЧЕТА
A
НОК(M, L)
Л1 ВР:10:02:00
15
Q
Л1 КРИТЕРИЙ РАЗЛОЖЕНИЯ КОЛЬЦА ВЫЧЕТОВ ПО ИЗОМОРФИЗМУ НА ДЕКАРТОВО ПР-Е КОЛЕЦ ВЫЧЕТОВ(КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ)
A
Zm x Zl ~= Zml <=> НОД(m, l) = 1
16
Q
Л1 ПРОСТАЯ ФОРМА КТО
A
ДЛЯ ЛЮБЫХ U, V СУЩЕСТВУЕТ X ТАКОЙ ЧТО X==U MOD m, X==V MOD l <=> (m, l) = 1
17
Q
Л1 КАК ИСКАТЬ ИДЕМПОТЕНТЫ В Zml?
A
КОНЕЦ ЛЕКЦИИ 1
18
Q
Л2 ПОИСК ОБРАТИМОГО
A
Л2 ВР:20:30
19
Q
A
20
Q
Л2 АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОРЯДКА ПО УМНОЖЕНИЮ
A
Л2 ВР:44:00
21
Q
Л2 Т О СУЩЕСТВОВАНИИ ПЕРВООБРАЗНОГО КОРНЯ
A
ЕСЛИ Р>2 - ПРОСТОЕ
ТО В Zp^n* ЕСТЬ ПЕРВООБРАЗНЫЙ КОРЕНЬ ИЗ 1 СТЕПЕНИ P^n - P^(n-1)
ВР:~49:00
22
Q
Л2 ПЕРВООБРАЗНЫЙ КОРЕНЬ В КОЛЬЦЕ ВЫЧЕТОВ ОТ Р^N - P - ПРОСТОЕ
A
ЭТО ЭЛЕМЕНТ С ПОРЯДКОМ ПО УМНОЖЕНИЮ P^N - P^(N-1)
23
Q
Л2 Т МАКС ВОЗМОЖНЫЙ ПОРЯДОК ЭЛ-ТА ИЗ Z2^n*
A
МАКС ВОЗМОЖНЫЙ ПОРЯДОК ЭЛ-ТА ИЗ Z2^n*
ЭТО НЕ Ф(2^n) = 2^n - 2^(n-1) = 2^(n-1)
ЭТО 2^(n-2)
ВР: ~58:00
24
Q
Л2 РЕШЕНИЕ УР-Я ВИДА Х^2 = 1 В КОЛЬЦАХ ВЫЧЕТА
A
Л2 ВР: 1:03:00
25
Л2 Т ЕСЛИ Р - ПРОСТОЕ ЗНАЧИТ КОРНЕЙ УР-Я Х = А^2 ИМЕЕТ НЕ БОЛЕЕ ДВУХ КОРНЕЙ
Л2 ВР 1:11:00
26
Л2 КАК УЗНАТЬ ЕСТЬ ЛИ РЕШЕНИЕ У УР-Я Х = А^2
Л2 ВР ~1:13:00
27
Л2 Т О СУЩЕСТВОВАНИИ КОРНЯ ИЗ -1
Т -1=Х^2 В Zp<=> p=4k+1
ДОК-ВО ~1:24:00 ЧЕРЕЗ Т ВИЛЬСОНА
28
Л3 ГРУППА
Л3 НАЧАЛО
МН-ВО С БИНАРНОЙ ОПЕРАЦИЕЙ, УДОВЛ СВ-ВАМ
1) АССОЦИАТИВНОСТЬ
2)СУЩЕСТВОВАНИЕ НЕЙТРАЛЬНОГО
3)СУЩЕСТВОВАНИЕ ОБРАТНОГО
29
Л3 АБЕЛЕВА ГРУППА
ГРУППА НАЗЫВАЕТСЯ АБЕЛЕВОЙ ЕСЛИ ЕЕ ОПЕРАЦИЯ УДОВЛЕТВОРЯЕТ КОММУТАТИВНОСТИ
ДОГОВОРЕННОСТЬ
АДДИТИВНО ЗАПИСЫВАЕМ ТОЛЬКО АБЕЛЕВЫ ГРУППЫ(ХОТЯ УМНОЖЕНИЕ ТОЖЕ МОЖЕТ БЫТЬ КОММУТИАТИВНЫМ)
30
Л3 ПОНЯТИЕ ПОРЯДКА ЭЛЕМЕНТА В ГРУППЕ
НАИМЕНЬШЕЕ ЧИСЛО ТАКОЕ ЧТО ПРИ ПРИМЕНЕНИИ К ЭЛЕМЕНТ ЗАДАННОЙ ОПЕРАЦИИ ЭТО ЧИСЛО РАЗ, ТО РЕЗУЛЬТАТ ОПЕРАЦИИ ОБРАЩАЕТСЯ В НЕЙТРАЛЬНЫЙ ЭЛЕМЕНТ ПО ЭТОЙ ОПЕРАЦИИ
31
Л3 Т О ДЕЛИМОСТИ ПОРЯДКА ЭЛЕМЕНТА В ГРУППЕ
ПОРЯДОК ЭЛЕМЕНТА В ГРУППЕ ДЕЛИТЕЛЬ МОЩНОСТИ ГРУППЫ
В СЛУЧАЕ ЕСЛИ ГРУППА КОНЕЧНАЯ
ДОК-ВО Л3 ВР 32:00
32
Л3 КОЛЬЦО
МН-ВО С ОПРЕДЕЛЕННЫМИ ДВУМЯ ОПЕРАЦИЯМИ(+ *)
УДОВЛЕТВОРЯЮЩИМИ СВ-ВАМ
1. МН-ВО АБЕЛЕВА ГРУППА ПО СЛОЖЕНИ
2. УМНОЖЕНИЕ СВЯЗАНО СО СЛОЖЕНИЕМ СВ-ВАМ ДИСТРИЬБУТИВНОСТИ
ДОП СВ-ВА
AB = BA
A(BC) = (AB)C
СУЩЕСТВОВАНИЕ ЕДИНИЦЫ
ТО ЕСТЬ В САМОМ ДЕЛЕ МЫ РАБОТАЕМ С КОММУТАТИВНЫМИ АССОЦИАТИВНЫМИ КОЛЬЦАМИ С 1
НО!
В КОЛЬЦАХ МОГУТ БЫТЬ НЕОБРАТИМЫЕ ЭЛ-ТЫ
33
Л3 ЗМ ПО ГРУППА ОБРАТИМЫХ ЭЛ-ТОВ
ГРУППА ОБРАТИМЫХ ЭЛЕМЕНТОВ ЯВЛЯЕТСЯ ГРУППОЙ ПО УМНОЖЕНИЮ , НО НЕ ПО СЛОЖЕНИЮ
34
Л3 Т О ПОРЯДКЕ ЭЛ-ТА КОЛЬЦА ПО СЛОЖЕНИЮ
ПОРЯДОК ЭЛ-ТА КОЛЬЦА ПО СЛОЖЕНИЮ - ДЕЛИТЕЛЬ ПОРЯДКА(МОЩНОСТИ) КОЛЬЦА
ЕСЛИ ЭЛ-Т ВЗАИМНО ПРОСТ С ОСНОВАНИЕМ(МОЩНОСТЬЮ КОЛЬЦА) ТО ЕГО ПОРЯДОК И ЕСТЬ МОЩНОСТЬ КОЛЬЦА
35
Л3 Т О ИЗОМОРФИЗМЕ ДЛЯ ЛЮБЫХ КОНЕЧНЫХ КОЛЕЦ
Т В ЛЮБОМ КОНЕЧНОМ КОЛЬЦЕ ЕСТЬ ПОДКОЛЬЦО(КОЛЬКО ЭЛ-ТОВ КРАТНЫХ ЕДИНИЧНОМУ ЭЛ-ТУ) ИЗОМОРФНОЕ КОЛЬЦУ ВЫЧЕТОВ Zn, ПРИЧЕМ МОЩНОСТЬ ПОДКОЛЬЦА КРАТНО n
36
Л3 Т О ПОЛНОМ ИЗОМОРФИЗМЕ КОНЕЧНЫХ КОЛЕЦ
ЕСЛИ МОЩНОСТЬ КОЛЬЦА ЕСТЬ Р - ПРОСТОЕ ЧИСЛО, ТО
ОНО ИЗОМОРФНО КОЛЬЦУ ВЫЧЕТОВ С ОСНОВАНИЕМ Р
37
Л3 НИЛЬПОТЕНТ
ЭЛ-Т КОЛЬЦА НЕНУЛЕВОЙ ТАКОЙ ЧТО ПРИ ВОЗВЕДЕНИИ ЕГО В НЕКУЮ СТЕПЕНЬ И ОН ОБРАЩАЕТСЯ В 0
38
Л3 ИДЕМПОТЕНТ
ЭЛ-Т КОЛЬЦА ТАКРОЙ ЧТО ОН НЕ НУЛЬ И НЕ ЕДИНИЦА НО ПРИ ВОЗВЕДЕНИИ ВО ВТОРУЮ СТЕПНЬ ОНИ ДАЮТ СЕБЯ ЖЕ
39
Л3 Т О СУЩ ОБРАТНОГО ИЛИ ДЕЛИТЕЛЯ НУЛЯ В КОН КОЛЬЦЕ
ЕСЛИ ЭЛЕМЕНИ НЕ НУЛЕВОЙ И ПРИНАДЛЕЖИТ КОЛЬЦУ ТО ОН ЛИБО ОБРАТИМ ЛИБО ДЕЛИТЕЛЬ НУЛЯ
ДОК-ВО
Л3 ВР 1:17:00
40
Л3 КАК УЗНАТЬ ЕСТЬ ЛИ ИЗОМОРФИЗМ М\У КАКИМ ТО КОЛЬЦОМ И ДЕКАРТОВЫМ ПР-ЕМ КОЛЕЦ?
Л3 ВР:~1:22:00
41
Л3 Т О СУЩЕСТВОВАНИИ ИЗОМОРФИЗМА М\У КОЛЬЦОМ И ДЕКАРТОВЫМ ПР-ЕМ КОЛЕЦ
ИЗОМОРФИЗМ М\У А И ХхУ СУЩЕСТВУЕТ <=> В А ЕСТЬ ИДЕМПОТЕНТНЫЕ ЭЛЕМЕНТЫ
ДОК-ВО: Л4 ВР 05:00
Л3 ВР 1:25:00
42
Л3 ПОЛЕ
ЕСЛИ В КОЛЬЦЕ ВСЕ ОТЛИЧНЫЕ ОТ НУЛЯ ИЕЮТ ОБРАТНЫЕ => ЭТО КОЛЬЦО - ПОЛЕ
43
Л4 Т О МН-ВЕ ОТОБРАЖЕНИЙ МНОЖЕСТВА В КОЛЬЦО
ТАКОЕ МН-ВО ТОЖЕ ЯВЛЯЕТСЯ КОЛЬЦОМ
ВР 47:00
44
Л4 КОЛЬЦО МНОГОЧЛЕНОВ
ВР 49:00
А - КОЛЬЦО
t - ПЕРЕМЕННАЯ
A[t] = {a0 + a1t +... +akt^k|ai is in A,, при k>n ak=0} - КОЛЬЦО МНОГОЧЛЕНОВ
45
Л4 РАЗМЕРНОСТЬ СУММЫ И ПР-Я МНОГОЧЛЕНОВ
deg(P + Q) <= max(deg(P), deg(Q))
deg(PQ) <= deg(P) + deg(Q)
46
Л4 Т О ОТОБРАЖЕНИИ КОЛЬЦА МНОГОЧЛЕНОВ В МН-ВО ОТОБРАЖЕНИЙ ЭТОГО КОЛЬЦА В СЕБЯ ЖЕ
ВР 1:14:00
ОТОБРАЖЕНИЕ НЕ ИНЬЕКТИВНО НЕ СЮРЬЕТИВНО
47
Л4 ЕСЛИ А КОН КОЛЬЦО ТОГДА v:А[t] -> A^A НЕ ИНЬЕКТИВЕН.
СЮРЬЕКТИВЕН ЛИ v?
Л4 ВР 1:23:00
ЕСЛИ А - ПОЛЕ ТО ОТВЕТ ДА
ЕСЛИ В А ЕСТЬ НЕОБРАТИМЫЕ ЭЛ-ТЫ, ТО НЕТ
48
Л4 Т О ЗАДАНИИ МНОГОЧЛЕНОМ ЛЮБОЙ Ф-ИИ ИЗ ПОЛЯ
ЕСЛИ А - ПОЛЕ ТО v:А[t] -> A^A,, Т Е ДЛЯ ЛЮБОЙ Ф-ИИ ИЗ ЭТОГО ПОЛЯ В НЕГО ЖЕ ЗАДАЕТСЯ МНОГОЧЛЕНОМ
49
Л5 УТВ.
МН-Н P(t) = SUM biLi(t) i=1...n
ДЛЯ НЕКОТОРЫХ НАБОРОВ ЧИСЕЛ ИЗ ПОЛЯ(a1, ..., an; b1, ..., bn) УДОВЛЕТВОРЯЮЩИЙ РАВЕНСТВУ P(ai) = bi ЯВЛЯЕТСЯ ЕДИНСТВЕННЫМ МН-НОМ РАЗМЕРНОСТИ НЕ ВЫШЕ n-1 УДОВЛЕТВОРЯЮЩИМ ЭТОМУ РАВЕНСТВУ
ВР 23:00
ДОК-ВО ОН УСТНО СКАЗАЛ
50
Л5 Т О ОТОБРАЖЕНИИ КОЛЬЦА МН-НОВ В МН-ВО ВСЕХ ОТОБРАЖЕНИЙ ИЗ ПОЛЯ В ПОЛЕ
v: A[t] -> K^K - СЮРЬЕКТИВНО
+
v: K[t](<=d) = {МН-НЫ СТ НЕ ВЫШЕ d}
|K| = q
v: K[t](<=q-1) -> K^K - БИЕКЦИЯ
ПРИМЕР:30:00
51
Л5 ЧТО БУДЕТ ЕСЛИ ВЗЯТЬ МН-НЫ СТЕПЕНИ Q А НЕ Q-1
ВР 35:00
ИТОГ: В К[t] ЕСТЬ ЕДИНСТВЕННЫЙ МН-Н СТЕПЕНИ Q КОТОРЫЙ ЗАДАЕТ 0 Ф-Ю.
ДЛЯ K = F2 ЭТО t^2 + t
52
Л5 КАК НАЙТИ ЕДИНСТВЕННЫЙ МН-Н СТЕПЕНИ Q РАВНЫЙ 0 Ф-ИИ ДЛЯ ЛЮБОГО ПОЛЯ К
ВР 40
53
Л5 Т О СВЯЗИ МН-ВА ОБРАТИМЫХ И КОЛЬЦЕ МН-НОВ
ВР 44:00
ЛЮБОЕ А ИЗ К* ЯВЛЯЕТСЯ КОРНЕМ МН-НА Т^(Q-1) - 1
Q-1 = |K*|
=> T(Т^(Q-1) - 1) ОБР В 0 НА ВСЕМ К.
54
Л5 КОЛЬЦО МН-НОВ ОТ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ
ВР: 49
ЕСЛИ K[t1] - КОЛЬЦО МН-НОВ С КОЭФФИЦИЕНТАМИ ИЗ K
ТО К[t1,t2] = (K[t1])[t2] - КОЛЬКО МН-НОВ, В КОТОРОМ КОЭФФИЦИЕНТЫ ЭТО МН-НЫ ИЗ К[t1]
В М ИЗ К[t1, ..., tn] СТАРШИЙ МОНОМ ИМЕЕТ ВИД: t1 ^ k1 + ... + tn ^ kn
deg M = k1 + ... + kn
55
Л5 ДОК-ВО ЧТО v: K[t1, ..., tn] -> K^Kn - СЮРЬЕКЦИЯ
56:00
56
Л5 ДОК-ВО ЧТО v: K[t1, ..., tn](<=Q-1) -> K^Kn - БИЕКЦИЯ
ВР:1:01:00
57
Л5 Т О ЗАДАНИИ Ф-ИИ N ПЕРЕМЕННЫХ МН-НОМ
ЛЮБУЮ Ф-Ю МОЖНО ОДНОЗНАЧНО ЗАДАТЬ МН-НОМ ОТ t1 ... tn, В КОТОРОМ КАЖДАЯ ПЕРЕМЕННАЯ ВХОДИТ В СТПЕПНИ <= Q-1
58
Л5 МНОГОЧЛЕН ЖИГАЛКИНА
P(t1 ... tn) = SUM a k1,..., kn * t1t2...tn причем ki = 0 или 1
59
Л5 БУЛЕВА Ф-Я
ВР:1:17:00
f : F2^n -> F2
(x1, ..., xn) ~> x1 * 2^n-1 + ... + xn-1 * 2 + xn - соотв м\у бул векторами и дв записью числа
60
Л5 ОТНОШЕНИЯ ПОРЯДКА НА F2^n
ЛЕКСИКОГРАФИЧЕСКИЙ ПОРЯДОК
(X1, ..., XN) < (Y1, ..., YN) ЕСЛИ X1 = Y1, ..., XK = YK,
X(K+1)
61
Л5 Т О ЗАДАНИИ БУЛЕВОЙ Ф-ИИ
ВР 1:27:00
БУЛЕВА Ф-Я ЗАДАЕТСЯ ОДНОЗНАЧНО ЗАДАЕТСЯ НАБОРОМ СВОИХ ЗНАЧЕНИЙ ЗАПИСАННЫХ В ЛЕКСИКОГРАФИЧЕСКОМ ПОРЯДКЕ
62
Л5 ПРИМЕР ПОСТРОЕНИЯ ВЕКТОРА РЕАЛИЗАЦИИ БУЛЕВОЙ Ф-ИИ И ПОЛИНОМА ЖИГАЛКИНА
ВР 1:28:00
63
Л6 Т О ИЗОМОРФИЗМЕ БУЛЕВОЙ АЛГЕБРЫ
ЛЮБАЯ КОНЕЧНАЯ БУЛЕВА АЛГЕБРА ИЗОМОРФНА МН-ВУ ВСЕХ ПОДМНОЖЕСТВ НЕКОТОРОГО КОНЕЧНОГО МН-ВА
ВР 29:00
64
Л6 БУЛЕВА АЛГЕБРА
МН-ВО С ОПР НА НЕМ БИН ОПЕРАЦИЯМИ ДИЗ КОН И УН ОПЕРАЦИЕЙ ОТРИЦАНИЯ И ВЫДЕЛЕННЫМИ ЭЛ-МИ 0 И 1, УДОВЛ УСЛОВИЯМ:
КОММ
АССОЦ
НЕЙТР ЭЛЕМЕНТ
ДИСТРИБУТИВНОСТТ
ИДЕМПОТЕНТНОСТЬ
ИНВОЛЮТИВНОСТЬ
ДОПОЛНИТЕЛЬНОСТЬ
ЗАКОНЫ ДЕМОРГАНА
ПОГЛОЩЕНИЕ
ВР22:30
65
Л6 ФОРМУЛА
1. КОНСТАНТЫ И ИМЕНА ПЕРЕМЕННЫХ - ЭТО ФОРМУЛЫ
2. ЕСЛИ A и B - Ф-ЛЫ ТО A*B - ТОЖЕ ФОРМУЛА(* - КАКАЯ ТО ДОПУСТИМАЯ ОПЕРАЦИЯ)
ДОГОВОРЕННОСТИ ОБ ОПУСКАНИИ СКОБОК
1. ОКОЛО ИМЕН ПЕРЕМЕННЫХ И КОНСТАНТ
2. МЫ ДОГОВАРИВАЕМСЯ О ПОРЯДКЕ ДЕЙСТВИЙ(УМНОЖЕНИЕ СИЛЬНЕЕ СЛОЖЕНИЯ И ВСЕ ПОДОБНОЕ)
66
Л6 МН-ВО ВСЕХ ФОРМУЛ
Ф
67
Л6 ЭКВИВАЛЕНТНЫЕ Ф-ЛЫ
ФОРМУЛЫ ЭКВИВАЛЕНТНЫ ЕСЛИ ИХ МОЖНО ПОЛУЧИТЬ ДРУГ ИЗ ДРУГО КОНЕЧНОЙ ЦЕПОЧКОЙ ТОЖДЕСТВЕННЫХ ПРЕОБРАЗРОВАНИЙ
68
Л6 Ф-ЛА БУЛЕВОЙ АЛГЕБРЫ
t1...tn - имена переменных, принимающих значения 0,1
1. t1, ..., tn, 0, 1 - ф-лы
2. Если А и В - ф-лы то (А)^(B), (A)or(B), not(A) - тоже ф-лы
69
Л 6 ПР-ЛА РАССТАНОВКИ СКОБОК ДЛЯ БУЛЕВОЙ АЛГЕБРЫ
1. ОПУСКАЕМ ДЛЯ ПЕРЕМЕННЫХ И КОНСТАНТ
2. КОНЬЮНКЦИЯ ВАЖНЕЕ ДИЗЬЮНКЦИИ
70
Л6 ЭКВИВАЛЕНТНОСТЬ Ф-Л БУЛЕВОЙ АЛГЕБРЫ
КАК И ПРОСТО ДЛЯ АБСТРАКТНЫХ ФОРМУЛ
71
Л6 ДИЗЬЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА
OR tk1^a1...tks^as
{k1...ks} in {1...n}
ai in {0, 1}
ВР 1:06:00
72
Л6 ЗМ БЫВАЮТ МНОГО ДНФ - ДОК-ВО
ВР 1:09:00
73
Л6 СОВЕРШЕННАЯ ДНФ
ЕСЛИ В КАЖДОМ МОНОМЕ ДНФ СОДЕРЖАТСЯ ВСЕ ПЕРЕМЕННЫЕ ТО ЕГО НАЗЫВАЮТ СДНФ
ПРИМЕР
XorY = X(YorNOTY) or (XorNOTX)Y = XY or X*notY or notX * Y
ЗМ В КАЖДОМ КЛАССЕ ЭКВИВАЛЕНТНОСТИ МН-ВА ФОРМУЛ ЕСТЬ СДНФ
74
Л6 УТВ НИКАКИЕ ДВЕ СДНФ НЕ ЭКВИВАЛЕНТНЫ - ДОК-ТЬ
ВР 1:15:00
75
Л6 Т ОТОБРАЖЕНИЕ v: Ф/~ -> F2^(F2^n) - СЮРЬЕКТИВНО
Т Е ДЛЯ ЛЮБОЙ БУЛЕВОЙ Ф-ИИ СУЩЕСТВУЕТ ФОРМУЛА ВИДА СДНФ - ДОК-ТЬ
ВР 1:20:00
76
Л6 ЗАДАЧА О ЗАДАНИИ БУЛЕВОЙ Ф-ИИ В ВИДЕ СОВ ДНФ? - ДОК-ВО
ВР 1:23:00
77
Л7 УТВ ЛЮБУЮ ФОРМУЛУ МОЖНО ПРИВЕТИ К ДНФ
ВР 2:00
78
Л7 УТВ ЛЮБУЮ ФОРМУЛУ МОЖНО ПРИВЕСТИ К СДНФ
ВР 6:00
79
Л7 НОСИТЕЛЬ МОНОМА\Ф-ИИ
МН-ВО ТАКИХ ЗНАЧЕНИЙ Ф-ИИ, КОТОРЫЕ ПРИ ПОДСТАНОВКЕ ОБРАЩАЮТ ЕГО В 1(НУ ИЛИ НЕ В 0 В ОБЩЕМ СЛУЧАЕ)
80
Л7 БУЛЕВ КУБ
ВР ~39:00
81
Л7 Т О ЗНАЧЕНИИ НОСИТЕЛЯ ДЛЯ СДНФ
НОСИТЕЛЬ Ф-ИИ(СДНФ) ЕСТЬ ОБЬЕДИНЕНИЕ НОСИТЕЛЕЙ ЕГО МОНОМОВ, КОТОРЫЕ В СВОЮ ОЧЕРЕДЬ РЕАЛИЗУЮТ ГРАНЬ БУЛЕВА КУБА
82
Л7 ЗАДАЧА О ПОКРЫТИИ
59:00
83
Л7 ПРИМЕР ОТОБРАЖЕНИЯ БУЛЕВОЙ Ф-ИИ ЧЕРЕЗ БУЛЕВ КУБ(ПЕРЕХОД К ВЫВОДУ ЧТО ЗАДАЧА НАХОЖДЕНИЯ ДНФ ДЛЯ БУЛ Ф-ИИ <=> ЗАДАЧА НАХОЖДЕНИЯ ПОКРЫТИЯ ЭТОЙ Ф-ИИ ГРАНЯМИ ЭТОГО КУБА)
59:00
84
Л7 МАКСИМАЛЬНЫЙ ИНТЕРВАЛ
ТАКАЯ ГРАНЬ ИЗ НОСИТЕЛЯ Ф-ИИ ЧТО ДЛЯ ЛЮБОЙ ГРАНИ В КОТОРОЙ ЛЕЖИТ МАКСИМАЛЬНЫЙ ИНТЕРВАЛ ВЕРНО ЧТО ОНА НЕ ЛЕЖИТ В НОСИТЕЛЕ
ПР ВР1:20:00 - ПОСТРОЕНИЕ ДНФ ПО БУЛЕВУ КУБУ
85
Л8 Т О РАЗМЕРНОСТИ МОНОМА
ЕСЛИ В МОНОМЕ К ПЕРЕМЕННЫХ, ТО РАЗМЕРНОСТЬ ПОКРЫТИЯ ЭТОГО МОНОМА(СООТВ ЕМУ ГРАНИ БУЛ КУБА) ЕСТЬ N-K
86
Л8 ОБЩАЯ ФОРМУЛИРОВК ЗАДАЧИ О ПОКРЫТИИ
ПОНЯТИЕ ТУПИКОВОГО ПОКРЫТИЯ
ВР 10:00
ПРИМЕР 14:30
87
Л8 ЯДРОВОЕ ПОКРЫТИЕ
ЕСЛИ СУЩЕСТВУЕТ ЭЛЕМЕНТ ТАКОЙ ЧТО НА НЕКОТОРОМ РАЗБИЕНИИ ОН ЛЕЖИТ В НЕКОТОРОМ МН-ВЕ, НО НЕ ЛЕЖИТ В ОСТАЛЬНЫХ, ТО ЭТО МН-ВО НАЗЫВАЮТ ЯДРОВЫМ
88
Л8 ЯДРО ПОКРЫТИЯ
МН-ВО ЭЛЕМЕНТОВ ПОКРЫТИЯ, ЧТО ОНИ ОБРАЗУЮТ ЯДРОВЫЕ ПОКРЫТИЯ
ВР 32:00
89
Л8 ЗАДАЧА О НАХОЖДЕНИИ НАИЛУЧШЕГО ТУПИКОВОГО ПОКРЫТИЯ
ИТОГ: ВР: 46:00
90
Л8 АБСТРАКТНЫЙ АЛГОРИТМ НАХОЖДЕНИЯ ДНФ ТУПИКОВОГО ПОКРЫТИЯ(СОКР ДНФ)
ВР 46:30
91
Л8 СОКРАЩЕННАЯ ДНФ
ДНФ СООТВЕТСТВУЮЩАЯ ПОКРЫТИЮ МАКСИМАЛЬНЫМИ ИНТЕРВАЛАМИ
92
Л8 РЕАЛЬНЫЙ АЛГОРИТМ НАХОЖДЕНИЯ СОКР ДНФ ПО БУЛЕВУ КУБУ - КОНЕЦ ЗАДАЧИ НАХОЖДЕНИЯ ТУПИКОВОГО ДНФ
ВР 52:50
93
Л8 КОНЬЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА
1:15:00
94
Л8 КАК ИСКАТЬ КНФ
ВР 1:18:00
95
Л8 ИНВОЛЮЦИЯ(ДВОЙСТВЕННОСТЬ)
БИЕКЦИЯ М\У БУЛЕВЫМИ Ф-МИ:
f*(x1, ..., xn) -> not f(not x1, ..., not xn)
96
Л8 СЛ-Е ИЗ ИНВОЛЮЦИИС
*ДНФ <-> КНФ
97
Л8 КАК НАХОДИТЬ F*
ВР 1:25:00
98
Л9 ПЕРЕХОД ОТ ДНФ К КНФ(точно правильно с примером)
ВР 15:50
99
Л9 КАК ХОРОШО РИСОВАТЬ 4 МЕРНЫЙ КУБ?
ВР 23:20
100
Л9 КАРТА КАРНО-НАХОЖДЕНИЕ ГРАНЕЙ 4-МЕРНЫХ ФИГУР
ВР 30:30
101
Л9 ПРИМЕР ПОСТРОЕНИЯ КАРТЫ КАРНО ПО ЗАДАННОЙ Ф-ИИ
ВР 57:00
102
Л9 НАХОЖДЕНИЕ НАИЛУЧШЕГО ВЫБОРА РЕБЕР ПО КАРТЕ КАРНО, ТАКОГО ЧТОБЫ ПОЛУЧИТЬ НАИЛУЧШУЮ ФОРМУЛУ
ВР 1:08:00
103
Л9 НАХОЖДЕНИЕ ТУПИКОВОЙ КНФ
ВР 1:18:00
104
Л10 АЛГОРИТМ КВАЙНА-МАКЛОЦКИ
ПОСМОТРЕТЬ В ИНЕТЕ
ВР27:30
105
Л10 КАК ИСКАТЬ СОКРАЩЕННУЮ ДНФ ДЛЯ N>4
ВР 28:30
106
Л10 ПРИМЕР ПРОСТРОЕНИЯ СОКРАЩЕННОЙ ДНФ ДЛЯ N>4
ВР 40:00
107
Л10 МОЖНО ЛИ ЧЕРЕЗ НЕКОТОРЫЕ ЗАДАННЫЕ БУЛ Ф-ИИ ВЫРАЗИТЬ ЛЮБУЮ ДРУГУЮ Ф-Ю?
ВР1:10:00
108
Л10 ПОЛНАЯ СИСТЕМА
СИСТЕМА БУЛ ОПЕРАЦИЙ, ТАКАЯ ЧТО ЛЮБУЮ БУЛ Ф-Ю МОЖНО ВЫРАЗИТЬ КАК ФОРМУЛУ ИЗ ЭТИХ ОПЕРАЦИЙ
109
Л10 ЗАМКНУТЫЙ КЛАСС
КЛАСС Ф-ИЙ ТАКОЙ ЧТО ВЫБРАВ ЛЮБЫЕ ДВА ЭЛ-ТА И ПОДСТАВИВ ОДИН ИЗ НИХ КАК АРГУМЕНТ ДРУГОГО, ПОЛУЧАЕТСЯ ЭЛ-Т ЭТОГО ЖЕ КЛАССА
110
Л
