Арифметические и логические основы работы компьютера

Основные действия над числами — это сложение и вычитание.

1. Сложение двоичных чисел осуществляется по следующим правилам:

 

0 + 0 = 0;

0 + 1 = 1;

1 + 0 = 1;

1 + 1 = 0 + единица переноса в старший разряд, т.е. 1 + 1 = 10₂.

 

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

 

Пример 2.21. Сложим в двоичной системе

110,111₂

+10,011₂

^{_____________}

1001,010₂

 

2. Вычитание двоичных чисел осуществляется по следующим правилам:

 

0 – 0 = 0;

1 – 0 = 1;

1 – 1 = 0;

10₂ – 1 = 1.

 

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

 

Пример 2.22. Выполните вычитание в двоичной системе следующих чисел:

 

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

 

 

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

4) полученное число переведем в десятичную систему счисления.

Ответ: +2, следовательно, все действия выполнены верно.

 

Связь между алгеброй логики и двоичным кодированием. Алгебра логики — раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Логическое высказывание — любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Алгебра логики изучает строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.Так, например, предложение «8 — четное число» следует считать высказыванием, так как оно истинное. Предложение «Москва — столица Бельгии» тоже высказывание, но ложное.

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

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

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления, с которой работает компьютер, является двоичная система, в которой используются только цифры 1 и 0.

Из этого следует:

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

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

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

Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию.

Простейшими логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И—НЕ», «ИЛИ—НЕ».

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

Работу логических элементов, как и логических функций, описывают с помощью таблиц истинности. Таблица истинности — это таблица, в которую записаны значения логической функции для каждого из 2n наборов аргументов на входе. Например, полная таблица истинности выражения с тремя переменными содержит 2³ = 8 строк; если заданы только 6 из них, то можно найти 2^8–6 = 2² = 4 разных логических выражения, удовлетворяющие этим 6 строчкам. Чтобы полностью определить логическую функцию, достаточно перечислить либо все наборы, при которых эта функция принимает значения, равные 1, либо все наборы, при которых эта функция принимает значения, равные 0.

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

Функция отрицания — это логическая функция от одного аргумента, которая принимает значение 1, если аргумент равен 0, и принимает значение 0, если аргумент равен 1, и называется отрицанием (инверсией) или логической функцией «НЕ».

В обыденной речи мы часто пользуемся словом «НЕ» или словами «НЕВЕРНО, ЧТО», когда хотим что-то отрицать. Пусть, например, кто-то сказал: «На улице холодно» (обозначим это высказывание через А). Если вы не согласны, то скажете: «На улице НЕ холодно» или: «Неверно, что на улице холодно» (ваше высказывание обозначим через В). Нетрудно заметить, что значения истинности высказываний А и В находятся в определенной связи: если А истинно, то В ложно, и наоборот.

Запись логической функции «НЕ»:                 , где черта над переменной — признак инверсии, либо X. Логическая функция «НЕ» от одного аргумента описывается таблицей истинности (табл. 2.6).

Таблица 2.6

Таблица истинности для логической функции «НЕ»

Логический элемент «НЕ» (инвертор) реализует операцию отрицания. Если на входе этого логического элемента 0, то на выходе 1, а когда на входе 1, на выходе 0.

Условное обозначение инвертора на структурных схемах приведено на рис. 2.2.

Рис. 2.2. Условное обозначение логического элемента «НЕ»

Функцией логического умножения n аргументов называется логическая функция, которая принимает значение 1, только когда все аргументы равны 1, а 0 — во всех остальных случаях. Высказывая конъюнкцию, мы утверждаем, что выполняются оба события, о которых идет речь в составляющих высказывания. Например, сообщая: «Петровы взяли отпуск за свой счет и уехали в Крым», мы выражаем в своем высказывании убеждение в том, что произошли оба этих события.

Функцию логического умножения называют также конъюнкцией или функцией «И». Элементарная функция логического умножения зависит от двух аргументов и описывается таблицей истинности (табл. 2.7).

 

Таблица 2.7

Таблица истинности для логической функции «И»

Логический элемент «И» реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах конъюнкции с двумя входами представлено на рис. 2.3.

Рис. 2.3. Условное обозначение логического элемента «И»

Функцией логического сложения n аргументов называется логическая функция, которая принимает значение 0, только когда все аргументы равны 0 (т.е. при наборе n нулей), и 1 во всех остальных случаях (т.е. когда хотя бы один аргумент равен единице).

Функцию логического сложения называют также дизъюнкцией или логической функцией «ИЛИ». Сообщая: «Петров смотрит телевизор или смотрит в окно», мы имеем в виду, что Петров делает хотя бы одно. При этом Петров может одновременно смотреть телевизор и смотреть в окно. И в этом случае дизъюнкция будет истинна.

Элементарная дизъюнкция зависит от двух аргументов и описывается следующей таблицей истинности (табл. 2.8).

 

Таблица 2.8

Таблица истинности для логической функции «ИЛИ»

Логический элемент «ИЛИ» реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе элемента «ИЛИ» будет единица, на ее выходе также будет единица. Условное обозначение на структурных схемах логического элемента «ИЛИ» с двумя входами показано на рис. 2.4.

 

 

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

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

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

• либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул;

• либо содержит меньшее число вхождений переменных.

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул.