Булевы функции. Табличное задание функции

Табличное задание функции

Как и бинарный закон компо­зиции, однородная функция двух переменных может быть задана таблицей соответствия (матрицей), строки и столбцы кото­рой соответствуют буквам алфавита. Таким способом можно представлять функции одной и двух переменных. Для представления функций трех и большего числа переменных потребовались бы трехмерные и, вообще, п -мерные таблицы. Этого можно избежать, если столбцы матрицы поставить в соответствие не буквам алфавита, а словам, т.е. образовать k столбцов. Для каждой функции отводится строка, клетки которой запол­няются буквами из данного алфавита. Матрицавсех функций п переменных в k -значном алфавите содержит строк и называ­ется общей таблицей соответствия. Например, для k =3 и п = 2 такая матрица имеет вид:

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

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

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

Число всевозможных булевых функций п переменных быстро возрастает с увеличением п (при п = 3 оно равно 256, а при п = 5 превышает 4 миллиарда). Но функции одной и двух перемен­ных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при п = 2).

Общаятаблица соответ­ствия для булевых функций одной переменной имеет следующий вид (справа указаны обозначения функций):

Две функции = 0 и = 1 представляют собой функции-константы (тождественный ноль и тождественная единица), так как они не изменяют своих значений при изменении аргумента. Функ­ция = х повторяет значения переменной х и потому просто сов­падает с ней.

Единственной нетривиальной функцией является, назы­ваемая отрицанием или инверсией. Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

Все 16 функций двух переменных приведены в табл. 8.1, где указаны условные обозначе­ния, названия и значения функции (в скобках даны встречающиеся в литературе варианты).

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

Шесть из приведенных функций не зависят от x ₁ или x ₂ (или от обоих вместе). Это две константы (= 0 и = 1), повторения (и) и отрицания (и), являющиеся функциями одной переменной (x ₁ или x ₂). Из остальных десяти функ­ций две (и) отличаются от соответствующих им (и) лишь порядком расположения аргументов и поэтому не являются само­стоятельными. Поэтому из 16 булевых функций двух переменных только восемь являются оригинальными ().

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

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