56. Булева алгебра логики. Сднф и днф. Карта Карно. Функциональные схемы как приложение булевых функций.
Формула называется дизъюнктивной нормальной формой (ДНФ) если она является дизъюнкцией элементарной конъюнкции.
Пример
Формула называется конъюнктивной нормальной формой (КНФ) если она является конъюнкцией элементарной дизъюнкции.
Пример
Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой нет одинаковых элементарных конъюнкций, и все конъюнкции состоят из одного и того же набора переменных, в которые каждая переменная входит только 1 раз.
Пример
Совершенная конъюнктивная нормальная форма (СКНФ) называется КНФ, в которой нет одинаковых элементарных дизъюнкций, и все дизъюнкции состоят из одного и того же набора переменных, в которые каждая дизъюнкция входит только 1 раз.
Пример
Любую функцию кроме констант 0 и 1 можно представить в виде как СДНФ, так и СКНФ.
СКНФ и СДНФ строятся по таблице истинности функции.
Алгоритм получения СДНФ по таблице истинности функции:
отметить в таблице строки, где функция равна 1
выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение переменной равно 1, то в конъюнкцию входит сама переменная, если равно 0, то в конъюнкцию входит отрицание.
все полученные конъюнкции объединить дизъюнкцией.
Алгоритм получения СКНФ по таблице истинности функции:
отметить в таблице строки, где функция равна 1
выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение переменной равно 0, то в дизъюнкцию входит сама переменная, если равно 1, то в дизъюнкцию входит отрицание.
все полученные конъюнкции объединить конъюнкцией.
Большое значение имеет минимизация ДНФ.
ДНФ называется минимальной, если она содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей ДНФ. Получение минимальной ДНФ из СДНФ путём тождественных преобразований.
Пример получения СДНФ и СКНФ по таблице истинности:
x | y | F |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
1.СДНФ
функция равна единице во второй и третей строке
составляем конъюнкцию второй строки
составляем конъюнкцию третей строки
объединим полученное дизъюнкцией +
получаем СДНФ = +
2.СКНФ
функция равна нулю в первой и последней строке
составляем дизъюнкцию второй строки
составляем дизъюнкцию второй строки
объединим полученное конъюнкцией ( )( )
получаем СКНФ = ( )( )
Функциональная схема
Конъюнктор (И) Дизъюнктор (ИЛИ) Инвертор (НЕ)
Карта Карно
Пример:
| pq |
|
|
|
r |
| 1 | 1 |
|
|
|
|
| 1 |
- 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. Исчисление высказываний.