- •6 Отношения. Унарные, бинарные, тернарные отношения.
- •13 Способы задания нечетких множеств. Операции над нечеткими множествами.
- •Операции над нечеткими множествами
- •15 Логика высказываний.
- •16 Логические операции. Формулы логики высказываний. Логические операции.
- •Формулы логики высказываний
- •17 Равносильность формул.
- •18 Нормальные формы формул, приведение к днф, кнф.
- •19 Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.
- •Алгоритм получения сднф по таблице истинности.
- •Алгоритм получения скнф по таблице истинности.
- •20 Булева алгебра. Логические функции одной или нескольких переменных.
- •21 Суперпозиции функций. Полные системы логических функций.
- •22 Минимизация в классе дизъюнктивных нормальных форм.
- •23 Исчисление высказываний и исчисление предикатов.
- •Исчисление предикатов
- •24 Аксиоматические теории. Выводимость формул в исчислении высказываний.
- •25. Теорема дедукции. Предикаты, кванторы.
- •26. Формулы логики предикатов, их равносильность, выполнимость и общезначимость.
- •27. Аксиомы исчисления предикатов.
- •28. Алгебраические структуры. Группы.
- •29. Циклические группы. Группы подстановок. Кольца и поля
- •30. Элементы теории кодирования. Представление о кодировании.
- •31. Расстояние Хемминга.
- •32. Теорема о корректирующей способности кодов.
- •33. Матричное кодирование. Групповые коды.
- •34. Коды Хемминга.
- •35. Элементы комбинаторики. Размещения и сочетания.
- •36 Перестановки и подстановки.
- •37 Разбиения Формула включений и исключений.
- •38 Теория графов. Основные понятия и определения.
- •39 Понятие графа. Виды графов.
- •40 Способы задания графов.
- •41 Смежность, инцидентность.
- •42.Операции над графами. Части графов.
- •43 Связность, компоненты связности.
- •44 Числа графов: цикломатическое, хроматическое, внешней и внутренней устойчивости.
- •45 Поиск маршрутов в графе. Задача о минимальном соединении.
- •46 Задача о кратчайшем пути.
- •47 Эйлеровы цепи и циклы. Гамильтоновы цепи и циклы.
- •48 Транспортные сети. Понятие транспортной сети.
- •49 Поток в транспортной сети. Разрез, пропускная способность разреза.
- •50 Алгоритмы построения максимального потока.
- •1) Процедура помечивания вершин.
- •2) Процедура изменения потока.
13 Способы задания нечетких множеств. Операции над нечеткими множествами.
Понятие нечеткого множества - эта попытка математической формализации нечеткой информации для построения математических моделей. В основе этого понятия лежит представление о том, что составляющие данное множество элементы, обладающие общим свойством, могут обладать этим свойством в различной степени и, следовательно принадлежать к данному множеству с различной степенью. При таком подходе высказывания типа “такой-то элемент принадлежит данному множеству” теряют смысл, поскольку необходимо указать “насколько сильно” или с какой степенью конкретный элемент удовлетворяет свойствам данного множества.
Определение 1. Нечетким множеством (fuzzy set) на универсальном множестве U называется совокупность пар (), где- степень принадлежности элементак нечеткому множеству. Степень принадлежности - это число из диапазона [0, 1]. Чем выше степень принадлежности, тем в большей мерой элемент универсального множества соответствует свойствам нечеткого множества.
Определение 2. Функцией принадлежности (membership function) называется функция, которая позволяет вычислить степень принадлежности произвольного элемента универсального множества к нечеткому множеству.
Нечеткое множество (или нечеткое число), описывает некотоpые понятия в фyнкциональном виде, т. е. такие понятия как "пpимеpно pавно 5", "скоpость чyть больше 300 км/ч" и т. д., как видно эти понятия невозможно пpедставить одним числом, хотя в pеальности люди очень часто пользyются ими.
Hечеткая пеpеменная это тоже самое, что и нечеткое число, только с добавлением имени, котоpым фоpмализyется понятие описуемое этим числом.
Операции над нечеткими множествами
Содержание
Пусть A и B - нечеткие множества на универсальном множестве E.
Говорят, что A содержится в B, если "x ОE mA(x) <mB(x).
Обозначение: A М B.
Иногда используют термин "доминирование", то есть в случае если A М B, говорят, что B доминирует A.
Равенство
A и B равны, если "xОE mA(x) = mB (x).
Обозначение: A = B.
Дополнение
Пусть M = [0,1], A и B - нечеткие множества, заданные на E. A и B дополняют друг друга, если
"xОE mA(x) = 1 - m B(x).
Обозначение: B = или A =
Очевидно, что = A. (Дополнение определено для M = [0,1], но очевидно, что его можно определить для любого упорядоченного M).
Пересечение
AЗB - наибольшее нечеткое подмножество, которое содержится одновременно в A и B.
mAЗB(x) = min( mA(x), mB(x)).
Объединение
А И В - наименьшее нечеткое подмножество, которое включает как А, так и В, с функцией принадлежности:
mAИ B(x) = max(mA(x), m B(x)).
Разность
А - B = АЗ с функцией принадлежности:
mA-B(x) = mA З (x) = min( mA(x), 1 - m B(x)).
Дизъюнктивная сумма
АЕB = (А - B)И(B - А) = (А З ) И( З B) с функцией принадлежности:
mA-B(x) = max{[min{m A(x), 1 - mB(x)}];[min{1 - mA(x), mB(x)}] }
14 Элементы математической логики.
Математическая логика – разновидность формальной логики, т.е. науки, которая изучает умозаключения с точки зрения их формального строения.
Определение. Высказыванием называется предложение, к которому возможно применить понятия истинно или ложно.
В математической логике не рассматривается сам смысл высказываний, определяется только его истинность или ложность, что принято обозначать соответственно И или Л.
Понятно, что истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами “и”, “или”.
Таким образом, операции с высказываниями можно описывать с помощью некоторого математического аппарата.
Вводятся следующие логические операции (связки) над высказываниями
Отрицание. Отрицанием (логическим “не”) высказывания Р называется высказывание, которое истинно только тогда, когда высказывание Р ложно.
Обозначается Р или.
Соответствие между высказываниями определяется таблицами истинности. В нашем случае эта таблица имеет вид:
P |
Р |
И |
Л |
Л |
И |
2) Конъюнкция. Конъюнкцией (логическим “и”) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.
Обозначается P&Q или РQ.
P |
Q |
P&Q |
И |
И |
И |
И |
Л |
Л |
Л |
И |
Л |
Л |
Л |
Л |
3) Дизъюнкция. Дизъюнкцией (логическим “или”) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.
Обозначается PQ.
P |
Q |
PQ |
И |
И |
И |
И |
Л |
И |
Л |
И |
И |
Л |
Л |
Л |
4) Импликация. Импликацией (логическим следованием) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда высказывание Р истинно, а Q – ложно.
Обозначается PQ (или РQ). Высказывание Р называется посылкой импликации, а высказывание Q – следствием.
P |
Q |
PQ |
И |
И |
И |
И |
Л |
Л |
Л |
И |
И |
Л |
Л |
И |
5) Эквиваленция. Эквиваленцией (логической равносильностью) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают.
Обозначается РQ или РQ.
P |
Q |
PQ |
И |
И |
И |
И |
Л |
Л |
Л |
И |
Л |
Л |
Л |
И |
С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул.