- •Содержание:
- •Тема 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. Решение задач с помощью динамических двоичных функций. Синтез логической схемы, реализующей заданную булеву функцию, с использованием блоков исключения одной переменной.
3. Сепарабельные и несепарабельные расширения.
Пусть — поле.
Выясним, может ли неразложимый в [x] многочлен обладать кратными корнями?
Для того чтобы f(x) обладал кратными корнями, многочленыf(x)иf(x)должны иметь общий отличный от константы множитель, который можно вычислить уже в[x]. Если многочленf(x)неразложим, то ни с каким многочленом меньшей степениf(x)не может иметь непостоянных общих множителей, следовательно, должно иметь место равенствоf '(x)= 0.
Положим
n n
f(x) =ax f(x) =ax-1
0 1
Так как f(x)= О, в нуль должен обращаться каждый коэффициент:
a = 0 ( = l, 2, ..., n).
В случае характеристики нуль отсюда следует, что a= 0 для всех0. Следовательно, непостоянный многочлен не может иметь кратных корней. В случае же характеристикиpравенстваa= 0 возможны и для0, но тогда обязаны выполняться сравнения
0(p).
Таким образом, чтобы многочлен f(x) обладал кратными корнями, все его слагаемые должны обращаться в нуль, за исключением техax, для которых0(p), т. е.f(x)должен иметь вид
f(x) = a0+apxp+a2px2p+…
Обратно: еслиf(x)имеет такой вид, тоf(x)=0.
В этом случае мы можем записать:
f(x) = (xp).
Тем самым доказано утверждение:В случае характеристики нуль неразложимый в [x] многочлен f (x) имеет только простые корни, в случае оке характеристики p многочлен f(x) (если он отличен от константы) имеет кратные корни тогда и только тогда, когда его можно представить как многочлен от xp.
Тема 6. Многозначные логики. Возникновение и формализация модальных логик. Применение многозначных логик. Основные понятия
Пусть Еk={0,1,...,k-1}. Функцияназывается функциейk-значной логики, если на всяком наборезначений переменных, где, значениетакже принадлежит множествуЕk. Совокупность всех функцийk-значной логики обозначаетсяPk.
,
Элементарные функции k-значной логики:
константы0,1,...,k-1 ;
отрицание Поста:(modk); отрицание Лукашевича: ~x= (k-1)-x;
характеристические функции числаi:
минимум xиy: min(x,y);максимум xиy: max(x,y);
сумма по модулюk:x+y(modk);произведение по модулюk:x y(mod k);
усеченная разность:
импликация:
функция Вебба:vk(x,y) = max(x,y)+1 (modk);
разность по модулю k:
Функции min, max, + ,обладают свойствами коммутативности и ассоциативности. Кроме того, справедливы соотношения:
Вводятся по определению:
Любую функцию из Рkможно представить в первой форме:
.
Любую функцию из Рkможно представить во второй форме:
,
где сложение и умножение берется по modk.
ЗАДАЧИ
6.1. Подсчитать число функций вРk(1), принимающих не болееk-1 значений от одной переменной.
6.2. Доказать следующие соотношения:
6.3. Представить функциюI k-2(x) в виде суперпозиции функций
6.4. Доказать справедливость следующих соотношений:
6.5. Представить функцию fпервой форме:
Полные системы функций:
система Поста: {};
система Россера-Туркетта:{}.
6.6. Cведением к заведомо полным системам доказать полноту систем функций:
1) {}; 2) {};
3) {1, x2-y, min(x,y)}; 4) {k-2,x+y, (~x)2y}
6.7. Доказать, что функция Вебба обладает свойством: [{v k(x,y)}] =Pk.
6.8. Является ли полной вРkсистема функций
6.9.Выяснить, полна ли вР3система: