- •1. Основные понятия теории множеств.
- •2. Понятие вектора.
- •3. Понятие соответствия между множествами.
- •4. Понятие отображения множеств.
- •5. Классификация множеств по мощности. Понятие счетного множества. Понятие несчётного множества.
- •6. Понятие отношения. Свойства отношений. Отношение эквивалентности, отношение строгого порядка, отношение нестрогого порядка.
- •7. Понятие операции, ассоциативной операции, дистрибутивной операции. Понятие алгебры, алгебраической системы, модели. Понятие группоида, полугруппы, коммутативной полугруппы.
- •8. Понятие группы. Группа подстановок.
- •9.Понятие кольца. Кольцо вычетов.
- •10. Определение поля
- •11. Перестановки
- •12.Перестановки с повторениями
- •13. Понятие сочетания. Теорема о числе сочетаний из n элементов по k. Свойства сочетаний.
- •Свойства сочетаний
- •14. Понятие сочетания с повторениями. Теорема о числе сочетаний с повторениями.
- •15. Понятие размещения. Теорема о числе размещений.
- •16. Понятие композиции. Теорема о числе композиций n.
- •18. Понятие композиции. Теорема о числе композиций n из k частей при рi0.
- •19. Основные понятия и определения теории графов.
- •20. Способы хранения графов в памяти эвм.
- •21. Алгоритм поиска на графах (поиск в глубину).
- •22. Алгоритм поиска на графах (поиск в ширину).
- •23. Понятие сильной связности. Анализ сильной связности с помощью алгоритмов поиска на графах.
- •25. Сильная связность. Отношение на вершинах графа называется отношением сильной связности. Сильная связность — отношение эквивалентности. Рассмотрим транзитивность:
- •26. Понятие логической функции. Способы задания логических функций.
- •27. Булева алгебра. Основные свойства операций булевой алгебры. Понятие двойственной и самодвойственной логической функции.
- •28. Алгебра Жегалкина. Основные свойства операций алгебры Жегалкина.
- •29. Алгебра Жегалкина. Представление логических функций полиномом Жегалкина.
- •33. Минимизация логических функций методом Квайна.
- •34. Понятие функционально-полной системы логических функций
- •35. 36 Понятие замкнутого класса. Класс монотонных логических функций.Понятие замкнутого класса. Класс линейный логических функций..
- •37. Теорема о функциональной полноте в слабом смысле.
- •38. Понятие замкнутого класса. Класс функций сохраняющих 0. Класс функций сохраняющих 1.
- •39. Понятие замкнутого класса. Класс самодвойственных функций.
- •40. Теорема о функциональной полноте.
33. Минимизация логических функций методом Квайна.
Теорема Квайна
Если исходя из СДНФ провести все возможные операции неполного склеивания, а затем все возможные операции элементарного поглощения, то в результате образуется сокращённая ДНФ, т.е. дезъюнкция всех простых имплекант.
Для получения минимальных ДНФ из сокращённой ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк - простые импликанты из полученной сокращённой ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в коституенту единицы, являющейся заголовком столбца.
В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, т.е. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных иплекант. В качестве минимальной ДНФ выбирается тупиковая, имеющая наименьшее число вхождений переменых.
34. Понятие функционально-полной системы логических функций
Функционально полная система логических функций представляет собой набор логических функций, с помощью которых можно записать любую, сколь угодно сложную функцию. В этом случае говорят, что этот набор образует базис. Функционально полными являются 3 базиса: 1) "И-ИЛИ-НЕ" (базис конъюнкции, дизъюнкции, инверсии) 2) "И-НЕ" (базис Шеффера) 3) "ИЛИ-НЕ" (базис Пирса или функция Вебба).
Элементы, реализующие операцию "И-НЕ", “ИЛИ-НЕ” и “Исключающее ИЛИ” на принципиальных и структурных схемах изображаются так: Примеры реализации логических операций в базисах “И-НЕ” и “ИЛИ-НЕ”.
Реализация операции “НЕ”:
Реализация операции “И”:
Пример реализации комбинационного устройства в базисе "И-НЕ". Пусть задана функция, реализуемая комбинационным устройством, в аналитической форме . Используя закон де Моргана и с учетом закона двойного инвертирования, запишем эту функцию в виде . Как следует из полученного аналитического выражения, логическое устройство должно содержать три двухвходовых и один трехвходовой элемент И-НЕ. Функциональная схема комбинационного устройства, построенная в базисе И-НЕ, показана на рис. 1.10.
|
35. 36 Понятие замкнутого класса. Класс монотонных логических функций.Понятие замкнутого класса. Класс линейный логических функций..
Замкнутый класс в теории булевых функций — такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества , снова входит в это же множество.
Классы логических функций
Функция, "сохраняющая 0".
Это - такая логическая функция, значение которой равно 0, если все аргументы равны 0: f(0,0,...,0) = 0.
Примером функции, сохраняющей 0, является функция .
Функция, "сохраняющая 1".
Это - такая логическая функция, значение которой равно 1, если все аргументы равны 1: f(1,1,...,1) = 1.
Примером функции, сохраняющей 1, является функция &.
"Монотонная" функция.
Это - такая логическая функция, которую можно выразить через & и .
Монотонную функцию можно распознать по ее таблице истинности. Для этого нужно взять все пары строк в таблице, которые отличаются всего в одном столбце (не считая крайнего правого). Например: 0,0,0,0 и 0,0,0,1; 1,0,0,1 и 1,1,0,1. Пусть в одной строке в некотором столбце стоит "0", а в другой строке в этом же столбце стоит "1". Нельзя, чтобы в крайнем правом столбце, где записано значение функции было наоборот: "1", а потом "0". Если такая ситуация нигде не встречается, то функция монотонная, и ее можно выразить через и &. Пример монотонной функции: .
"Линейная" функция.
Это - такая логическая функция, которую можно выразить через , 0 и 1.
Чтобы узнать, линейна ли функция, надо выразить ее через полином Жегалкина и посмотреть, не встречается ли там операция &. Если нет, то функция линейна. Для функций от 1 и 2 переменных мы уже приводили формулы, выражающие их через &, и константы.
Двойственные функции.
Логические функции f и g называются двойственными, если
f(~x1, ~x2,...,~xN) = ~g(x1, x2,..., xN).
Кратко это будем обозначать так: "f" * "g". Двойственные функции легко обнаружить с помощью простого приема. Надо заменить в таблице истинности все "0" на "1", а все "1" на "0". Полученная таблица истинности и будет таблицей двойственной функции. Ниже приведен список двойственных функций для всех унарных и бинарных операций. "0" * "1" "x" * "x" "~" * "~" "&" * " " " " * " " "|" * " " "<" * " " ">" * " "
"Самодвойственная" функция.
Это - логическая функция, которая двойственна самой себе:
f(~x1, ~x2,...,~xN) = ~f(x1, x2,..., xN).