Контрольные вопросы

Какое Правило счета присуще сложению в двоичной системе?

Что необходимо сделать, если при сложении получился избыток?

Как осуществляется умножение многозначных чисел в различных позиционных системах счисления?

Что необходимо сделать, если при вычитании разряд уменьшаемого числа равен нулю?

Существует ли какая-нибудь разница между осуществлением деления в десятичной системе счисления и любой другой? Если да, то какая?

Задание

Оформление отчета

Название, цель работы;

Задание;

Письменные ответы на контрольные вопросы;

Краткий вывод по работе.

3. «Представление целых чисел в компьютере»

При сложении обратных кодов чисел А и В имеют место четыре основных и два особых случая:

А и В положительные.

При суммировании складываются все разряды, включая разряд знака. Так как знаковые разряды положительных слагаемых равны нулю, разряд знака суммы тоже равен нулю.

Например,

Получен правильный результат.

А положительное, В отрицательное и по абсолютной величине больше, чем А.

Например,

Получен правильный результат в обратном коде. При переводе в прямой код биты цифровой части результата инвертируются:

1 0000111= -710.

А положительное, В отрицательное и по абсолютной величине меньше, чем А.

Например,

Компьютер исправляет полученный первоначальный неправильный результат (6 вместо 7) переносом единицы из знакового разряд в младший разряд суммы.

А и В отрицательные.

Например,

Полученный первоначально неправильный результат (обратный код числа -1110 вместо обратного кода числа -1010) компьютер исправляет переносом единицы из знакового разряда в младший разряд суммы.

При переводе результата в прямой код биты цифровой части инвертируются: 1 0001010= -1010.

При сложении может возникнуть ситуация, когда старшие разряды результата операции не помещаются в отведённой для него области памяти. Такая ситуация называется переполнением разрядной сетки формата числа.

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

А и В положительные, сумма А+В больше, либо равна 2n-1, где n - количество разрядов формата чисел (для однобайтового формата n=8, 2n-1=27=128).

Семи разрядов цифровой части числового формата недостаточно для размещения восьмиразрядной суммы (16210=101000102), поэтому старший разряд суммы оказывается в знаковом разряде. Это вызывает несовпадение знака суммы и знаков слагаемых, что является свидетельством переполнения разрядной сетки.

А и В отрицательные, сумма абсолютных величин А и В больше либо равна 2n-1.

Например,

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

Все эти случаи имеют место и при сложении дополнительных кодов чисел:

А и В положительные. Здесь нет отличий от случая 1, рассмотренного для обратного кода.

А положительное, В отрицательное и по абсолютной величине больше, чем А.

Получен правильный результат в дополнительном коде. При переводе в прямой код биты цифровой части результата инвертируются и к младшему разряду прибавляется единица:

1 0000110+1=1 0000111=-710.

А положительное, В отрицательное и по абсолютной величине меньше, чем А.

Получен правильный результат. Единицу переноса из знакового разряда компьютер отбрасывает.

А и В отрицательные.

Получен правильный результат в дополнительном коде. Единицу переноса из знакового разряда компьютер отбрасывает.

Случаи переполнения для дополнительных кодов рассматриваются по аналогии со случаями 5 и 6 для обратных кодов.

Сравнение рассмотренных форм кодирования целых чисел со знаком показывает:

на преобразование отрицательного числа в обратный код компьютер затрачивает меньше времени, чем на преобразование в дополнительный код, так как последнее состоит из двух шагов - образования обратного кода и прибавления единицы к его младшему разряду;

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

Умножение и деление

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

Другой регистр АЛУ, участвующий в выполнении этой операции, вначале содержит множитель. Затем по мере выполнения сложений содержащееся в нём число уменьшается, пока не достигнут нулевого значения.

Для иллюстрации умножим 1100112 на 1011012.

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

Представление вещественных чисел

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

При их написании вместо запятой принято писать точку. Так, например, число 5 - целое, а числа 5.1 и 5.0 - вещественные.

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

1.25*100=0.125*101=0.0125*102=… ,

12.5*10-1=125.0*10-2=1250.0*10-3=… .

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

Такое, наиболее выгодное для компьютера, представление вещественных чисел называется нормализованным.

Мантиссу и порядок q-ичного числа принято записывать в системе с основанием q, а само основание - в десятичной системе.

Примеры нормализованного представления:

Вещественные числа в компьютерах различных типах записываются по-разному. При этом компьютер обычно предоставляет программисту возможность выбора из нескольких числовых форматов наиболее подходящего для конкретной задачи - с использованием четырёх, шести или десяти байтов.

В качестве примера приведём характеристики форматов вещественных чисел, используемых IBM-совместимыми персональными компьютерами.

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

При хранении числа с плавающей точкой отводятся разряды для мантиссы, порядка, знака числа и знака порядка:

