Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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




К началу выполнения арифметического действия операнды операции помещаются в соответствующие регистры АЛУ.

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

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

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

 

Пример. Сложить двоичные нормализованные числа 0,10111×2–1 и 0,11011×210.

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

 

Пример. Выполнить вычитание двоичных нормализованных чисел 0,10101×210 и 0,11101×21

Разность порядков уменьшаемого и вычитаемого здесь равна единице, поэтому перед вычитанием мантисса второго числа сдвигается на один разряд вправо

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

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

 

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

 

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

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

 

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

 

Основные понятия алгебры логики. Элементарные логические операции

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

Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается повествовательное предложение, о котором можно сказать, истинно оно или ложно (третьего не дано). Высказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА (обозначим 1). Например, содержание высказывания А: «дважды два равно четырем» истинно А = 1, а высказывание В: «три больше пяти» всегда есть ЛОЖЬ.

Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.

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

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

Это правило можно записать в виде следующей таблицы:

 

А
   
   

 

Такая таблица называется таблицей истинности.

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда истинны оба высказывания, записывается С = А Ù В или С = А & В (при этом говорят «С равно А и В»). Примером такой операции может быть следующая: пусть высказывание А состоит в том, что «высота шкафа меньше высоты двери», событие В «ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, сели ширина шкафа меньше ширины двери И высота шкафа меньше высоты двери», т.е. данная операция применяется, если два высказывания связываются союзом И.

Таблица истинности этой операции, как следует из определения, имеет вид

 

А В А & В
     
     
     
     

 

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = A Ú В (при этом говорят: «С равно А ИЛИ В). Пример такой операции следующий: пусть высказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллейбусе», событие С «студент добрался домой на автобусе ИЛИ троллейбусе», т.е. данная операция применятся, если два высказывания связываются союзом ИЛИ.

Таблица истинности такой операции следующая:

 

А В A Ú В
     
     
     
     

 

Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, которое ложно только тогда, когда посылка истинна, а заключение ложно, записывается С = А ® В (при этом говорят: «из А следует В»). Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, «если идет дождь, то на небе тучи». Очевидно, операция не симметрична, т.е. из В ® А не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.

Таблица истинности импликации следующая:

 

А В А ® В
     
     
     
     

 

Импликация имеет следующие свойства:

А ® В ≠ В ® А

А ® А = 1

0 ® А = 1

1 ® А = А

А ® 1 = 1

А ® 0 =

Эквиваленцией двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А «В (.С = А º В). Примером такой операции может быть любое высказывание типа: событие А равносильно событию В.

Таблица истинности:

 

А В А «В
     
     
     
     

 

Эквиваленция имеет следующие свойства:

А «В = В «А

А «В = «

А «1 = А

А «0 =

 

С помощью логических операций из простых высказываний (логических переменных и констант) можно построить логические выражения, которые также называются булевскими функциями. Например, С = (( Ú В) ® В) Ú А.

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

Операции не являются независимыми; одни из них могут быть выражены через другие. Можно доказать с помощью таблиц истинности следующие равносильности:

 

 

Одну и ту же зависимость между логическими переменными можно выразить различными формулами. Поэтому важно иметь возможность приводить формулы с помощью эквивалентных преобразований к некоторому стандартному виду. Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований (формулы 1 - 23).

Первая из них – дизъюнктивная нормальная форма (ДНФ), имеет вид

 

A1 Ú А2 Ú … Ú Аn,

 

где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний, например: В = ( & А2 & A3) Ú (А4 & А5).

Вторая – конъюнктивная нормальная форма (КНФ), имеет вид

 

A1 Ù А2 Ù … Ù Аn,

 

где каждое из составляющих есть дизъюнкция Гфостых высказываний и их отрицаний, например: В = ( Ú А2 Ú ) & (А4 Ú А5) & А6.

Задать булевскую функцию можно, определяя ее значения для всех наборов значений аргументов. Каждый аргумент может иметь два значения: 0 и 1, следовательно, n аргументов могут принимать 2n различных наборов. Пусть, например, булевская функция имеет три аргумента: Х1, X2, Х3. Общее число наборов 23 = 8. Зададим таблицу истинности функции, указав для каждого набора значение функции.

 

 

В комбинациях, где функция принимает значение 1, единица заменяется именем функции, а нуль — именем с отрицанием (т.е. комбинации 0 0 1 ставиться в соответствие выражение & &X3), все элементы соединяются знаками дизъюнкции.

Для рассматриваемого примера получим

F(X1, Х2, X3) = ( & &X3)Ú( & Х2 & X3)Ú(Х1 & &X3) Ú(Х1&Х2&X3).

Как нетрудно заметить, построенная функция удовлетворяет заданной таблице истинности. Функция представляет дизъюнктивную нормальную форму. Кроме того, в каждую группу дизъюнкций входят все аргументы функции. Такая ДНФ называется совершенной, а каждая группа дизъюнкций называется коституентой единицы.

Аналогично, для комбинаций, где функция принимает значение нуля, можно построить алгебраическую форму

F(X1, Х2, X3) = (Х1ÚХ2ÚX3) & (Х1Ú ÚX3) & ( ÚХ2ÚX3) & ( Ú ÚX3),

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

 





Поделиться с друзьями:


Дата добавления: 2016-11-12; Мы поможем в написании ваших работ!; просмотров: 3118 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Вы никогда не пересечете океан, если не наберетесь мужества потерять берег из виду. © Христофор Колумб
==> читать все изречения...

2279 - | 2102 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.