Boolean Functions

Question 1

Булева функция

Answer 1

Функция, зависящая только от булевых переменных и принимающая значения в интервале {0,1}. f: {0,1}^n — {0,1}

Question 2

Мощность множества булевых функций

Answer 2

(2)^2^n

Question 3

Элементарные булевы функции

Answer 3

1) Логическое «или» — функция максимума — дизъюнкция
2) Логическое «и» — функция минимума — конъюнкция
3) Сложение по модулю 2
4) Эквивалентность
5) «если у, то х» — импликация
6) Отрицание дизъюнкции

Question 4

Элементарная конъюнкция

Answer 4

Конъюнкция литералов булевых переменных, каждая из которых встречается не более 1 раза

Question 5

ДНФ

Answer 5

Дизъюнкция конечного множества элементарных конъюнкций называется дизъюнктивной нормальной формой

Question 6

Совершенная ДНФ

Answer 6

ДНФ, которая содержит только полные элементарные конъюнкции

Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама, либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ).

Question 7

Утверждение: Связь ДНФ и СДНФ

Answer 7

Любую логическую формулу А, которая не является противоречием, можно преобразовать в ДНФ, а её — в СДНФ

Question 8

Утверждение: Связь КНФ и СКНФ

Answer 8

Любую логическую формулу А, которая не является тавтологией, можно преобразовать в КНФ, а её — в СКНФ

Question 9

Принцип двойственности

Answer 9

Двойственная к суперпозиции булевых функций функция есть суперпозиция двойственных функций

Question 10

Двойственная функция

Answer 10

Пусть f — булевая функция, тогда функция g называется двойственной, если g(x1, … xn) = !f (!x1, … !xn)
! — это горизонтальная черта, то есть отрицание

Question 11

Альтернативная формулировка принципа двойственности

Answer 11

Если булева функция f реализуется формулой А, в состав которой входят g1, g2,… То двойственная функция f* реализуется формулой, которая получается из А заменой каждого вхождения gi на g*i

Question 12

Двойственное разложение Шеннона

Answer 12

…

Question 13

Свойства двойственных функций

Answer 13

1) (f) = f
2) 0* = 1, 1* = 0
3) Дизъюнкция и конъюнкция являются двойственными по отношению друг к другу

Question 14

Правила Де-Моргана

Answer 14

Отрицание конъюнкции есть дизъюнкция отрицаний.
Отрицание дизъюнкции есть конъюнкция отрицаний.

Question 15

КНФ

Answer 15

Нормальная форма, которая представлена в виде конъюнкции конечного числа элементарных дизъюнкций.

Элементарной дизъюнкцией назовем дизъюнкцию переменных множества X, в которую каждая переменная входит не более одного раза (с инверсией или без инверсии).

Question 16

СКНФ

Answer 16

?

Question 17

Полиномиальная нормальная форма, её степень

Answer 17

Сумма по модулю 2 попарно различных элементарных конъюнкций. Степенью ПНФ называется максимальный ранг среди содержащихся в ней элементарных конъюнкций

Question 18

Совершенная ПНФ

Answer 18

ПНФ называется совершенной, если она содержит только полные элементарные конъюнкции

Question 19

Ранг ЭК, полная ЭК

Answer 19

Число литералов, входящих в элементарную конъюнкцию, называется её рангом. Полной называется элементарная конъюнкция, в которую входит максимальное число литералов

Question 20

Полином Жегалкина

Answer 20

Полином Жегалкина — многочлен над полем Z2, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или.

Другими словами, это ПНФ, образованная ЭК, которые не содержат отрицаний переменных

Question 21

Теорема Жегалкина

Answer 21

Каждая булева функция представима в виде полинома Жегалкина.
Для любой булевой функции существует единственный полином Жегалкина

Question 22

Основные замкнутые классы булевых функций

Answer 22

1) To — класс, сохраняющий константу 0
2) T1 — класс, сохраняющий константу 1
3) Ts — класс самодвойственных булевых функций
4) TL — класс линейных булевых функций
5) TM — класс монотонных булевых функций

Question 23

Линейная булевая функция

Answer 23

Функция называется линейной, если её полином Жегалкина имеет степень не выше 1

Question 24

Самодвойственная функция

Answer 24

Функция f(x1,…,xn) называется самодвойственной, если f(x1,…,xn) = !f(!x1,…,!xn)

Question 25

Замкнутое множество булевых функций

Answer 25

Множество булевых функций S называется замкнутым, если [S] = S, если S замкнуто, то последовательность суперпозиций функций из S тоже содержится в S.

Если любая булева функция, являющаяся суперпозицией функций некоторого множества, принадлежит этому множеству, то такое множество называют замкнутым

Question 26

Замыкание

Answer 26

Пусть S — подмножество булевых функций, замыканием [S] называется множество таких булевых функций, которое представимо формулами через функции множества S

Question 27

Свойства замыкания

Answer 27

1) S € [S]
2) [[S]] = [S]
3) Если S1 € S2, то [S1] € [S2]
4) [S1] U [S2] € [ S1 U S2 ]
5) Замыкание пересечения S1, S2 лежит в пересечении замыканий

Question 28

Критерий Поста

Answer 28

Система S булевых функций является полной тогда и только тогда, когда S не содержится целиком ни в одном из основных замкнутых классов To, T1…

Question 29

Полная система булевых функций

Answer 29

Множество булевых функций S называется полной системой, если замыкание этого множества совпадает с множеством всех функций, [S] = Ф.

Question 30

Монотонная функция

Answer 30

Пусть а = (а1, а2, … аn), b = (b1, b2, … bn), ai <= bi. Функция f (x1, .. xn) монотонная, если f(a) <= f(b)

Question 31

Свойства суммы по модулю 2

Answer 31

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