- •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. Изоморфизм и гомоморфизм - ????????????
12. Исключение лишних членов при упрощении булевых формул.
Процесс многоступенчатого склеивания приводит к импликантам, которые не склеиваются с другими. Такие импликанты называют простыми. Форма записи булевой функции в ДНФ, состоящая только из простых импликант, называется сокращенной дизъюнктивной нормальной формой (Сокр ДНФ).
В некоторых случаях в Сокр ДНФ могут содержаться лишние импликанты, которые могут быть исключены без изменения значения функции.
Одним из методов отыскания лишних импликант является метод испытания членов: чтобы испытать некоторый член функции, следует исключить его из Сокр ДНФ и подставить в оставшееся выражение такие значения аргументов, которые обращают исключенный член в единицу. Если при такой подстановке оставшееся выражение окажется тождественно равным единице, то испытуемый член является лишним.
=======================================================================================
13. Конституенты и импликанты и их роль в алгебре логики.
Конституента – элементарная составляющая логического выражения, она состоит из импликантов.
Импликанты это- конъюнктивные термы переменного ранга. Они бывают следующий видов:
Первичные импликанты - импликанты, входящие в выражения для минимизированной функции.
Существенные импликанты - импликанты, безусловно входящие в состав ФАЛ (т.е. каждая из них является единственной первичной импликантой, входящией в состав одного из первоначальных минтермов (минтермов СНДФ))
Нефункциональные импликанты - импликанты, не входящие в состав ни одного из минтермов.
Минтерм — булева функция, принимающая истинное значение лишь при одной-единственной комбинации своих аргументов.
Конституенты и импликанты широко применяются в различных операциях по упрощению логических выражений.
=======================================================================================
14. Минимизация булевой функции методом квайна.
Метод Квайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.[1][2][3]
Преобразование функции можно разделить на два этапа:
на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;
на втором этапе — переход от сокращённой формы к минимальной форме.
Первый этап (получение сокращённой формы)
Представим, что заданная функция \mathbf{f} представлена в СДНФ. Для осуществления первого этапа преобразование проходит два действия:
Операция склеивания;
Операция поглощения.
Переход к сокращенной форме основан на последовательном применении 2х операций – склеивание, поглощение. Пусть исходная функция представлена в СДНФ, тогда операция склеивания выглядит путем выявления в выражении пар вида xy и . Затем производится их склеивание , т.е. выявляются пары импликант, различающиеся на 1 аргумент, производится их склеивание и результаты склеивания вводятся в выражение функции в виде дополнительных членов. Далее производится операция поглощения, которая основывается на равенстве . Операция производится путем вычеркивания всех членов, поглощенных членами, введенными в результате проведения операции склеивания. Операции склеивания и поглощения производятся последовательно до тех пор, пока их выполнение оказывается не возможным.