- •Введение
- •1. Теория множеств
- •1.1. Основные понятия
- •1.2. Операции над множествами
- •1.3. Алгебраические свойства операций над множествами
- •1.4. Нечёткие множества
- •2. Элементы комбинаторики
- •2.1. Основные правила комбинаторики
- •2.2. Выборки элементов без повторений
- •2.3. Выборки элементов с повторениями
- •2.4. Объединение комбинаторных конфигураций
- •2.5. Бином Ньютона
- •3. Отношения на множествах
- •3.1. Декартово произведение множеств
- •3.2. Булев куб и его свойства
- •3.3. Понятие отношения
- •3.4. Операции над отношениями
- •3.5. Свойства отношений на множестве
- •3.6. Отношения эквивалентности, толерантности и порядка
- •3.7. Нечеткие отношения
- •3.8. Понятие отображения
- •3.9. Алгебраическая операция
- •3.10. Общие сведения об алгебраических системах
- •4 Булевы функции
- •4.1. Основные определения и операции над высказываниями
- •4.2. Типы пф.
- •4.3. Равносильность формул
- •4.4. Дизъюнктивные и конъюнктивные нормальные формы
- •4.5 Алгоритм приведения пф к нормальным формам
- •4.6 Аналитический способ приведения к сднф
- •4.7. Табличный способ приведения к сднф
- •4.8. Табличный способ приведения к скнф
- •4.9. Логическое следствие
- •4.10. Алгоритм проверки правильности рассуждений
- •4.11. Алгоритм определения всех логических следствий из данных посылок
- •4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
- •4.13. Полнота систем булевых функций
- •4.14. Полином Жегалкина
- •4.15. Замкнутость
- •4.16. Теорема Поста
- •4.17. Нечеткая логика
- •5. Многозначные функции
- •5.1. Функции и формулы k-значной логики
- •5.2. Полнота и замкнутость функций k-значной логики
- •5.3. Особенности k – значной логики
- •6.. Основные понятия теории графов.
- •6.1. Задачи теории графов.
- •6.2. Основные определения.
- •6.3. Степени вершин графа.
- •6.4. Изоморфизм графов.
- •6.5. Матричные способы задания графов.
- •6.6. Основные операции над графами.
- •6.7. Маршруты в графах
- •6.8. Связность в графах.
- •Связность и матрица смежности графа.
- •6.9. Матрица взаимодостижимости.
- •6.10. Деревья Свободные деревья.
- •Ориентированные, упорядоченные и бинарные деревья.
- •6.11. Эйлеровы графы.
- •6.12 Гамильтоновы графы.
- •6.13. Планарные графы.
- •6.14. Потоки в сетях. Основные определения.
- •Теорема Форда и Фалкерсона.
- •Алгоритм построения максимального потока в сети.
- •7. Конечные автоматы
- •7.1. Понятие конечного автомата Общие сведения о конечных автоматах
- •7.2. Абстрактное определение конечного автомата
- •7.3. Автоматная функция и её моделирование Понятие ограниченно детерминированной функции
- •Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •7.4. Эксперименты с автоматами
- •8. Рекуррентные уравнения
- •8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
- •8.2. Решение линейного неоднородного рекуррентного уравнения
- •8.3. Решение рекуррентного уравнения для чисел Фибоначчи
- •Заключение
- •Библиографический список
- •Оглавление
- •1.Теория множеств 5
- •2 Элементы комбинаторики 14
- •3 Отношения на множествах 22
- •4. Булевы функции 42
- •5. Многозначные функции 64
- •6. Основные понятия теории графов 70
- •7. Конечные автоматы 106
- •8. Рекуррентные уравнения 120
- •394026 Воронеж, Московский просп., 14
3.9. Алгебраическая операция
Отображение
f:
An
A
называется n-местной
алгебраической операцией
на множестве A.
Очевидно, что n-местная
алгебраическая операция на множестве
A
является
(
)
– местным отношением на множестве A.
При
операция f:
A0
A
есть {(,
a)}
для некоторого
aA.
Эта операция называется константой
на множестве A
и отождествляется с некоторым элементом
a
этого
множества.
При
операция
f
называется унарной,
а при
- бинарной.
Примерами унарных операций являются:
Элементарные функции одного аргумента -
и другие;Операция над множествами – дополнение
;Операции над отношениями – дополнение
,
обратное отношение
,
составное отношение
и другие.
Примерами бинарных операций являются:
Арифметические операции – сложение, вычитание, умножение, деление, возведение в степень.
Операции над множествами – пересечение, объединение и разность.
Операция композиции функций, отображений, отношений.
Обозначим
символом ┬
произвольную бинарную алгебраическую
операцию. Тогда операция над элементами
,
дающая результат
записывается в виде a┬b
= c.
Свойства бинарных операций:
Ассоциативность - (a┬b)┬с = a┬(b┬с). (Выполнение этого условия означает, что скобки в этом выражении можно не расставлять.)
Коммутативность - a┬b= b┬a.
дистрибутивность - a┬(b┴c)=(a┬b)┴(a┬c) - дистрибутивность операции ┬ слева относительно операции ┴ и (a┴b)┬c=(a┬c)┴(b┬c) – дистрибутивность операции ┬ справа относительно операции ┴
Способы задания операций
Унарные операции задаются:
Перечнем всех аргументов
и соответствующих им значений
:
Таблица 9
-
f=
Списком всех пар “аргумент – значение” для всех возможных значений аргументов: f={
}.Формулой
,
например
.
Бинарные операции задаются:
Таблицей (таблица Кэли). Слева и сверху таблицы выписываются все значения аргументов, а на пересечении строк и столбцов – результат операции. Например, для операции “сложение по модулю 3” на множестве {0,1,2} имеет следующий вид:
Таблица 10
|
0 |
1 |
2 |
0 |
0 |
1 |
2 |
1 |
1 |
2 |
0 |
2 |
2 |
0 |
1 |
Списком, путем перечисления всех троек
.
Например, для предыдущей операции:
{(0,0,0),
(0,1,1), (0,2,2), (1,0,1), (1,1,2), (1.2,0), (2,0,2), (2,1,0),
(2,2,1)}
Формулой
или ab=
c. Например:
,
где
- операция сложения по модулю 3.
3.10. Общие сведения об алгебраических системах
Алгебраическая
система – это множество с определенными
на нем операциями и отношениями.
Алгебраическая
система –
это объект A
,
где
- непустое множество,
- семейство алгебраических операций, а
- семейство отношений, заданных на
множестве
.
Множество
называется носителем
алгебраической системы, а его элементы
– элементами системы. Алгебраическая
система называется конечной,
если множество
конечно.
Множества
всех главных операций и отношений в
называется сигнатурой
в
.
Алгебраическая система называется
универсальной
алгеброй,
если множество ее отношений пусто
,
и называется реляционной
системой
или моделью,
если пусто множество основных операций
.
Пусть
A
- алгебраическая система, в которой
,
причем
есть
арная
операция, а
есть
местное
отношение. Тогда последовательность
целых чисел
называется типом
алгебраической системы
A.
Пусть
A
и B
- две алгебраические системы одного и
того же типа. Отображение
,
называется гомомофизмом
системы A
в систему B,
если выполняются следующие условия:
и
для
всех
и
.
Если
- гомоморфизм, то его обозначают
AB.
Гомоморфизм
AB
являющийся инъекцией, называется
мономорфизмом.
Гомоморфизм
AB,
являющийся сюръекцией, называется
эпиморфизмом
и при этом система B
называется гомоморфным
образом
системы A.
Гомоморфизм
A
A называется
эндоморфизмом.
Сюръективный мономорфизм
AB,
для которого
гомоморфизм, называется изоморфизмом
и обозначается
AB.
Изоморфизм
AA
называется автоморфизмом
системы A.
Понятие изоморфизма – одно из важнейших понятий в современной математике. При изоморфизме сохраняются действие всех основных операций и отношений. Это позволяет переносить изучение свойств с одной системы на другую.
