2.2. ТАБЛИЦЫ СООТВЕТСТВИЯ

Множество функций переменных можно представить с помощью таблицы соответствия, столбцы которой отводятся для слов длины , а строки — для функций. При этом номера столбцов определяются расположенными над ними -разрядными двоичными числами, которые читаются по вертикали сверху вниз. Номера функций отождествляются с -разрядными двоичными числами, записанными в соответствующих строках таблицы. Таблицу соответствия часто называют также таблицей истинности. Таблица соответствия для булевых функций одной переменной имеет вид (справа указаны обозначения функций)

Функции представляют собой константы (соответственно тождественный нуль и тождественную единицу), так как они не изменяют своих значений при изменении аргумента. Функция — это повторение, так как ее значения просто совпадают со значениями переменной . Единственной нетривиальной функцией является , называемая отрицанием или инверсией (читается «не ). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

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

Таблица 2.1

(см. оригинал)

Среди остальных 10 функций две отличаются от соответствующих им функций лишь порядком расположения аргументов. Поэтому из 16 булевых функций двух переменных оригинальными являются только восемь: . Можно также заметить, что среди булевых функций некоторого числа переменных содержатся всевозможные функции меньшего числа переменных, которые называются вырожденными функциями. Так, среди функций одной переменной имеются две вырожденные — константы 0 и 1, которые можно рассматривать как функции от нуля переменных. Функции двух переменных содержат те же константы и четыре функции одной переменной и т. д.

Функции от любого числа переменных можно получить с помошью суперпозиции, т. е. замещения переменных некоторыми функциями. Например, подставляя в вместо а дизъюнкцию и вместо b импликацию , а затем вместо с отрицание , получаем . Таблица соответствия для этой функции трех переменных записывается на основе таблиц элементарных функций (табл. 2.1):

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