- •1. Булевы функции двух переменных.
- •2. Булевы функции: эквивалентность и сумма по модулю два. Таблицы истинности, комбинационные схемы, изображение базисных элементов.
- •3. Булевы функции: Штрих шеффера и стрелка Пирса.
- •4. Совднф и совкнф. 5. 6. Построение их по таблице истинности
- •7. Карты карно и их связь с таблицами истинности
- •8. Построение сднф по карте карно. 9. Построение скнф по карте карно
- •10. Построение булевой формулы по комбинационной схеме
- •11. Упрощение булевых формул
- •12. Исключение лишних членов при упрощении булевых формул.
- •13. Конституенты и импликанты и их роль в алгебре логики.
- •14. Минимизация булевой функции методом квайна.
- •15. Минимизация булевой функции по методу блейка
- •Минимизация булевой функции по методу нельсона
- •Функциональная полнота систем логических функций. 19. Примеры функционально полных систем
- •20. Основные понятия исчисления предикатов.
- •21. Алгебра предикатов: операции отрицания, конъюнкции и дизъюнкции.
- •22. Алгебра предикатов: операции импликации и эквивалентности.
- •!!!!!!!«Эквивалентность – не нашел!»!!!!!!!
- •23. Понятие квантора. Двойственность кванторов.
- •24. Применение кванторов в исчислении предикатов – не нашел!
- •25. Характеристическая функция принадлежности для обычных и нечетких множеств.
- •26. Понятие нечеткого подмножества
- •27. Включение, равенство, дополнение и пересечение нечетких множеств
- •28. Объединение, разность, возведение в степень нечетких множеств
- •29. Разность и симметрическая разность нечетких множеств
- •30. Понятие нечеткого отношения. Проекция и носитель нечеткого отношения
- •31. Объединение, пересечение и алгебраическое произведение двух нечетких отношений.
- •32. Алгебраическая сумма и симметрическая разность двух нечетких отношений
- •33. Композиция двух нечетких отношений.
- •40. Ориентированные и неориентировапнные графы. Деревья.
- •41. Способы задания графов
- •42. Задание графа матрицей Инцидентности.
- •43. Задание графа матрицей смежности.
- •44. Задача о кратчайшем пути на графе с ребрами единичной длины.
- •45. Построение графа наименьшей длины
- •46. Транспортные сети. Основные понятия.
- •47. Задача о наибольшем потоке в транспортной сети.
- •48. Понятие алгебраической системы
- •50. Строки символов как примеры полугрупп и моноидов - ????????????????.
- •51. Понятие группы.
- •52. Подгруппы. Построение подгрупп заданной группы.-???????????????????
- •54. Группа подстановки.
- •55. Группа с операцией сложения по модулю m - ????????????
- •56/ Группа с операцией умножения по модулю m - ????????????
- •57. Кольца.
- •58. Поля.
- •59. Поле галуа.
- •60 Многочлены над полями галуа??????????
- •61. Изоморфизм и гомоморфизм - ????????????
15. Минимизация булевой функции по методу блейка
Недостатком метода Квайна является то, что для его применения необходимо представить функцию в СДНФ. Процесс такого представления для функции с большим числом аргументов зачастую является весьма громоздкой задачей, т.е. было бы желательно найти возможность построения сокращенной ДНФ не по СДНФ, а по произвольной ДНФ данной функции. Идея построения сокращенной ДНФ по произвольной ДНФ была предложена в работах А. Блейка и П.С. Порецкого. Суть метода состоит в том, что в произвольной ДНФ осуществляют все операции обобщенного склеивания.
Если в ДНФ для данной функции f(А, В, С) входят две конъюнкции вида АС и B , то имеет место следующее равенство:
Запишем функцию f (А, В, С) в следующем виде:
Из этого вытекает метод построения сокращенной ДНФ. Этот метод заключается в том, что если в ПФ есть конъюнкции с переменными С и , то не изменяя исходную функцию необходимо пополнить ее новыми членами вида АВ. После этого надо провести поглощения и вновь повторить пополнение ДНФ. Этот процесс необходимо производить до тех пор, пока не будут возникать новые конъюнкции вида АВ. По окончании преобразований получаем сокращенную ДНФ.
Минимизация булевой функции по методу нельсона
Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной конъюнктивной нормальной формы.
Метод эффективен, если функция имеет “сравнительно мало” нулей.
Расписывается СКНФ по таблице или преобразуется из формулы, задающей данную функцию. В СКНФ раскрывают все скобки, удаляют конъюнкции, которые поглощаются по формулам полного поглощения. То, что остается, и есть сокращенная ДНФ.
Пример 5. Найдем сокращенную ДНФ для функции методом Нельсона.
СКНФ .
Раскрываем скобки:
, что и требовалось.
Минимизация булевой функции по карте Карно.
Для минимизации функций относительно небольшого числа переменной (не более шести) наиболее простым и наглядным является графический метод, использующий карты Карно.
Карта Карно – это прямоугольник, разбитый на квадраты, число которых равно числу наборов рассматриваемой функции, т. е. 2n. Клетки размечаются так, чтобы наборы, для которых возможны смежные конституенты, оказались бы в соседних клетках.
При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид
Единицы, представленные в клетках, обозначают конституенты единицы рассматриваемой функции. Отыскание минимальной ее формы сводится к определению варианта, при котором все конституенты единицы накрываются (охватываются контурами покрытия) наименьшим числом наиболее коротких импликант. Объединение клеток на карте эквивалентно выполнению операции склеивания.
Всегда нужно стремиться к минимальному количеству контуров и максимальной площади каждого из них, руководствуясь следующими правилами:
площадь контура покрытия должна быть Sk = 2m-i клеток, где – целое число, m – число переменных. Если, например, m = 3, то Sk = 1, 2, 4, или 8 клеток;
число сокращаемых переменных Nперем. = log2 Sk , т.е. при Sk = 1 не сокращается ни одна переменная, при Sk = 2 сокращается одна переменная и т.д.