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)
Замкнутое множество булевых функций
Множество булевых функций S называется замкнутым, если [S] = S, если S замкнуто, то последовательность суперпозиций функций из S тоже содержится в S.
Если любая булева функция, являющаяся суперпозицией функций некоторого множества, принадлежит этому множеству, то такое множество называют замкнутым
Замыкание
Пусть S — подмножество булевых функций, замыканием [S] называется множество таких булевых функций, которое представимо формулами через функции множества S
Свойства замыкания
1) S € [S]
2) [[S]] = [S]
3) Если S1 € S2, то [S1] € [S2]
4) [S1] U [S2] € [ S1 U S2 ]
5) Замыкание пересечения S1, S2 лежит в пересечении замыканий
Критерий Поста
Система S булевых функций является полной тогда и только тогда, когда S не содержится целиком ни в одном из основных замкнутых классов To, T1…
Полная система булевых функций
Множество булевых функций S называется полной системой, если замыкание этого множества совпадает с множеством всех функций, [S] = Ф.
Монотонная функция
Пусть а = (а1, а2, … аn), b = (b1, b2, … bn), ai <= bi. Функция f (x1, .. xn) монотонная, если f(a) <= f(b)
Свойства суммы по модулю 2
1) 0 + х = х, 1 + х = !х
2) x + y = y + x, (x + y) + z = x + (y + z), x(y + z) = xy + xz
3) a v b = a + b + ab
4) a1 v a2 v .. ak = a1 + a2 + … ak , ai*aj = 0
