Булевы (гулевы) функции

Что такое булева алгебра?
Булевой алгеброй называется непустое множество AA с двумя бинарными операциями ∧∧ (аналог конъюнкции), ∨∨ (аналог дизъюнкции), одной унарной операцией ¬¬ (аналог отрицания)
В алгебре логики основными (элементарными) операциями являются отрицание, логическое сложение (дизъюнкция), логическое умножение (конъюнкция), импликация, эквивалентность.
При упрощении булевых формул или высказываний, связанных скобками и логическими операциями, используют следующие правила приоритета (или старшинства) логических операций - от наиболее сильной - к слабой:
¬∧∨→↔
Словесно: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Суперпозиции
Суперпозиция функций, композиция функций — функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Пусть нам дан некоторый набор булевых функций K. Получить новую функцию, являющеюся композицией функций из K, мы можем следующими способами:
1) Подстановкой одной функции в качестве некоторого аргумента для другой;
2) Отождествлением аргументов функций.

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

Двойственная функция
Будем называть булеву функцию f*(x1,x2,…,xn), n1, двойственной относительно функции f(x1,x2,…,xn), если она получена из f(x1,x2,…,xn) инверсией всех аргументов и самой функции:
f*(x1, x2,…, xn) f '(x1', x2',…, xn').
Замечание. При n=0 полагают, что функция 0 двойственна 1, а 1 двойственна 0.