- •Множества. Операции над множествами.
- •Законы алгебры множеств.
- •Мощность множества. Теорема о числе подмножеств конечного множества.
- •Бинарные отношения и их типы
- •Отношение эквивалентности. Теорема о разбиении множества на классы.
- •Перестановки и сочетания
- •Формулы о подсчете числа подстановок из сочетаний с повторениями и без повторений.
- •Высказывания. Операции над высказываниями.
- •Булевы функции
- •12. Законы равносильности. Доказать законы Де Моргана.
- •13. Формулы алгебры логики, их классификация и примеры.
- •14. Алгоритмы определения типа формулы.
- •15. Двойственные формулы. Принцип двойственности.
- •20. Сднф и алгоритмы ее построения.
- •21. Скнф и алгоритмы ее построения.
- •22. Теорема о разложении.
- •23. Контактные схемы.
- •24. Логические схемы.
- •26.Область истенности булевой фун-ции. Покрытие обл. Заданной в днф.
- •27.Метод Блейка,Нельсона, графический метод.
- •28. Минимальная днф. Метод инпликантных матриц.
- •29.Сокращенная днф. Теорема о связи сднф и мднф.
- •30. Тупиковая днф. Теорема о связи тднф и мднф
- •31.Алгоритмпостроения тупиковой днф
- •41. Квантор общности. Теорема о применении квантора общности для предиката определенном на конечном множестве.
- •42. Квантор существования. Теорема о применении квантора существования для предиката определенного на конечном множестве.
- •43. Законы алгебры логики предикатов.
- •44. Тождественно истинные предикаты, примеры. Теорема о тождественно истинных предикатах.
- •45. Тождественно ложные предикаты и теорема о тождественно ложных предикатах.
- •46. Понятие следствия и равносильности предикатов, примеры.
- •47. Формулы алгебры логики предикатов и их классификация.
- •48. Законы Де Моргана для алгебры логики предикатов.
- •49. Закон пронесения квантора общности через конъюнкцию.
- •50. Закон пронесения квантора существования через дизъюнкцию.
- •51.Закон пронесения квантора общности и существования через импликацию.
- •53. Детерминированные функции и графическое изображение (примеры).
- •54. Ограничено-детерминированные функции.
- •55. Диаграммы Мура.
- •56. Канонические уравнения ограничено-детерминированных функций.
- •57. Машины Тьюринга.
- •58. Простейшие функции. Теорема о простейших функциях.
- •59. Операция примитивной рекурсии. Примитивно-рекурсивные функции. Примеры.
- •60. Операция минимизации. Рекурсивные функции.
- •61. Тезисы Тьюринга и Черча. Теорема о связи между рекурсивными функциями и функциями вычислимыми по Тьюрингу (без доказательства).
- •62. Графы. Способы задания графов.
- •63. Формула Эйлера.
- •64. Графы к3,3 и к5,5. Теорема.
- •65. Плоские графы. Теорема о плоских графах (без доказательства).
- •66. Эйлеровые графы. Теорема о Эйлеровых графах. Гамильтоновы графы.
- •67. Деревья. Теорема о деревьях (без доказательства).
- •68. Предмет теории кодирования, алфавитное кодирование.
- •69. Префиксный код. Теорема о префиксном коде.
- •70. Разделимый код. Теорема Маркова (без доказательства).
21. Скнф и алгоритмы ее построения.
Cовершенная конъюнктивная нормальная форма формулы алгебры логики, содержащей ровно n различных переменных, есть ее конъюнктивная нормальная форма, в которой:
1) все дизъюнкции попарно различны;
2) каждая дизъюнкция содержит ровно n членов;
3) в каждой дизъюнкции встречаются все n переменных.
На примере 2 мы рассмотрели один из способов построения СКНФ, основанный на составлении таблицы истинности. Следующий способ построения СКНФ основан на применении законов алгебры логики.
Пример: Найти совершенную конъюнктивную нормальную форму формулы .
Используя, , получаем .
Данная формула является конъюнктивной нормальной формой. Она равносильна формуле .
Используя закон дистрибутивности, получаем:
Применяя закон идемпотентности, получаем требуемую совершенную конъюнктивную нормальную форму
.
22. Теорема о разложении.
ТеоремаВсякая булева функция f(x1,x2,…,xn) может быть представлена в следующей форме:
где 1 ≤ k ≤ n, в дизъюнкции берется по всем наборам значений переменных.
Это представление носит название разложения функции по переменным . Например, при n = 4, k = 2 разложение имеет вид:
Докажем справедливость разложения (3.1). Для этого возьмем произвольный набор значений переменных . Покажем, что левая и правая части соотношения (3.1) принимают при нем одно и то же значение. Действительно, так как xG = 1 тогда и только тогда, когда x = G, то среди 2К конъюнкции правой части (3.1) в единицу обращается только одна, в которой . Все остальные конъюнкции равны нулю.
Поэтому . В качестве следствия из разложения (3.1) получаем следующие два специальных разложения.
23. Контактные схемы.
Под контактными схемами мы будем понимать электрические цепи, содержащие только контакты. Каждый контакт может находиться в двух состояниях – разомкнут (0) и замкнут (1). Такие цепи мы будем изображать диаграммой, на которой возле контактов пишется или . Причем значение 1 этих переменных соответствует прохождению через данный контакт, а значения 0 нет.
Если контакты x и y соединены последовательно, то цепь замкнута, когда оба контакта замкнуты и разомкнута, когда хотя бы один из контактов разомкнут. Ясно, чт о такой схеме
соответствует булева функция .
Если контакты x и y соединены параллельно, то цепь замкнута, когда хотя бы один контакт замкнут и разомкнута, когда оба контакта разомкнуты. Ясно, что такой схеме
соответствует булева функция .
Указанное соответствие позволяет любую булеву функцию представить в виде контактной схемы. С другой стороны, любая контактная схема с последовательно или параллельно соединенными контактами реализуется булевой функцией. Задача анализа контактной схемы и состоит в построении соответствующей ей булевой функции.
24. Логические схемы.
Устройства, реализующие элементарные булевы функции, называются логическими элементами. Логические элементы изображаются в виде прямоугольников, внутри которых помещаются условные названия или символы соответствующих функций
Из данных логических элементов путем соединения входа одного из них с выходом другого можно строить все более сложные логические схемы. Для полученных таким образом схем легко записывают соответствующие им булевы функции.
25. Мин-ция булевых функций. Геометр. интерприт. Задачи минимизации
Существует тривиальный алгоритм построения минимальной ДНФ для произвольной булевой функции . Для этого все ДНФ, составленные из символов упорядочиваются по числу букв и по порядку для каждой ДНФ Д проверяется соотношение . Первая по порядку ДНФ, для которой это соотношение выполняется, есть, очевидно, минимальная ДНФ функции .
Рассмотрим геометрическую интерпретацию задачи минимизации булевых функций. Обозначим через множество всех точек , где . Ясно, что – множество всех вершин единичного n-мерного куба. Сопоставим каждой булевой функции подмножество из , определенное следующим образом:
Например, функции, заданной следующей таблицей истинности:
Соответствует подмножество
вершин трехмерного единичного куба
Данное соответствие является взаимно однозначным и обладает следующими свойствами:
1) булевой функции соответствует подмножество ;
2) булевой функции соответствует подмножество ;
3) булевой функции соответствует подмножество .
Теперь ясно, что задача построения минимальной ДНФ сводится к отысканию такого покрытия подмножества интервалами , чтобы число было наименьшим.