операции обобщенного склеивания

х-у \/ х-г\/ уг = х-у У x-z, (х V г/)-(5 V г)-((/ V г) = (x V У) {х V г); X \jf х-у = X \/ у,

х.(х V г/) = ху-

(1,17)

(1.18)

Теоремы (1.6) - (1.13) и (1.15) - (1.18) записаны парами, причем каждая из теорем пары является двойственной другой, так как из одной теоремы пары можно получить другую на основании принципа двойственности, т. е. путе.м взаимной замены операций дизъюнкции и конъюнкции, а также элементов О и 1, если они имеются. Теорема (1.14) самодвойственна, так как она не изменяется по принципу двойственности (отсутствуют элементы О и 1 и операции дизъюнкции и конъюнкции).

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

Некоторые теоремы и тождества алгебры логики имеют особое значение, так как позволяют упрощать логические выражения. Например, в соотношениях (1.6), (1.10) -(1.12), (1.15) -(1.18) правая часть проще левой, поэтому, произведя в логических выражения.х соответствующие преобразования, можно добиться существенного их упрощения. Особенно часто для преобразования логических выражений, с целью их упрощения, используются тождества (1.15) - (1.18).

Операция сумма по модулю два (исключающее ИЛИ, логическая неравнозначность) обозначается символом ф и определяется соотношением

х®у = ху\/xy = {x\/y){xV у). (1.19)

Используя аксиомы алгебры логики (1.1) - (1.5), легко убедиться, что:

ОфО=1®1 = 0; Оф1 = 1фО=1. (1.20)

Из соотношений следует, что зиачепне хфг/ совпадает со значением младшего разряда суммы двух двоичных чисел, где х я у - значения младших разрядов этих чисел. Соответственно этому значение г-го разряда суммы двух дроичных чисел будет определяться значением д;,-ф j/j ©2,-, где х, и yi - значения (-х разрядов двоичных чисел, а г,-перенос в i-й разряд из предыдущего ((-1)-го разряда.

Операция сумма по модулю два коммутативна, ассоциативна и дистрибутивна относительно операции конъюнкции, т. е.

х®у = у®х, X Э) {у (S Z) = (х Q у) ®г, х{у ® г) =ху ® хг.

(1.2!)

Для операции сумма по модулю два справедливы также следующие тождества:

хфО = х; хф1=х; х®х = 0; хфх=1; хе~У xV ху = (х\/ у){х\/у) = х®у = х®у.

(1.22)

1.2. Переключательные функции

Любое логическое выражение, составленное из п переменных Хп,.... Xi с помощью конечного числа операций алгебры логики, можно рассматривать как некоторую функцию п переменных. В соответствии с аксиомами (1.1) -(1.5) функция может принимать в зависимости от значений переменных только два значения: О и 1. Такие функции являются весьма удобным инструментом для описания, анализа и синтеза переключательных схем, выходные сигналы которых характеризуются лишь двумя уровнями напряжения: высоким (1) и низким (0). В связи с этим такие функции называются переключательными (термин «переключательная» часто будем опускать, так как никакие другие функции не рассматриваются).

Позиционные системы счисления. Совокупность правил записи чисел называется системой счисления. Наиболее часто используются позиционные системы счисления, в которых целое положительное число записывается в виде последовательности символов е„е„ ... ...ер...е2еи а вес каждого символа ер определяется его позицией в записи числа. В Дальнейшем будут использоваться только позиционные системы счисления, в которых вес символа вр равен где q - основание системы счисления, а ер=0, 1,<7-1. Тогда любое целое положительное число Е в системе счисления с основанием q можно записать в виде Я= (en...ep...ei)5=en(?"~-f ...-f ei<7°=>

- 2 epq-. При вычислении суммы полагаем, что все значения

р=\

Ср и qp- представлены в привычной десятичной системе счисления.

Максимальное ге-разрядное число получается при ep=q-\ для п

всех р: Ятах= 2 (<?-)<?""=<?"-1.Из этого следует, что существу-

ет различных ге-разрядных чисел (с учетом нуля). В табл. 1.1 показан перевод 16 чисел из одной системы в другую при наиболее часто используемых основаниях систем счисления q-2, 10, 8, 16.

Перевод чисел из системы счисления с произвольным основанием в десятичную систему счисления (q-W) выполняется по приведенным формулам, для чего требуется перевести в десятичную систему счисления только числа вр и q. Несколько сложнее произвести перевод чисел из десятичной системы счисления в систему счисления с основанием qф\Q. Наиболее просто такой перевод выполняется для q~2, 8, 16. Пусть требуется перевести число (1987)!о в указанные системы счисления. Перевод осуществляется последовательным делением числа, заданного в десятичной системе счисления, на q = 9,:

tm 8

J8 -

£7

Bee 8

8 8

Та б л и Ц a 1.1

Таким образом, (1987) !0= (3703)8. Для перевода полученного числа в двоичную систему счисления достаточно каждую цифру представить в двоичном коде: (3703)8= (11.111.000.011)2. Перевод полученного двоичного числа в 16-ричную систему счисления- выполняется его разбиением на тетрады (тетрада - четыре разряда) и переводом каждой тетрады в 16-ричную систему счисления: (111.1100,0011)2= (7СЗ) ,9. Итак, получили (1987) ,о= (3703)8= = (11111000011)2= (7СЗ),в.

Для обозначения произвольных десятичных чисел используются символы i, / и тому подобное, а двоичные числа записываются в виде en...ep...ei, где ер=0 или 1. Равенства для десятичных и двоичных чисел записываются, опуская индекс, указывающий основание системы счисления i=en...ep...ei.

Свойства переключательных функций. Для функций п перемен-