Математический аппарат инженера

Однако при использовании вычислительных машин различия в сложности выполнения операций булевой алгебры и арифметических операций значительно ослабляются.

8. Типы булевых функций. В алгебре логики из множества v = 2²ⁿ различных булевых функций n переменных у= f(x₁, x₂, ..., x_n ) выделяются следующие пять типов булевых функций.

1) Функции, сохраняющие константу 0, т. е. такие f(x₁, x₂, ..., x_n), что f(0,0,…,0) = 0. Так как на одном из 2ⁿ наборов (x₁, x₂, ..., x_n ) значения таких функций фиксированы, то их число равно 2^2n-1 = 1/2 2²ⁿ = 1/2 v, т. е. половина всех функций n переменных сохраняет константу 0.

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

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

- 518 -

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

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

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

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

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

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

- 519 -

С помощью табл. 6 можно следующим образом охарактеризовать свойства булевых функций с позиций функциональной полноты (звездочкой отмечены свойства, которыми обладает данная функция:

Отсюда видно, что рассмотренные в (9.4) системы операций (дизъюнкция и отрицание, конъюнкция и отрицание, штрих Шеффера, стрелка Пирса) удовлетворяют теореме о функциональной полноте. Система операций алгебры Жегалкина (сумма по модулю 2 и конъюнкция) вместе с константой 1 образует ослабленно функционально полную систему.

Выбрав любую элементарную функцию и дополнив ее одной или несколькими другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте, можно выразить через них все другие булевы функции. Например, в основу одного из таких комплектов можно положить импликацию и константу 0. Тогда x₁ ∨ x₂ = (x₁ → x₂) → x₂ и x̅ = x → 0, а через дизъюнкцию и отрицание выразятся и все остальные функции. В качестве другого функционально полного комплекта можно взять конъюнкцию, эквиваленцию и константу 0. При этом x̅ = x~0 и формулы алгебры логики, построенной на этих операциях, будут двойственны формулам алгебры Жегалкина, если в качестве двойственных символов принять + и ~, а также 1 и 0.