DM_shpory
62. Префиксная нормальная форма. Процедура получения пнф.
Префиксной нормальной формой (ПНФ) называется формула, имеющая вид
Q1x1, Q2x2, …, QnxnF — кванторы; F — формула, не имеющая кванторов, с операциями {&, Ú, Ø}. В логике предикатов для любой формулы существует эквивалентная ей префиксная нормальная форма
Процедура получения ПНФ:
1) Используя формулы
P1 ~ P2 = (P1 ® P2) & (P2 ® P1),
P1 ® P2 = Ø P1 Ú P2
заменить ®, ~ на &, Ú, Ø.
2) Спустить символы отрицания непосредственно на символы предикатов
3) Для формул, содержащих подформулы вида
"xP1(x) Ú "xP2(x), $xP1(x) Ú $xP2(x),
ввести новые переменные, позволяющие использовать эквивалентные соотношения
4) С помощью эквивалентных соотношений получить формулы в виде ПНФ
Содержание
- 2. Операции над множествами. Круги Эйлера. Покрытия и разбиения. Классы разбиения.
- 3. Законы алгебры множеств. Формула включений и исключений.
- 5. Соответствия. Способы задания соответствий.
- 6. Инволюция (обращение) соответствий. Объединение, пересечение, дополнение, произведение соответствий.
- 7. Функциональные соответствия, их связь с графиками функций.
- 8. Соответствие Галуа и его роль в проективном распознавании образов. Замкнутое подмножество.
- 9. Отношение. Бинарное отношение. Рефлексивное, симметричное, антисимметричное, асимметричное, транзитивное отношения.
- Унарные:
- Бинарные:
- Соответствия a, b, r
- 10. Отношение эквивалентности. Фактор-множество множества по отношению.
- 11. Отношение предпорядка, упорядоченности, строгой упорядоченности. Отношение частичного порядка.
- 12. Замыкание отношений. Рефлексивное, симметричное, транзитивное замыкание отношений.
- 13. Понятие нечеткого множества. Функция принадлежности. Способы формализации нечетких множеств. Наиболее распространенные параметрические функции принадлежности.
- 14. Основные логические операции над нечеткими множествами и их свойства.
- 15. Диаграмма Хассе как способ задания отношения частичного порядка на множестве.
- 16. Отображения. Изоморфизм. Автоморфизм. Гомоморфизм. Эпиморфизм. Эндоморфизм. Мономорфизм. Биморфизм.
- 17. Бинарная операция и ее основное множество. Способы задания бинарной операции. Таблица Кэли. Операционный квадрат таблицы Кэли.
- 18. Группоид. Квазигруппа. Латинский квадрат. Лупа. Полугруппа. Моноид. Группа. Абелева группа.
- 19. Группа симметрий фигуры.
- 20. Группа подстановок.
- 21. Иерархия систем с двумя бинарными операциями. Кольцо. Тело. Поле (коммутативное тело). Поле Галуа.
- 22. Решетка (структура). Решетка как частично упорядоченное множество.
- 23. Решетка как универсальная алгебра.
- Графы и ориентированные графы
- 27. Виды графов: двудольные графы, регулярные графы, полные графы, деревья, планарные графы
- 28. Изоморфизм графов.
- 29. Способы задания графов.
- 32. Эйлеров путь в графе. Задача о кенигсбергских мостах. Эйлеров цикл. Теорема о существовании эйлерова цикла.
- 33. Алгоритм нахождения эйлерова цикла и его вычислительная сложность.
- 34. Гамильтонов цикл в графе. Алгоритм с возвратом для поиска гамильтонова пути. Оценки вычислительной сложности алгоритма.
- 35. Задача коммивояжера. Алгоритм поиска субоптимального решения.
- 36. Задача построения минимального остовного дерева. Алгоритм Краскала. Алгоритм Прима. Оценка вычислительной сложности этих алгоритмов.
- 37. Перенумерация вершин графа. Алгоритм топологической сортировки.
- 39. Принцип оптимальности Беллмана. Алгоритм нахождения кратчайшего пути в ориентированном графе и его вычислительная сложность.
- 1 Begin
- 40. Алгоритм вычисления расстояний между всеми парами вершин графа. Общий случай.
- 41. Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры. Оценка вычислительной сложности.
- 1 Begin
- 5 Begin
- 42. Алгоритм топологической сортировки. Алгоритм нахождения расстояния от источника до всех остальных вершин в графе в случае бесконтурного графа. Оценка вычислительной сложности
- 43. Знаковые графы и их практическое применение. Задачи из области социологии малых групп, экономики и политики.
- 44. Теорема о структуре (теорема Харари о балансе).
- 45. Знаковые орграфы как модель когнитивных карт. Контуры положительной и отрицательной обратной связи и устойчивость/изменчивость моделей на орграфах.
- 46. Двудольные графы. Необходимое и достаточное условие двудольности графа.
- 47. Сети Петри. Функционирование сети Петри. Конечные разметки сети.
- Иллюстрация к правилу срабатывания перехода
- 48. Сети Петри. Ограниченность, безопасность, сохраняемость, достижимость, живость. Моделирование на сетях Петри.
- 50. Конечный автомат как математическая модель устройства с конечной памятью и как управляющая система. Способы описания конечных автоматов: перечислительный; диаграмма состояний; таблица состояний.
- 51. Алгебра логики. Функции алгебры логики. Существенные и несущественные переменные. Бинарные логические операции. Формула. Суперпозиция функций. Таблицы истинности и таблицы Кэли.
- 52. Формы записи операций (функций) — инфиксная, префиксная, постфиксная. Эквивалентные формулы.
- 53. Основные схемы логически правильных рассуждений.
- 54. Функционально полные системы (базисы). Булева алгебра логики. Функциональная полнота системы булевых функций. Примеры других алгебр логики.
- 55. Основные эквивалентные соотношения в булевой алгебре. Выражение через дизъюнкцию, конъюнкцию и отрицание других логических бинарных операций. Двойственность.
- 56. Булева алгебра логики. Сднф и днф. Карта Карно. Функциональные схемы как приложение булевых функций.
- 57. Функции k-значной логики и их задание с помощью таблицы истинности и с помощью таблицы Кэли. Примеры k-значных логик.
- 59. Квантор всеобщности и квантор существования.
- 61. Истинные формулы и эквивалентные соотношения логики предикатов.
- 62. Префиксная нормальная форма. Процедура получения пнф.
- 63. Формальные теории. Принципы построения формальной теории.
- 64. Исчисление высказываний.