- •Содержание:
- •Тема 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. Решение задач с помощью динамических двоичных функций. Синтез логической схемы, реализующей заданную булеву функцию, с использованием блоков исключения одной переменной.
1.3.Строение простого алгебраического расширения поля.
Теорема 1.5. Пусть a — алгебраический над полем P элемент положительной степени n. Тогда любой элемент поля P(a) однозначно представим в виде линейной комбинации n элементов 1, a, ..., an-1 с коэффициентами из Р.
Доказательство. Пусть — любой элемент поля P (a). По теореме 1.4, P(a) = P[a]; следовательно, существует в P[x] полином f такой, что
(1) = f(a).
Пусть g — минимальный полином для a над P; в силу условия теоремы его степень равна п. По теореме о делении с остатком, существуют в P[x] полиномы h и r такие, что
(2) f = gh + r, где r = 0 или der r < der g = n , т. е. r=c0+c1x +…cn-1xn-1 (ciP). Полагая в (2) x = а и учитывая равенство (1), имеем
(3) = c0+c1a +…cn-1an-1
Покажем, что элемент однозначно представим в виде линейной комбинации элементов 1, a, ..., an-1. Пусть
(4) = d0+d1a +…dn-1an-1 (di P)
—любое такое представление. Рассмотрим полином
= (с0 – d0) + (c1 - di.)x + . . . + (сn-1 –dn-1)xn-1
Случай, когда степень меньше n, невозможен, так как в силу (3) и (4) (a) = 0 и степень меньше степени g. Возможен лишь случай, когда = 0, т. е. с0 = d0, . . . , сn-1 = dп-1. Следовательно, элемент однозначно представим в виде линейной комбинации элементов 1, a,…,an-1.
1.4.Освобождение от алгебраической иррациональности в знаменателе дроби.
Задача об освобождении от алгебраической иррациональности в знаменателе дроби состоит в следующем. Пусть a — алгебраический элемент степени n>1 над полем P; f и h — полиномы из кольца полиномов P [x]и h(a) 0. Требуется представить элемент f(a)/h(a)0P(a) в виде линейной комбинации степеней элемента a, т. е. в виде (a),
где 0P[x].
Эта задача решается следующим образом. Пусть g — минимальный полином для a над P. Так как, по теореме 1.4, полином неприводим над P и h(a) 0, то g не делит h и, значит, полиномы h и g — взаимно простые. Поэтому существуют в P[x] такие полиномы u и v, что
uh+vg=1 (1)
Поскольку g(a) = 0, из (1) следует, что
u(a)g(a) = 1, 1/h(a) = u(a).
Следовательно, f(a)/h(a) = f(a)u(a), причем f,u 0P[x] и f(a)u(a)0P[a]. Итак, мы освободились от иррациональности в знаменателе дроби f(a)/h(a) .
Пример.
Освободиться от иррациональности в знаменателе дроби
.
Решение. В нашем случае =. Минимальным многочленом этого числа является
p(x)=x3-2.
Многочлены p(x) и g(x)=-x2+x+1 взаимно просты. Поэтому существуют такие многочлены и , что
p+g=1.
Для отыскания и применим алгоритм Евклида к многочленам p и g:
-x3-2 -x2+x+1 -x2+x+1 2x-1
x3-x2-x -x-1 -x2+1/2x -1/2x+1/4
x2+x-2 1/2x+1
x2-x-1 1/2x-1/4
2x-1 5/4
Таким образом,
p=g(-x-1)+(2x-1),
g=(2x-1)(-1/2x+1/4)+5/4.
Откуда находим
(2x-1)=p+g(x+1),
5/4=g-(p+g(x+1))(-1/2x+1/4)
или
p1/5(2x-1)+g(4/5+1/5(2x2+x-1))=1,
p1/5(2x-1)+g(2/5x2+1/5x+3/5)=1.
Таким образом,
(x)= (2/5x2+1/5x+3/5).
Тогда
y()=y()=.
Следовательно
.