Покажем на примерах, как записываются некоторые числа в нормализованном виде в четырёхбайтовом формате с семью разрядами для записи порядка.

Число -0.12510= -0.0012= -0.1*2-10 (отрицательный порядок записан в дополнительном коде):

Арифметические действия над нормализованными числами

При сложении и вычитании сначала производится подготовительная операция, называемая выравниванием порядков.

При сложении и вычитании чисел с плавающей точкой они предварительно выравниваются таким образом, чтобы порядок большего по величине числа становился порядком результата.

Рассмотрим такой пример.

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

X = 0.11000001•211 и Y = -0.10000110•2110.

Допустим, под мантиссу в машине отведено 9 разрядов (8 - цифровые разряды, 1 - под знаковый разряд) и под порядок - 4 разряда (3 разряда - величина порядка, 1 разряд - знак порядка), т.е. заданные числа в прямом коде можно записать так:

Процесс сложения заданных чисел состоит из следующих шагов:

1-й шаг - выравнивание порядков для того, чтобы порядок числа X стал равен большему порядку числа Y:

X > 0 110 0 00011000

2-й шаг - перевод обеих мантисс в обратный код:

мантисса числа X 0 00011000

мантисса числа Y 1 01111001

3-й шаг - сложение мантисс:

0 00011000

+ 1 01111001

1 10010001

4-й шаг - перевод результата операции в прямой код:

1 01101110

5-й шаг - нормализация результата, сдвиг мантиссы влево на один разряд:

1 11011100

порядок уменьшается на единицу, вместо 110 становится равным 101.

6-й шаг - окончательно получаем результат, который расположится в ячейке таким образом:

? > 0 101 1 11011100

Эта запись выражает число следующего вида:

- 0. 11011100•2+101

При умножении порядки двух чисел складываются, а мантиссы перемножаются в соответствии с соотношением

x•y=2Px+Py•(mx•my)

При делении чисел о плавающей запятой порядки вычитаются, а мантиссы делятся, т.е.х/у=2Px-Py•(mx/my).

Если мантисса m результата арифметических операций умножения и деления выходит за пределы, указываемые неравенством (4), то она подвергается нормализации.В результате выравнивания порядков одноименные разряды чисел оказываются расположенными в соответствующих разрядах обоих регистров, после чего мантиссы складываются или вычитаются.

В случае необходимости полученный результат нормализуется путём сдвига мантиссы результата влево. После каждого сдвига влево порядок результата уменьшается на единицу.

Пример 1. Сложить двоичные нормализованные числа 0.10111*2-1 и 0.11011*210. Разность порядков слагаемых здесь равна трём, поэтому перед сложением мантисса первого числа сдвигается на три разряда вправо:

Пример 2. Выполнить вычитание двоичных нормализованных чисел 0.10101*210 и 0.11101*21. Разность порядков уменьшается и вычитаемого здесь равна единице, поэтому перед вычитанием мантисса второго числа сдвигается на один разряд вправо:

Результат получился не нормализованным, поэтому его мантисса сдвигается влево на два разряда с соответствующим уменьшением порядка на две единицы: 0.1101*20.

Умножение

Пример 3. Выполним умножение двоичных нормализованных чисел:

(0.11101*2101)*(01001*211)=(0.11101*0.1001)*2(101+11)=0.100000101*21000

Деление

Пример 4. Выполнить деление двоичных нормализованных чисел:

0.1111*2100 : 0.101*211=(0.1111 : 0.101)*2(100-11)=0.11*210

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

Контрольные вопросы

Какая разница между целыми числами без знака и со знаком?

Для чего предназначены обратный и дополнительный коды?

Как из прямого кода получить обратный и дополнительный?

В чем особенность получения обратного и дополнительного кодов отрицательных чисел?

Как получить модифицированные обратный и дополнительный коды?

Для чего предназначены вещественные числа и как они записываются?

Что такое нормализованное представление вещественных чисел и для чего оно используется?

Задание

Оформление отчета

Название, цель работы

Задание

Письменные ответы на контрольные вопросы

Краткий вывод по работе

4. «Логические основы построения цифровых автоматов»

1+1=1.

Конъюнкция двух переменных равна 0, если хотя бы одна переменная равна 0:

0*0=0;

0*1=0;

1*0=0;

1*1=1.

Инверсия одного значения переменной совпадает с ёё другим значением:

1=0;

0=1.

Законы алгебры логики

Законы однопарных элементов:

универсального множества:

x+1=1; x*1=x.

нулевого множества:

x+0=x; x*0=0.

Законы отрицания:

двоичного отрицания:

дополнительности:

двойственности (де Моргана):

Комбинационные законы:

Формула, истинная при всех возможных интерпретациях, называется общезначимой (или тавтологией).

