- •Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.
- •Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.
- •Функции. Инъекции, сюръекции, биекции. Понятие последовательности.
- •Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.
- •Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.
- •Конечные, счетные, континуальные множества. Мощность булеана.
- •Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.
- •Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности.
- •Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно и вполне упорядоченные множества.
- •Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание с помощью таблицы Кэли.
- •Морфизмы алгебраических систем.
- •Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
- •Конгруэнции, фактор-алгебры, теорема о гомоморфизме.
- •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=<A,∑> называется пара, где А – непустое множество, носитель алгебраической системы; ∑ - сигнатура алгебраической системы, множество функциональных и предикатных символов с указанием их местности. Примеры: <ω, +(2), •(2), ≤(2), 0(0), 1(0)>; <R, +(2), -(2), e(0)>
Сигнатура ∑ называется функциональной (предикатной), если она не содержит предикатных (функциональных) символов. Система А называется алгеброй (моделью), если ее сигнатура функциональна (предикатна).
Группоид – алгебраическая система с одной двухместной операцией. Эта единственная операция часто обозначается символом •. Если А – конечное множество, то действия операции • можно задать квадратной таблицей, в которой для каждой пары записан результат действия. Такая таблица называется таблицей Кэли группоида А. (Что-то наподобие таблицы умножения).
Полугруппа – группоид, у которого операция • ассоциативна. Т.е. x•(y•z)=(x•y) •z/
Моноид – полугруппа, для которой существует элемент e называемый единицей, такой, что e•x=x•e=x.
Группа – моноид, в котором для любого элемента существует элемент , называемый обратным к x, такой, что x•x-1=x-1•x=e.
Группа называется коммутативной или абелевой, если x•y=y•x.
Морфизмы алгебраических систем.
Пусть даны алгебраические системы: α=<A,∑>, β=<B,∑>. Отображение φ: А→В называется гомоморфизмом системы α в систему β, если выполняются следующие условия:
1) должно выполняться согласование для функциональных символов
2) должно выполняться согласование предикатных символов
Если φ: А→В – гомоморфизм, то будем писать φ: α→β.
При гомоморфизме сохраняются действия операций и отношения.
Гомоморфизм φ: α→β, являющийся инъекцией, называется мономорфизмом (т.е. )
Гомоморфизм φ: α→β, являющийся сюръекцией, называется эпиморфизмом, и при этом система β называется гомоморфным образом системы α.
Сюръективный мономорфизм φ: α→β, для которого φ-1 – гомоморфизм, называется изоморфизмом (φ: α≈β).
Изоморфизм φ: α→α называется автоморфизмом системы α.
Утверждения:
idA: α≈α (Рефлексивность)
если φ: α≈β, то φ-1: β≈α (симметричность)
если φ: α≈β и ψ: β≈γ, то φ•ψ: α≈γ (транзитивность)
Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
Алгебраическая система α=<A,∑> называется подсистемой системы β=<B,∑>, если выполняются следующие условия:
для любого функционального символа , соответствующих функций и любых элементов выполняется равенство fα(a1,…, an) = fβ(a1,…, an), т.е интерпретации символа f действуют одинаково на элементах из А
для любого предикатного символа , соответствующих предикатов Рα, Рβ справедливо равенство , т.е. предикат Рα содержит в точности те кортежи отношения Рβ, которые состоят из элементов множества А.
Если ∑ - функциональная (предикатная) сигнатура, то подсистема α алгебры (модели) β называется подалгеброй (подмоделью).
Теорема: Если β – алгебраическая система, , , то существует единственная подсистема с носителем В(Х), такая, что и для любой подсистемы , для которой .
Доказательство: В качестве В(Х) рассмотрим пересечение носителей А всех подсистем , содержащих Х. Т.к. , то . Единственность подсистемы β(Х) очевидна.
Подсистема β(Х) из данной теоремы называется подсистемой, порожденной множеством Х в β. Она является наименьшей подсистемой системы β, содержащей множество Х.
Для описания устройства подсистемы β(Х) определим индукцией понятие терма сигнатуры ∑:
переменные и константные символы из ∑ есть суть термы
если - n-местный функциональный символ, t1,…, tn – термы, то f(t1,… tn) – терм
никаких термов, кроме построенных по пп. 1,2, нет.
Таким образом, термом является любое функциональное выражение, составленное с помощью сигнатурных функциональных символов. Множество всех термов сигнатуры ∑ обозначается через Т(∑).
Пусть t(x1,…, xk) – терм из Т(∑), все переменные которого содержаться среди x1,…, xk; α=<A,∑> - алгебраическая система. Значение терма t при значениях переменных x1,…, xk (t(a1,..., ak)) определяется по индукции:
если t – переменная xi (константный символ с), то значение t есть ai (c).
если терм t есть f(t1,…, tn), а t1(a1,…, ak)=b1,…, tn(a1,…, ak)=bn, то t(a1,…, ak)=b(t1,…, tn)
Теорема (о структуре подсистемы, порожденной множеством): Если β=<B,∑> - алгебраическая система, , то носитель подсистемы
Доказательство: Индукцией по числу шагов построения терма t получаем, что если и , то для любой подсистемы , содержащей Х. Поэтому достаточно показать, что множество замкнуто относительно операций системы β. Пусть . Тогда , поскольку .
Таким образом, носитель подсистемы β(Х) состоит из всех элементов, которые получаются при подстановке элементов из Х в термы.