Логика, как наука развивается с IV в. до н. э. начиная с трудов Аристотеля. Именно он подверг анализу человеческое мышление, такие его формы, как понятие, суждение, умозаключение.
Логика – (от греч. “логос”, означающего “слово” и “смысл”) – наука о законах, формах и операциях правильного мышления. Ее основная задача заключается в нахождении и систематизации правильных способов рассуждения.
Рис. 1. Основные формы абстрактного мышления
Понятие – это форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов. Всякое понятие имеет содержание и объем. Например, понятие “Черное море” – отражает единичный предмет, “Сиамская кошка” – отражает класс сиамских кошек.
Высказывание (суждение) – некоторое предложение, которое может быть истинно (верно) или ложно. Например, Абакан – столица Хакасии. Утверждение – суждение, которое требуется доказать или опровергнуть. Рассуждение – цепочка высказываний или утверждений, определенным образом связанных друг с другом.
Умозаключение – логическая операция, в результате которой из одного или нескольких данных суждений получается (выводится) новое суждение. Умозаключения бывают: Дедуктивные (от общего к частному) – Все ученики ходят в школу. Вася – ученик. Вася ходит в школу. Индуктивные (от частного к общему) – Банан и персик – сладкие. Значит, все фрукты сладкие на вкус. Аналогия – Наши коровы едят траву и дают молоко. В Австралии есть поля, коровы едят эту траву. Следовательно, австралийские коровы тоже дают молоко.
В алгебре логики высказывания обозначаются именами логических переменных (А, В, С). Истина, ложь – логические константы.
Логическое выражение – запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая 1) или ЛОЖЬ (логический 0).
Сложное логическое выражение – логическое выражение, составленное из одного или нескольких простых (или сложных) логических выражений, связанных с помощью логических операций.
| | | следующая лекция ==> | |
| Шестнадцатеричная система счисления используется для компактного представления (на бумаге или на экране) двоичной информации, хранимой в памяти ЭВМ. | | |
Основные действия над числами - это сложение и вычитание.
- 1. Сложение двоичных чисел
- 0 + 0 = 0 0+1 = 1 1+0=1
- 1 + 1=0 + единица переноса в старший разряд, т.е. 1 + 1=10 2 .
При сложении двоичных чисел в каждом разряде в соответствии с правилами производится сложение двух цифр слагаемых или двух этих цифр и единицы, если имеется перенос из соседнего младшего разряда. В результате получается цифра соответствующего разряда суммы и, возможно, также единица переноса в старший разряд.
Пример 1. Сложить в двоичной системе
- 2. Вычитание двоичных чисел осуществляется в соответствии со следующими правилами:
- 0-0 = 0 1-0=1 1-1=0 10 2 -1 = 1
При вычитании двоичных чисел в данном разряде при необходимости занимается единица из следующего, старшего разряда. Эта занимаемая единица равна двум единицам данного младшего разряда. Такое действие производится каждый раз, когда цифра в разряде вычитаемого больше цифры в том же разряде уменьшаемого. Пример 2. Выполните вычитание в двоичной системе следующих чисел:
Операции над положительными и отрицательными числами
Распространенными формами представления чисел со знаками является их представление в прямом, обратном и дополнительном коде.
Последние две формы применяются особенно широко, так как позволяют упростить конструкцию арифметико-логического устройства компьютера путем замены разнообразных арифметических операций операцией сложения.
Прямой код числа образуется кодированием знака числа нулем, если число положительно, и единицей, если число отрицательно.
Пример 1. Представьте положительное число 127ю=1111111 2 в прямом коде: 0 1111111
Пример 2. Представьте отрицательное число - 1)0 в прямом коде:
Обратный код числа получается инвертированием всех цифр двоичного кода абсолютной величины числа, кроме разряда знака: нули заменяются единицами, а единицы - нулями.
Пример 3. Представьте отоинательное число - 1 ш в обратном коде:
Пример 4. Представьте отпиттятетткнпе хшг.тто - 1 77 10 в обратном коде:
Код модуля числа Обратный код числа
Дополнительный код числа получается образованием обратного кода с последующим прибавлением единицы к его младшему разряду.
Пример 5. Представьте отрицательное число - 1ю в дополнительном коде: 11111111
Пример 6. Представьте отрицательное число -127ю в дополнительном коде:
Сложение чисел в дополнительном коде
Пример 1. Выполните следующую арифметическую операцию «-5+3».
Наши действия в этом случае таковы:
3. Осуществим сложение чисел.
4. Если результат получился отрицательным, то следует инвертировать все разряды числа, кроме знакового, и в младший разряд результата добавить единицу.
Ответ: - 2, следовательно, все действия выполнены верно.
Пример 2. Выполните следующую арифметическую операцию «5 - 3». Выполняя операцию вычитания и представляя отрицательное число в дополнительном коде, можно операцию вычитания заменить сложением.
1. Представим числа в двоичном коде:
2. Отрицательное число следует представить в дополнительном коде. Для этого инвертируем все разряды числа, кроме знакового, и в младший разряд результата добавим единицу.
3. Осуществим сложение чисел.
- 4. Если результат получился положительным, то единицу переноса из знакового разряда отбрасывают.
- 5. Полученное число следует перевести в десятичную систему счисления. Ответ: + 2, следовательно, все действия выполнены верно.
Связь между алгеброй логики и двоичным кодированием
Алгебра логики - раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Логическое высказывание - любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Алгебра логики изучает строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.
Так, например, предложение «8 - четное число» следует считать высказыванием, так как оно истинное. Предложение «Москва - столица Бельгии» тоже высказывание, так как оно ложное.
Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения «студент первого курса» и «мороженое - вкусное». Первое предложение ничего не утверждает о студенте, а второе использует слишком неопределенное понятие «вкусное». Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла. Предложения типа «в городе А более миллиона жителей », «у нее голубые глаза » не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь.
Такие предложения называются высказывательными формами. Высказыва- тельная форма - повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления, с которой работает компьютер, является двоичная система счисления, в которой используются только цифры 1 и 0.
Из этого следует:
- - одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной в двоичной системе счисления, так и логических переменных;
- - на этапе конструирования аппаратных средств алгебра логики позволяет значительно упростить логические функции, описывающие функционирование схем компьютера, и, следовательно, уменьшить число элементарных логических элементов, из десятков тысяч которых состоят основные узлы компьютера.
Данные и команды в компьютере представляются в виде двоичных последовательностей различной структуры и длины. Существуют различные физические способы кодирования двоичной информации. В электронных устройствах компьютера двоичные единицы чаще всего кодируются более высоким уровнем напряжения, чем двоичные нули.
Логический элемент компьютера - это часть электронной логической схемы, которая реализует элементарную логическую функцию.
Простейшими логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-HE». Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем.
Работу логических элементов, как и логических функций, описывают с помощью таблиц истинности. Таблица истинности - это таблица, в которую записаны значения логической функции для каждого из 2 П наборов аргументов на входе. Например, полная таблица истинности выражения с тремя переменными содержит 2 3 =8 строчек, если заданы только 6 из них, то можно найти 2 8 " 6 =2 2 =4 разных логических выражения, удовлетворяющие этим 6 строчкам. Для того чтобы полностью определить логическую функцию, достаточно перечислить либо все наборы, при которых эта функция принимает значения, равные 1, либо все наборы, при которых эта функция принимает значения, равные 0.
Элементарные логические функции и логические элементы
Логические функции, зависящие от одной или двух переменных, называются элементарными. К основным логическим функциям относятся следующие элементарные функции: отрицание, логическое умножение, отрицание от логического умножения, логическое сложение, отрицание от логического сложения, импликация и т.д.
Функция отрицания - это логическая функция от одного аргумента, которая принимает значение 1, если аргумент равен 0, и принимает значение 0, если аргумент равен 1, и называется отрицанием (инверсией) или логической функцией «НЕ».
В обыденной речи мы часто пользуемся словом «НЕ», или словами «НЕВЕРНО, ЧТО», когда хотим что-то отрицать. Пусть, например, кто-то сказал: «На улице холодно». (Обозначим это высказывание А.) Если вы не согласны, вы скажете: «На улице НЕ холодно». Или: «Неверно, что на улице холодно». (Ваше высказывание обозначим В.) Нетрудно заметить, что значения истинности высказываний А и В находятся в определенной связи: если А истинно, то В ложно, и наоборот.
Запись логической функции «НЕ» можно обозначить как F = X, где черта над переменной - признак инверсии, либо как -iX. Логическая функция «НЕ» от одного аргумента описывается таблицей истинности (табл. 8).
Таблица 8. Таблица истинности для логической функции «НЕ»
Логический элемент «НЕ» (инвертор) реализует операцию отрицания. Если на входе этого логического элемента 0, то на выходе 1, а когда на входе 1, на выходе 0.
Условное обозначение инвертора на структурных схемах приведено на рис. 12.
Рис. 12.
Функцией логического умножения п аргументов называется логическая функция, которая принимает значение 1 только в том случае, когда все аргументы равны 1, а 0 - во всех остальных случаях.
Высказывая конъюнкцию, мы утверждаем, что выполняются оба события, о которых идет речь в высказывании. Например, сообщая: «Петровы взяли отпуск за свой счет и уехали в Крым», мы выражаем в своем высказывании свое убеждение в том, что произошли оба этих события.
Функцию логического умножения называют также конъюнкцией или функцией «И». Элементарная функция логического умножения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 9).
Таблица 9. Таблица истинности для логической функции «И»
При записи логической функции «И» возможны следующие варианты: F=X AY;
F=XY, где знаки «Л», «&», « » - знаки, обозначающие операцию логического умножения. Все варианты записи равнозначны.
Рис. 13.
Логический элемент «И» реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах конъюнкции с двумя входами представлено на рис. 13.
Функцией логического сложения п аргументов называется логическая функция, которая принимает значение 0 только в том случае, когда все аргументы равны 0 (т.е. при наборе п нулей), и 1 во всех остальных случаях (т.е. когда хотя бы один аргумент равен единице).
Функцию логического сложения называют также дизъюнкцией или логической функцией «ИЛИ». Сообщая: «Петров смотрит телевизор или смотрит в окно», мы имеем в виду, что хотя бы одно Петров делает. При этом Петров может одновременно смотреть телевизор и смотреть в окно. И в этом случае дизъюнкция будет истинна.
Элементарная дизъюнкция зависит от двух аргументов и описывается следующей таблицей истинности (табл. 10).
Таблица 10. Таблица истинности для логической функции «ИЛИ»
Рис. 14.
При записи логической функции «ИЛИ» возможны следующие варианты:
где знаки «V», «+» обозначают операцию логического сложения.
Логический элемент «ИЛИ» реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе элемента «ИЛИ» будет единица, на ее выходе также будет единица. Условное обозначение на структурных схемах логического элемента «ИЛИ» с двумя входами представлено на рис. 14.
Функция отрицания от логического умножения «И-НЕ» принимает значение 0, когда все аргументы равны 1, и 1 - во всех остальных случаях. Функция отрицания от логического умножения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 11).
Таблица 11. Таблица истинности для функции отрицания от логического умножения
При записи функции отрицания от логического умножения возможны следующие варианты:
Рис. 15.
Логический элемент «И-НЕ» состоит из элемента «И» и инвертора и осуществляет отрицание результата функции И. Условное обозначение на структурных схемах логического элемента «И-НЕ» с двумя входами представлено на рис. 15.
Функция отрицания от логического сложения принимает значение 1, когда все аргументы равны 0, и значение 0 - во всех остальных случаях.
Функция отрицания от логического сложения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 12).
Таблица 12. Таблица истинности для функции отрицания от логического сложения
При записи функции отрицания от логического сложения возможны следующие варианты:
Рис. 16.
Логический элемент «ИЛИ-HE» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата логической функции «ИЛИ». Условное обозначение на структурных схемах логического элемента «ИЛИ-HE» с двумя входами представлено на рис. 16.
В сложных выражениях с использованием логических операций «И», «ИЛИ», «НЕ» сначала выполняется операция отрицания «НЕ», затем операция конъюнкции «И». В последнюю очередь выполняется операция дизъюнкции «ИЛИ». Для того чтобы изменить указанную последовательность выполнения операций, в выражениях следует использовать скобки. Кроме перечисленных функций, одной из важнейших операций является импликация (следование), которая обозначается -> и описывается соответствующей таблицей (табл. 13).
Таблица 13. Таблица истинности для функции импликации
Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.
Рассмотрим высказывание: «Если завтра будет хорошая погода, то я пойду гулять». Здесь А= Завтра будет хорошая погода и В= Я пойду гулять. Ясно, что человек окажется лжецом лишь в том случае, если погода действительно окажется хорошей, а гулять он не пойдет. Если же погода будет плохой, то независимо от того, пойдет он гулять или нет, во лжи его нельзя обвинить: обещание пойти гулять он давал лишь при условии, что погода будет хорошей.
В обычной речи связка «если..., то» описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться «бессмысленностью» импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: «если на Луне есть вода, то в зоопарке живут тигры», «если клубника - ягода, то в магазине есть хлеб».
Импликация заведомо истинна, если условие А ложно. Другими словами, из неверного условия может следовать все, что угодно. Например, высказывание «Если 2>3, то крокодилы летают» является истинным.
Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно» называется эквиваленцией или двойной импликацией и обозначается знаками, =. Эквиваленция описывается соответствующей таблицей
Таблица 14. Таблица истинности для функции эквиваленции
Например, сообщая: «Я получу паспорт тогда и только тогда, когда мне исполнится 14 лет», человек утверждает не только то, что после того, как ему исполнится 14 лет, он получит паспорт, но и то, что паспорт он сможет получить только после того, как ему исполнится 14 лет.
Таким образом, высказывание XY истинно тогда и только тогда, когда значения X и Y совпадают. Следует учитывать, что рассмотренную нами операцию - импликацию можно выразить через дизъюнкцию и отрицание:
а эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:
Каким выражением может быть F?
Построим таблицу истинности для всех предложенных в ответе выражений:
Вычислим логические выражения для четырех предложенных ответов. Видим, что совпали значения логических выражений в столбцах X v Y v Z и F, следовательно, правильный ответ 3.
Пример 2. Для какого из указанных значений X истинно высказывание
Видно, что высказывание представляет собой отрицание выражения ((Х>2) -> -> (Х>3)). Оно истинно, когда ((Х>2) -> (Х>3)) ложно. Импликация ложна в единственном случае: левое высказывание истинно (в нашем случае Х>2 истинно для Х=3 и Х=4), а правое ложно (это справедливо для Х=1, Х=2 и Х=3). Поэтому единственный вариант, когда эта импликация ложна (следовательно, исходное выражение истинно), - третий.
Основные законы алгебры логики
В алгебре логики имеется ряд законов, позволяющих производить равносильные (тождественные) преобразования логических выражений. Правила преобразования логических выражений представлены в табл. 15.
Таблица 15. Правила преобразования логических выражений
|
двойного отрицания |
Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание |
|
|
переместительный (коммутативный) |
А Л В = В Л А |
А V В = В V А |
|
сочетательный (ассоциативный) |
(А Л В) Л С = А А (В Л С) |
(A v В) v С = A v (В v С) |
|
распределительный (дистрибутивный) |
(А Л В) V С = (А V В) А (А VC) |
Aa(BvC) = AaBvAa С |
|
де Моргана |
А В = А" + В отрицание логического произведения эквивалентно логической сумме отрицаний множителей |
А + В = А -В отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых |
|
поглощения |
А А (А V В) = А |
А V А А В = А |
|
склеивания |
(А V В) Л (-А V В) = В |
(А А В) v (-А V В) = В |
|
исключения третьего (операция переменной с ее инверсией) |
для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. |
|
Порядок выполнения логических операций задается круглыми скобками. Для уменьшения числа скобок считается, что сначала выполняется операция отрицания, затем конъюнкция, и только потом дизъюнкция. В последнюю очередь выполняется импликация и равносильность.
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной математике. Они служат для упрощения формул и приведения их к определенному виду путем использования основных законов алгебры логики.
Под упрощением формулы, не содержащей операций импликации и эквивален- ции, понимают равносильное преобразование, приводящее к формуле, которая:
- - либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул;
- - либо содержит меньшее число вхождений переменных.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (законы поглощения, склеивания, де Моргана).
Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул.
Пример 1.
(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с ее инверсией и правило операций с константами).
Пример 2.
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с ее инверсией).
Пример 3. Какое логическое выражение равносильно выражению
По правилу де Моргана выполним преобразование
Пользуясь правилом двойного отрицания, в итоге получаем:
, следовательно, правильный ответ 2.
Контрольные вопросы и задания
- 1. Расскажите о правилах двоичной арифметики.
- 2. Прямой, обратный и дополнительный коды числа - поясните разницу между ними.
- 3. Какая связь существует между двоичным кодированием и алгеброй логики?
- 4. Какие элементарные логические функции и логические элементы вы знаете? Приведите в качестве примеров их таблицы истинности.
- 5. Выполните сложение следующих чисел:
6. Выполните вычитание следующих чисел:
- 7. Опишите связь между алгеброй логики и двоичным кодированием. Приведите примеры логических высказываний.
- 8. Что такое таблица истинности?
- 9. Дайте характеристику логической функции НЕ. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции НЕ.
- 10. Дайте характеристику логической функции И. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции И.
- 11. Дайте характеристику логической функции ИЛИ. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции ИЛИ.
- 12. Расскажите о логической операции «импликация». Приведите ее таблицу истинности.
- 13. Какое логическое высказывание эквивалентно выражению -i (A v -iB д С)?
14. Дан фрагмент таблицы истинности выражения F.
АРИФМЕТИЧЕСКИЕ И ЛОГИЧЕСКИЕ ОСНОВЫ РАБОТЫ КОМПЬЮТЕРА
АРИФМЕТИЧЕСКИЕ ОСНОВЫ ЭВМ
В настоящее время в обыденной жизни для кодирования числовой информации используется десятичная система счисления с основанием 10, в которой используется 10 элементов обозначения: числа 0, 1, 2, … 8, 9. В первом (младшем) разряде указывается число единиц, во втором - десятков, в третьем - сотен и т.д.; иными словами, в каждом следующем разряде вес разрядного коэффициента увеличивается в 10 раз.
В цифровых устройствах обработки информации используется двоичная система счисления с основанием 2, в которой используется два элемента обозначения: 0 и 1. Веса разрядов слева направо от младших разрядов к старшим увеличиваются в 2 раза, то есть имеют такую последовательность: 8421.
В общем виде эта последовательность имеет вид:
…252423222120,2-12-22-3…
и используется для перевода двоичного числа в десятичное.
Например, двоичное число 101011 эквивалентно десятичному числу 43:
25·1+24·0+23·1+22·0+21·1+20·1=43
В цифровых устройствах используются специальные термины для обозначения различных по объёму единиц информации: бит, байт, килобайт, мегабайт и т.д.
Бит или двоичный разряд определяет значение одного какого-либо знака в двоичном числе. Например, двоичное число 101 имеет три бита или три разряда. Крайний справа разряд, с наименьшим весом, называется младшим, а крайний слева, с наибольшим весом, - старшим.
Байт определяет 8-разрядную единицу информацию, 1 байт=23 бит, например, 10110011 или 01010111 и т.д., 1 кбайт = 210 байт, 1 Мбайт = 210 кбайт = 220 байт.
Для представления многоразрядных чисел в двоичной системе счисления требуется большое число двоичных разрядов. Запись облегчается, если использовать шестнадцатеричную систему счисления.
Основанием шестнадцатеричной системы счисления является число 16=24, в которой используется 16 элементов обозначения: числа от 0 до 9 и буквы A, B, C, D, E, F.
Для перевода двоичного числа в шестнадцатеричное достаточно двоичное число разделить на четырёхбитовые группы: целую часть справа налево, дробную - слева направо от запятой. Крайние группы могут быть неполными.
Каждая двоичная группа представляется соответствующим шестнадцатеричным символом (таблица 1). Например, двоичное число 0101110000111001 в шестнадцатеричной системе выражается числом 5C39.
Таблица 1
Пользователю наиболее удобна десятичная система счисления. Поэтому многие цифровые устройства, работая с двоичными числами, осуществляют приём и выдачу пользователю десятичных чисел. При этом применяется двоично-десятичный код.
Двоично-десятичный код образуется заменой каждой десятичной цифры числа четырёхразрядным двоичным представлением этой цифры в двоичном коде (см. таблицу 1). Например, число 15 представляется как 00010101 BCD (Binary Coded Decimal). При этом в каждом байте располагаются две десятичные цифры. Заметим, что двоично-десятичный код при таком преобразовании не является двоичным числом, эквивалентным десятичному числу.
ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ
Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.
Что же собой представляет алгебра логики? Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два значения: 0, либо 1.
Что такое простое логическое высказывание? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.
ЛОГИЧЕСКИЕ ОПЕРАЦИИ.
ДИЗЪЮНКЦИЯ, КОНЪЮНКЦИЯ И ОТРИЦАНИЕ
Так как же связываются между собой простые логические высказывания, образуя сложные? В естественном языке мы используем различные союзы и другие части речи. Например, «и», «или», «либо», «не», «если», «то», «тогда». Пример сложных высказываний: «у него есть знания и навыки», «она приедет во вторник, либо в среду», «я буду играть тогда, когда сделаю уроки», «5 не равно 6». Как мы решаем, что нам сказали правду или нет? Как-то логически, даже где-то неосознанно, исходя из предыдущего жизненного опыта, мы понимает, что правда при союзе «и» наступает в случае правдивости обоих простых высказываний. Стоит одному стать ложью и все сложное высказывание будет лживо. А вот, при связке «либо» должно быть правдой только одно простое высказывание, и тогда все выражение станет истинным.
Булева алгебра переложила этот жизненный опыт на аппарат математики, формализовала его, ввела жесткие правила получения однозначного результата. Союзы стали называться здесь логическими операторами.
Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем.
Такими операциями являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Часто конъюнкцию обозначают &, дизъюнкцию - ||, а отрицание - чертой над переменной, обозначающей высказывание.
Название логической операции Логическая связка
Инверсия «не»;
«неверно, что»
Конъюнкция «и»; «а»; «но»; «хотя»
Дизъюнкция «или»
Конъюнкция
Рассмотрим два высказывания:
A = «Основоположником алгебры логики является Джордж Буль»,
B = «Исследования Клода Шеннона позволили применить алгебру логики в вычислительной технике».
Очевидно, новое высказывание «Основоположником алгебры логики является Джордж Буль, и исследования Клода Шеннона позволили применить алгебру логики в вычислительной технике» истинно только в том случае, когда одновременно истинны оба исходных высказывания.
Конъюнкция - логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.
Конъюнкцию также называют логическим умножением.
При конъюнкции истина сложного выражения возникает лишь в случае истинности всех простых выражений, из которых состоит сложное. Во всех остальных случаях сложное выражение будет ложно.
Для записи конъюнкции используются следующие знаки: И,ˆ,⋅,&.
Например: A И B, AˆB, A⋅B, A&B.
Конъюнкцию можно описать в виде таблицы, которую называют таблицей истинности:
A B A B
1 1 1
1 0 0
0 1 0
0 0 0
В таблице истинности перечисляются все возможные значения исходных высказываний (столбцы A и B), причём соответствующие им двоичные числа, как правило, располагают в порядке возрастания: 00, 01, 10, 11. В последнем столбце записан результат выполнения логической операции для соответствующих операндов.
Дизъюнкция
Рассмотрим два высказывания:
A = «Идея использования в логике математической символики принадлежит Готфриду Вильгельму Лейбницу»,
B = «Лейбниц является основоположником бинарной арифметики».
Очевидно, новое высказывание «Идея использования в логике математической символики принадлежит Готфриду Вильгельму Лейбницу или Лейбниц является основоположником бинарной арифметики» ложно только в том случае, когда одновременно ложны оба исходных высказывания.
Дизъюнкция - логическая операция, которая каждым двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.
Дизъюнкцию также называют логическим сложением.
При дизъюнкции истина сложного выражения наступает при истинности хотя бы одного входящего в него простого выражения или двух сразу. Бывает, что сложное выражение состоит более, чем из двух простых. В этом случае достаточно, чтобы одно простое было истинным и тогда все высказывание будет истинным.
Для записи дизъюнкции используются следующие знаки: ИЛИ; V;|;+.
Например: A ИЛИ B; A∨B; A|B; A+B.
Дизъюнкция определяется следующей таблицей истинности:
A B A B
0 0 0
0 1 1
1 0 1
1 1 1
Инверсия
Инверсия - логическая операция, которая каждому высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному.
Инверсию также называют логическим отрицанием.
Отрицание – это унарная операция, т.к выполняется по отношению к одному простому выражению или по отношению к результату сложного. В результате отрицания получается новое высказывание, противоположное исходному.
Для записи инверсии используются следующие знаки: НЕ;¬;−Например: НЕ А; ¬А; А−.
Инверсия определяется следующей таблицей истинности:
A A0 0
0 1
1 0
1 1
Отрицанием высказывания «У меня дома есть компьютер» будет высказывание «Неверно, что у меня дома есть компьютер» или, что в русском языке то же самое, что «У меня дома нет компьютера».
Отрицанием высказывания «Я не знаю китайский язык» будет высказывание «Неверно, что я не знаю китайский язык» или, что в русском языке: «Я знаю китайский язык».
Отрицанием высказывания «Все юноши 8-х классов – отличники» является высказывание «Неверно, что все юноши 8-х классов – отличники», другими словами, «Не все юноши 8-х классов – отличники».
Таким образом, при построении отрицания к простому высказыванию либо используется речевой оборот «неверно, что...», либо отрицание строится к сказуемому, тогда к соответствующему глаголу добавляется частица «не».
Любое сложное высказывание можно записать и виде логического выражения – выражения, содержащего логические переменные, знаки логических операций и скобки.
Логические операции в логическом выражении выполняются в следующей очерёдности: инверсия, конъюнкция, дизъюнкция.
Изменить порядок выполнения операций можно с помощью расстановки скобок.
Логические операции при выполнении имеют следующий приоритет: инверсия, конъюнкция, дизъюнкция.
Таблицы истинности
Логические операции удобно описывать так называемыми таблицами истинности, в которых отражают результаты вычислений сложных высказываний при различных значениях исходных простых высказываний. Простые высказывания обозначаются переменными (например, A и B).
ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА
В ЭВМ используются различные устройства, работу которых прекрасно описывает алгебра логики. К таким устройствам относятся группы переключателей, триггеры, сумматоры.
Кроме того, связь между булевой алгеброй и компьютерами лежит и в используемой в ЭВМ системе счисления. Как известно она двоичная. Поэтому в устройствах компьютера можно хранить и преобразовывать как числа, так и значения логических переменных.
Переключательные схемы
В ЭВМ применяются электрические схемы, состоящие из множества переключателей.
Переключатель может находиться только в двух состояниях: замкнутом и разомкнутом. В первом случае – ток проходит, во втором – нет. Описывать работу таких схем очень удобно с помощью алгебры логики. В зависимости от положения переключателей можно получить или не получить сигналы на выходах.
Вентили, триггеры и сумматоры
Вентиль представляет собой логический элемент, который принимает одни двоичные значения и выдает другие в зависимости от своей реализации. Так, например, есть вентили, реализующие логическое умножение (конъюнкцию), сложение (дизъюнкцию) и отрицание.Триггеры и сумматоры – это относительно сложные устройства, состоящие из более простых элементов – вентилей.
Триггер способен хранить один двоичный разряд, за счет того, что может находиться в двух устойчивых состояниях. В основном триггеры используется в регистрах процессора.
Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.
Логические элементы. Вентили
В основе построения компьютеров, а точнее аппаратного обеспечения, лежат так называемые вентили. Они представляют собой достаточно простые элементы, которые можно комбинировать между собой, создавая тем самым различные схемы.
Одни схемы подходят для осуществления арифметических операций, а на основе других строят различную память ЭВМ.
Вентель - это устройство, которое выдает результат булевой операции от введенных в него данных (сигналов).
Простейший вентиль представляет собой транзисторный инвертор, который преобразует низкое напряжение в высокое или наоборот (высокое в низкое). Это можно представить как преобразование логического нуля в логическую единицу или наоборот. Т.е. получаем вентиль НЕ.
Соединив пару транзисторов различным способом, получают вентили ИЛИ-НЕ и И-НЕ. Эти вентили принимают уже не один, а два и более входных сигнала. Выходной сигнал всегда один и зависит (выдает высокое или низкое напряжение) от входных сигналов.
В случае вентиля ИЛИ-НЕ получить высокое напряжение (логическую единицу) можно только при условии низкого напряжении на всех входах. В случае вентиля И-НЕ все наоборот: логическая единица получается, если все входные сигналы будут нулевыми. Как видно, это обратно таким привычным логическим операциям как И и ИЛИ. Однако обычно используются вентили И-НЕ и ИЛИ-НЕ, т.к. их реализация проще: И-НЕ и ИЛИ-НЕ реализуются двумя транзисторами, тогда как логические И и ИЛИ тремя.
Выходной сигнал вентиля можно выражать как функцию от входных.
Транзистору требуется очень мало времени для переключения из одного состояния в другое (время переключения оценивается в наносекундах). И в этом одно из существенных преимуществ схем, построенных на их основе.
Сумматор и полусумматор
Арифметико-логическое устройство процессора (АЛУ) обязательно содержит в своем составе такие элементы как сумматоры. Эти схемы позволяют складывать двоичные числа.
Как происходит сложение? Допустим, требуется сложить двоичные числа 1001 и 0011. Сначала складываем младшие разряды (последние цифры): 1+1=10. Т.е. в младшем разряде будет 0, а единица – это перенос в старший разряд. Далее: 0 + 1 + 1(от переноса) = 10, т.е. в данном разряде снова запишется 0, а единица уйдет в старший разряд. На третьем шаге: 0 + 0 + 1(от переноса) = 1. В итоге сумма равна 1100.
Полусумматор
Теперь не будем обращать внимание на перенос из предыдущего разряда и рассмотрим только, как формируется сумма текущего разряда. Если были даны две единицы или два нуля, то сумма текущего разряда равна 0. Если одно из двух слагаемых равно единице, то сумма равна единицы. Получить такие результаты можно при использовании вентиля ИСКЛЮЧАЮЩЕГО ИЛИ.
Перенос единицы в следующий разряд происходит, если два слагаемых равны единице. И это реализуемо вентилем И.
Тогда сложение в пределах одного разряда (без учета возможной пришедшей единицы из младшего разряда) можно реализовать изображенной ниже схемой, которая называется полусумматором. У полусумматора два входа (для слагаемых) и два выхода (для суммы и переноса). На схеме изображен полусумматор, состоящий из вентилей ИСКЛЮЧАЮЩЕЕ ИЛИ и И.
Сумматор
В отличие от полусумматора сумматор учитывает перенос из предыдущего разряда, поэтому имеет не два, а три входа.
Чтобы учесть перенос приходится схему усложнять. По-сути она получается, состоящей из двух полусумматоров.
Рассмотрим один из случаев. Требуется сложить 0 и 1, а также 1 из переноса. Сначала определяем сумму текущего разряда. Судя по левой схеме ИСКЛЮЧАЮЩЕЕ ИЛИ, куда входят a и b, на выходе получаем единицу. В следующее ИСКЛЮЧАЮЩЕЕ ИЛИ уже входят две единицы. Следовательно, сумма будет равна 0.
Теперь смотрим, что происходит с переносом. В один вентиль И входят 0 и 1 (a и b). Получаем 0. Во второй вентиль (правее) заходят две единицы, что дает 1. Проход через вентиль ИЛИ нуля от первого И и единицы от второго И дает нам 1.
Проверим работу схемы простым сложением 0 + 1 + 1 = 10. Т.е. 0 остается в текущем разряде, и единица переходит в старший. Следовательно, логическая схема работает верно.
Работу данной схемы при всех возможных входных значениях можно описать следующей таблицей истинности.
Триггер как элемент памяти. Схема RS-триггера
Память (устройство, предназначенное для хранения данных и команд) является важной частью компьютера. Можно сказать, что она его и определяет: если вычислительное устройство не имеет памяти, то оно уже не компьютер.
Элементарной единицей компьютерной памяти является бит. Поэтому требуется устройство, способное находиться в двух состояниях, т.е. хранить единицу или ноль. Также это устройство должно уметь быстро переключаться из одного состояния в другое под внешним воздействием, что дает возможность изменять информацию. Ну и наконец, устройство должно позволять определять его состояние, т.е. предоставлять во вне информацию о своем состоянии.
Устройством, способным запоминать, хранить и позволяющим считывать информацию, является триггер. Он был изобретен в начале XX века Бонч-Бруевичем.
Разнообразие триггеров весьма велико. Наиболее простой из них так называемый RS-триггер, который собирается из двух вентилей. Обычно используют вентили ИЛИ-НЕ или И-НЕ.
RS-триггер на вентилях ИЛИ-НЕ
RS-триггер «запоминает», на какой его вход подавался сигнал, соответствующий единице, в последний раз. Если сигнал был подан на S-вход, то триггер на выходе постоянно «сообщает», что хранит единицу. Если сигнал, соответствующий единице, подан на R-вход, то триггер на выходе имеет 0. Не смотря на то, что триггер имеет два выхода, имеется в виду выход Q. (Q с чертой всегда имеет противоположное Q значение.)
Другими словами, вход S (set) отвечает за установку триггера в 1, а вход R (reset) – за установку триггера в 0. Установка производится сигналом, с высоким напряжением (соответствует единице). Просто все зависит от того, на какой вход он подается.
Большую часть времени на входы подается сигнал равный 0 (низкое напряжение). При этом триггер сохраняет свое прежнее состояние.
Возможны следующие ситуации:
Q = 1, сигнал подан на S, следовательно, Q не меняется.
Q = 0, сигнал подан на S, следовательно, Q = 1.
Q = 1, сигнал подан на R, следовательно, Q = 0.
Q = 0, сигнал подан на R, следовательно, Q не меняется.
Ситуация, при которой на оба входа подаются единичные сигналы, недопустима.
Как триггер сохраняет состояние? Допустим, триггер выдает на выходе Q логический 0. Тогда судя по схеме, этот 0 возвращается также и в верхний вентиль, где инвертируется (получается 1) и уже в этом виде передается нижнему вентилю. Тот в свою очередь снова инвертирует сигнал (получается 0), который и имеется на выходе Q. Состояние триггера сохраняется, он хранит 0.
Теперь, допустим, был подан единичный сигнал на вход S. Теперь в верхний вентиль входят два сигнала: 1 от S и 0 от Q. Поскольку вентиль вида ИЛИ-НЕ, то на выходе из него получается 0. Ноль идет на нижний вентиль, там инвертируется (получается 1). Сигнал на выходе Q становится соответствующим 1.
Существуют позиционные и непозиционные системы счисления.
В непозиционных системах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.
В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая – 7 единиц, а третья – 7 десятых долей единицы.
Сама же запись числа 757,7 означает сокращенную запись выражения
700 + 50 + 7 + 0,7 = 7 10 2 + 5 10 1 + 7 10 0 + 7 10 -1 = 757,7.
Любая позиционная система счисления характеризуется своим основанием.
За основание системы можно принять любое натуральное число - два, три, четыре и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д. Запись чисел в каждой из систем счисления с основанием q означает сокращенную запись выражения
a n-1 q n-1 + a n-2 q n-2 + ... + a 1 q 1 + a 0 q 0 + a -1 q -1 + ... + a -m q -m ,
где a i – цифры системы счисления; n и m – число целых и дробных разрядов, соответственно.
Например:
Как порождаются целые числа в позиционных системах счисления?
В каждой системе счисления цифры упорядочены в соответствии с их значениями: 1 больше 0, 2 больше 1 и т.д.
Продвинуть цифру 1 значит заменить её на 2, продвинуть цифру 2 значит заменить её на 3 и т.д. Продвижение старшей цифры (например, цифры 9 в десятичной системе) означает замену её на 0. В двоичной системе, использующей только две цифры – 0 и 1, продвижение 0 означает замену его на 1, а продвижение 1 – замену её на 0.
Целые числа в любой системе счисления порождаются с помощью Правила счета :
Применяя это правило, запишем первые десять целых чисел
· в двоичной системе: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001;
· в троичной системе: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100;
· в пятеричной системе: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14;
· восьмеричной системе: 0, 1, 2, 3, 4, 5, 6, 7, 10, 11.
Какие системы счисления используют специалисты для общения с компьютером?
Кроме десятичной широко используются системы с основанием, являющимся целой степенью числа 2 , а именно :
· двоичная (используются цифры 0, 1);
· восьмеричная (используются цифры 0, 1, ..., 7);
· шестнадцатеричная (для первых целых чисел от нуля до девяти используются цифры 0, 1, ..., 9, а для следующих чисел - от десяти до пятнадцати – в качестве цифр используются символы A, B, C, D, E, F).
Полезно запомнить запись в этих системах счисления первых двух десятков целых чисел:
|
|
Из всех систем счисления особенно проста и поэтому интересна для технической реализации в компьютерах двоичная система счисления.
Как перевести целое число из десятичной системы в любую другую позиционную систему счисления?
Пример: Перевести число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:
Ответ: 75 10 = 1 001 011 2 = 113 8 = 4B 16 .
Сложение
Таблицы сложения легко составить, используя Правило Счета.
Сложение в шестнадцатиричной системе
При сложении цифры суммируются по разрядам, и если при этом возникает избыток, то он переносится влево.
Пример 1. Сложим числа 15 и 6 в различных системах счисления.
Пример 2. Сложим числа 15, 7 и 3.
| Шестнадцатеричная: F 16 +7 16 +3 16 | Ответ: 5+7+3 = 25 10 = 11001 2 = 31 8 = 19 16 . Проверка: 11001 2 = 2 4 + 2 3 + 2 0 = 16+8+1=25, 31 8 = 3*8 1 + 1*8 0 = 24 + 1 = 25, 19 16 = 1*16 1 + 9*16 0 = 16+9 = 25. |
Пример 3. Сложим числа 141,5 и 59,75.
Ответ: 141,5 + 59,75 = 201,25 10 = 11001001,01 2 = 311,2 8 = C9,4 16
Проверка. Преобразуем полученные суммы к десятичному виду:
11001001,01 2 = 2 7 + 2 6 + 2 3 + 2 0 + 2 -2 = 201,25
311,2 8 = 3*8 2 + 1 8 1 + 1*8 0 + 2*8 -1 = 201,25
C9,4 16 = 12*16 1 + 9*16 0 + 4*16 -1 = 201,25
Вычитание
Пример 4. Вычтем единицу из чисел 10 2 , 10 8 и 10 16
Пример 5. Вычтем единицу из чисел 100 2 , 100 8 и 100 16 .
Пример 6. Вычтем число 59,75 из числа 201,25.
Ответ: 201,25 10 – 59,75 10 = 141,5 10 = 10001101,1 2 = 215,4 8 = 8D,8 16 .
Проверка. Преобразуем полученные разности к десятичному виду:
10001101,1 2 = 2 7 + 2 3 + 2 2 + 2 0 + 2 –1 = 141,5;
215,4 8 = 2*8 2 + 1*8 1 + 5*8 0 + 4*8 –1 = 141,5;
8D,8 16 = 8*16 1 + D*16 0 + 8*16 –1 = 141,5.
Умножение
Выполняя умножение многозначных чисел в различных позиционных системах счисления, можно использовать обычный алгоритм перемножения чисел в столбик, но при этом результаты перемножения и сложения однозначных чисел необходимо заимствовать из соответствующих рассматриваемой системе таблиц умножения и сложения.
| Умножение в двоичной системе | Умножение в восьмеричной системе |
Ввиду чрезвычайной простоты таблицы умножения в двоичной системе, умножение сводится лишь к сдвигам множимого и сложениям.
Пример 7. Перемножим числа 5 и 6.
Ответ: 5*6 = 30 10 = 11110 2 = 36 8 .
11110 2 = 2 4 + 2 3 + 2 2 + 2 1 = 30;
36 8 = 3 8 1 + 6 8 0 = 30.
Пример 8. Перемножим числа 115 и 51.
Ответ: 115*51 = 5865 10 = 1011011101001 2 = 13351 8 .
Проверка. Преобразуем полученные произведения к десятичному виду:
1011011101001 2 = 2 12 + 2 10 + 2 9 + 2 7 + 2 6 + 2 5 + 2 3 + 2 0 = 5865;
13351 8 = 1*8 4 + 3*8 3 + 3*8 2 + 5*8 1 + 1*8 0 = 5865.
Деление
Деление в любой позиционной системе счисления производится по тем же правилам, как и деление углом в десятичной системе. В двоичной системе деление выполняется особенно просто, ведь очередная цифра частного может быть только нулем или единицей.
Пример 9. Разделим число 30 на число 6.
Ответ: 30: 6 = 5 10 = 101 2 = 5 8 .
Пример 10. Разделим число 5865 на число 115.
Восьмеричная: 13351 8:163 8
Ответ: 5865: 115 = 51 10 = 110011 2 = 63 8 .
110011 2 = 2 5 + 2 4 + 2 1 + 2 0 = 51; 63 8 = 6*8 1 + 3*8 0 = 51.
Пример 11. Разделим число 35 на число 14.
Восьмеричная: 43 8: 16 8
Ответ: 35: 14 = 2,5 10 = 10,1 2 = 2,4 8 .
Проверка. Преобразуем полученные частные к десятичному виду:
10,1 2 = 2 1 + 2 -1 = 2,5;
2,4 8 = 2*8 0 + 4*8 -1 = 2,5.
Сложение и вычитание
При сложении обратных кодов чисел А и В имеют место четыре основных и два особых случая:
1. А и В положительные. При суммировании складываются все разряды, включая разряд знака. Так как знаковые разряды положительных слагаемых равны нулю, разряд знака суммы тоже равен нулю. Например:
Получен правильный результат.
Получен правильный результат в обратном коде. При переводе в прямой код биты цифровой части результата инвертируются: 1 0000111 = –7 10 .
Компьютер исправляет полученный первоначально неправильный результат (6 вместо 7) переносом единицы из знакового разряда в младший разряд суммы.
Полученный первоначально неправильный результат (обратный код числа –11 10 вместо обратного кода числа –10 10) компьютер исправляет переносом единицы из знакового разряда в младший разряд суммы.
При переводе результата в прямой код биты цифровой части числа инвертируются: 1 0001010 = –10 10 .
При сложении может возникнуть ситуация, когда старшие разряды результата операции не помещаются в отведенной для него области памяти. Такая ситуация называется переполнением разрядной сетки формата числа . Для обнаружения переполнения и оповещения о возникшей ошибке в компьютере используются специальные средства. Ниже приведены два возможных случая переполнения.
5. А и В положительные, сумма А+В больше, либо равна 2 n–1 , где n – количество разрядов формата чисел (для однобайтового формата n=8, 2 n–1 = 27 = 128). Например:
Семи разрядов цифровой части числового формата недостаточно для размещения восьмиразрядной суммы (162 10 = 10100010 2), поэтому старший разряд суммы оказывается в знаковом разряде. Это вызывает несовпадение знака суммы и знаков слагаемых, что является свидетельством переполнения разрядной сетки.
Здесь знак суммы тоже не совпадает со знаками слагаемых, что свидетельствует о переполнении разрядной сетки.
Все эти случаи имеют место и при сложении дополнительных кодов чисел:
1. А и В положительные. Здесь нет отличий от случая 1, рассмотренного для обратного кода.
2. А положительное, B отрицательное и по абсолютной величине больше, чем А. Например:
Получен правильный результат в дополнительном коде. При переводе в прямой код биты цифровой части результата инвертируются и к младшему разряду прибавляется единица: 1 0000110 + 1 = 1 0000111 = –7 10 .
3. А положительное, B отрицательное и по абсолютной величине меньше, чем А. Например:
Получен правильный результат. Единицу переноса из знакового разряда компьютер отбрасывает.
4. А и В отрицательные. Например:
Получен правильный результат в дополнительном коде. Единицу переноса из знакового разряда компьютер отбрасывает.
Случаи переполнения для дополнительных кодов рассматриваются по аналогии со случаями 5 и 6 для обратных кодов.
Сравнение рассмотренных форм кодирования целых чисел со знаком показывает:
· на преобразование отрицательного числа в обратный код компьютер затрачивает меньше времени, чем на преобразование в дополнительный код, так как последнее состоит из двух шагов - образования обратного кода и прибавления единицы к его младшему разряду;
· время выполнения сложения для дополнительных кодов чисел меньше, чем для их обратных кодов, потому что в таком сложении нет переноса единицы из знакового разряда в младший разряд результата.
Умножение и деление
Во многих компьютерах умножение производится как последовательность сложений и сдвигов. Для этого в АЛУ имеется регистр, называемый накапливающим сумматором, который до начала выполнения операции содержит число ноль. В процессе выполнения операции в нем поочередно размещаются множимое и результаты промежуточных сложений, а по завершении операции - окончательный результат.
Другой регистр АЛУ, участвующий в выполнении этой операции, вначале содержит множитель. Затем по мере выполнения сложений содержащееся в нем число уменьшается, пока не достигнет нулевого значения.
Для иллюстрации умножим 110011 2 на 101101 2 .
Деление для компьютера является трудной операцией. Обычно оно реализуется путем многократного прибавления к делимому дополнительного кода делителя.
Сложение и вычитание
При сложении и вычитании сначала производится подготовительная операция, называемая выравниванием порядков.
В результате выравнивания порядков одноименные разряды чисел оказываются расположенными в соответствующих разрядах обоих регистров, после чего мантиссы складываются или вычитаются.
В случае необходимости полученный результат нормализуется путем сдвига мантиссы результата влево. После каждого сдвига влево порядок результата уменьшается на единицу.
Пример 1. Сложить двоичные нормализованные числа 0.10111 2 –1 и 0.11011*2 10 . Разность порядков слагаемых здесь равна трем, поэтому перед сложением мантисса первого числа сдвигается на три разряда вправо:
Пример 2. Выполнить вычитание двоичных нормализованных чисел 0.10101*2 10 и 0.11101*2 1 . Разность порядков уменьшаемого и вычитаемого здесь равна единице, поэтому перед вычитанием мантисса второго числа сдвигается на один разряд вправо:
Результат получился не нормализованным, поэтому его мантисса сдвигается влево на два разряда с соответствующим уменьшением порядка на две единицы: 0.1101*2 0 .
Умножение
Пример 3. Выполнить умножение двоичных нормализованных чисел:
(0.11101*2 101)*(0.1001*2 11) = (0.11101*0.1001)* 2 (101+11) = 0.100000101*2 1000 .
Деление
Пример 4. Выполнить деление двоичных нормализованных чисел:
0.1111*2 100: 0.101*2 11 = (0.1111: 0.101) * 2 (100–11) = 1.1*2 1 = 0.11 2 10 .
Использование представления чисел с плавающей точкой существенно усложняет схему арифметико-логического устройства.
Упражнения
4.1. Используя Правило Счета, запишите первые 20 целых чисел в десятичной, двоичной, троичной, пятеричной и восьмеричной системах счисления.
[ Ответ ]
4.2. Какие целые числа следуют за числами:
[ Ответ ]
4.4. Какой цифрой заканчивается четное двоичное число? Какой цифрой заканчивается нечетное двоичное число? Какими цифрами может заканчиваться четное троичное число?
[ Ответ ]
4.5. Какое наибольшее десятичное число можно записать тремя цифрами:
o а) в двоичной системе;
o б) в восьмеричной системе;
o в) в шестнадцатеричной системе?
4.6. В какой системе счисления 21 + 24 = 100?
Решение. Пусть x - искомое основание системы счисления. Тогда 100 x = 1 · x 2 + 0 · x 1 + 0 · x 0 , 21 x = 2 · x 1 + 1 · x 0 , 24 x = 2 · x 1 + 4 · x 0 . Таким образом, x 2 = 2x + 2x + 5 или x 2 - 4x - 5 = 0. Положительным корнем этого квадратного уравнения является x = 5.
Ответ. Числа записаны в пятеричной системе счисления.
4.7. В какой системе счисления справедливо следующее:
o а) 20 + 25 = 100;
o б) 22 + 44 = 110?
4.8. Десятичное число 59 эквивалентно числу 214 в некоторой другой системе счисления. Найдите основание этой системы.
[ Ответ ]
4.9. Переведите числа в десятичную систему, а затем проверьте результаты, выполнив обратные переводы:
[ Ответ ]
4.10. Переведите числа из десятичной системы в двоичную, восьмеричную и шестнадцатеричную, а затем проверьте результаты, выполнив обратные переводы:
а) 125 10 ; б) 229 10 ; в) 88 10 ; г) 37,25 10 ; д) 206,125 10 .
[ Ответ ]
4.11. Переведите числа из двоичной системы в восьмеричную и шестнадцатеричную, а затем проверьте результаты, выполнив обратные переводы:
| а) 1001111110111,0111 2 ; | г) 1011110011100,11 2 ; |
| б) 1110101011,1011101 2 ; | д) 10111,1111101111 2 ; |
| в) 10111001,101100111 2 ; | е) 1100010101,11001 2 . |
[ Ответ ]
4.12. Переведите в двоичную и восьмеричную системы шестнадцатеричные числа:
а) 2СE 16 ; б) 9F40 16 ; в) ABCDE 16 ; г) 1010,101 16 ; д) 1ABC,9D 16 .
[ Ответ ]
4.13. Выпишите целые числа:
o а) от 101101 2 до 110000 2 в двоичной системе;
o б) от 202 3 до 1000 3 в троичной системе;
o в) от 14 8 до 20 8 в восьмеричной системе;
o г) от 28 16 до 30 16 в шестнадцатеричной системе.
4.14. Для десятичных чисел 47 и 79 выполните цепочку переводов из одной системы счисления в другую:
[ Ответ ]
4.15. Составьте таблицы сложения однозначных чисел в троичной и пятеричной системах счисления.
[ Ответ ]
4.16. Составьте таблицы умножения однозначных чисел в троичной и пятеричной системах счисления.
[ Ответ ]
4.17. Сложите числа, а затем проверьте результаты, выполнив соответствующие десятичные сложения:
[ Ответ ]
4.18. В каких системах счисления выполнены следующие сложения? Найдите основания каждой системы:
[ Ответ ]
4.19. Найдите те подстановки десятичных цифр вместо букв, которые делают правильными выписанные результаты (разные цифры замещаются разными буквами):
[ Ответ ]
4.20. Вычтите:
[ Ответ ]
4.21. Перемножьте числа, а затем проверьте результаты, выполнив соответствующие десятичные умножения:
| а) 101101 2 и 101 2 ; | д) 37 8 и 4 8 ; |
| б) 111101 2 и 11,01 2 ; | е) 16 8 и 7 8 ; |
| в) 1011,11 2 и 101,1 2 ; | ж) 7,5 8 и 1,6 8 ; |
| г) 101 2 и 1111,001 2 ; | з) 6,25 8 и 7,12 8 . |
[ Ответ ]
4.22. Разделите 10010110 2 на 1010 2 и проверьте результат, умножая делитель на частное.
[ Ответ ]
4.23. Разделите 10011010100 2 на 1100 2 и затем выполните соответствующее десятичное и восьмеричное деление.
[ Ответ ]
4.24. Вычислите значения выражений:
o а) 256 8 + 10110,1 2 * (60 8 + 12 10) - 1F 16 ;
o б) 1AD 16 - 100101100 2: 1010 2 + 217 8 ;
o в) 1010 10 + (106 16 - 11011101 2) 12 8 ;
o г) 1011 2 * 1100 2: 14 8 + (100000 2 - 40 8).
4.25. Расположите следующие числа в порядке возрастания:
o а) 74 8 , 110010 2 , 70 10 , 38 16 ;
o б) 6E 16 , 142 8 , 1101001 2 , 100 10 ;
o в) 777 8 , 101111111 2 , 2FF 16 , 500 10 ;
o г) 100 10 , 1100000 2 , 60 16 , 141 8 .
4.26. Запишите уменьшающийся ряд чисел +3, +2, ..., -3 в однобайтовом формате:
o а) в прямом коде;
o б) в обратном коде;
o в) в дополнительном коде.
4.27. Запишите числа в прямом коде (формат 1 байт):
а) 31; б) -63; в) 65; г) -128.
[ Ответ ]
4.28. Запишите числа в обратном и дополнительном кодах (формат 1 байт):
а) -9; б) -15; в) -127; г) -128.
[ Ответ ]
4.29. Найдите десятичные представления чисел, записанных в дополнительном коде:
а) 1 1111000; б) 1 0011011; в) 1 1101001; г) 1 0000000.
[ Ответ ]
4.30. Найдите десятичные представления чисел, записанных в обратном коде:
а) 1 1101000; б) 1 0011111; в) 1 0101011; г) 1 0000000.
[ Ответ ]
4.31. Выполните вычитания чисел путем сложения их обратных (дополнительных) кодов в формате 1 байт. Укажите, в каких случаях имеет место переполнение разрядной сетки:
| а) 9 - 2; | г) -20 - 10; | ж) -120 - 15; |
| б) 2 - 9; | д) 50 - 25; | з) -126 - 1; |
| в) -5 - 7; | е) 127 - 1; | и) -127 - 1. |
[ Ответ ]
Лекция 4. Арифметические основы компьютеров
Лекция 5. Арифметические и логические основы работы компьютера.
2.Правила создания блоксхем.
1. Алгоритмы и способы их описания.
Алгоритм - это точное предписание, которое определяет процесс, ведущий от исходных
данных к требуемому конечному результату.
Пример: правила сложения, умножения, решения алгебраических уравнений, умножения матриц и
т.п.
К сведению: Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией
арабского имени хорезмийского математика IX века альХорезми. Благодаря латинскому
переводу трактата альХорезми европейцы в XII веке познакомились с позиционной системой
счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система
счисления и правила счета в ней.
Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающийся с обработки
некоторой совокупности возможных исходных данных и направленный на получение определенных
этими исходными данными результатов. Термин вычислительный процесс распространяется и на
обработку других видов информации, например, символьной, графической или звуковой.
Основные свойства алгоритмов:
1.Результативность означает возможность получения результата после выполнения
конечного количества операций.
2. Определенность состоит в совпадении получаемых результатов независимо от
пользователя и применяемых технических средств.
3. Массовость заключается в возможности применения алгоритма к целому классу
однотипных задач, различающихся конкретными значениями исходных данных.
4. Дискретность - возможность расчленения процесса вычислений, предписанных
алгоритмом, на отдельные этапы, возможность выделения участков программы с
определенной структурой.
Для задания алгоритма необходимо описать следующие его элементы:
набор объектов, составляющих совокупность возможных исходных данных,
промежуточных и конечных результатов;
правило начала;
правило непосредственной переработки информации (описание последовательности
действий);
правило окончания;
правило извлечения результатов.
Способы описания алгоритмов:
Словесно формульный;
структурный или блок схемный;
с помощью графов схем;
с помощью сетей Петри.
При словесноформульном способе алгоритм записывается в виде текста с формулами по
пунктам, определяющим последовательность действий.
Пример: необходимо найти значение следующего выражения: у = 2а – (х+6).
Словесноформульным способом алгоритм решения этой задачи может быть записан в
следующем виде:
1. Ввести значения а и х.
2. Сложить х и 6.
3. Умножить a на 2.
4. Вычесть из 2а сумму (х+6).
5. Вывести у как результат вычисления выражения.
При блок схемном описании алгоритм изображается геометрическими фигурами
(блоками), связанными по управлению линиями (направлениями потока) со стрелками. В
блоках записывается последовательность действий.
Преимущества:
1.наглядность: каждая операция вычислительного процесса изображается отдельной
геометрической фигурой.
2.графическое изображение алгоритма наглядно показывает разветвления путей решения
задачи в зависимости от различных условий, повторение отдельных этапов
вычислительного процесса и другие детали.
К сведению: Оформление программ должно соответствовать определенным требованиям. В
настоящее время действует единая система программной документации (ЕСПД), которая
устанавливает правила разработки, оформления программ и программной документации. В
ЕСПД определены и правила оформления блоксхем алгоритмов (ГОСТ 10.00280 ЕСПД, ГОСТ
10.00380 ЕСПД).
Операции обработки данных и носители информации изображаются на схеме
соответствующими блоками. Большая часть блоков по построению условно вписана в
прямоугольник со сторонами а и b. Минимальное значение а = 10 мм, увеличение а
производится на число, кратное 5 мм. Размер b=1,5a. Для от дельных блоков допускается
соотношение между а и b, равное 1:2. В пределах одной схемы рекомендуется изображать
блоки одинаковых размеров. Все блоки нумеруются.
Виды блоков:
2.Правила создания блоксхем.
1.
Линии, соединяющие блоки и указывающие последовательность связей между ними,
2.
3.
4.
5.
6.
7.
должны проводится параллельно линиям рамки.
Стрелка в конце линии может не ставиться, если линия направлена слева направо или
сверху вниз.
В блок может входить несколько линий, то есть блок может являться преемником
любого числа блоков.
выходят две линии.
Из блока (кроме логического) может выходить только одна линия.
Логический блок может иметь в качестве продолжения один из двух блоков, и из него
Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В
случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не
ставить.
Схему алгоритма следует выполнять как единое целое, однако в случае
необходимости допускается обрывать линии, соединяющие блоки.
Структурные схемы алгоритмов:
Последовательность двух или более операций;
выбор направления;
повторение.
Любой вычислительный процесс может быть представлен как комбинация этих
элементарных алгоритмических структур.
Виды алгоритмов:
линейные;
ветвящиеся;
циклические.
В линейном алгоритме операции выполняются последовательно, в порядке их записи.
Каждая операция является самостоятельной, независимой от какихлибо условий. На схеме
блоки, отображающие эти операции, располагаются в линейной последовательности.
Линейные алгоритмы имеют место, например, при вычислении арифметических выражений,
когда имеются конкретные числовые данные и над ними выполняются соответствующие
условию задачи действия.
Пример линейного алгоритма:
Составить блок – схему алгоритма вычисления арифметического выражения
у=(b2ас):(а+с)
Алгоритм называется ветвящимся, если для его реализации предусмотрено несколько
направлений (ветвей). Каждое отдельное направление алгоритма обработки данных
является отдельной ветвью вычислений.
Ветвление в программе - это выбор одной из нескольких последовательностей команд при
выполнении программы. Выбор направления зависит от заранее определенного признака,
который может относиться к исходным данным, к
промежуточным или конечным результатам. Признак
характеризует свойство данных и имеет два или более
значений.
Ветвящийся процесс, включающий в себя две ветви,
называется простым, более двух ветвей - сложным.
Сложный ветвящийся процесс можно представить с помощью
простых ветвящихся процессов.
Направление ветвления выбирается логической проверкой, в
результате которой возможны два ответа:
1.«да» - условие выполнено
2.«нет» - условие не выполнено.
Следует иметь в виду, что, хотя на схеме алгоритма должны
быть показаны все возможные направления вычислений в
зависимости от выполнения определенного условия (или
условий), при однократном прохождении программы процесс реализуется только по одной
ветви, а остальные исключаются.
Важно! Любая ветвь, по которой осуществляются вычисления, должна приводить к
завершению вычислительного процесса.
Пример алгоритма с ветвлением:
Составить блоксхему алгоритма с ветвлением для вычисления следующего выражения:
Y = (а+b), если Х <0;
с/b, если Х>0.
Циклическими называются алгоритмы, содержащие циклы.
Цикл - это многократно повторяемый участок алгоритма.
Этапы организации цикла:
подготовка (инициализация) цикла (И);
выполнение вычислений цикла (тело цикла) (Т);
модификация параметров (М);
проверка условия окончания цикла (У).
Порядок выполнения этих этапов, например, Т и М, может изменяться.
Типы циклов:
В зависимости от расположения проверки условия окончания цикла различают циклы с
нижним и верхним окончаниями.
Для цикла с нижним окончанием (рис. а) тело цикла выполняется как минимум один раз, так
как сначала производятся вычисления, а затем проверяется условие выхода из цикла.
В случае цикла с верхним окончанием (рис. б) тело цикла может не выполниться ни разу в
случае, если сразу соблюдается условие выхода.
а б
Рис.Примеры циклических алгоритмов
Виды циклов:
Цикл называется детерминированным, если число повторений тела цикла заранее известно или
определено.
Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а
зависит от значений параметров (некоторых переменных), участвующих в вычислениях.
Пример циклического алгоритма:
Алгоритм нахождения суммы 10ти чисел
На ЭВМ могут решаться задачи различного характера, например:
научноинженерные; разработки системного программного обеспечения; обучения; управления
производственными процессами и т. д.
В процессе подготовки и решения на ЭВМ научно инженерных задач можно выделить следующие
этапы:
1.постановка задачи;
2.математическое описание задачи;
3.выбор и обоснование метода решения;
4.алгоритмизация вычислительного процесса;
5.составление программы;
6.отладка программы;
7.решение задачи на ЭВМ и анализ результатов.
В задачах другого класса некоторые этапы могут отсутствовать, например, в задачах разработки
системного программного обеспечения отсутствует математическое описание.
На данном этапе формулируется цель решения задачи и подробно описывается ее содержание.
Анализируются характер и сущность всех величин, используемых в задаче, и определяются
условия, при которых она решается.
Корректность постановки задачи является важным моментом, так как от нее в значительной
степени зависят другие этапы.
Настоящий этап характеризуется математической формализацией задачи, при которой
существующие соотношения между величинами, определяющими результат, выражаются
посредством математических формул.
Так формируется математическая модель явления с определенной точностью, допущениями и
ограничениями. При этом в зависимости от специфики решаемой задачи могут быть использованы
различные разделы математики и других дисциплин.
Математическая модель должна удовлетворять по крайней мере двум требованиям:
реалистичности и реализуемости. Под реалистичностью понимается правильное отражение
моделью наиболее существенных черт исследуемого явления.
Реализуемость достигается разумной абстракцией, отвлечением от второстепенных деталей,
чтобы свести задачу к проблеме с известным решением. Условием реализуемости является
возможность практического выполнения необходимых вычислений за отведенное время при
доступных затратах требуемых ресурсов.
Модель решения задачи с учетом ее особенностей должна быть доведена до решения при помощи
конкретных методов решения. Само по себе математическое описание задачи в большинстве
случаев трудно перевести на язык машины. Выбор и использование метода решения задачи
позволяет привести решение задачи к конкретным машинным операциям. При обосновании выбора
метода необходимо учитывать различные факторы и условия, в том числе точность вычислений,
время решения задачи на ЭВМ, требуемый объем памяти и другие.
Одну и ту же задачу можно решить различными методами, при этом в рамках каждого метода
можно составить различные алгоритмы.
На данном этапе составляется алгоритм решения задачи согласно действиям, задаваемым
выбранным методом решения. Процесс обработки данных разбивается на отдельные относительно
самостоятельные блоки, и устанавливается последовательность выполнения блоков.
Разрабатывается блоксхема алгоритма.
Контрольные вопросы:
1.Поясните понятие «алгоритм».
2.В чем состоит особенность описания алгоритмов с помощью структурной схемы и конструкций
алгоритмического языка?
3.Перечислите типовые алгоритмические конструкции и объясните их назначение.
4.Что такое исполнитель алгоритма? Что или кто может являться исполнителем алгоритма?
5.Поясните алгоритм работы исполнителя на примере роботаманипулятора или автомата
(например, автомата продажи газет).
Loading...