2.4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма

Возникает вопрос. Если в качестве В допустить некоторый запас элементарных функций, то всякая ли функция алгебры логики может быть выражена в виде формулы? Ближайшие рассмотрения направлены на решение этого вопроса.

Обозначим

x^σ=xΛσV Λ ,

где σ – параметр, равный либо 0, либо 1.

Очевидно, что

Легко видеть, что x^σ=1, тогда и только тогда, когда x=σ.

Теорема (о разложении функций по переменным)

Каждую функцию алгебры логики f(x₁, …, x_n) при каждом m=1…n можно представить в виде:

(2.1)

где дизъюнкция берется по всем возможным наборам значений переменных x₁, …, x_m (это представление называется разложением функции по переменным x₁, …, x_m).

Доказательство:

Рассмотрим произвольный набор значений переменных (α₁,…,α_n) и подставим его в левую и правую части равенства (2.1).

Левая часть дает f(α₁, …, α_n).

Правая

Т.е. на каждом наборе (α₁, …, α_n) левая и правая части совпадают, что и требовалось доказать.

В качестве следствий из этой теоремы получаем два специальных случая разложения.

1) Разложения по переменной

f(x₁, …, x_n-1, x_n)= x_nΛ f(x₁, …, x_n-1, 1)V Λ f(x₁, …, x_n-1, 0).

Функции f(x₁, …, x_n-1, 1) и f(x₁, …, x_n-1, 0) называются компонентами разложения.

2) Разложение по всем n переменным

(2.2)

Это разложение (2.2) называется совершенной дизъюнктивной нормальной формой (совершенной д.н.ф.).

Имеет место

Теорема: Каждая функция алгебры логики может быть выражена в виде формулы через отрицание, конъюнкцию и дизъюнкцию.

Доказательство:

1) Если f(x₁, …, x_n) ≡ 0, то f(x₁, …, x_n) = x₁Λ .

2) Если f(x₁, …, x_n) ≠ 0,

то .

Доказанная теорема носит конструктивный характер. Она позволяет для каждой функции построить формулу, ее реализующую (в виде совершенной д.н.ф.). Для этого:

1. В таблице истинности для функции f(x₁, …, x_n) отмечаем все строки (σ₁, …, σ_n), в которых f(σ₁, …, σ_n)=1.

2. Для каждой такой строки образуем логическое произведение .

3. Все полученные конъюнкции соединяем знаком дизъюнкции.

Пример 10.

1) Найти совершенную д.н.ф. для функции x₁→x₂.

Имеем три набора (0, 0), (0, 1), (1, 1), на которых эта функция равна 1. Поэтому

x₁→x₂=x₁°Λx₂°V x₁°Λx₂¹ V x₁¹Λx₂¹= Λ V Λx₂V x₁Λx₂.

3. Найти совершенную д.н.ф. для функции, заданной нижеследующей таблицей 8.

Таблица 8

x1	x2	x3	f(x1, x2, x3)
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

f(x₁, x₂, x₃) = Λ Λ V Λ Λx₃V x₁Λ Λx₃ V x₁Λx₂Λ x₃.

Совершенная дизъюнктивная нормальная форма имеет вид ΣП. Нельзя ли для булевых функций получить выражение типа ПΣ? Покажем, что при f≠1 это возможно.

Для этого разложим двойственную функцию f* к функции f (f*≠0) в совершенную д.н.ф..

Возьмем тождество для двойственных функций

Т.к. f**=f, то

Это выражение носит название совершенной конъюнктивной нормальной формы (совершенной к.н.ф.).

Пример 11.

1. Построить совершенную к.н.ф. для функции x₁→x₂.

f(x₁,x₂)=0 только для набора (1, 0)

x₁→x₂= V =x₁°Vx₂¹ = V x₂.

2) Построить совершенную к.н.ф. для f(x₁, x₂, x₃) из предыдущего примера

f(x₁, x₂, x₃) =(x₁V Vx₃)Λ(x₁V V )Λ( Λx₂Λ x₃)Λ

Λ( V Vx₃).

Выводы: В качестве средства для задания булевых функций наряду с таблицами можно использовать язык формул над множеством функций, состоящим из отрицания, конъюнкции и дизъюнкции. Так как табличный язык по громоздкости примерно эквивалентен языку совершенных д.н.ф. (к.н.ф.), то язык формул не хуже языка таблиц. Можно показать, что на самом деле он существенно лучше таблицы.

К примеру, рассмотрим функцию

f(x₁, …, x₂₀) =x₁V x₂V…Vx₂₀ .

Эта формула в правой части содержит 39 символов, ее же таблица содержит 2²⁰ строк, т.е. больше миллиона.