Прикладная информатика (стр. 4 )

При этом пользуются следующим алгоритмом:

1) цифра в каждой позиции умножается на основание в степени на 1 меньшую, чем номер позиции;

2) полученные таким образом значения складываются.

Например:

12310 = 1*102+2*101+3*100;

1023.2810=1*103+0*102+2*101+3*100+2*10-1+8*10-2

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

1238 = 1х82+2х81+3х80=8310;

1012 = 1х22+0х21+1х20=510;

1Е316 = 1х162+14х161+3х160=48310.

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

Десятичная система счисления является однородной. Это означает, что одних и тех же символов достаточно для изображения любого числа. Но в повседневной жизни мы пользуемся и неоднородными системами счисления, и системами счисления с другим основанием. Пример тому – неметрические системы единиц (1 пуд=40 фунтов), система счета времени (1 минута = 60 секунд).

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

Обозначим через p основание системы счисления. Тогда веса позиций числа могут быть представлены следующим образом:

Таким образом, любое число X в позиционной системе счисления с основанием p можно представить в следующей развернутой форме записи:

,

или

,

где,

p – основание системы счисления;

m – количество позиций или разрядов, отведенное для изображения целой части числа;

s – количество разрядов, отведенное для изображения дробной части числа;

n=m+s – общее количество разрядов в числе,

ai – любой допустимый символ в разряде (т. е. должен принадлежать множеству {0,1,…,p-1}).

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

pp=10p

В компьютерных науках наибольшее распространение получила не десятичная, а системы счисления с основанием, кратным 2 – двоичная, восьмеричная, шестнадцатеричная.

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

Например:

=1*27+1*26+0*25+1*24+0*23+0*22+1*21+0*20=16210

В восьмеричной системе счисления допустимыми символами являются 0,1,…7.

Например:

2428=2*82+4*81+2*80=16210

В шестнадцатеричной системе допустимыми символами являются 0,1,…9,A, B,C, D,E, F.

Например:

A216=10*161+2*160=16210

3.3. Перевод чисел из одной системы счисления в другую

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

Пример 1:

13410→2-ую систему счисления. Производим деление на 2 и выписываем остатки:

Частичные частные	134	67	33	16	8	4	2	1
Остаток	0	1	1	0	0	0	0

Таким образом, 13410=

Пример 2: 42710→16-ую систему счисления. Производим деление на 16 и выписываем остатки:

Частичные частные	427	26	1
Остаток	11	10

Таким образом, 42710=1AB16

Пример 3: 318→10-ую систему счисления. Запишем 10 в восьмеричной системе:1010=128. Будем производить деление 31 на 12 в восьмеричной системе и выписывать остатки:

Частичные частные	31	2
Остаток	5

Таким образом, 318=2510

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

Пример 4:

0.13410→2-ую систему счисления

0.134*2=0.268

0.268*2=0.536

0.536*2=1.072

0.072*2=0.144

0.144*2=0.288

0.288*2=0.576

0.576*2=1.152

Таким образом, 0.13410=0.0010001…2

Пример 5:

0.0112→10-ую систему счисления

Переведем 10 в двоичную систему счисления

1010=10102

0.011*1010=11.110 целая часть соответствует 310

0.11*1010=111.10 целая часть соответствует 710

0.1*1010=101.0 целая часть соответствует 510

Таким образом, 0.0112=0.37510

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

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

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

Например:

62.7538= 0112

1D8.7A16=011 10102

=0=5C16

Аналогичные правила работаю и в общем случае.

Пусть даны системы счисления с основаниями p и q, p=qs, где s – целое число. Для перевода числа из системы с основанием p в число в систему с основанием q требуется каждую цифру исходного числа заменить на ее эквивалент в системе с основанием q. Для перевода числа из системы с основанием q в число в систему с основанием p требуется каждые s цифр исходного числа заменить на их эквивалент в системе с основанием p.

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

