Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание с помощью таблицы Кэли.

Алгебраической системой A=<A,∑> называется пара, где А – непустое множество, носитель алгебраической системы; ∑ - сигнатура алгебраической системы, множество функциональных и предикатных символов с указанием их местности. Примеры: <ω, +⁽²⁾, •⁽²⁾, ≤⁽²⁾, 0⁽⁰⁾, 1⁽⁰⁾>; <R, +⁽²⁾, -⁽²⁾, e⁽⁰⁾>

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

Группоид – алгебраическая система с одной двухместной операцией. Эта единственная операция часто обозначается символом •. Если А – конечное множество, то действия операции • можно задать квадратной таблицей, в которой для каждой пары записан результат действия. Такая таблица называется таблицей Кэли группоида А. (Что-то наподобие таблицы умножения).

Полугруппа – группоид, у которого операция • ассоциативна. Т.е. x•(y•z)=(x•y) •z/

Моноид – полугруппа, для которой существует элемент e называемый единицей, такой, что e•x=x•e=x.

Группа – моноид, в котором для любого элемента существует элемент , называемый обратным к x, такой, что x•x^-1=x^-1•x=e.

Группа называется коммутативной или абелевой, если x•y=y•x.

11. Yandex.RTB R-A-252273-3
    Содержание

    • Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.
    • Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.
    • Функции. Инъекции, сюръекции, биекции. Понятие последовательности.
    • Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.
    • Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.
    • Конечные, счетные, континуальные множества. Мощность булеана.
    • Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.
    • Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности.
    • Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно и вполне упорядоченные множества.
    • Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание с помощью таблицы Кэли.
    • Морфизмы алгебраических систем.
    • Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
    • Конгруэнции, фактор-алгебры, теорема о гомоморфизме.
    • 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. Логические сети. Реализация булевых функций контактными схемами и схемами из функциональных элементов.

    Yandex.RTB R-A-252273-4