- •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. Изоморфизм и гомоморфизм - ????????????
Функциональная полнота систем логических функций. 19. Примеры функционально полных систем
Функционально полная система логических функций представляет собой набор логических функций, с помощью которых можно записать любую, сколь угодно сложную функцию. В этом случае говорят, что этот набор образует базис. Функционально полными являются 3 базиса:
1) "И-ИЛИ-НЕ" (базис конъюнкции, дизъюнкции, инверсии)
2) "И-НЕ" (базис Шеффера)
3) "ИЛИ-НЕ" (базис Пирса или функция Вебба).
Примеры реализации логических операций в базисах “И-НЕ” и “ИЛИ-НЕ”.
|
|
|
|
Реализация операции “НЕ”:
|
|
|
|
Реализация операции “И”:
|
|
|
|
Пример реализации комбинационного устройства в базисе "И-НЕ". Пусть задана функция, реализуемая комбинационным устройством, в аналитической форме
.
Используя закон де Моргана и с учетом закона двойного инвертирования, запишем эту функцию в виде
.
Как следует из полученного аналитического выражения, логическое устройство должно содержать три двухвходовых и один трехвходовой элемент И-НЕ. Функциональная схема комбинационного устройства, построенная в базисе И-НЕ, показана на рис. 1.10.
20. Основные понятия исчисления предикатов.
Решение многих задач обработки информации требует ее логического анализа. Для автоматизации логического рассуждения необходим некоторый формальный язык, на котором можно формулировать посылки и делать логические выводы. Такой язык имеется. Он носит название языка логики предикатов.
В математике, информатике, кибернетике и других науках наряду с высказываниями встречаются выражения, грамматически имеющие форму высказываний, но содержащие предметные переменные некоторых множеств, а не конкретные объекты этих множеств. Здесь под предметными переменными понимаются произвольные, неконкретизированные объекты указанных множеств. Такие выражения можно получить из любых высказываний, заменив в них обозначения предметов предметными переменными множеств, к которым принадлежат эти предметы. Если в последних выражениях все предметные переменные снова заменить какими-либо элементами данных множеств (необязательно исходными), то опять получим высказывания.
Исчисление предикатов - это такая логическая система, с помощью которой можно выразить большую часть знаний, относящихся к математике, математической лингвистике, естественным разговорным языком. Эта система содержит правила логического вывода, позволяющие делать верные логические построения новых утверждений, исходя из некоторого заданного множества утверждений. Благодаря своей общности исчисление предикатов может претендовать на использование для компьютерного построения умозаключений.
Например,
“2 – простое число” - высказывание; “3>1” - высказывание.
Но, заменив числа в этих высказываниях предметной переменной n из множества натуральных чисел, получим выражения:
“n - простое число”, “n1>n2”, являющиеся не высказываниями, а предикатами. Предикаты отражают свойства и отношения между предметами из предметной области. Обозначим
P1(n) - свойство “быть простым числом”, а P2(n1,n2) отношение “n1 больше n2”.
В общем случае мы ничего не можем сказать о значении предиката, но подставив, например, в P1 и P2 значения n=2, n1=3, n2=1, получим
P1(2) - “2-простое число”, P2(3,1) - “3 больше 1” -
истинные высказывания, а подставив значения n=4, n1=1, n2=3. получим
P1(4) - “4 – простое число”, P2(1,3) - “1 больше 3” –
ложные высказывания, т.е. предикат при подстановки конкретных констант из предметной области, может принимать значение И или Л.
=========================================================