Разложение булевых функций

Теорема 2. Каждая функция из может быть представлена следующим образом:

1. ,

2. ,

3. .

Доказательство пункта 1: Возможны два случая:

1) , тогда .

2) , тогда

Аналогично доказываются пункты 2 и 3.

Теорема 3. Каждая функция из при , представима в виде:

1. ,

где

2. , где

3. ,

где ,

Доказательство пункта 1: Рассмотрим произвольный набор длины .

Слева мы имеем .

Учтем, что

по определению,

а это означает, что .

Так как , значит, равна нашей формуле в том и только в том случае, когда .

Отсюда – это справа, так как остальные конъюнкции = 0. А слева мы получаем то же выражение, потому что . Итак, .

Пункты 2 и 3 доказываются аналогично.