- •Введение
- •1. Теория множеств
- •1.1. Основные понятия
- •1.2. Операции над множествами
- •1.3. Алгебраические свойства операций над множествами
- •1.4. Нечёткие множества
- •2. Элементы комбинаторики
- •2.1. Основные правила комбинаторики
- •2.2. Выборки элементов без повторений
- •2.3. Выборки элементов с повторениями
- •2.4. Объединение комбинаторных конфигураций
- •2.5. Бином Ньютона
- •3. Отношения на множествах
- •3.1. Декартово произведение множеств
- •3.2. Булев куб и его свойства
- •3.3. Понятие отношения
- •3.4. Операции над отношениями
- •3.5. Свойства отношений на множестве
- •3.6. Отношения эквивалентности, толерантности и порядка
- •3.7. Нечеткие отношения
- •3.8. Понятие отображения
- •3.9. Алгебраическая операция
- •3.10. Общие сведения об алгебраических системах
- •4 Булевы функции
- •4.1. Основные определения и операции над высказываниями
- •4.2. Типы пф.
- •4.3. Равносильность формул
- •4.4. Дизъюнктивные и конъюнктивные нормальные формы
- •4.5 Алгоритм приведения пф к нормальным формам
- •4.6 Аналитический способ приведения к сднф
- •4.7. Табличный способ приведения к сднф
- •4.8. Табличный способ приведения к скнф
- •4.9. Логическое следствие
- •4.10. Алгоритм проверки правильности рассуждений
- •4.11. Алгоритм определения всех логических следствий из данных посылок
- •4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
- •4.13. Полнота систем булевых функций
- •4.14. Полином Жегалкина
- •4.15. Замкнутость
- •4.16. Теорема Поста
- •4.17. Нечеткая логика
- •5. Многозначные функции
- •5.1. Функции и формулы k-значной логики
- •5.2. Полнота и замкнутость функций k-значной логики
- •5.3. Особенности k – значной логики
- •6.. Основные понятия теории графов.
- •6.1. Задачи теории графов.
- •6.2. Основные определения.
- •6.3. Степени вершин графа.
- •6.4. Изоморфизм графов.
- •6.5. Матричные способы задания графов.
- •6.6. Основные операции над графами.
- •6.7. Маршруты в графах
- •6.8. Связность в графах.
- •Связность и матрица смежности графа.
- •6.9. Матрица взаимодостижимости.
- •6.10. Деревья Свободные деревья.
- •Ориентированные, упорядоченные и бинарные деревья.
- •6.11. Эйлеровы графы.
- •6.12 Гамильтоновы графы.
- •6.13. Планарные графы.
- •6.14. Потоки в сетях. Основные определения.
- •Теорема Форда и Фалкерсона.
- •Алгоритм построения максимального потока в сети.
- •7. Конечные автоматы
- •7.1. Понятие конечного автомата Общие сведения о конечных автоматах
- •7.2. Абстрактное определение конечного автомата
- •7.3. Автоматная функция и её моделирование Понятие ограниченно детерминированной функции
- •Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •7.4. Эксперименты с автоматами
- •8. Рекуррентные уравнения
- •8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
- •8.2. Решение линейного неоднородного рекуррентного уравнения
- •8.3. Решение рекуррентного уравнения для чисел Фибоначчи
- •Заключение
- •Библиографический список
- •Оглавление
- •1.Теория множеств 5
- •2 Элементы комбинаторики 14
- •3 Отношения на множествах 22
- •4. Булевы функции 42
- •5. Многозначные функции 64
- •6. Основные понятия теории графов 70
- •7. Конечные автоматы 106
- •8. Рекуррентные уравнения 120
- •394026 Воронеж, Московский просп., 14
4.14. Полином Жегалкина
Так как формула, построенная в системе 6) состоит из констант 0, 1 и функций x1,x2 и x1x2, то после раскрытия скобок выражение формулы переходит в полином по модулю 2 (полином Жегалкина).
Теорема. Каждая функция из P2 может быть выражена при помощи полинома по модулю 2. Т.е. в виде ƒ(x1,x2,…,xn) = xi1 ∙ xi2 ∙∙∙ xin с, где в каждом наборе (i1, i2,…,in) все ik (k=1,…,n) различны и суммирование ведется по несовпадающему набору значений . Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка следования слагаемых.
Полином Жегалкина называется нелинейным, если он содержит произведения переменных, и линейным – если он их не содержат.
Для получения полинома Жегалкина булевой функции используются аксиомы булевой алгебры и равенства, выражающие операции отрицания, , через операции , ⊙.
x̅ = x 1, x y = xy, xy = x y xy
Можно доказать тождества:
1) x y = y x; x ∙ y = y ∙x
2) (x y) z = x (y z); (x ∙ y) ∙ z = x ∙ (y ∙ z)
3) x x = 0; x ∙x = x
4) x (y z) = x y x z
5) 0 x = x
6) 0 ∙ x = 0
7) 1 ∙ x = x
8) x x̅ = 1
9) x ∙ x̅ = 0
Пример. Определить полином Жегалкина для функции
ƒ (x, y, z) = x̅ y̅ z x̅yz x y̅ z̅.
Используя выше приведенные формулы, получим: ƒ (x, y, z) = (x̅ y̅ z x̅yz x̅ y̅z x̅yz) x y̅ z̅ = (x̅ y̅ z x̅yz) x y̅ z̅ = x̅ y̅z x̅yz x y̅ z̅) (x̅ y̅ z x̅yz) x y̅ z̅ = x̅ y̅ z x̅yz x y̅ z̅ x̅ y̅z x y̅ z̅ x̅yz x y̅ z̅ = x̅ y̅ z x̅yz x y̅ z̅ = x̅z (y y̅) x y̅ z̅ = x̅ z̅ ∙ 1 x y̅ z̅ = x̅ z̅ x y̅ z̅ = (x 1) z x (y 1) (z 1) = xz z (xy x) (z 1) = xz z xyz xz xy x = x z xy xyz - полином Жегалкина
Заметим, что если в эквивалентности ψ = ψ ψ формулы и ψ являются различными конституентами единицы, то их произведения ψ = 0. Тогда ψ = ψ. Следовательно, для получения полинома Жегалкина из совершенной ДНФ можно сразу заменить на .
4.15. Замкнутость
Пусть A – некоторое подмножество функций из P2. Замыканием A называется множество тех булевых функций, которые представимы в виде формул через функции множества A. Замыкание множества A обозначается [A]. Заметим, что замыкание инвариантно относительно операций введения и удаления фиктивных переменных.
Примеры: 1) A = P2, т. к. [A] = P2;
2) A = {1, x1 x2}. Замыканием этого множества будет класс L всех линейных функций, имеющих вид ƒ(x1,x2,…,xn) = c0 c1x1 c2 x2 … cn xn, где ci = 0i1, причем (i =0,…,n)
Свойства замыкания:
1) [A] = A
2) [[A]] = [A]
3) если A1 A2 , то [A1] [A2]
4) [A1 A2] [A1] [A2]
Класс (множество) A называется (функционально) замкнутым, если [A] = A.
Примеры.
1) P2 – замкнутый класс.
2) L – замкнут, т.к. линейное выражение, составленное из линейных выражений, в свою очередь, является линейным выражением.
В терминах замыкания и замкнутого класса можно определить полноту (эквивалентную исходному определению), а именно: A – полная система, если [A] = P2.