- •Конспект лекций
- •Лекция 1. Множества
- •1.1. Основные определения
- •1.2. Операции над множествами
- •1.3. Свойства операций
- •1.4. Уравнения на множествах
- •1.5. Декартово произведение множеств
- •Лекция 2. Отображения и отношения
- •2.1. Способы описания бинарного отношения
- •2.2. Виды бинарных отношений
- •2.3. Эквивалентность
- •2.4. Отношение порядка
- •2.5. Замыкание отношений
- •Лекция 3. Графы
- •3.1. Основные определения
- •3.2. Частичный граф
- •3.3. Неориентированные графы
- •3.4. Расширения модели
- •3.5. Оптимизационные задачи на графах
- •3.5.1. Поиск путей в графе
- •3.5.1.1. Кратчайшие пути
- •3.5.1.2. Нахождение максимального пути
- •3.5.1.3. Циклы Эйлера
- •3.5.6. Поток в транспортной сети
- •3.5.7. Транспортная задача
- •4.1. Основные определения
- •4.2. Простейшие функции
- •4.3. Дизъюнктивные нормальные формы и теорема о разложении
- •4.4 Минимизация функций в классе днф
- •4.5. Минимизация функций
- •4.5.1. Метод минимизации по картам Карно
- •4.5.2. Метод неопределенных коэффициентов
- •4.5.3. Метод Квайна — Мак-Класки
- •4.6. Классы функций алгебры логики
- •4.6.1. Монотонные функции
- •4.6.2. Самодвойственные функции
- •4.6.3. Линейные функции.
- •4.6.4. Функции, сохраняющие константу
- •4.7. Функциональная полнота.
4.1. Основные определения
Булевой (логической) переменной называют переменную, принимающую значение из множества {0,1}. Название «логическая» следует из того, что её значения трактуются чаще всего как «истина» (для 1) и «ложь» (для 0).
Функцией алгебры логики (переключательной или булевой функцией) от n переменных называют однозначное отображение множества всевозможных наборов значений n булевых переменных в множество {0,1}.
Такую функцию можно представить в виде таблицы из n+1 столбцов и 2n строк. Эта таблица называется таблицей истинности.
Наборы значений переменных располагают в лексикографическом порядке (в порядке возрастания), как в примере в табл. 4.1 для n = 3.
Число всевозможных наборов значений переменных составляет N=2n. Число различных функций, которые могут быть записаны в таблице, равно 2N.
Таблица
4.1 x1 x2 x3 f 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
Для приведённого примера функцию можно представить как Т1={001,010,100, 111}.
Третий способ описания – представление функций в виде вектора. Так как порядок перечисления наборов входных переменных установлен, то достаточно указать только столбец функции. Для приведенного примера это будет вектор <01101001> .
Определение. Булева функция существенно зависит от переменной хi, если найдутся два набора значений переменных, отличающиеся только i-й компонентой, на которых значения функции не совпадают. Переменная, от которой функция существенно не зависит, называется несущественной или мнимой для данной функции.
Пример. Пусть функция на наборах значений переменных <00110> и <01110> равна, соответственно, 1 и 0. Эта функция существенно зависит от второй переменной, потому что её значение на этих наборах определяется только значением этой переменной.
Будем считать, что функция не изменится, если в нее добавить или из нее убрать любое количество несущественных переменных.
Таблица
4.2 x
0 x
`x
1
0
0
0
1
1
1
0
1
0
1
Пусть [n] – число функций, существенно зависимых от n переменных. Тогда [1] = 2, [0] = 2. Для любого n это число можно подсчитать по рекуррентной формуле
[n] = 2N- [0] - Cn1[1] - Cn2[2] - .... Cnn-1[n-1].
Здесь N=2n, первая компонента – число функций от n переменных, из которого последовательно для i=0,1,..., n-1 вычитаются произведения числа функций, существенно зависимых от i переменных, на число способов, которыми можно выбрать i переменных из n.
Так, для n = 2 [2]=16-2-2×2=10. Для n=3 [3]=256-2-3×2-3×10=218.