- •Содержание:
- •Тема 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. Решение задач с помощью динамических двоичных функций. Синтез логической схемы, реализующей заданную булеву функцию, с использованием блоков исключения одной переменной.
Формулы. Реализация функций формулами. Равносильные формулы. Принцип двойственности.
Пусть F = {f1,f2,…,f2n} – множество булевых функций. Формулой надFназывается выражение вида:f[F] =f(t1,t2,…,tn),fF,ti– либо переменная, либо формула надF. МножествоF– базис, функцияf– главная (внешняя) функция (операция),ti– подформулы. Обычно для элементарных булевых функций используют инфиксную форму записи. Устанавливают следующий приоритет:, &,,.отрицание или инверсия, & – конъюнкция,дизъюнкция,импликация. Всякой формулеFоднозначно соответствует функцияf. Это соответствие задается алгоритмом интерпретации, который позволяет вычислить значение формулы при заданных значениях переменных. Зная таблицы истинности для функций базиса, можно вычислить таблицы истинности той функции, которую реализует данная формула.
Пример.Задана формулаF1:= (x1&x2)((x1& )(&x2)).
Таблица истинности:
x1 |
x2 |
x1 & |
& x2 |
(x1 & ) ( & x2) |
x1 & x2 |
F1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
Т.о. формула F1реализует дизъюнкцию.
Одна функция может иметь множество реализаций над базисом. Формула, реализующая одну и ту же функцию, называется равносильной. Отношение равносильностей формул является эквивалентностью.
Имеют место следующие равносильности:
1. | |
2. | |
3. | |
4. | |
5. | |
6. | |
7. | |
8. |
|
9. | |
10. |
Принцип двойственности.Пустьf(x1,…,xn)Pn– булева функция. Тогдаf*(x1,…,xn)(с чертой сверху) =f*(x1,…,xn)называется двойственной функциейf.f** =f.
Дизъюнктивная нормальная форма.
Элементарной конъюнкцией называется такая формула A, которая является конъюнкцией, возможно одночленной, переменных и их отрицаний. Говорят, что формулаAнаходится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией, возможно одночленной, элементарных конъюнкций. ДНФ:A = x1·x2x1· .
Теоремао приведении формулы к ДНФ.AB, находящаяся в ДНФ, чтоAB.B называется ДНФА.
Доказательство:В качестве доказательства приводят алгоритм построения ДНФ формулыА.
1.С помощью основных равносильностей, которые позволяют устранить операции импликации и эквивалентности, строят. При этомА1не содержит операций импликации и эквивалентности.
Основные равносильности:
1);
2);
3);
4);
5);
6);
7);
8)
2.ОтА1переходят кА2, в которой отрицание только перед переменной1)A1A
2)
Полученная А2равносильнаАи состоит из многочисленных конъюнкций и дизъюнкций. КА2применяют формулу дистрибутивности конъюнкции относительно дизъюнкции. ПолучимА3, находящуюся в дизъюнктивной нормальной форме.
Конъюнктивная нормальная форма.
Аназывается элементарной дизъюнкцией, если она состоит из переменных и их отрицаний, связанных операцией дизъюнкции. Говорят, чтоАнаходится в КНФ, если она представляет собой конъюнкцию, возможно одночленную, элементарных дизъюнкций. КНФ:A=x1& (x2) & (x1).
Теоремао приведении к КНФ.ABA, находящаяся в КНФ.B называется КНФА.
Доказательство: Аналогично теореме 1. Применяют обобщенные законы Де Моргана, чтобы привести операции отрицания к переменным. Применяют формулы дистрибутивности дизъюнкции относительно конъюнкции.A3Aи находится в КНФ.
Тема 3. Полиномы Жегалкина. Cуществование и единственность представления булевой функции полиномом Жегалкина (теорема Жегалкина). Теоремы о полноте системы функций алгебры логики. Пять классов булевых функций: линейные функции; функции, сохраняющие нуль; функции, сохраняющие единицу; монотонные функции; самодвойственные функции. Функционально полные системы логических функций. Примеры функционально полных базисов. Минимизация булевых функций.
Конечное множество булевых функций называютсистемой булевых функций. Систему булевых функций называют полной, если любая булева функция может быть выражена в виде формулы над этой системой (другими словами, если она представима через функции данной системы).
Примером полной системы является так называемый стандартный базис, содержащий дизъюнкцию, коньюнкцию и отрицание: . Полнота этой системы легко доказывается тем, что любая булева функция может быть представлена в виде ДНФ или КНФ. А учитывая, чтои, полными являются даже системыи.
Другой распространённой полной системой булевых функций является базис Жегалкина: , включающий исключающее или, коньюнкцию и константу 1.Можно доказать, что любая булева функция представима в виде так называемого полинома Жегалкина:
где . В частном случае, полином Жегалкина имеет линейный вид:
Булева функция, представимая в виде линейного полинома Жегалкина, называется линейной.
Существует простой способ выражения любой булевой функции над базисом Жегалкина. Этот способ носит название метода неопределённых коэффициентов. Рассмотрим этот метод на примере:
Рассмотрим функцию . В общем виде полином Жегалкина для этой функции имеет вид:
Вычислим все коэффициенты начиная с , последовательно подставляя в полином известные значения функции:
Таким образом, функция имеет вид:
и не является линейной.