00-системы счисления-алгебра. 1 Позиционные системы счисления
 Скачать 0.91 Mb.
|
1 2 1.1. Позиционные системы счисления Совокупность правил записи чисел называется системой счисления. Наиболее часто используются позиционные системы, в которых целое положительное число записывается в виде последовательности символов  , а вес каждого символа равен qр, где q — основание системы счисления, ep – 0,1,..., q-1. Тогда любое целое положительное число Е в системе счисления с основанием qможно записать в виде: При вычислении суммы полагаем, что все значения ери qpпредставлены в привычной десятичной системе счисления. Максимальное n-разрядное число получается при ер = q — 1 для всех р = 0,1,..., n—1:  Напомним, что в десятичной системе счисления (в десятичном коде) основанием системы является число q=10, используемых цифр — десять: 0, 1, 2, ..., 9, а цены («веса») единиц в соседних разрядах отличаются в 10 раз. В этой системе любое число представляется последовательностью коэффициентов в разложении этого числа по степеням числа 10. Так, например, число 3810 (индекс 10 указывает на запись числа в десятичной системе счисления) выражается суммой: 3810=3101+8100, где основание системы 10 возводится в нулевую степень (в первом, младшем разряде), в первую степень (во втором разряде), а коэффициентами ряда являются цифры 3 и 8, последовательное написание которых представляет рассматриваемое число. В двоичной системе счисления основанием системы является число 2, используемых цифр — две: 0 и 1, а веса единиц в соседних разрядах отличаются вдвое. Число в двоичной системе счисления представляется последовательностью коэффициентов в разложении этого числа по степеням числа 2. Так, число 3810 выражается следующим рядом по степеням 2: 3810=125+024+023+122+121+020=1001102, где индекс 2 указывает, что данная совокупность знаков выражает число в двоичной системе счисления (является двоичным кодом числа). Как следует из последнего примера, двоичный код формируется так же, как десятичный; его знаки — коэффициенты в разложении числа по степеням основания (в данном случае по степеням 2). Заметим, что рассмотренный двоичный код (у которого веса единиц в соседних разрядах отличаются вдвое) называется натуральным двоичным кодом. В таком коде было записано приведенное ранее число. Преимуществом двоичной системы счисления является то, что она использует только две цифры. Поэтому в аппаратуре для выполнения операций над числами в двоичной системе счисления (над двоичными числами) достаточно пользоваться двумя значениями, к примеру, напряжения. Восприятие же человеком информации, представленной в двоичной системе счисления, сильно затруднено как из-за ее монотонности, так и из-за большого числа разрядов, необходимых для ее представления. В общем случае существует qnразличных n-разрядных чисел (с учетом нуля). Системы счисления с основаниями q= 2k при k= 2,3,4,... жестко связаны с двоичной системой счисления (k = 1). Для перевода чисел из этих систем в двоичную запись достаточно цифры ер = 0,1,2,...,2k - 1 всех разрядов числа представить k-разрядным двоичным кодом. Не более сложно и взаимное преобразование чисел из одной системы счисления в другую. Для общения человека с ЭВМ наиболее удобна система счисления с основанием q= 16 (k = 4). В табл. 1 показан перевод 15 чисел из одной системы счисления в другую для наиболее часто используемых оснований q= 10,2, 16.
Для кодирования информации в электронных схемах широкое применение находит унитарный код, содержащий символ 1 только в одной позиции n-разрядного кода (в остальных позициях проставляются символы 0), т. е. для представления информации используется специальное двоичное ее кодирование. Так, например, числа от 0 до 7 можно записать с помощью унитарного кода: 010 = 00000001; 410 = 00010000; 110 = 00000010; 510 = 00100000; 210 = 00000100; 610 = 01000000; 310 = 00001000; 710 = 10000000. Унитарный код чаще всего применяется для кодирования нечисловой информации. В частности, на выходах полных дешифраторов всегда реализуется унитарный код. Элементы алгебры логики Математические средства решения логических задач составляют содержание алгебры логики, или булевой алгебры, названной так в честь ее создателя — английского математика Джорджа Буля. В соответствии с ней истинному высказыванию (наступлению события) приписывается, ставится в соответствие символ 1 (логическая 1), а ложному (не наступлению события) — символ 0 (логический 0). Необходимо отметить, что символы 0 и 1 никакого отношения к числовому значению сигнала не имеют. Они лишь описывают качественное состояние события, и поэтому к ним неприменимы арифметические операции. В электрических цепях эти символы обычно представляются так же, как аналогичные в цифровом сигнале: логическая 1 — высоким U1, а логический 0 — низким уровнем потенциала U0. Далее простое высказывание (событие) будем обозначать символом х, а сложное событие, являющееся функцией простых, — символом у. В алгебре логики определены отношение эквивалентности (=) и три операции: дизъюнкция (операция ИЛИ), обозначаемая знаком V; конъюнкция (операция И), обозначаемая знаком & или точкой, которую можно опускать (например, х у = х у); отрицание (инверсия, операция НЕ), обозначаемое чертой над переменными или над элементами 0 и 1 (например, х, 0, 1). Из изложенного ранее следует, что булева алгебра оперирует с переменными, принимающими только два значения: 0 и 1, т. е. с двоичными переменными. Алгебра логики определяется следующей системой аксиом:
Тождества, определяющие правила выполнения операций для одной переменной и с константами формулируются следующим образом:
Для алгебры логики действительны следующие законы:
Функция двоичных переменных, принимающая те же два значения, называется логической функцией (переключательной функцией, функцией алгебры логики). Логическая функция может быть выражена словесно, в алгебраической форме и таблицей, называемой переключательной таблицей или таблицей истинности. Для функции n переменных можно использовать общее обозначение: y=f(хn-1, xn-2, … ,x1,x0). Любое самое сложное логическое высказывание можно описать, используя три логические операции: сложение (дизъюнкцию), умножение (конъюнкцию) и отрицание (инверсию), — которыми могут быть связаны простые высказывания. В указанном смысле этот набор логических функций называют функционально полным набором или базисом. Для аналитического описания функционирования логических схем важную роль имеют понятия термов. Термами называются переменные, инверсии переменных, их конъюнкции и дизъюнкции: Х1, Х2, Х2Х1Х0, Х2Х0. Минимальным термом (минтермом или конституентой единицы) называется функция вида конъюнкции n переменных:  ,где знак (тильда) означает прямое или инверсное значение переменной. Минтерм равен единице только на единственном наборе переменных. Максимальным термом (макстермом или конституентой нуля) называется функция вида дизъюнкции n переменных:  ,где знак (тильда) означает прямое или инверсное значение переменной. Макстерм равен нулю только на единственном наборе переменных. Конъюнктивным термом (контермом) называется конъюнкция любого числа переменных  .Дизъюнктивным термом (дизтермом) называется дизъюнкция любого числа переменных .Нормальные формы представления функций Любое логическое устройство при его физической реализации может быть составлено из простейших схем, которые называют логическими элементами (ЛЭ). Каждый ЛЭ выполняет одну элементарную логическую операцию (И, ИЛИ, НЕ). Следовательно, чтобы по логической функции произвести синтез (создание) логического устройства, необходимо эту функцию выразить элементарными логическими операциями. Для того, чтобы логическую функцию выразить элементарными логическими операциями, её представляют в виде специальных форм. Совершенной дизъюнктивной нормальной формой (СДНФ) называется логическая функция n переменных, представленная в виде дизъюнкции некоторого числа минтермов:  .Совершенной конъюнктивной нормальной формой (СКНФ) называется логическая функция n переменных, представленная в виде конъюнкции некоторого числа макстермов:  .Дизъюнктивной нормальной формой (ДНФ) называется логическая функция, представленная в виде конъюнкции некоторого числа контермов: Конъюнктивной нормальной формой (КНФ) называется логическая функция, представленная в виде дизъюнкции некоторого числа дизтермов: Базисные логические функции Совокупность элементарных логических функций, с помощью которых можно записать любую функцию у, называется функционально полной системой функций или логическим базисом. Три элементарные логические функций И, ИЛИ, НЕ составляют базис, который называется булевым базисом. Функция логическое сложение (ИЛИ) переменных хn-1, хn-2,... х1, х0, записывается в виде у=хn-1хn-2...x0. Значение у=0 имеет место только при x0 =x1=... =.хn-1=0. Если хотя бы одно слагаемое равно единице, то у = 1. Т. е. при любом числе слагаемых, равных единице, сумма их равна единице: у= 1, если x0=1, или x1=1, или xi=1, или все переменные х равны единице. Этим объясняется еще одно название рассматриваемой операции — операция ИЛИ. Табл. 2 — таблица истинности операции ИЛИ двух переменных. В каждой ее строке записаны значения переменных x0 и x1 и соответствующее им значение функции у.
Устройство, выполняющее операцию дизъюнкции, называется дизъюнктором или элементом ИЛИ. Э  лектрическая реализация операции ИЛИ дана на рис. 3,а. Замкнутое состояние ключа соответствует логической единице (Кл=1), разомкнутое — логическому нулю (Кл=0). Лампочка будет светить (Л=1), если выполняются условия: ключ Кл0 замкнут, ключ Кл1 разомкнут – Кл0=1, Кл1=0 ИЛИ ключ Кл0 разомкнут, ключ Кл1 замкнут ИЛИ ключ Кл0 замкнут, ключ Кл1 замкнут. Высказывание «лампочка светит, если...» может быть представлено функцией, реализующей операцию ИЛИ: у=х0x1, где X0 соответствует состоянию ключа Кл0, x1 — состоянию ключа Кл1, а у — состоянию лампочки. Функция логическое умножение (И) n переменных записывается в виде у=хn-1хn-2...x0 Из приведенного выражения следует, что если хотя бы одна из переменных равна нулю, то функция равна нулю. Только в том случае, когда х0 = 1, И х1=1, И, ..., И хn-1= 1, y=1. Поэтому данная операция называется также операцией И.
Устройство, выполняющее операцию конъюнкция, называется конъюнктором или элементом И. На рис. 3, б показана электрическая реализация операции И. Лампочка будет светить (у=1), если замкнуть ключ Кл0 (x0=1) и замкнуть ключ Кл1 (x1=1). Логическое уравнение, выражающее состояние лампочки, имеет вид y=x0 x1, где значения x0 и x1 соответствуют состояниям ключей Кл0 и Кл1. Функция логическое отрицание (НЕ) записывается в виде у=х.
1 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
,
,
,
,
