- •Содержание:
- •Тема 1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Диаграммы Венна. Свойства теоретико-множественных операций. Представление множеств в эвм. 5
- •Операции над множествами.
- •Свойства теоретико-множественных операций. Представление множеств в эвм.
- •Многоместные отношения. Композиция отношений. Степень и ядро отношений.
- •Свойства отношений. Представление отношений в эвм.
- •Формулы. Реализация функций формулами. Равносильные формулы. Принцип двойственности.
- •Дизъюнктивная нормальная форма.
- •Конъюнктивная нормальная форма.
- •Теорема Поста
- •Геометрическая интерпретация минимизации функций алгебры логики.
- •Метод неопределённых коэффициентов.
- •Метод карт Карно
- •Тема 4. Алгебраические системы. Дистрибутивные решетки. Определение решетки, дистрибутивной решетки. Булева решетка. Алгебраические системы.
- •Группоиды и полугруппы.
- •Понятие группы.
- •Кольца. Тела и поля.
- •Решетки. Диаграмма Хассе.
- •Дистрибутивная решетка.
- •Булева алгебра.
- •Тема 5. Поля Галуа и их применение. Классическая теория Галуа. Расширения полей и их классификация. Сепарабельные и нормальные расширения. Расширения полей q, f_q, c(t).
- •1.2 Расширения полей и их классификация.
- •1.1.Простое расширение поля.
- •1.2.Минимальный полином алгебраического элемента.
- •1.3.Строение простого алгебраического расширения поля.
- •1.4.Освобождение от алгебраической иррациональности в знаменателе дроби.
- •3. Сепарабельные и несепарабельные расширения.
- •Тема 6. Многозначные логики. Возникновение и формализация модальных логик. Применение многозначных логик. Основные понятия
- •Тема 7. Методы пересчета. Перестановки, сочетания, транспозиции. Методы генерирования перестановок: лексикографический порядок, векторы инверсий, вложенные циклы, транспозиция смежных элементов.
- •Тема 8. Производящие функции. Способы построения производящих функций. Пример построения производящей функции при известном рекуррентном соотношении.
- •Тема 10. Синтез автоматов. Абстрактный уровень проектирования автомата.
- •Тема 11. Минимизация числа состояний автомата. Минимизация числа состояний синхронного автомата методом Хафмена.
- •6. Минимизация числа состояний методом таблиц.
- •Тема 13. Автоматы с памятью. Канонический метод структурного синтеза. Построение логической схемы структурного автомата. Графический метод структурного синтеза.
- •Тема 14. Сети Петри и их свойства. Основные понятия сетей Петри. Конечные разметки сети. Ограниченность сети. Моделирование с помощью сетей Петри. Формальное определение сети Петри.
- •Тема 15. Описание систем с помощью сетей Петри. Применение сетей Петри при разработке графического языка программирования.
- •Тема 17. Решение задач с помощью динамических двоичных функций. Синтез логической схемы, реализующей заданную булеву функцию, с использованием блоков исключения одной переменной.
Тема 4. Алгебраические системы. Дистрибутивные решетки. Определение решетки, дистрибутивной решетки. Булева решетка. Алгебраические системы.
Множество М вместе с заданными на них операциями называется алгеброй.
Обозначается A=
Множество Mназывается основным, или несущим множеством, или просто носителем.
называется сигнатурой алгебры А.
Пример алгебры:
,
где множество M – множество натуральных чисел N;
–любая операция, в частности операция сложения.
Множество М вместе с заданными на нем отношениями называется моделью.
Обозначается
Например, моделью может быть множество с соотношением “быть больше или быть равным”M
Множество M вместе с заданными на нем операциями и отношенияминазывается алгебраической системой или алгебраической структурой.
Примеры алгебраической структуры:
Группоиды и полугруппы.
Алгебраическая система , гдесостоит из одной двухместной операции, как правило, операция умножения называется группоидом .
Операцию умножения не следует отождествлять с арифметической операцией умножения. Эту операцию можно выполнять над любыми двумя элементами V, причем эта операция не выходит за границы этого множества.
В случае конечного M группоид часто задают с помощью таблиц Кэли.
Пример:
Представим группоид таблицей Кэли:
, где (1)
0 |
1 |
2 |
3 |
4 | |
0 |
0 |
1 |
2 |
0 |
1 |
1 |
1 |
2 |
0 |
1 |
2 |
2 |
2 |
0 |
1 |
2 |
0 |
3 |
0 |
1 |
2 |
0 |
1 |
4 |
1 |
2 |
0 |
1 |
2 |
Примерыгруппоидов:
Множество всех целых чисел относительно операции вычитания. В то же время натуральные числа не образуют группоида относительно операции вычитания.
Группоид (1) называется идемпотентным, если
(2)
Группоид (1) называется коммутативным, если
(3)
Понятие группы.
Если для любых элементов группоида (1) имеет место ассоциативный закон:
(4),
то группоид U называется полугруппой или моноидом.
Если полугруппа обладает коммутативным свойством, т.е. ,
то полугруппу называют абелевой.
Группой называется алгебра (1),удовлетворяющая следующим условиям:
1)ассоциативности
2)существование нейтрального элемента или единичного элемента
3)существование обратного элемента
Условия (1), (2), (3) часто называют аксиомами группы.
Если дополнительно к этим условиям выполняется условие
4) коммутативности
,
то группу называют коммутативной или абелевой.
Пусть группоид задан таблицей Кэли
a |
b |
c | |
a |
b |
c |
a |
b |
c |
a |
b |
c |
a |
b |
c |
Операция
1) ассоциативна
2) существует нейтральный элемент (в данном случае с)
3) для каждого элемента существует обратный элемент
Следовательно, рассмотренный группоид является абелевой группой, так как таблица Кэли симметрична относительно главной диагонали.
Группа называется конечной, если множество А конечно, в противном случае - бесконечной.
Число элементов в конечной группе называют ее порядком.
Кольца. Тела и поля.
Кольцом называется алгебра с двумя операциями, обладающими следующими свойствами:
Двойка есть абелева группа, нулевой элемент которой
Двойка -подгруппа
Операция дистрибутивна операции +, т.е.
Примером кольца может служить множество чисел, в котором выполняются операции сложения и умножения.
Кольца, в которых для всех отличных от нуля элементов, существуют обратные, называемые телами, иначе говоря, кольцо называется телом, если множество А, отличных от нуля элементов.
образует группу относительного умножения. В этом случае говорят, что в теле заданы 2 группы:
1) аддитивная
2)мультипликативная
Если мультипликативная группа абелева, то тело называется коммутативным, или полем.
Изоморфными называются объекты, которые имеют одну и ту же форму, одинаковое назначение и выполняют одинаковую функцию.
Два группоида , называются изоморфными между собой, если существует взаимно однозначная функциятакая, что.
Обобщением понятия изоморфизма является понятие гомоморфизма.
Отображение f группоида на группоид называется гомоморфизмом, если.
От гомоморфизма не требуется взаимнооднозначного соответствия, хотя любой изоморфизм называется гомоморфизмом.