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

Булева функция считается заданной, если можно указать значения истинности этой функции при всех возможных комбинациях значений истинности входящих в нее элементов. Таблицу, которая представляет все возможные комбинации значений истинности некоторого набора элементов А,В,С,…называется БАЗИСОМ.

Если значение «истина» обозначить 1, а значение «ложь» - 0, то для одного элемента А базис содержит 2¹ колонок

# А=0 1,

для двух элементов А,В - 2² колонок

# А=0 1 0 1

# В=0 0 1 1,

для трех элементов А,В,С – 2³ колонок

# А=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 элементов существует столько базисов, сколько существует перестановок из 2ⁿ колонок, а именно: (2ⁿ)!

Если колонки базиса упорядочены и расположены в возрастающем порядке, то базис будет стандартным. Все остальные базисы – нестандартные.

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

Операции над изображающими числами производятся по следующим правилам:

#(АВ)=#А#В,

причем сложение #А и #В выполняется поразрядно по правилу 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

Дата добавления: 2014-01-04