- •Московский государственный институт радиотехники, электроники и автоматики (технический университет)
- •Операции над множествами
- •Пересечение множеств Объединение множеств Дополнение множества Лекция 2 Теория булевых функций. Булева алгебра.
- •Булева алгебра характеристических векторов.
- •Утверждение
- •Следствие
- •Булева алгебра высказываний (алгебра логики)
- •Лекция 3 Определение и способ задания булевых функций
- •Лекция 4 Дизъюнктивные нормальные формы (днф) Конъюнктивные нормальные формы (кнф)
- •Лекция 5 Продолжение темы «днф»
- •Метод карт Карно для нахождения минимальной днф
- •Лекция 6 Метод Квайна – Мак-Клоски для нахождения минимальной днф
- •Идея метода Квайна (алгоритм)
- •Формализация Мак-Клоски.
- •Лекция 7 Функционально полные системы функций
- •Лекция 8 Продолжение темы «Многочлены Жегалкина»
- •Классы функций. Замкнутые и незамкнутые классы. Получение констант и элементарных булевых функций из заданной системы функций
- •Лемма о немонотонной функции
- •Лемма о нелинейной функции
- •Лекция 9
- •Лекция 10 Функциональные элементы. Схемы
- •Лекция 12 Эйлеровы графы
- •Лекция 13 Сети. Пути в орграфах. Остовы минимальной длины
- •Лекция 14 Парное сочетание (паросочетание) двудольных графов
- •Алгоритм оптимального назначения
- •Лекция 15 Потоки в транспортных сетях
Лекция 3 Определение и способ задания булевых функций
Булевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб.
Способы задания функций
Табличный
X1 X2 X3 … XN |
F(X) |
0 0 0 0 0 0 0 0 0 |
|
… |
|
1 1 1 1 1 1 1 1 1 |
n |
значение функции от данных аргументов.
Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.
Векторный
F = (n)
3. Геометрический
Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1.
Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)
На векторах, помеченных звездочкой, функция обращается в 1.
Nf= {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.
В виде формулы.
Функция f зависит от переменной xiфиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают.
Будем говорить, что f зависит от переменной xiсущественно, если существуют такие два набора значений, отличающихся только значением переменной xi, на которых значения функций различно.
Фиктивные переменные у функции можно добавлять и исключать.
Две булевы функции называются равными или равносильными, если одну можно получить из другой путем добавления и изъятия фиктивных переменных.
Строим таблицу функций при n = 1.
X |
0 |
X |
_ X |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
Таблица всех элементарных булевых функций, применяемых в записи формул
X |
Y |
0 |
& |
_____ YX |
X |
___ XY |
Y |
+ |
V |
|
~ |
_ Y |
X Y |
_X |
YX |
/ |
1 | |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 | |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 | |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 | |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Все эти функции от двух аргументов мы и будем называть элементарными булевыми функциями.
Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание.
Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры.
Суперпозиции булевых функций
Ф = {ф1…фk}
F называется элементарной суперпозицией функции из множества Ф, если она получена одним из следующих способов.
Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента).
В одну из функций системы вместо любого аргумента ставится значение любой функции из этой системы.
Ф1= {Y…xn}
Фi = (x1 … фj(x1…xn) … xn)
Ф(1)– множество всех элементарных суперпозиций из системы Ф.
Ф(k+1)– множество всех элементарных суперпозиций из систему Фk.
Функция g называется суперпозицией функций из системы, если
g Фn
Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции.
Конкретное выражение суперпозиции будем называть формулой над системой Ф.
G = Fф
Суперпозиция элементарных булевых функций – формула.
Для удобства записи договоримся, что отрицание – самая сильная операция. Следующая – конъюнкция, а остальные – равносильны.
_ _
X+Y = XY V XY
_ _
X ~ Y = XY V XY
__
X Y = X V Y
_ _
X Y = X Y