- •Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.
- •Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.
- •Функции. Инъекции, сюръекции, биекции. Понятие последовательности.
- •Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.
- •Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.
- •Конечные, счетные, континуальные множества. Мощность булеана.
- •Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.
- •Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности.
- •Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно и вполне упорядоченные множества.
- •Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание с помощью таблицы Кэли.
- •Морфизмы алгебраических систем.
- •Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
- •Конгруэнции, фактор-алгебры, теорема о гомоморфизме.
- •17.Многообразия. Теорема Биркгофа.
- •Решетки. Дистрибутивные решетки. Критерий дистрибутивности.
- •Булевы алгебры. Теорема Стоуна. Принцип двойственности для булевых алгебр.
- •Булево кольцо.
- •18. Алгебры отношений. Реляционные алгебры.
- •27. Виды и способы задания графов.
- •28. Подграфы и части графа. Операции над графами. N-Мерные кубы.
- •Объединение: .
- •29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).
- •30. Расстояние в графах. Центральные и периферийные вершины.
- •31. Взвешенное расстояние. Алгоритм Форда-Беллмана.
- •32. Степени вершин. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла.
- •33. Гамильтоновы графы. Постановка задачи коммивояжера.
- •34. Деревья, леса. Остовы графов. Цикломатическое число, коранг. Алгоритм построения остова минимального веса. Обходы графов по глубине и ширине.
- •35. Упорядоченные и бинарные деревья. Соответствия между ними.
- •36. Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов.
- •37. Раскраска графов. Планарные графы.
- •38. Формулы алгебры логики, их таблицы истинности.
- •39. Булевы функции, способы их задания. Представления булевых функций формулами.
- •40. Эквивалентность формул.
- •41. Двухэлементная булева алгебра. Алгебра булевых функций. Фактор-алгебра алгебры формул.
- •42. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.
- •43. Теорема Шеннона. Теорема о функциональной полноте. Способы построения сднф и скнф.
- •44. Импликанты, простые импликанты. Сокращенные, тупиковые, минимальные нормальные формы. Алгоритм Квайна построения мднф.
- •45. Карты Карно. Построение мднф с помощью карт Карно.
- •46. Принцип двойственности. Самодвойственные функции.
- •47. Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции.
- •48. Классы Поста. Полные системы булевых функций. Теорема Поста. Базисы.
- •49. Логические сети. Реализация булевых функций контактными схемами и схемами из функциональных элементов.
Конгруэнции, фактор-алгебры, теорема о гомоморфизме.
Конгруэнцией на алгебре α=<A,∑> называется такое отношение эквивалентности , при котором для любого , любого n-местного символа , произвольных наборов , если a1θb1,…, anθbn, то f(a1,…, an)θf(b1,…,bn). Т.е. все операции согласованы с отношением эквивалентности.
Рассмотрим фактор-множество множества А по конгруэнции θ: . Определим на этом множестве алгебру сигнатуры ∑. Константе с алгебры А поставим в соответствие элемент θ(с), который в А/θ будет интерпретировать константный символ с. Если f – n-местный символ из ∑, то зададим на множестве А/θ действие функции f по правилу:
f(θ(x1),…, θ(xn))=θ(f(x1,…, xn)).
Убедимся, что для любых это определение корректно, т.е. не зависит от выбора представителей классов эквивалентности. Действительно, если θ(xi)=θ(yi), i=1,2,…,n, то xiθyi, откуда в силу свойства конгруэнции имеем f(x1,…, xn)θf(y1,…, yn), т.е. θ(f(x1,…, xn))=θ(f(y1,…, yn)).
Получившаяся алгебра α/θ=<A/θ,∑> называется фактор-алгеброй алгебры α по конгруэнции θ.
Очевидно, что отображение А→А/θ, при котором элементу ставится в соответствие класс θ(х), является эпиморфизмом алгебры α на фактор-алгебру α/θ. Этот эпиморфизм называется естественным гомоморфизмом.
Если φ: α→β – гомоморфизм алгебр, то множество оказывается конгруэнцией на алгебре α и называется ядром гомоморфизма φ.
Теорема о гомоморфизме: Если φ: α→β – эпиморфизм, ψ: α→α/Kerφ – естественный гомоморфизм, то существует изоморфизм χ: β→α/Kerφ такой, что φ•χ=ψ.
Доказательство: Положим χ(b)=ψ(a), где выбрано так, что b=φ(a)/ Если b=φ(a’), то , откуда ψ(a)=ψ(a’). Следовательно, отображение χ определяется корректно. Равенство φ•χ=ψ очевидно. Из него вытекает, что χ – сюръекция. Непосредственно проверяется, что χ – гомоморфизм. Если χ(b)=χ(b’), то ψ(a)=ψ(a’), где b=φ(a), b’=φ(a’). Отсюда , следовательно b=b’, что доказывает возможную однозначность отображения χ. Т.к. сигнатура функциональна, из существования функции χ-1 и того, что χ – гомоморфизм, следует, что χ является изоморфизмом.
Отображения φ, ψ и χ можно представить диаграммой:
17.Многообразия. Теорема Биркгофа.
Пусть Ai, - семейство множеств. Декартовым произведением множеств Ai, называется множество
Отметим, что если I={1,2,…,n} – конечное множество индексов, то декартово произведение можно взаимно однозначно рассматривать как множество . Таким образом данное определение согласуется с введенным ранее определением декартова произведения конечного числа множеств.
Пусть - некоторые алгебры сигнатуры ∑. Декартовым произведением алгебр называется алгебра , в которой функциональные символы интерпретируются по следующему правилу: для любых функций полагаем F(f1,…, fn)=f, где f(i)=Fαi(f1(i),…,fn(i)) для любого .
Пусть t1, t2 - термы сигнатуры ∑. Запись t1≈t2 называется тождеством сигнатуры ∑. Она означает, что любые значения, вычисленные по терму t1, совпадают с соответствующими значениями, вычисленными по терму t2.
Класс К алгебр сигнатуры ∑ называется многообразием, если существует множество тождеств сигнатуры ∑ такое, что алгебра сигнатуры ∑ принадлежит классу К тогда и только тогда, когда в ней выполняются все тождества из множества Т.
Теорема Биркгофа: Непустой класс алгебр К сигнатуры ∑ тогда и только тогда является многообразием, когда К замкнут относительно подалгебр, фактор-алгебр и декартовых произведений, т.е. класс К вместе с каждой алгеброй содержит любую ее подалгебру, фактор-алгебру, а также вместе с любым семейством алгебр содержит их декартово произведение.