8(495)909-90-01
8(964)644-46-00
pro@sio.su
Главная
Системы видеонаблюдения
Охранная сигнализация
Пожарная сигнализация
Система пожаротушения
Система контроля удаленного доступа
Оповещение и эвакуация
Контроль периметра
Система домофонии
Парковочные системы
Проектирование слаботочных сетей
Аварийный
контроль
Раздел: Документация

0 1 2 3 4 ... 119

они имеются. Теорема (1.14) самодвойственна, так как она не изменяется по принципу двойственности (отсутствуют элементы 0 и 1 и операции дизъюнкции и конъюнкции).

Все теоремы могут быть доказаны аналитически или методом перебора. В табл. 1.1 приведено доказательство одного из тождеств (1.13) методом перебора.

Таблица 1.1. Пример использования метода перебора

х у

х V у

х у

0 0

01

10 1 1

0V0 = 0 = 1 0V1=1=0 1 V0 = 1 = 0 1 V 1 = 1 = 0

0-0 = 1-1 = 1 0 1 = 1-0 = 0 1-0 = 0-1 = 0 1-1 = 00 = 0

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

(х у) V (х • z) - х у V х • z.

Но скобки нельзя опустить в выражении х (у V х) z, поскольку

x-(y\/x)-z = x- y- zx-yVx-z.

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

Операции дизъюнкции, конъюнкции и отрицания легко реализовать довольно простыми контактными (релейными) цепями и электронными схемами с односторонней проводимостью, имеющими конечное число входов и один выход и называемыми логическими элементами (ЛЭ).

Операция сумма по модулю два. Кроме основных операций алгебры логики (дизъюнкция, конъюнкция, отрицание), определяемых аксиомами (1.2) - (1.5), целесообразно оперировать более сложными операциями, такими как ИЛИ-НЕ, И-НЕ

(1.13) и сумма по модулю два. Эти операции, естественно, определяются через основные операции алгебры логики.

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

х ф у = х • у V х • у.(1-19)

Легко убедиться, что х © у = (х V у) • (х V у). Это выражение также можно использовать для определения операции сумма по модулю два. Очевидно, что х © у = х ф у. На основании аксиом алгебры логики (1.2) - (1.5) можно показать, что

0 9 0=161 = 0, 091 = 100 = 1.(1.20)

Из данных соотношений следует, что значение х 9 у совпадает со значением младшего разряда суммы двух двоичных чисел, где х i/i у - значения младших разрядов этих чисел. Соответственно этому значение г-го разряда суммы двух двоичных чисел будет определяться значением х,- © у, © z,-, где х,- и у, - значения г-х разрядов двоичных чисел, а г, - перенос в г-й разряд из предыдущего г - 1-го разряда.

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

х © у = у © X, х © (у © z) = (х © у) © Z,

х (у ф z) = х у ф X Z.

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

