8.1. Элементарная конъюнкция и ДНФ

Пусть имеем множество переменных X={x₁, x₂, …, x_n}.

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

Примеры. Пусть X={x₁, x₂, x₃, x₄}, тогда x₁x ₂x₄, x₁x₃, x₁ 1 являются элементарными конъюнкциями, а x₁x₁x ₂, x₁x₂ x ₂x₄ не являются. •

Определение. Число переменных, образующих элементарную конъюнкцию, назовем ее рангом.

Примеры. Ранги элементарных конъюнкций x₁x ₃x₄ и 1 равны трем и нулю. •

Определение. Полной конъюнкцией назовем элементарную конъюнкцию, состоящую из всех n переменных множества X, то есть конъюнкцию ранга n.

Пример. При n = 4 конъюнкция x₁x₂ x ₃x₄ – полная. •

Определение. Две конъюнкции называются ортогональными по переменной x_i, если эта переменная входит в одну конъюнкцию с инверсией, а в другую без инверсии.

Пример. Конъюнкции x₁x₂ x ₃ и x ₁x₃x ₄ ортогональны по переменным x₁ и x₃. •

Определение. Две конъюнкции называются смежными, если они ортогональны по одной и только одной переменной x_i (принято также говорить ''смежны по переменной x_i'').

Пример. Конъюнкции x₁x₂ x ₃ и x₁x₃x ₄ являются смежными по переменной x₃ (ортогональны только по x₃). •

Определение. Две конъюнкции называются соседними, если они ортогональны по одной и только одной переменной x_i и совпадают по остальным (принято также говорить ''соседние по переменной x_i'').

Пример. Конъюнкции x₁x₂ x ₃ и x₁x₂ x₃ являются соседними по переменной x₃ (ортогональны только по x₃ и совпадают по x₁ и x₂). •

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

Примеры. Конъюнкции x₁x₂ x ₃ и x₁x₂ x₃ являются соседними по переменной x₃, следовательно, к ним применим закон склеивания соседних конъюнкций по x₃:

x₁x₂ x ₃ x₁x₂ x₃= x₁x₂ .

Конъюнкции x₁x₂ x ₃ и x₁x₃x ₄ являются смежными по переменной x₃, следовательно, к ним применим закон обобщенного склеивания смежных конъюнкций по x₃:

x₁x₂ x ₃ x₁x₃x ₄ = x₁x₂ x ₃ x₁x₃x ₄ x₁x₂ x ₄.

Определение. Дизъюнктивной нормальной формой(ДНФ) булевой функции f(x₁, …, x_n) назовем дизъюнкцию различных элементарных конъюнкций, задающую функцию f(x₁, …, x_n).

Пример. x₁x ₂ x₁x ₂x₃ x₁x ₃x ₄ = ДНФ. •

Определение. Длиной ДНФ назовем число ее конъюнкций, а рангом ДНФ – сумму рангов конъюнкций.

Пример. Длина ДНФ из предыдущего примера равна трем, а ранг – восьми. •

Будем применять обозначение ДНФ_f, если захотим отметить, что ДНФ представляет булеву функцию f(x₁, …, x_n).

Очевидно, что совершенная ДНФ является частным случаем ДНФ, все конъюнкции которой полные. Любая ДНФ может быть преобразована в совершенную ДНФ с использованием основных равносильностей – законов склеивания и поглощения конъюнкций.