- •Введение
- •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
5. Многозначные функции
Конечнозначная логика вводится как обобщение двузначной логики. Она используется для описания функционирования сложных управляющих систем. Компоненты этих систем могут находиться в конечном числе состояний.
5.1. Функции и формулы k-значной логики
Функция , аргументы и значения, которой определены на множестве истинностных значений , называется функцией k-значной логики.
Каждую функцию k-значной логики от n – аргументов можно задать в виде таблицы содержащей строк.
Таблица 15
|
|
0 0 0 |
|
0 0 1 |
|
. . . . . . . . . . . . . . . . |
. . . . . . . . . . |
0 0 k-1 |
|
0 1 0 |
|
. . . . . . . . . . . . . . . . |
. . . .. . . . . . . |
0 k-1 k-1 |
|
Множество всех функций k-значной логики обозначается ( ). Заметим, что . В частности число функций от двух переменных в равно =19683, т.е. это множество практически не обозримо. Поэтому в так же как и в , используется задание функций с помощью формул. В качестве «элементарных» в k-значной логике рассматриваются следующие функции:
` .
Эта функция представляет собой отрицание в смысле «циклического сдвига значений».
– это обобщение отрицания в смысле «зеркального отображения значений». Оно носит название отрицание Лукашевича.
.
Эта функция также является обобщением некоторых свойств отрицания.
.
Это характеристическая функция значения i, которая также обобщает отрицание.
– это обобщение конъюнкции.
– это есть второе обобщение конъюнкции.
– обобщение дизъюнкции.
– второе обобщение дизъюнкции.
Используя переменные, допустимые значения которых являются элементы множества и символы некоторых функций из можно строить формулы, которые задают функции из .
Любая функция из может быть представлена в виде:
, где под конъюнкцией понимается , а под дизъюнкцией . В этом выражении дизъюнкция распространяется по всем наборам элементов .
Данное представление является аналогом СДНФ.
5.2. Полнота и замкнутость функций k-значной логики
Система функций из ( ) называется (функционально) полной, если любая функция из может быть записана в виде формулы через функции этой системы.
Примерами полных систем является:
= .
= .
= .
= ,где .
Функция называется фуннцией Вебба представляет собой аналог функции Шеффера.
Пусть – произвольное подмножество функции из . Замыканием называется множество [] всех функций из , представленных в виде формул через функции множества `
Класс называется (функционально) замкнутым, если замыкание []=.
Таким образом, в терминах замыкания можно определить полноту системы функций, а именно является полной системой если замыкание []= .
Справедлива теорема о функциональной полноте - теорема Кузнецова А.В.:
Можно построить систему замкнутых классов в - 1, 2,…,s, каждый из которых не содержит целиком ни одного из остальных классов и такую, что подсистема функций из полна тогда и только тогда, когда она целиком не содержится ни в одном из классов 1, 2,…,s. Это аналог теоремы Поста.
Теорема Кузнецова доказывает, что возможно выразить, условие полноты системы в терминах принадлежности ее к специальным классам 1, 2,…,s, однако практическое построение классов даже при небольших k связано с трудоемкими вычислениями. Поэтому возникает вопрос о поиске других более эффективных критериев полноты. Эта цель достигается за счет введения ограничений , т.е. за счет знания дополнительной информации о системе .
Существенными называются функции из , если они существенно зависят не менее чем от двух переменных.
Теорема Яблонского
Пусть система функций из , где k ³ 3, содержит все функции одной переменной, принимающие не более k-1 значений. Тогда для полноты системы необходимо и достаточно, чтобы содержало существенную функцию , принимающую все k значений.
Следствие (критерий Слупецкого):
Пусть система функций из , где к ³ 3, содержит все функции одной переменной. Тогда для полноты системы необходимо и достаточно, чтобы содержало существенную функцию , принимающую все k значений.
Непосредственное использование теоремы и ее следствия не всегда удобно, так как для этого необходимо установить наличие в всех функций одной переменной, принимающих не более k-1 значения, т.е. функций. С ростом k громоздкость вычислений возрастает. Поэтому это требование целесообразно заменить требованием, в котором система функций порождало бы множество функций одной переменной.
Известно, что функции из могут быть получены из конкретных систем функций одной переменной.
Теорема 1 (Пикара).
Все функции одной переменной из могут быть порождены тремя функциями:
,
,
.
Теорема 2
Все функции одной переменной из могут быть порождены k функциями
и функцией .
Теорема 3 (Мартина).
Функция из при к ³ 3 является функция Шеффера, тогда и только тогда, когда порождает все функции одной переменной принимающие не более k-1 значений.