Содержание
- 2. Электронные ресурсы Режим доступа: http://www.iprbookshop.ru/ Балюкевич Э.Л. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/
- 3. Электронные ресурсы Режим доступа: http://www.iprbookshop.ru/ ЭБС «IPRbooks», по паролю Лавров И.А. Задачи по теории множеств, математической
- 4. Электронные ресурсы www.intuit.ru Бесплатный доступ после регистрации
- 5. 1. Теория булевых функций 2. Логические исчисления 3. Алгоритмические системы
- 6. 1. Булевы функции
- 7. 1.1 Определения
- 8. Функция f:{0,1}n→{0,1} от n переменных x1, x2, …, xn называется булевой
- 9. Утверждение Для булевой функции от n аргументов существует 2n различных наборов аргументов.
- 10. Поскольку каждая булева функция имеет конечное количество наборов аргументов, то булеву функцию можно задать в виде
- 11. Базовые логические связки – отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция
- 12. 1
- 13. Из логических переменных с помощью логических связок можно составлять конструкции, которые образуют формулы алгебры логики Пусть
- 14. Пусть даны формулы булевых функций F(y1, y2, …, ym ), f1(x1, x2, …, xn ), …,
- 15. Пример F(y1, y2 )= y1~ y2 f1(x1, x2 )= x1 f2(x1, x2 )= x1& x2 (F|
- 16. Теорема (О подстановке формул) Если F(y1, y2, …, ym ) и fi (x1, x2, …, xn
- 17. Формулы, реализующие одну и ту же функцию, называются равносильными (т.е. на всех наборах переменных их значение
- 18. Правило подстановки Если в равносильных формулах: F(y1, y2, …, ym ) ≡G(y1, …, ym ) –
- 19. ФАЛ, при образовании которых используются только операции отрицания, конъюнкции и дизъюнкции, называются булевыми формулами. Теорема Для
- 20. Множество булевых функций с определенными на нем операциями отрицания, конъюнкции и дизъюнкции называется булевой алгеброй. Множество
- 21. Для булевых функций выполняется ряд равносильностей Операции с константами: 1) A ∨ 1 ≡ 1;A &
- 22. при выполнении преобразований часто используются законы поглощения: 1) A & (A ∨ B) ≡ A; A
- 23. 1.2 Принцип двойственности
- 24. Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция f*(x1, x2,
- 25. Пример f1(x1 )= x1 f2(x1, x2 )= x1& x2 f1 *(x1 )= ¬f1(¬ x1 )= x1
- 26. Теорема (Общий принцип двойственности) Если G(x1, …, xn ) получена подстановкой формул fi из F(y1, …,
- 27. Теорема (Принцип двойственности для булевых функций) Двойственная к булевой функции может быть получена заменой констант 0
- 28. Булевы функции с операциями умножения и сложения по модулю 2 образуют алгебру Жегалкина. Аксиомы алгебры Жегалкина:
- 29. 1.3 Нормальные формы
- 30. Табличный способ определения истинности сложного выражения имеет ограниченное применение. Тогда может быть использован способ приведения формул
- 31. Элементарной дизъюнкцией (конъюнкцией) называется дизъюнкция переменных и/или их отрицаний ДНФ – это дизъюнкция элементарных конъюнкций. КНФ
- 32. ДНФ (КНФ) называется совершенной, если каждая переменная формулы входит в каждую элементарную конъюнкцию (дизъюнкцию) ровно один
- 33. Примеры Элементарные дизъюнкции: x∨y, z. Элементарные конъюнкции: x&¬y&z, x. f(x,y,z) = x&y&z ∨¬x&y – ДНФ f(x,y,z)
- 34. X & Y
- 35. Введем обозначения
- 36. Теорема О разложении булевой функции по k переменным
- 37. n=3, k=2
- 38. Доказательство Выберем какой-либо набор значений для переменных x1, …, xn. Пусть это будет σ1, …, σn.
- 39. Подставим в правую часть формулировки теоремы вместо x1, …, xn набор σ1, …, σn. Получим. Поскольку
- 40. Получена левая часть формулы теоремы. Поскольку набор был выбран произвольно, получаем, что утверждение верно любого набора
- 41. Следствие 1 Разложение Шеннона
- 42. Следствие 2 При k=n
- 43. Построение СДНФ 1. Найти строки в таблице истинности , где значение функции f истинное. 2. Каждому
- 44. Построение СКНФ 1. Найти строки в таблице истинности , где значение функции f ложное. 2. Каждому
- 45. Получение из ДНФ. Если некоторое произведение ДНФ не содержит какой-либо переменной, то необходимо домножить это произведение
- 46. Получение из КНФ. Если некоторая элементарная дизъюнкция КНФ не содержит какой-либо переменной, то необходимо дизъюнктивно добавить
- 48. Скачать презентацию