- •1. Булевы функции двух переменных.
- •2. Булевы функции: эквивалентность и сумма по модулю два. Таблицы истинности, комбинационные схемы, изображение базисных элементов.
- •3. Булевы функции: Штрих шеффера и стрелка Пирса.
- •4. Совднф и совкнф. 5. 6. Построение их по таблице истинности
- •7. Карты карно и их связь с таблицами истинности
- •8. Построение сднф по карте карно. 9. Построение скнф по карте карно
- •10. Построение булевой формулы по комбинационной схеме
- •11. Упрощение булевых формул
- •12. Исключение лишних членов при упрощении булевых формул.
- •13. Конституенты и импликанты и их роль в алгебре логики.
- •14. Минимизация булевой функции методом квайна.
- •15. Минимизация булевой функции по методу блейка
- •Минимизация булевой функции по методу нельсона
- •Функциональная полнота систем логических функций. 19. Примеры функционально полных систем
- •20. Основные понятия исчисления предикатов.
- •21. Алгебра предикатов: операции отрицания, конъюнкции и дизъюнкции.
- •22. Алгебра предикатов: операции импликации и эквивалентности.
- •!!!!!!!«Эквивалентность – не нашел!»!!!!!!!
- •23. Понятие квантора. Двойственность кванторов.
- •24. Применение кванторов в исчислении предикатов – не нашел!
- •25. Характеристическая функция принадлежности для обычных и нечетких множеств.
- •26. Понятие нечеткого подмножества
- •27. Включение, равенство, дополнение и пересечение нечетких множеств
- •28. Объединение, разность, возведение в степень нечетких множеств
- •29. Разность и симметрическая разность нечетких множеств
- •30. Понятие нечеткого отношения. Проекция и носитель нечеткого отношения
- •31. Объединение, пересечение и алгебраическое произведение двух нечетких отношений.
- •32. Алгебраическая сумма и симметрическая разность двух нечетких отношений
- •33. Композиция двух нечетких отношений.
- •40. Ориентированные и неориентировапнные графы. Деревья.
- •41. Способы задания графов
- •42. Задание графа матрицей Инцидентности.
- •43. Задание графа матрицей смежности.
- •44. Задача о кратчайшем пути на графе с ребрами единичной длины.
- •45. Построение графа наименьшей длины
- •46. Транспортные сети. Основные понятия.
- •47. Задача о наибольшем потоке в транспортной сети.
- •48. Понятие алгебраической системы
- •50. Строки символов как примеры полугрупп и моноидов - ????????????????.
- •51. Понятие группы.
- •52. Подгруппы. Построение подгрупп заданной группы.-???????????????????
- •54. Группа подстановки.
- •55. Группа с операцией сложения по модулю m - ????????????
- •56/ Группа с операцией умножения по модулю m - ????????????
- •57. Кольца.
- •58. Поля.
- •59. Поле галуа.
- •60 Многочлены над полями галуа??????????
- •61. Изоморфизм и гомоморфизм - ????????????
48. Понятие алгебраической системы
Если в прошлых веках и в начале XX века алгебра изучала весьма ограниченное число алгебраических структур, то сейчас можно дать очень общее определение алгебры – а именно: наука о свойствах множеств, на которых определена та или иная система операций и отношений. В развитие такого взгляда на алгебру внес большой вклад А.И. Мальцев. В частности, он ввел понятие алгебраической системы, что и является темой данного раздела. Благодаря работам А.И. Мальцева стало ясно, что алгебра и математическая логика – две тесно связанные между собой дисциплины.
Алгебраическая система (или алгебраическая структура) в универсальной алгебре — множество (носитель) с заданным на нём набором операций и отношений (сигнатура), удовлетворяющим некоторой системе аксиом. Алгебраическая система с пустым множеством отношений называется универсальной алгеброй, а система с пустым множеством операций — моделью.
n-арная операция на G — это отображение прямого произведения n экземпляров множества в само множество . По определению, 0-арная операция — это просто выделенный элемент множества. Чаще всего рассматриваются унарные и бинарные операции, поскольку с ними легче работать. Но в связи с нуждами топологии, алгебры, комбинаторики постепенно накапливается техника работы с операциями большей арности, здесь в качестве примера можно привести теорию операд (клонов полилинейных операций) и алгебр над ними (мультиоператорных алгебр).
Для алгебраических систем естественным образом определяются морфизмы как отображения, сохраняющие операцию. Таким образом определяются категории групп, колец, R-модулей и т. п.
Если множество обладает структурой топологического пространства, и операции являются непрерывными, то его называют топологической алгебраической системой. Так, в топологической группе операции умножения и взятия обратного элемента являются непрерывными.
Список алгебраических систем
Множество можно считать вырожденной алгебраической системой с пустым набором операций и отношений ([1] — С.15).
Группоиды, полугруппы, группы
Группоид — множество с одной бинарной операцией , обычно называемой умножением.
Правая квазигруппа — группоид, в котором возможно правое деление, то есть уравнение имеет единственное решение для любых и .
Квазигруппа — одновременно правая и левая квазигруппы.
Лупа — квазигруппа с единичным элементом , таким, что .
Полугруппа — группоид, в котором умножение ассоциативно: .
Моноид — полугруппа с единичным элементом.
Группа — моноид, в котором для каждого элемента a группы можно определить обратный элемент a−1, такой, что .
Абелева группа — группа, в которой операция коммутативна, то есть, . Операцию в абелевой группе часто называют сложением ('+').
Кольца
Полукольцо — похоже на кольцо, но без обратимости сложения.
Почти-кольцо — также обобщение кольца, отличающееся от обычного кольца отсутствием требования коммутативности сложения и отсутствием требования дистрибутивности умножения по сложению (левой или правой)
Кольцо — структура с двумя бинарными операциями: абелева группа по сложению, моноид по умножению, выполняется закон дистрибутивности: .
Коммутативное кольцо — кольцо с коммутативным умножением.
Целостное кольцо — кольцо, в котором произведение двух ненулевых элементов не равно нулю.
Тело — кольцо, в котором ненулевые элементы образуют группу по умножению.
Поле — коммутативное кольцо, являющееся телом.
Алгебры
Алгебра (линейная) — пространство с билинейной дистрибутивной операцией умножения, иначе говоря, кольцо с согласованной структурой пространства
Ассоциативная алгебра — алгебра с ассоциативным умножением
Алгебра термов
Коммутативная алгебра
Градуированная алгебра
Алгебра Ли — алгебра с антикоммутативным умножением (обычно обозначаемым ), удовлетворяющим тождеству Якоби
Алгебра Лейбница — алгебра с умножением (обычно обозначаемым ), удовлетворяющим тождеству Якоби
Алгебра Йордана — коммутативная алгебра с тождеством слабой ассоциативности:
Алгебра некоммутативная йорданова — некоммутативная алгебра с тождеством слабой ассоциативности: и тождеством эластичности:
Альтернативная алгебра — алгебра с тождествами
Алгебра Мальцева — антикоммутативная алгебра с тождеством
Алгебра над операдой — один из наиболее общих видов алгебраических систем. Здесь сама операда играет роль сигнатуры алгебры.
Решётки
Решётка — структура с двумя коммутативными, ассоциативными, идемпотентными операциями, удовлетворяющими закону поглощения.
Булева алгебра.
49. Полугруппы и моноиды.
В математике, полугруппой называют множество с заданной на нем ассоциативной бинарной операцией .
Примеры полугрупп
Положительные целые числа с операцией сложения.
Любая группа является также и полугруппой.
Идеал кольца всегда является полугруппой относительно операции умножения.
Множество всех отображений множества в себя с операцией суперпозиции отображений
Множество всех бинарных отношений на множестве с операцией умножения бинарных отношений.
Множество всех слов над некоторым алфавитом с операцией конкатенации (присоединения)
Две полугруппы S и T называются изоморфными, если существует биекция f : S → T, такая что .
Структура полугруппы
Если , то принято обозначать
Подмножество A полугруппы S называется подполугруппой, если оно замкнуто относительно полугрупповой операции и само в свою очередь является полугруппой.
Если подмножество A непусто и AS (SA) лежит в A, то A называют правым (левым) идеалом. Если A является одновременно левым и правым иделом, то его называют двусторонним идеалом, или просто идеалом.
Пересечение двух идеалов - также идеал; из этого следует, что полугруппа не может иметь более одного наименьшего идеала. Пример полугруппы, в которой нет наименьшего идеала - положительные целые числа с операцией сложения. Если же наименьший идеал есть, а полугруппа коммутативна, то он является группой.
Благодаря ассоциативности, можно корректно определить натуральную степень элемента полугруппы как
.
Для степени элемента справедливо .
Частным случаем полугрупп являются полугруппы с делением, в которых для каждых двух элементов a и b определено правое (a/b) и левое (b\a) частное.
Отношения Грина
В 1951 году Грин ввел пять фундаментальных отношений эквивалентности на полугруппе. Они оказались существенными для понимания полугруппы как в локальном, так и в глобальном аспектах. Отношения Грина на полугруппе определяются следующими формулами
Уже из определения видно, что R - левая конгруэнция, а L - правая конгруэнция. Также известно, что . Одним из наиболее фундаментальных утверждений в теории полугрупп является лемма Грина, которая утверждает, что если элементы a и b R-эквивалентны, u,v такие, что au=b, bv=a и - соответствующие правые сдвиги, то - взаимно обратные биекции на и наоборот соответственно. Также они сохраняют H-классы.
Моноид — полугруппа с нейтральным элементом.
Таким образом, моноидом называется множество , на котором задана бинарная ассоциативная операция, обычно именуемая умножением, и в котором существует такой элемент , что для любого . Элемент называется единицей и часто обозначается . В любом моноиде имеется ровно одна единица.
Примеры
Множество всех отображений произвольного множества в себя является моноидом относительно операции последовательного выполнения (композиции) отображений. Единицей служит тождественное отображение.
Множество эндоморфизмов любой универсальной алгебры является моноидом относительно операции суперпозиции, единица — тождественный эндоморфизм.
Всякая группа является моноидом.
Свойства
Всякую полугруппу без единицы можно вложить в моноид.
Всякий моноид можно представить как моноид всех эндоморфизмов некоторой универсальной алгебры.
Произвольный моноид можно рассматривать также как категорию с одним объектом.
Для любого элемента моноида можно определить нулевую степень как [1].