§ 5.2. Изображающие числа и базис

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

Условимся значение истинности элемента («истина») обозначать 1, а значение «ложь» — 0. Тогда для одного элемента А базисом будет

для двух элементов базис содержит 22 столбцов:

для трех элементов базис состоит из 23 столбцов:

и вообще для элементов базис содержит строк и столбцов. Если колонки базиса рассматривать как целые двоичные числа, записанные так, что самый младший разряд их соответствует первой строке базиса, а самый старший последней строке, то колонки базиса для элементов представляют собой числа от 0 до Будем считать эти числа номерами колонок базиса и отметим сверху каждую колонку ее номером. Если колонки базиса упорядочены и записаны в возрастающем порядке их номеров слева направо, то базис будет стандартным-, все другие базисы — нестандартные. Для элементов существует столько базисов, сколько можно составить перестановок из колонок, т. е. Стандартный базис для элементов обозначается причем порядок элементов в квадратных скобках совпадает с порядком строк базиса.

Строки базиса называют изображающими числами соответствующих элементов и обозначают приписыванием слева от элемента знака Заметим, что по отношению к стандартному базису изображающее число состоит из чередующихся нулей и единиц, состоит из пар нулей и пар единиц, из четверок нулей и четверок единиц и

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

По определению, изображающее число суммы двух элементов равно сумме изображающих чисел слагаемых:

причем сложение выполняется поразрядно без переносов в высшие разряды по правилу

Например, по отношению к

Изображающее число конъюнкции двух элементов определяется как произведение изображающих чисел сомножителей:

причем перемножение выполняется поразрядно по правилу

Например, по отношению к

Изображающее число отрицания А получается из изображающего числа заменой в каждом разряде 0 на 1 и 1 на 0, например,

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

Руководствуясь правилами (5.2) — (5.4), можно найти изображающее число любой булевой функции. Например, по отношению к

Следовательно, данная функция истинна только при таких комбинациях значений истинности элементов которые соответствуют 3, 7, 8, 9, 11 и 15-му столбцам базиса.

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

Используя изображающие числа, можно доказать любое из правил 1 -20 булевой алгебры. Докажем, например, соотношение

вытекающее из правила 19 пополнения булевой функции. Изображающее число левой части было сосчитано в предыдущем примере и равно 0001 0001 1101 0001. Изображающее число правой части отличается от этого числа только на

Поразрядное логическое сложение с 0001 0001 1101 0001 не изменяет этого последнего числа. Следовательно, изображающие числа левой и правой частей рассматриваемого соотношения тождественны.

Для того чтобы проверить истинность импликации

достаточно по отношению к вычислить

1111 и убедиться, что в разрядах 3, 4, 5, 7 последнего числа стоят единицы.