20. Элементарные булевы функции и способы их задания (табличный, векторный, формульный, графический, карта Карно).
Определение. Функцияотnаргументовназывается булевой функцией (или функцией алгебры логики), если каждому наборуона ставит в соответствие число.
Для задания булевых функциймы будем использовать таблицы, векторы, формулы и графики. Примем следующее обозначение:– это множество всех наборов, где.
–функция тождественный ноль (константа 0),
–функция тождественная единица (константа 1),
–тождественная функция,
–функция отрицание х (читается «не х»).
|
(011) (111)
(001) (101)
(010) (110)
(000) (100)
| Элементы множества можно сопоставить вершинамn-мерного единичного куба (на рисунке изображена проекция 3-мерного куба на плоскость). Элементы этого множества можно считать двоичной записью чисел 0, 1, 2,…, 2n–1. Это графический способ задания булевой функции. |
| х1 х2 | g0 | g1 | g2 | g3 | g4 | g5 | g6 | g7 | g8 |
| 0 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
В таблице перечислены некоторые булевы функции от двух аргументов х1и х2:
–константа 0,
–константа 1,
–дизъюнкция (логическое сложение, «х1или х2»),
–конъюнкция (логическое умножение, «х1и х2»),
–сложение по модулю 2,
–эквиваленция,
–импликация (логическое следование),
–стрелка Пирса (антидизъюнкция),
–штрих Шеффера (антиконъюнкция).
С помощью таблицы можно задать булеву функцию от любого числа аргументов. Таблица для функции от nаргументов содержит 2nстрок. В каждой строке записан набор значений аргумента длиныnиз нулей и единиц, а также значение функции на этом наборе. При заполнении строк таблицы будем придерживаться правила: для каждогоi= 1,2,3,…,2nнабор значений аргумента вi-й строке представляет собой запись числа (i – 1) в двоичной системе счисления. Таким образом, значения самой функции в таблице будут записаны в виде столбца из нулей и единиц высоты 2n. Если этот столбец записать в виде отдельной строки, то получим так называемый векторный способ задания булевой функции. Например, штрих Шеффера можно задать векторным способом. Поскольку имеется ровноразличных наборов длины 2nиз нулей и единиц и каждый из них можно рассматривать как вектор, задающий некоторую булеву функцию отnаргументов, то существует ровноразличных булевых функций отnаргументов.
Карта Карно – это таблица, которая является ещё одним способом задания булевой функции. Каждому набору значений аргументов во внутренней части этой таблице соответствует одна клетка.
Пример.Карта Карно для функцииf(x,y,z) = (00110001)
|
| ху | |||||
| 00 | 01 | 11 | 10 | |||
| z | 0 | 0 | 1 | 0 | 0 | |
| 1 | 0 | 1 | 1 | 0 | ||
|
| ||||||
- 1. Основные понятия теории графов, удаленность вершины, центр, радиус и диаметр графа.
- 2. Способы задания графов, свойства матриц смежности и инциденций, теорема о рукопожатиях.
- 3. Основные операции над графами, неравенства для числа вершин, ребер и компонент связности графа.
- 4. Типы графов, дополнительные графы, двудольные графы, критерий двудольности.
- 5. Обходы графов: эйлеровы цепи и циклы, необходимые и достаточные условия их существования, алгоритм Флери.
- 6. Обходы графов: гамильтоновы цепи и циклы, достаточные условия их существования.
- 7. Деревья, их свойства, кодирование деревьев, остовные деревья.
- 8. Экстремальные задачи теории графов: минимальное остовное дерево, алгоритмы Прима и Краскала.
- 9. Экстремальные задачи теории графов: задача коммивояжера, «жадный» алгоритм
- 10. Экстремальные задачи теории графов: задача о кратчайшем пути, алгоритм Дейкстры.
- 11. Изоморфизм и гомеоморфизм графов, методы доказательства изоморфности и неизоморфности графов.
- 12. Плоские укладки графов, планарные графы, критерий Понтрягина-Куратовского.
- 13. Необходимые условия планарности, формула Эйлера для планарных графов.
- 14. Правильные вершинные раскраски графов, хроматическое число, неравенства для хроматического числа.
- 15. Теорема о пяти красках, гипотеза четырех красок, «жадный» алгоритм.
- 16. Хроматический многочлен, его нахождение и свойства.
- 17. Задача о поиске выхода из лабиринта, реберная раскраска графа.
- 18. Ориентированные графы, источники и стоки, топологическая сортировка, алгоритм Демукрона.
- 19. Составление расписания выполнения комплекса работ в кратчайшие сроки методами теории графов.
- 20. Элементарные булевы функции и способы их задания (табличный, векторный, формульный, графический, карта Карно).
- 21. Существенные и фиктивные переменные булевых функций, основные тождества, эквивалентные преобразования формул.
- 22. Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом неопределенных коэффициентов.
- 23. Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом эквивалентных преобразований.
- 24. Разложение булевых функций в сднф и скнф.
- 25. Минимизация днф и кнф методом эквивалентных преобразований.
- 26. Минимизация днф и кнф с помощью карт Карно.
- 27. Замкнутые классы булевых функций т0, т1, l, лемма о нелинейной функции.
- 28. Замкнутые классы булевых функций s и м, леммы о несамодвойственной и немонотонной функции.
- 29. Полная система функций, теорема о двух системах булевых функций.
- 30. Теорема Поста о полноте системы булевых функций, алгоритм проверки системы на полноту, базис.
- 31. Схемы из функциональных элементов, правила построения и функционирования, метод синтеза сфэ, основанный на сднф и скнф.
- 32. Метод синтеза сфэ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника, сложность получаемых схем.
- 33. Основные комбинаторные операции, сочетания и размещения (с возвращением и без возвращения элементов).
- 34. Комбинаторные принципы сложения, умножения, дополнения, включения-исключения.
- 35. Биномиальные коэффициенты, их свойства, бином Ньютона.
- 36. Треугольник Паскаля, полиномиальная формула.
- 37. Алфавитное кодирование: необходимое и достаточные условия однозначности декодирования.
- 38. Алфавитное кодирование: теорема Маркова, алгоритм Маркова.
- 39. Коды с минимальной избыточностью (коды Хаффмана), метод построения.
- 40. Линейные коды, порождающая матрица, двойственный код.
- 41. Самокорректирующиеся коды (коды Хэмминга), метод построения.
- 42. Определение, схема и функционирование абстрактного автомата, способы задания автоматов.
- 43. Типы конечных автоматов, автоматы Мили и Мура, автоматы-генераторы.
- 44. Слова и языки, операции над ними, их свойства.
- 45. Регулярные выражения и регулярные языки, теорема Клини.
- 46. Задача анализа автоматов-распознавателей.
- 47. Задача синтеза автоматов-распознавателей.
- 48. Эквивалентные состояния автомата-распознавателя, эквивалентные автоматы-распознаватели, минимизация автоматов-распознавателей, алгоритм Мили.
- 49. Эквивалентные состояния автомата-преобразователя, эквивалентные автоматы- преобразователи, минимизация автоматов- преобразователей, алгоритм Мили.
- 50. Детерминированные и недетерминированные функции, примеры, способы задания.
- 51. Ограниченно-детерминированные (автоматные) функции, способы их задания.
- 52. Логические автоматы, способы их задания, синтез двоичного сумматора.
- 53. Операции над логическими автоматами: суперпозиция и введение обратной связи.