- •Содержание:
- •Тема 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. Решение задач с помощью динамических двоичных функций. Синтез логической схемы, реализующей заданную булеву функцию, с использованием блоков исключения одной переменной.
Многоместные отношения. Композиция отношений. Степень и ядро отношений.
n-местным отношением называется любое подмножество множества Аn, где А- произвольное множество,n1. Двухместное отношение называют бинарным.
Многоместное отношение используется, например, в теории баз данных.
Пример: R A1 A2 … An = {(a1, a2, … ,an) | a1 A1 & a2 A2 & … an An}.
A1=A2= … =An=A
Пусть R1 A C, а R2 C B. Композицией двух отношенийR1иR2называется отношениеR A Вопределяемое следующим образом:
R := R1R2 := {(а,b) | a A & b B & c C & aR1c & cR2b}
Композиция отношений на множестве Аявляется отношением на множествеА.
Степень и ядро отношений.
Пусть R– отношение на множествеА. Степенью отношенияRна множествеАназывается его композиция с самим собой.Rn :=R·…·R
Соответственно: R0 = 1;R1 = R;R2 = R·R и вообще Rn = R·Rn-1
Если R– отношение изАвВ, то естьRA B, то композиция отношенияR ·R-1называется ядром отношенияR.
Ядро отношения RизАвВявляется отношением наА.
Свойства отношений. Представление отношений в эвм.
Пусть R– есть отношение на множествеА:R A А | a,b A
Введем следующие понятия: 1)обратное отношение:R-1:={(a,b)|(a,b)R};2)дополнение отношения: := {(a,b)|(a,b)R};3)тождественно отношение:I:= {(a,a)|aR};4)универсальное отношение:U := {(a,b) | aA & bA}.
Замечание: пусть R– отношение на множествеА (R А2),тогда:
отношение Rназывается рефлексивным, если аА, аRа
Если аА, -аRа, то такое отношениеRназывают антирефлексивным.
Если а,bА, аRb bRа. Такое отношениеRназывают симметричным.
Если а,bА, аRb & bRа a=b. Такое отношениеRназывают антисимметричным.
Если а,b,сА, аRb & bRс аRс. Такое отношениеRназывают транзитивным.
Если а,bА, аb aRb bRa.Такое отношениеRназывают полным (линейным).
Теорема:пустьR– отношение на множествеА, то естьR A А, тогда: __отношениеRрефлексивно тогда и только тогда, если тождественное отношение включается во множествоR. __отношениеRсимметрично тогда и только тогда, когдаR = R-1(равно обратному отношению). __отношениеRтранзитивно тогда и только тогда, когда композиция отношенийR·RR(включается в отношениеR). __отношениеRантисимметрично тогда и только тогда, когда пересечение отношенияRс обратным отношением включается в тождественное отношение:RR-1 I.
__отношение Rантирефлексивно тогда и только тогда, когда пересечение отношенияRс тождественным отношениемIобразует пустое множество:R I =. __отношениеRполно тогда и только тогда, когда объединение отношенияRс тождественным отношениемIи с обратным отношением образует полное отношениеU:
R I R-1 = U.
Представление отношений в ЭВМ.
Пусть R– отношение наА (R A A)и |А|=n, тогда отношениеRможно представить матрицейR: array[1…n,1…n]of0…1, где
Матрица ||R|| - матрица отношений.
Тема 2. Высказывательные формы. Функции алгебры логики. Основные понятия и определения. Способы задания булевых функций. Таблица истинности. Существенные и несущественные переменные. Булевы функции одной и двух переменных. Формулы. Реализация функций формулами. Равносильные формулы. Специальные разложения БФ.
Переключательные функции. Существенные и несущественные переменные. Булевы функции одной переменной. Булевы функции двух переменных.
Функции вида f :E2nE2, гдеE2= {0;1} – функции алгебры логики или булевы функции. Множество булевых функций отnпеременных обозначимpnиpn:= {f |f:E2nE2}. Булеву функцию отnпеременных можно задать таблицей истинности.
x1 |
… |
xn–1 |
xn |
f(x1,…,xn) |
0 |
… |
0 |
0 |
|
0 |
… |
0 |
1 |
|
0 |
… |
1 |
0 |
|
… |
… |
… |
… |
|
1 |
… |
1 |
1 |
|
Если число переменных n, то в таблице истинности имеется 2nстрок, соответствующих всем различным комбинациям значений переменных, которым можно сопоставить 22^nразличных столбцов, соответствующих различным функциям. Т.о. число булевых функций отnпеременных |pn| = 22^n. Булева функцияf pnсущественно зависит от переменнойxi, если существует такой набор значенийa1,a2,…,ai–1,ai+1,…,an–1,an, что выполняется условиеf(a1,a2,…,ai–1,ai+1,…,an–1,an)f(a1,a2,…,ai–1, 1,ai+1,…,an–1,an). В этом случаеxi– существенная переменная, в обратном случаеxi– несуществующая (фиктивная) переменная.
Пример.Пусть булевы функцииf1(x1,x2);f2(x1,x2) заданы следующей таблицей истинности:
x1 |
x2 |
f1 |
f2 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
Для этих функций переменная x1 – существенная, аx2 – несущественная. По определению булевы функции равны, если одна из другой получается введением (или удалением) несущественных переменных.
Булевы функции одной переменной представим в виде таблицы.
Переменная х |
0 |
1 |
| |
Название |
Обозначение |
|
|
Фиктивные |
нуль |
0 |
0 |
0 |
x |
тождественная |
x |
0 |
1 |
|
отрицание |
x,x,x' |
1 |
0 |
|
единица |
1 |
1 |
1 |
|
Булевы ф-ции 2-х переменных описаны в книге.