Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 5 страница

Теперь, для того чтобы получить СКНФ, достаточно проинвертировать последнее выражение:

Y_СКНФ = (А Ú В Ú С Ú D) (А Ú В Ú С Ú ) (A Ú  Ú C Ú D) (  Ú B Ú C Ú ).

13.3. Алгебра Жегалкина

Другая алгебра булевых функций строится на основе операций сложения по модулю 2 и конъюнкции. Она называется алгеброй Жегалкина (АЖ).

Свойства АЖ:

1) Коммутативность x Å y = y Å x, xy = yx.

2) Ассоциативность x Å(y Å z) = (x Å y)Å z, x (y z) = (x y) z.

3) Дистрибутивность умножения относительно сложения x (y Å z) = x y Å x z.

4) Свойства констант x 1 = x, x 0 = 0, x Å0 = x.

Справедливы также соотношения:

     = 1Å x, x ₁ Ú x ₂ = x ₁Å x ₂Å x ₁ x ₂, x ₁Å x ₂ = x₁  Ú x ₂.

Используя эти формулы, можно перейти от АЖ к БА и обратно.

Например.

1) x (  Ú y) = x [(1Å x)Å y Å(1Å x) y ] = x (1Å x Å y Å y Ú x y) = x (1Å x Å x y) = x Å x x Å x x y = x y.

2) 1Å x Å y Å x y = (1Å x)(1Å y) = .

Через операции алгебры Жегалкина можно выразить все другие БФ. Пример показан в табл. 13.2.

                           Таблица 13.2.

x 1 ® x 2 =  Ú x 2 = 1Å x 1Å x 1 x 2

x 1 ~ x 2 = (  Ú x 2)(x 1 Ú ) = 1Å x 1Å x 2

x 1 x 2 =  = x 1Å x 1 x 2

x 1 | x 2 =  = 1Å x 1 x 2

x 1 ¯ x 2 =  = 1Å x 1Å x 2Å x 1 x 2

13.4. Функциональная полнота БФ

В алгебре логики из множества n =  различных БФ n переменных y = f (x ₁,..., x_n) выделяют пять типов БФ.

1) Функции, сохраняющие константу 0, т.е. такие f (x ₁,..., x_n), что f (0,..., 0) = 0, их число .

2) Функции, сохраняющие константу 1, т.е. такие f (x ₁,..., x_n), что f (1,..., 1) = 1, их число равно половине общего числа всех функций n переменных т.е. .

3) Самодвойственные функции, т.е. такие, которые, принимают противоположные значения на любых двух противоположных наборах. Их число .

4) Линейные функции, т.е. такие, которые представляются в алгебре Жегалкина каноническим многочленом, не содержащим произведений переменных a ₀ + a ₁ x ₁ +... + a_nx_n, где коэффициенты a ₀,..., a_n принимают значения 0 или 1. Так как всего коэффициентов n + 1, то число различных линейных функций будет .

5) Монотонные функции, т.е. такие, которые для любых двух наборов из множества значений переменных, частично упорядоченного соотношением (a ₁,..., a _n) £ (b ₁,..., b _n), при a _i £ b _i (i = 1, 2,..., n), удовлетворяют неравенству f (a ₁,..., a _n) £ f (b ₁,..., b _n).

Система функций, суперпозицией которых представляется любая функция из некоторого множества БФ, называется функционально полной. Если в такой системе допускаются константы 0 и 1, то ее называют ослаблено функционально полной. Говорят, что ФПС функций образует базис в логическом пространстве. Система функций называется минимально полным базисом, если удаление из нее любой функции превращает эту систему в неполную.