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

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

Все системы счисления делятся на позиционные и непозиционные.

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

В десятичной системе используются десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; эта система имеет основанием число десять.

Любое число N в позиционной системе счисления с основанием р может быть представлена в виде полинома от основания р:

N=ак*р^к+ ак-1*р^к-1+…+ а1*р¹+ а0*р⁰+ а-1*р^-1+ а-2*р^-2+… (1.1).

здесь N — число, а — коэффициенты (цифры числа), р — основание системы счисления (р>1).

Принято представлять числа в виде последовательности цифр:

N=ак*ак-1…а1а0*а-1а-2…

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

В ЭВМ применяют позиционные системы счисления с недесятичным основанием: двоичную, восьмеричную, шестнадцатеричную.

В аппаратной основе ЭВМ лежат двухпозиционные элементы, которые находятся только в двух состояниях; одно из них обозначается 0, а другое — 1. Поэтому основной системой счисления применяемой в ЭВМ является двоичная система.

Двоичная система счисления. Используются две цифры: 0 и 1. В двоичной системе любое число может быть представлено в виде:

Х=bМ bМ-1… b1 b0* b-1 bМ-2… ,.

где bj либо 0, либо 1.

Эта запись соответствует сумме степеней числа 2, взятых с указанными коэффициентами:

Х=bМ*2^М+ bМ-1*2^М-1+…+ b1*2¹+ b0*2⁰+ b-1*2^-1+ b-2*2^-2+…

Восьмеричная система счисления. Используется восемь цифр: 0, 1, 2, 3, 4, 5, 6, 7. Употребляется в ЭВМ как вспомогательная для записи информации в сокращенном виде. Для представления одной цифры восьмеричной системы используется три двоичных разряда (триада) (таблица 2.1).

Шестнадцатеричная система счисления. Для изображения чисел употребляются 16 цифр. Первые десять цифр этой системы обозначаются цифрами от 0 до 9, а старшие шесть цифр — латинскими буквами: 10-А, 11-В, 12-С, 13-D, 14-Е, 15-F. Шестнадцатеричная система используется для записи информации в сокращенном виде. Для представления одной цифры шестнадцатеричной системы счисления используются четыре двоичных разряда (тетрада) (таблица 1).

Таблица 1. Наиболее важные системы счисления.

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

Пример:

Перевести 10 101 101.1012 «10» с.с.

10 101 101.1012 =1*27+0*26+1*25+0*24+1*23+1*22+0*21+1*20+1*2−1+0*2−2+ 1*2−3=173.62 510.

Перевести 703.048 «10» с.с.

703.048 =7*82+0*81+3*80+0*8−1+4*8−2=451.62 510.

Перевести В2Е.416 «10» с.с.

В2Е.416=11*16²+2*16¹+14*16⁰+4*16^-1=2862.2510.

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

Пример

Перевести 18 110 «8» с.с.

Результат 18 110=2658.

Перевести 62 210 «16» с.с.

Результат 62 210=26Е16.

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

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

Пример.

Перевести 0.312 510 «8» с.с.

Замечание. Конечной десятичной дроби в другой системе счисления может соответствовать бесконечная (иногда периодическая) дробь. В этом случае количество знаков в представлении дроби в новой системе берется в зависимости от требуемой точности.

Пример.

Перевести 0.6510 «2» с.с. Точность 6 знаков.

Ответ: 0,1 010 012.

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

Пример. Перевести 23.12 510 «2» с.с.

Таким образом: 2310=101 112; 0.12 510=0.0012.

Результат: 23.12 510=10 111.0012.

Необходимо отметить, что целые числа остаются целыми, а правильные дроби — дробями в любой системе счисления.

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

Пример.

Задание.

• 236. 45 688;
• 4568. 12 568;
• 8АВF.52Е16;
• 25Е2.56С16;
• 4569 °F.76Е16;
• 145АС.5В16;
• 125. 4258;
• 985. 1468;
• 2В12.48В16;
• 5987. 23 668.

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

Пример.

Перевести 1 101 111 001.11012 «8» с.с.

Перевести 11 111 111 011.1001112 «16» с.с.

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

Пример. Перевести 175.248 «16» с.с.

Двоичная арифметика.

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

Таблица 2.

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

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

Х=1101, У=101;

Х=1101, У=101, К=111;

При вычитании двоичных чисел в данном разряде при необходимости занимается из старшего разряда. Эта занимаемая 1 равна двум 1 данного разряда.

Пример. Заданы двоичные числа Х=10 010 и У=101. Вычисть Х-У.

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

Пример. 1 001 101=?

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

2. Алгебра логики. Логические связи, значения, высказывания. Логические операции. Логические схемы и логические машины

Алгебру логики называют булевой алгеброй в честь выдающегося английского математика XIX в. Джорджа Буля, который разработал ее основы.

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

В логической алгебре существуют всего три базовых логических операции:

• ? логическое отрицание (логическая операция НЕ, или инверсия),
• ? логическое умножение (логическая операция И),
• ? логическое сложение (логическая операция ИЛИ).

Логическое отрицание (инверсия)

Логическое отрицание — одна из базовых операций в алгебре логики.

Присоединение частицы НЕ к сказуемому данного высказывания, А называется инверсией или отрицанием А, при этом логическое отрицание (инверсия)обратно по значению истинности исходному.

Инверсия обычно обозначается чертой над выражением (читается «не А»).

Если высказывание, А истинно, то его отрицание ложно, и наоборот. Инверсии соответствует следующая таблица истинности:

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

Логическое умножение (конъюнкция)

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

Соединение двух (или нескольких) высказываний союзом И называетсяконъюнкцией или логическим умножением. Логическое умножение схоже с союзом И в естественном языке, если он употребляется в смысле «и то, и это». Операцию логического умножения часто называют операциейЛОГИЧЕСКОГО И.

Высказывание, А * В истинно (равно 1) тогда, когда равны 1 (истинны) обе переменных.

Конъюнкция обозначается символом, знаком умножения (*) или знаком амперсанд &.

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

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

Конъюнкция n переменных истинна тогда и только тогда, когда все составляющие ее переменные истинны.

Логическое сложение (дизъюнкция)

Логическое сложение — одна из трех базовых операций логической алгебры.

Соединение двух (или нескольких) высказываний союзом ИЛИ называетсядизъюнкцией или логическим сложением. Логическое сложение схоже с союзом ИЛИ в естественном языке, если он употребляется в смысле «или то, или это, или оба сразу». Операцию логического сложения часто называют операцией ЛОГИЧЕСКОГО ИЛИ.

Высказывание А+В истинно (равно 1) тогда, когда истинно хотя бы одно из входящих в него высказываний, А или В, и ложно только тогда, когда ложны оба слагаемых (равны 0).

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

Дизъюнкция обозначается символом v или знаком сложения (+).

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

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

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

Дизъюнкция n переменных ложна тогда и только тогда, когда все составляющие ее переменные ложны.

В логических схемах BEAM-роботов логическое ИЛИ используется для согласования двух логических сигналов.