Булевы функции

Функция f (x₁, x₂,..., x_n), принимающая два значения: 0 и 1 и зависящая от переменных, каждая из которых может принимать значения 0 и 1, называется булевой или переключательной. Из определения следует, что область определения булевой функции – совокупность всевозможных n-мерных наборов из нулей и единиц, а для её задания достаточно указать, какие значения функции соответствуют каждому из наборов (табл. 3.3).

Таблица 3.3 – Задание булевой функции

Порядок расположения наборов, принятый в таблице, называется стандартным или естественным. При таком порядке каждому набору

[Ò1] a = (a₁,...,a_n), где a_i есть 0 или 1, ставится в соответствие число

N = a₁ 2^n-1 +... + a_n-1 2 + a_n .

Наборам (0, 0,...,0, 0), (0, 0,...,0, 1),..., (1, 1,...,1, 1) соответствуют числа 0, 1,..., 2ⁿ-1. Естественным порядком будет расположение наборов в порядке возрастания соответствующих им чисел. Десятичное число, соответствующее входному набору, является его номером. Поэтому очевидно, что количество k входных наборов для булевой функции n переменных равно k=2ⁿ. Количество же различных функций n переменных можно определить из следующих соображений. Каждая функция задается набором своих k значений (для k входных наборов), которому также можно поставить в соответствие k-разрядное двоичное число. Располагая теперь в таблице функции в порядке возрастания соответствующих им чисел, мы получим все возможные различные функции. Количество таких функций будет равно .

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

Таблица 3.4 – Булевы функции одной переменной

Таблица 3.5 – Булевы функции двух переменных

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

Функции f₁, f₁₆ – константы 0 и 1. Они не зависят существенно ни от одной переменной.

Функции f₄ = х₁, f₁₁ =`х<sub>2</sub>, f<sub>6</sub> = х<sub>2</sub>, f<sub>13</sub> =`х₁ зависят существенно только от одной переменной.

f₂ = х₁ ٨ х₂ – конъюнкция или логическое умножение (знак «٨» можно заменять на «∙», либо опускать).

f₈ = х₁ ٧ х₂ – дизъюнкция или логическое сложение.

f₁₀ – эквивалентность, х₁ ~ х₂.

f₇ = х₁ Å х₂ или х₁ + х₂ (mod 2) – сложение по модулю два.

f₁₂, f₁₄ – импликация, х₂ ® х₁ и х₁ ® х_2.

f₁₅ – штрих Шеффера, х₁ | х_2.

f₉ – стрелка Пирса, х₁ ¯ х₂ (другое название – функция Вебба).

f₃, f₅ – функции запрета х₁ и х₂ соответственно. f₃ = х₁ ® х₂,

f₅ = х₂ ® х₁.

Исходя из элементарных функций можно строить формулы, т.е. рассматривать функции от функций например, (x₁ Å x₂)`х₂) ® х₃.