Формула называется противоречивой, если она ложна в любой интерпретации.

тавтологии:

x + x = x ;

;

коммутативные:

ассоциативные (сочетательные):

закон абсорбции (поглощения):

склеивания

дистрибутивные (распределения):

Законы двойственности де Моргана были обобщены Шенноном на произвольное количество двоичных переменных: инвертирование произвольной комбинации двоичных переменных, связанных знаками дизъюнкции и конъюнкции, эквивалентно инвертированию комбинации переменных с одновременной заменой конъюнкции на дизъюнкцию, и наоборот.

Рассмотрим на примерах некоторые приёмы и способы, применяемые при упрощении логических формул:

(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, законы дополнительности и нулевого множества).

(применяется правило де Моргана, выносится за скобки общий множитель, используется закон дополнительности).

(выносятся за скобки общие множители, применяется закон универсального множества).

Рассмотрим доказательство соотношения:

-- распределительный закон;

(применяются законы тавтологии и универсального множества).

Представление функций алгебры логики

Булевой (переключательной, двоичной) функцией называется двоичная переменная у, значение которой зависит от значений других двоичных переменных (x1,x2…xn), именуемых аргументами:

Задание булевой функции означает, что каждому из возможных сочетаний аргументов поставлено в соответствие определённое значение у.

При n аргументах общее число сочетаний N=22n. Так как по каждому сочетанию аргументов соответствует два значения функции (0,1), то общее число функции F=22n.

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

В таблице ниже представлена функция одной переменной y=y(x). При n=1 существует 4 функции, каждая из которых имеет своё название.

Табличное задание функции одной переменной

Для алгебры логики установлено, что

если где z1 и z2 - двоичные функции,

то .

Операцию замены одной функции другими функциями называют

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

Рассмотрим функцию двух аргументов. По определению существует 16 функций двух аргументов (таблица 4.3). При помощи набора булевых функций двух аргументов можно описать любую цифровую систему. НА практике используют не все функции, а лишь те из них, которые методом

суперпозиции обеспечивают представление любой другой функции. Набор таких функций называют функционально полным набором (ФПН).

Существует несколько ФПН. В качестве ФПН применяется дизъюнкция, конъюнкция и инверсия. Этот набор называют Основной ФПН (ОФПН).

Кроме ОФПН широкое применение получили:

функционально-полная система, включающая в себя только одну функцию - функцию Пирса (ИЛИ-НЕ);

функционально-полная система, включающая в себя только одну функцию - функцию Шеффера (И-НЕ).

При помощи этих функций можно построить любую цифровую систему.

Синтез логических устройств в базисе ОФПН состоит из представления этих функций в нормальных формах и минимизации.

Табличное задание функции двух переменных

Синтез и анализ переключательных схем

Переключательная схема - схематическое изображение некоторого устройства, состоящее из переключателей и соединяющих их

проводников, а так же входов и выходов на которые подается и с которых снимается электрический сигнал.

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие переменную х, которая принимает значение 1 только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то переменная х равна нулю. При этом два переключателя Х и связаны таким образом, что когда Х замкнут, то разомкнут и наоборот.

Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю должна соответствовать переменная .

Логическая переменная, равная единице, если схема проводит ток и равная нулю - если не проводит, является функцией от переменных соответствующих всем переключателям схемы, и называется функцией проводимости.

Рассмотрим функции проводимости F некоторых переключательных схем:

а)

Схема не содержит переключателей и проводит ток всегда, следовательно, F=1;

Схема содержит один постоянно разомкнутый контакт, следовательно, F=0;

в)

Схема проводит ток, когда переключатель Х замкнут, и не проводит, когда Х разомкнут, следовательно, F(x) = x;

г)

Схема проводит ток, когда разомкнут, и не проводит, когда замкнут, следовательно, F() = ;

д)

Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(x,y) = xy;

е)

Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(x,y) = x v y.

При рассмотрении переключательных схем решают, как правило, одну из основных задач: синтез или анализ схемы.

Синтез переключательной схемы по заданным условиям ее работы сводится к следующим трем этапам:

Составление функции проводимости по заданным условиям.

Упрощение этой функции

Построение соответствующей схемы.

Анализ схемы характеризуется следующими этапами:

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

Получение упрощенной формулы.

Рассмотрим примеры решения задач синтеза и анализа несложных переключательных схем.

Задачи синтеза

Построим схему, содержащую 4 переключателя х, у, z и t, такую чтобы она проводила ток, тогда и только тогда, когда замкнут контакт переключателя t и какой-нибудь из остальных трех контактов.

Решение:

Функция проводимости для данного случая имеет вид F(x,y,z,t) = t(x v y v z), а схема имеет вид:

