Здавалка
Главная | Обратная связь

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



Решение булевых уравнений

 

Основные правила алгебры логики следующие (здесь и далее знак «+» обозначает дизъюнкцию (логическое «или»), знак «∙» - конъюнкцию (логическое «и»), черта над переменной – знак отрицания, а знак «=» обозначает логическую эквивалентность):



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

 

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

Булева функция считается заданной, если можно указать значения истинности этой функции при всех возможных комбинациях значений истинности входящих в нее элементов. Таблицу, которая представляет все возможные комбинации значений истинности некоторого набора элементов А, В, С, ..., называют базисом. Если значение «истина» обозначить 1, а значение «ложь» — 0, то для одного элемента А базис содержит 21 колонок:

для двух элементов А, В — 22 колонок:

для трех элементов А, В, С — 23 колонок:

 


и вообще для n элементов А1 ..., Аn базис содержит и строк и 2 колонок. Если колонки базиса рассматривать как целые двоичные числа, записанные так, что самый младший разряд их соответствует первой строке базиса, а самый старший — последней строке, то колонки базиса для n элементов представляют собой числа от 0 до 2n— 1. Будем считать эти числа номерами колонок базиса и отметим сверху каждую колонку ее номером. Если колонки базиса упорядочены и записаны в возрастающем порядке их номеров слева направо, то базис будет стандартным, все другие базисы — нестандартные. Для n элементов существует столько базисов, сколько можно составить перестановок из 2n колонок, т. е. (2n)! Стандартный базис для элементов А, В, С, ... обозначается b [А, В, С, ...], причем порядок элементов в квадратных скобках совпадает с порядком строк базиса.

Строки базиса называют изображающими числами соответствующих элементов и обозначают приписыванием слева от элемента знака #. Заметим, что по отношению к стандартному базису b[А, В, С, В] изображающее число ФА состоит из чередующихся нулей и единиц, #В — из пар нулей и пар единиц, # С — из четверок нулей и четверок единиц и т. д., т. е. #D = 0000 0000 1111 1111.

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

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

причем сложение #А и #В выполняется поразрядно без переносов в высшие разряды по правилу 0 + 0 = 0,0+1 = 1+0= 1,1 + 1 = 1. Например, по отношению к базису b [А, В, С] изображающее число #(А + В + С)=#(А+В)+#С=#А+#В+#С= = 0101 0101+0011 0011+0000 1111=0111 1111.

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

причем умножение #А и #В выполняется поразрядно по правилу 00 = 0, 01 = 10 = 0, 11 = 1. Например, по отношению к b[А, В, С]

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







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.