x©0 = x, i9l = i, хфх = 0, 101=1, х (В У = x- j/Vx-t/ = (xV у)(х Vj/) = x®j/ = x©j7;

0при четном п,

1при нечетном п,

где хр = х для всех р (формула справедлива только для одной переменной, повторенной п раз).

Для упрощения выражений, содержащих операцию 0, полезны тождества

х © х у = х - у, х © ж .у = 3: V у, х © (х V у) = х у, х © (х V у) = х V у,

х (В~х у = х - у, х (В (х V у) = х у, х у ф (х V у) = у, х у © (х V у) = х, х у ф х у = х у © (х V у) = (х V у) е (ж V у) = х © у, х - у © (х V у) = XV у © (х V у) - 1.


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

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

х у ф z = (х у) ф z, х у ф г • w = (х у) ф (z • w),

xV у® z = xV (уф z), x\/y®z\/w = x\/(y®z)\/w,

arV у © z w = zV [уф (z w)),

x у ф z V v ф w = [(x у) ф z] V (v ф w),

что следует из определения (1-19) операции сумма по модулю два и иерархии операций конъюнкции и дизъюнкции. После приобретения практических навыков некоторые скобки можно будет опускать, чтобы излишне не усложнять аналитические выражения.

Алгебра логики тесно связана с теорией множеств [5]. Вместо операций дизъюнкции, конъюнкции и отрицания в теории множеств используются операции объединения, пересечения и дополнения. Элементам 0 и 1 соответствуют пустое множество и множество, состоящее из всех его элементов.

1.2. Позиционные системы счисления

Совокупность правил записи чисел называется системой счисления. Наиболее часто используются позиционные системы, в которых целое положительное число записывается в виде последовательности символов еп ] .. .ер ... еео, а вес каждого символа ер равен qp, где q - основание системы счисления, ер = 0, l,...,g- 1. Тогда любое целое положительное число

Е в системе счисления с основанием q можно записать в виде: Е = (еп ! .. .ер.. .е0), =

= en.xqn~x + ...+ ерЧР + ... + e0q° = "е ерЯр-

р=0

При вычислении суммы полагаем, что все значения ер и qp представлены в привычной десятичной системе счисления. Максимальное n-разрядное число получается при ер = q - 1 для всех р = 0,1,..., п - 1:

тах = Е(9-1)-9Р = 9П-1-(1-23)

р=0

Таким образом, существует qn различных n-разрядных чисел (с учетом нуля). В табл. 1.2 показан перевод 16 чисел из одной системы счисления в другую для наиболее часто используемых оснований 9 = 2,10,8,16.

Таблица 1.2. Запись чисел в основных системах счисления

ч

2

10

8

16

2

10

8

16

0000

00

00

0

1000

08

10

8

0001

01

01

1

1001

09

11

9

0010

02

02

2

1010

10

12

А

ООП

03

03

3

1011

11

13

В

0100

04

04

4

1100

12

14

С

0101

05

05

5

1101

13

15

D

оно

06

06

6

1110

14

16

Е

0111

07

07

7

1111

15

17

F

Двоичная система счисления (q = 2) используется для представления информации в ЭВМ, что обусловлено легкостью реализации двоичных электронных элементов (требуется высоконадежное различение только двух состояний элементов). Восприятие же человеком информации, представленной в двоичной системе счисления, сильно затруднено как из-за ее монотонности, так и из-за большого числа разрядов, необходимых для ее представления.

В некоторых случаях нумерацию разрядов n-разрядного числа удобнее производить числами от 1 до п:

Е = (en...ep...ei)g =

= enqn-1 +... + epqP-* +...+ el9° = £ epqp~l.

P=i

Перевод чисел из системы счисления с произвольным основанием q в десятичную систему счисления (q = 10) выполняется по вышеприведенным формулам, для чего требуется перевести в десятичную систему счисления только числа ер и q. Несколько сложнее перевести числа из десятичной системы счисления в систему счисления с основанием q ф 10. Наиболее просто такая операция выполняется для 9 = 2,8,16.

Пусть требуется перевести число (1993)ю в указанные системы, счисления. Перевод в восьмеричную систему счисления осуществляется последовательным делением десятичного числа на основание системы счисления q - Ь:


1993 J8

16 249 ]8 39 24 31 8

32 9 24 3

73 8 7 72 1

1 т т т

вес: 8° 81 82 83

Таким образом, (1993)ю = (3711)8. Для перевода полученного числа в двоичную систему счисления достаточно каждую цифру представить в двоичном коде: (3711)8 = (11.111.001.001)2 (точки введены только для удобства чтения двоичного числа в 8-ричной системе счисления). Перевод двоичного числа в 16-ричную систему счисления выполняется его разбиением на тетрады (тетрада - четыре разряда) и переводом каждой тетрады в 16-ричную систему счисления: (111.1100.1001)2 = (7C9)i6. Итак, (1993)ю = (3711)8 = (11111001001)2 = (7C9)i6-

В общем случае числа имеют целую и дробную части. Такие числа в позиционных системах счисления с основанием q можно записать в виде

Е = (en i.. .e0,e i .. . e m)g =

= en-iqn-1 + ... + e0q° + eq1 + ... + e-.mq~m

Целой частью числа Е называется наибольшее целое число, не превосходящее Е. Целая часть числа Е обозначается через [Е] (так [13,25] = 13). Дробной частью числа называется разность {Е} = Е-[Е] (так {13,25} = 0,25). Всегда 0 < {Е} < 1.

Системы счисления с основаниями q = 2к при к = 2,3,4,... жестко связаны с двоичной системой счисления (к - 1). Для перевода чисел из этих систем в двоичную запись достаточно цифры ер = 0,1,2,...,2* - 1 всех разрядов числа представить jfc-разрядным двоичным кодом. Не более сложно и взаимное преобразование чисел из одной системы счисления в другую. Для общения человека с ЭВМ наиболее удобна система счисления с основанием q = 16 (к = 4), что обусловлено большей компактностью записи чисел, чем в системах счисления с q = 8 (к = 3), при приемлемом для запоминания человеком числе различных цифр (символов), используемых для обозначения всех значений разрядов.

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

иначе двоично-десятичным кодом 8-4-2-1 (каждая десятичная цифра 0,1,...,9 заменяется прямым двоичным эквивалентом 0000,0001,1001 - двоичной тетрадой; шесть двоичных тетрад 1010, 1011, 1100, 1101, 1110 и 1111 не используются). Так, можно записать, что

1993 = 0001100110010011.

Десятичные числа в цифровых устройствах (например, в декадных счетчиках) иногда представляются в двоично-десятичном коде 5-4-2-1, который отличается от кода прямого замещения весом старшего разряда тетрады. Числа от 0 до 9 в этом коде имеют представление:

0ю = 0000, 110 = 0001, 2ю = 0010, 310 = ООН, 4ю = 0100, 5ю = 1000, 6ю = Ю01, 710 = 1010, 8ю= 1011, 9ю= И00.

В принципе, на основании приведенного выше выражения для записи чисел Е в позиционных системах счисления можно определить унитарную систему счисления, в которой используется основание q = 1, а ее единственный символ обозначить через ер = 1 (формально следовало бы положить ер = 0). Так как qp = 1, то вес разряда не зависит от его положения в записи числа, т. е. система счисления, по существу, превращается в непозиционную. Это самая древняя система счисления, используемая до сих пор, например, охотниками, делающими зарубки на стволе ружья. В электронике унитарная система счисления применяется довольно часто для представления чисел количеством импульсов, подаваемых на вход устройства (например, Е = (llllll)i = 6ю, где символ 1 означает один импульс).

Для кодирования информации в электронных схемах широкое применение находит унитарный код, содержащий символ 1 только в одной позиции n-разрядного кода (в остальных позициях проставляются символы 0), т.е. для представления информации используется специальное двоичное ее кодирование. Так, например, числа от 0 до 7 можно записать с помощью унитарного кода:

08 = 00000001, ;48 = 00010000, 18 = 00000010, ;58 = 00100000, 28 = ОООООЮО, ;68 = 01000000, 38 = 00001000,; 78 = 10000000.

Унитарный код чаще всего применяется для кодирования нечисловой информации. В частности, на выходах полных дешифраторов (см. § 6.1) всегда реализуется унитарный код.

Дополнительные полезные сведения по системам счисления и кодированию числовой информации можно найти в [б].



0 1 2 3 4 ... 119