Построим схему с пятью переключателями, которая проводит ток в том и только в том случае, когда замкнуты ровно четыре из этих переключателей.

Решение:

F(a,b,c,d,e) =

Схема имеет вид:

Задачи анализа

Найдем функцию проводимости схемы:

Решение:

Имеется четыре возможных пути прохождения тока при замкнутых переключателях a, b, c, d, e: через переключатели а, b; через переключатели а, e, d; через переключатели c, d и через переключатели с, e, b.

Функция проводимости F(a,b,c,d,e)=

Упростим переключательные схемы:

Решение:

F(x,y)=

Упрощенная схема:

Анализ и синтез более сложных схем может проводиться по тем же правилам, что и для вычислительных схем.

Контрольные вопросы

Какие 3 базовые логические операции существуют?

В чём состоит смысл булевой функции?

Каков приоритет (в порядке убывания) базовых логических функций?

Где на практике можно применять аппарат булевой алгебры?

В чём заключается закон двойственности Моргана-Шеннона?

Задание

Оформление отчета

Название, цель работы

Задание

Письменные ответы на контрольные вопросы

Краткий вывод по работе

5. «Решение задач алгебры логики»

Цель работы

«Усвоить основные операции алгебры логики, порядок выполнения операций в логических выражениях, научиться составлять таблицы истинности»

Порядок выполнения работы

Ознакомиться с теоретической частью

Получить задание у преподавателя

Оформить отчет

Теоретическая часть

условные обозначения логических операций

¬ A, не A (отрицание, инверсия)

A ? B, A и B (логическое умножение, конъюнкция)

A ? B, A или B (логическое сложение, дизъюнкция)

A > B импликация (следование)

таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация» (см. презентацию «Логика»)

операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A > B = ¬ A ? B или в других обозначениях A > B =

если в выражении нет скобок, сначала выполняются все операции «НЕ», затем - «И», затем - «ИЛИ», и самая последняя - «импликация»

иногда полезны формулы де Моргана:

¬ (A ? B) = ¬ A ? ¬ B

¬ (A ? B) = ¬ A ? ¬ B

Пример задания:

Для какого из указанных значений X истинно высказывание ¬((X > 2)>(X > 3))?

1 2) 23) 34) 4

Решение:

определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем - отрицание (операция «НЕ») для выражения в больших скобках

выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 - ложное); сначала определяем результаты сравнения в двух внутренних скобках:

по таблице истинности операции «импликация» находим третий столбец (значение выражения в больших скобках), применив операцию «импликация» к значениям второго и третьего столбцов (в каждой строке):

значение выражения равно инверсии третьего столбца (меняем 1 на 0 и наоборот):

таким образом, ответ - 3.

Контрольные задания (часть 1).

Для какого из указанных значений числа X истинно высказывание

((X < 5)>(X < 3)) ? ((X < 2)>(X < 1))?

1 2) 23) 34) 4

Для какого числа X истинно высказывание ((X > 3)?(X < 3)) >(X < 1)?

12) 23) 34) 4

Для какого числа X истинно высказывание X > 1 ? ((X < 5)>(X < 3))?

12) 23) 34) 4

Для какого имени истинно высказывание:

¬ (Первая буква имени гласная > Четвертая буква имени согласная)?

ЕЛЕНА2) ВАДИМ3) АНТОН4) ФЕДОР

Для какого символьного выражения неверно высказывание:

Первая буква гласная > ¬ (Третья буква согласная)?

1)abedc2)becde3) babas 4) abcab

Для какого числа X истинно высказывание (X > 2)?(X > 5)>(X < 3)?

5 2) 23) 34) 4

Для какого из значений числа Z высказывание ((Z > 2)?(Z > 4)) >(Z > 3) будет ложным?

12) 23) 34) 4

Для какого имени истинно высказывание:

¬ (Первая буква имени согласная > Третья буква имени гласная)?

ЮЛИЯ2) ПЕТР3) АЛЕКСЕЙ4) КСЕНИЯ

Для какого из значений числа Y высказывание (Y < 5) ? ((Y > 1) > (Y > 5)) будет истинным?

12) 23) 34) 4

Для какого имени истинно высказывание:

(Вторая буква гласная > Первая буква гласная) ? Последняя буква согласная?

ИРИНА2) МАКСИМ3) МАРИЯ4) СТЕПАН

Основные законы алгебры логики

Укажите, какое логическое выражение равносильно выражению A ? ¬(¬B ? C).

¬A ? ¬B ? ¬C 2) A ? ¬B ? ¬C3) A ? B ? ¬C4) A ? ¬B ? C

Решение (использование законов де Моргана):

перепишем заданное выражение и ответы в других обозначениях:

заданное выражение

ответы: 1) 2) 3) 4)

посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана,

а затем используем закон двойного отрицания по которому :