Сложение. Представим себе, что мы считаем 15 (или любое другое количество большее 10) предметов на пальцах. После того как мы зажмем все десять пальцев, мы откроем ладони, чтобы начать заново загибать пальцы и считать дальше. Нужно положить палочку или камень, или как-нибудь иначе отметить, что мы перешли на второй десяток. Теперь переведем все это на язык арифметики. Мы работали в десятичной системе счисления. Каждый раз, зажимая палец, мы прибавляли к тому, что было, единицу. Когда пальцев (цифр) не хватит, переносим единицу (одну палочку) в следующий разряд и начинаем считать с нуля.

0 + 1=1, 1+1=2, 2+1=3, 3+1=4, 4+1=5, 5+1=6, 6+1=7, 7+1=8, 8+1=9, 9+1=10

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

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

Сложение в троичной системе счисления имеет вид:

0 + 1 = 1 1 + 1 = 2 2 + 1 = 10

Таблица 3.3. Полная таблица сложения для двоичной системы счисления

Пример 101 + 11 1000

0	+	0	=	0
0	1	1
1	0	1
1	1	10

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

Таблица 3.4. Таблица вычитания для двоичной системы счисления

Пример 101 - 11 10

0	-	0	=	0
1	0	1
1	1	0
10	1	1

Вычитание большего числа из меньшего в двоичной системе

Чтобы из меньшего числа вычесть большее, необходимо:

1) вычесть из большего меньшее;

2) приписать к результату знак «минус».

Пример. Вычислить:

1) 111-11 = 100;

2) -100.

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

Таблица 3.5. Таблица умножения для двоичной системы счисления

Пример 101 х11 101 +101 1111

0	х	0	=	0
0	1	0
1	0	0
1	1	1

Деление. Многоразрядные числа делятся в столбик по тому же алгоритму, что и десятичные. Алгоритм для деления нацело:

1. Подбором найти число, которое при умножении на делитель дает число меньшее первых цифр делимого: 11 х 1 = 11. Записать это число в ответ.

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

Повторять операции 1 и 2, пока не кончатся все цифры в делимом.

Таблица 3.6. Таблица деления

Пример

1	:	1	=	1		1111 -11	11
101
0	1	0		011 -11
На ноль делить нельзя		0

3.5. Основные логические операции и таблицы истинности логических выражений

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

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

Пример

Высказывание «Волга впадает в Каспийское море» – истинно, его отрицание «Неверно, что Волга впадает в Каспийское море» или «Волга не впадает в Каспийское море» – ложно. Наоборот, «Дважды два равно пять» — ложно, тогда «Неверно, что дважды два равно пять» или «Дважды два не равно пять» — истинно.

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

Таблица 3.7. Таблица истинности для операции «отрицание»

(А – исходное высказывание, 1 – истина, 0 – ложь)

А	Ā
1	0
0	1

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

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

Логическим умножением (конъюнкцией) двух высказываний А и В является новое высказывание С, которое истинно только тогда, кода истинны оба высказывания. Записывается С = А Ù В или С = А&В (при этом говорят С равно А и В).

Правило истинности для конъюнкции можно представить в виде табл. 3.8.

Пример

«2 = 2 и 3 = 3». Здесь истинно каждое из простых высказываний и, следовательно, истинно полученное высказывание. Иными словами: 1) истинно, что «два равно двум»; 2) истинно, что «три равно трем», следовательно, 3) истинно, что «два равно двум и три равно трем».

Таблица 3.8. Таблица истинности для операции «конъюнкция»

(А и В – исходные высказывания, 1 – истина, 0 –ложь):

A	B	A & B
1	1	1
1	0	0
0	1	0
0	0	0

Логическим сложением (дизъюнкцией) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = АÚВ или С = А + В (при этом говорят С равно А или В).

Таблица 3.9. Таблица истинности для операции «дизъюнкция»

(А и В – исходные высказывания, 1 – истина, 0 – ложь):

A	B	A Ú B
1	1	1
1	0	1
0	1	1
0	0	0

Пример