Boolean Functions Flashcards
Булева функция
Функция, зависящая только от булевых переменных и принимающая значения в интервале {0,1}. f: {0,1}^n — {0,1}
Мощность множества булевых функций
(2)^2^n
Элементарные булевы функции
1) Логическое «или» — функция максимума — дизъюнкция
2) Логическое «и» — функция минимума — конъюнкция
3) Сложение по модулю 2
4) Эквивалентность
5) «если у, то х» — импликация
6) Отрицание дизъюнкции
Элементарная конъюнкция
Конъюнкция литералов булевых переменных, каждая из которых встречается не более 1 раза
ДНФ
Дизъюнкция конечного множества элементарных конъюнкций называется дизъюнктивной нормальной формой
Совершенная ДНФ
ДНФ, которая содержит только полные элементарные конъюнкции
Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама, либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ).
Утверждение: Связь ДНФ и СДНФ
Любую логическую формулу А, которая не является противоречием, можно преобразовать в ДНФ, а её — в СДНФ
Утверждение: Связь КНФ и СКНФ
Любую логическую формулу А, которая не является тавтологией, можно преобразовать в КНФ, а её — в СКНФ
Принцип двойственности
Двойственная к суперпозиции булевых функций функция есть суперпозиция двойственных функций
Двойственная функция
Пусть f — булевая функция, тогда функция g называется двойственной, если g(x1, … xn) = !f (!x1, … !xn)
! — это горизонтальная черта, то есть отрицание
Альтернативная формулировка принципа двойственности
Если булева функция f реализуется формулой А, в состав которой входят g1, g2,… То двойственная функция f* реализуется формулой, которая получается из А заменой каждого вхождения gi на g*i
Двойственное разложение Шеннона
…
Свойства двойственных функций
1) (f) = f
2) 0* = 1, 1* = 0
3) Дизъюнкция и конъюнкция являются двойственными по отношению друг к другу
Правила Де-Моргана
Отрицание конъюнкции есть дизъюнкция отрицаний.
Отрицание дизъюнкции есть конъюнкция отрицаний.
КНФ
Нормальная форма, которая представлена в виде конъюнкции конечного числа элементарных дизъюнкций.
Элементарной дизъюнкцией назовем дизъюнкцию переменных множества X, в которую каждая переменная входит не более одного раза (с инверсией или без инверсии).
СКНФ
?
Полиномиальная нормальная форма, её степень
Сумма по модулю 2 попарно различных элементарных конъюнкций. Степенью ПНФ называется максимальный ранг среди содержащихся в ней элементарных конъюнкций
Совершенная ПНФ
ПНФ называется совершенной, если она содержит только полные элементарные конъюнкции
Ранг ЭК, полная ЭК
Число литералов, входящих в элементарную конъюнкцию, называется её рангом. Полной называется элементарная конъюнкция, в которую входит максимальное число литералов
Полином Жегалкина
Полином Жегалкина — многочлен над полем Z2, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или.
Другими словами, это ПНФ, образованная ЭК, которые не содержат отрицаний переменных
Теорема Жегалкина
Каждая булева функция представима в виде полинома Жегалкина.
Для любой булевой функции существует единственный полином Жегалкина
Основные замкнутые классы булевых функций
1) To — класс, сохраняющий константу 0
2) T1 — класс, сохраняющий константу 1
3) Ts — класс самодвойственных булевых функций
4) TL — класс линейных булевых функций
5) TM — класс монотонных булевых функций
Линейная булевая функция
Функция называется линейной, если её полином Жегалкина имеет степень не выше 1
Самодвойственная функция
Функция f(x1,…,xn) называется самодвойственной, если f(x1,…,xn) = !f(!x1,…,!xn)
