Изображающие числа и базис
Булева функция считается заданной, если можно указать значения истинности этой функции при всех возможных комбинациях значений истинности входящих в нее элементов. Таблицу, которая представляет все возможные комбинации значений истинности некоторого набора элементов А,В,С,…называется БАЗИСОМ.
Если значение «истина» обозначить 1, а значение «ложь» - 0, то для одного элемента А базис содержит 21 колонок
# А=0 1,
для двух элементов А,В - 22 колонок
# А=0 1 0 1
# В=0 0 1 1,
для трех элементов А,В,С – 23 колонок
# А=0 1 0 1 0 1 0 1
# В=0 0 1 1 0 0 1 1
# С=0 0 0 0 1 1 1 1.
Строки базиса называются изображающими числами соответствующих элементов и обозначают приписыванием слева знака #.
Очевидно, что для n элементов существует столько базисов, сколько существует перестановок из 2n колонок, а именно: (2n)!
Если колонки базиса упорядочены и расположены в возрастающем порядке, то базис будет стандартным. Все остальные базисы – нестандартные.
Как видно, используя базис, можно в явном виде перечислить все значения истинности булевой функции при всех возможных значениях истинности элементов, от которых эта функция зависит.
Операции над изображающими числами производятся по следующим правилам:
#(АВ)=#А#В,
причем сложение #А и #В выполняется поразрядно по правилу 00=0; 01=1; 10=1; 11=1, например, изображающее число #(АВС) по отношению к базису b[А,В,С]
# (АВС)=0 1 1 1 1 1 1 1.
Изображающее число коньюнкции двух элементов определяется как произведение изображающих чисел сомножителей
#(АВ)=(#А)(#В),
Причем перемножение А и В выполняется поразразрядно по правилу 00=0, 01=0, 10=0, 11=1. Например, по отношению к базису b[А,В,С]
# (АС)=0 0 0 0 0 1 0 1.
Изображающее число отрицания А получится из изображающего числа А заменой в каждом разряде 0 на 1 и 1 на 0, например
#(А)= 1 0 1 0 1 0 1 0.
Используя введенные выше понятия, вычислим по отношению к базисам b[А,В,С] и b[А1,В1,С1] соответственно изображающие числа функций в левых и правых частях приведенных соотношений эквивалентности:
#(АВС) = 1 0 0 0 0 0 0 0
#[А(ВС)] = 0 0 0 1 0 1 0 1
#(АВВС) = 0 0 1 0 1 1 1 0 (4.2)
#[С(АВ)¬А¬С] = 1 0 1 0 0 1 1 1
Значения столбцов 9 0 12 2 4 14 12 10
#( ¬А1В1¬С1) = 0 0 1 0 0 0 0 0
#[¬В1¬ (А1С1)] = 1 1 0 0 1 0 0 0
#(¬А1С1А1В1) = 0 0 0 1 1 0 1 1 (4.3)
#(¬А1А1В1С1) = 1 0 1 0 1 0 1 1
Значения столбцов 10 2 9 4 14 0 12 12