- •Содержание:
- •Тема 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. Решение задач с помощью динамических двоичных функций. Синтез логической схемы, реализующей заданную булеву функцию, с использованием блоков исключения одной переменной.
Операции над множествами.
Самого понятия множество недостаточно, следует определить способы конструирования новых множеств из уже имеющихся, т.е. задать операции над множествами.
Множество A содержится в множестве B (множество B включает множество A), если элемент множества A есть элемент множества B. AB:=xA=>xB. В этом случае A называют подмножеством B, а B – надмножеством A.
Обычно рассматривают следующие операции над множествами:
1. Объединение AB := { x | xAxB}
2. Пересечение AB:= { x | xA & xB}
3. Разность A \ B := { x | xAxB}
4. Симметричная разность AB:=(AB) \ (AB)
5. Дополнение :={ x | x A }Операция Дополнение подразумевает некоторый универсумU: :=U\A
Свойства теоретико-множественных операций. Представление множеств в эвм.
Пусть задан универсум U, тогда для любых множествA,B,C, являющихся подмножествомUвыполняются следующие свойства:
1) Идемпотентность: A A = A ! A A =A.
2)Комутативность:AB=BA! AB=BA.
3) Ассоциативность: A(BC) = (AB)C ! A(BC)=(AB)C.
4) Дистрибутивность: A(BC)=(AB)(AC) ! A(BC)=(AB)(AC).
5) Поглощение: (AB)A=A ! (AB)A=A.
6) Свойство нуля: A =A ! A=.
7)Свойство единицы:AU=U! AU=A.
8)Инволютивность: !!А = А.
9)Законы де Моргана: =! =.
10)Свойства дополнения:A=U! A=.
11)Свойство разности:A\B=A
В справедливости этих свойств можно убедиться различными способами, например нарисовать диаграммы Эйлера для левой и правой частей равенства и убедиться, что они совпадают, или же привести формальное рассуждение для каждого равенства.
Упорядоченные пары. Прямое произведение множеств. Отношения. Многоместные отношения. Композиция отношений. Степень отношений. Ядро отношения. Свойства отношений. Представление отношений в ЭВМ.
Упорядоченные пары. Декартово (прямое) произведение множеств. Отношения.
В предыдущем разделе операции над множествами давали множества той же природы. Например, если исходные множества были множествами чисел, то и полученные в результате операций множества были множествами чисел. В этом разделе мы определим операцию, с помощью которой меняется природа элементов получающихся множеств.
Упорядоченной парой (набор длинны 2) из элементов aиb(a,b), взятых именно в этом порядке, называется множество, состоящее из двух множеств, включающих элементa: {a},{a,b}.
(a,b)= {{a},{a,b}}
Таким образом, понятие упорядоченной пары не выводит рассмотрение за пределы теории множеств. Но тем не менее независимое определение упорядоченной пары технически удобнее. Исходя из приведенного определения , доказывается справедливость следующей леммы:
Лемма:упорядоченные пары (a,b) и (c,d) равны тогда и только тогда, когда выполняется условие: (a,b) = (c,d) | a = с & b = d
Пусть А и В – два множества. Прямым (декартовым) произведением двух множеств А и В называется множество упорядоченных пар, в котором первый элемент каждой пары принадлежит множеству А, а второй множеству В.
Обозначают: АВ := {(а,b) | а А & bB}
Степенью множества А называется его прямое произведение самого на себя.
Соответственно: А1:=A;А2:=AA;А3:=AA2; и вообще Аn:=AAn-1
Теорема:|АВ| = |А| |В|
Доказательство:
Первый компонент упорядоченной пары можно выбрать |А|способами:|А|- число элементов множестваА;|В|- число элементов множестваВ.
Таким образом, всего имеется |А|·|В|упорядоченных пар.
Пример: А= {1,2,3}, |A| = 3;B= {4,5}, |B| = 2;
|АВ| = |А| |В|= 3·2 = 6;
|АВ|= |{(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)}| = 6;
Пусть А и В – два множества. Бинарным отношением Rиз множества А в множество В называется подмножество прямого произведения:R A B.
Для бинарных отношений обычно используется инфиксная форма записи:
a R b: (a,b) R A B.
если А=В, то говорят, чтоRесть отношение на множествеА.