Основные равносильности

К основным относят следующие равносильности, которые ре­комендуется запомнить и применять при упрощении формул.

11) Формула Шенона.Докозательство

Определение. Разложением Шеннона называется следую­щее разложение булевой функции f(x₁, ...,x_n) по переменной x_i:

Доказательство(не умоляя общности, для i =1). Покажем, что формула верна в обоих случаях: для x₁ = 0 и x₁ = 1.

Если x₁ = 0, то f (0, x₂, ... , x_n) = 0 f (1, x₂, ... , x_n) Ú 1 f (0, x₂, ... , x_n) =

= f (0, x₂, ... , x_n).

Если x₁ = 1, то f (1, x₂, ... , x_n) =1 f (1, x₂, ... , x_n) Ú 0 f (1, x₂, ... , x_n) == f (0, x₂, ... , x_n).

О пределение. Сомножитель f (x₁, ..., x_{i -1}, 1, x_i+1,... , x_n) в формуле Шеннона называется коэффициентом разложения функции f (x₁, x₂, ... , x_n) по переменной x_i при x_i, а сомножитель f (x₁, ..., x_{i -1}, 0, x_i+1,... , x_n) — коэффициентом разложения функции f (x₁, x₂, ... , x_n) по x_i при .

Пример.Функцию разложим по переменной x:

12) Разложение функции по k переменным. Доказательство

Разложим функцию f(x₁, ...,x_n) последовательно по двум пе­ременным: сначала саму функцию по переменной x₁, затем коэф­фициенты разложения по переменной x₂.

Рассмотрим булеву функцию f (x₁, x₂, ... , x_n) и, используя формулу Шеннона, последовательно разложим функцию

- по первой переменной,

- по двум первым переменным,

- по k первым переменным.

1. Разложим функцию по первой переменной:

f (x₁, x₂, ... , x_n) = x₁ f (1, x₂, ... , x_n) Ú `x₁ f ( 0, x₂, ... , x_n).

2. Разложим в полученной формуле оба коэффициента разложения по второй

переменной:

f (x₁, x₂, ... , x_n) = x₁ f (1, x₂, ... , x_n) Ú `x₁ f ( 0, x₂, ... , x_n) =

= x₁ [ x₂ f (1,1, x₃, ... , x_n) Ú`x₂ f (1,0, x₃, ... , x_n) ] Ú

Ú`x<sub>1</sub> [ x<sub>2</sub> f (0,1, x<sub>3</sub>, ... , x<sub>n</sub>) Ú`x₂ f (0,0, x₃, ... , x_n) ] =

= x₁ x₂ f (1,1, x₃, ... , x_n) Ú x₁`x₂ f (1,0, x₃, ... , x_n) Ú

Ú`x<sub>1</sub> x<sub>2</sub> f (0,1, x<sub>3</sub>, ... , x<sub>n</sub>) Ú`x₁`x₂ f (0,0, x₃, ... , x_n) =

[ свернем последнюю формулу в более короткую, используя следующие

обозначения: x = x¹ и `x = x⁰, то есть x^с, где c Î {0,1}, и условимся

читать символы x^с как “x в степнени c “]

3. По аналогии с предыдущей формулой запишем формулу разложения

функции по k переменным: и докажем, что данное разложение верно.

Доказательство.Подставим в левую и правую части равенства произвольный набор a₁ a₂ ... a_n:

Упростим правую часть, рассуждая следующим образом. Нетрудно проверить, что 1, если и только если a_i = c_i (в самом деле: 0 ⁰ = 1, 1¹ = 1, но 0 ¹ = 0 и 1⁰ = 0), поэтому конъюнкция равна единице лишь в единственном случае, когда наборы a₁ a₂ ... a_k и с₁ с₂ ... с_k совпадают. А это значит, что она не обращает в ноль лишь одно слагаемое правой части — то, для которого a₁ a₂ ... a_k = с₁ с₂ ... с_k и в котором сама обращается в единицу. Подставив в ставшееся слагаемое a₁ a₂ ... a_k вместо с₁ с₂ ... с_k , получим

13) Получение СовДНФ из разложения функции по переменным. Утверждение о существовании и единственности СовДНФ.Алгоритм построения СовДНФ по таблице истинности функции.

Применив формулу разложения булевой функции f (x₁, x₂, ... , x_n) по k переменным при k = n, получим:

Поскольку коэффициентами разложения f (c₁, c₂, ... , c_n) в этой формуле являются значения функции f (x₁, x₂, ... , x_n) на всевозможных наборах c₁ c₂ ... c_n, то возможны два случая:

- если набор c₁ c₂ ... c_n Î M⁰ ( f ), то f (c₁, c₂, ... , c_n ) = 0 и поэтому обращается в 0 соответствующее слагаемое правой части;

- если набор c₁ c₂ ...c_n Î M¹ ( f ), то f(c₁, c₂, ... , c_n ) = 1 и слагаемое упрощается.

В результате имеем формулу разложения функции по всем переменным:

Определение.Совершенная дизъюнктивная нормальная форма булевой функции , или СовДНФ, — это формула вида: