Имеется ряд специальных подклассов формул, позволяющих задавать все булевы функции. В этом разделе мы определим два таких подкласса функций, использующих только операции
и
.
Пусть
- это множество пропозициональных переменных. Введем для каждого
обозначения:
и
. Формула
(
), в которой
и все переменные разные, т.е.
при
, называется элементарной конъюнкцией (элементарной дизъюнкцией).
Определение 1.4.Формула
называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид
где каждая формула
- это элементарная конъюнкция.
называется совершенной ДНФ, если в каждую из ее конъюнкций
входят все
переменных из
Аналогично, формула
называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций, т.е.
где каждая формула
- это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую
входят все
переменных из
Рассмотрим произвольную булеву функцию
, зависящую от переменных из
. Oбозначим через
множество наборов значений переменных, на которых
принимает значение 1, а через
множество наборов, на которых
принимает значение 0, т.е.
и
Определим по этим множествам две формулы:
и
Теорема 1.1.
(1) Если функция
не равна тождественно 0, то формула
- это совершенная ДНФ, задающая функцию
.
(2) Если функция
не равна тождественно 1, то формула
- это совершенная КНФ, задающая функцию
.
Пример 1.2. Например, для функции
, представленной в таблице 1.1
совершенная ДНФ равна
, а ее совершенная КНФ:
Отметим, что совершенные ДНФ и КНФ часто являются чересчур сложными и длинными представлениями булевых функций. В нашем примере
