Дискр мат лекция 1

1.Алгебра логики

1.1.Системы счисления. Перевод чисел из одной системы

счисления в другую.

1.1.1. Позиционные системы счисления

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

Примером непозиционной системы счисления является система, основанная на римских цифрах. В этой системе имеется набор основных символов, а именно I–единица,V- пять,X - десять, L- пятьдесят, C-сто и т.д. Каждое число в этой системе представляется как комбинация таких символов. Например, число 88 в этой системе запишется так LXXXVIII. В этой системе смысл каждого символа не зависит от того, какое место занимает символ. Так, цифра X, участвуя 3 раза в написании числа, каждый раз обозначает одну и ту же величину – десять. Римские цифры встречаются на циферблатах часов, однако в математической практике они не применяются, так как арифметические операции с такими числами необычайно трудны.

Позиционные системы счисления строятся следующим образом:

выбирается

некоторое число

k – основание

системы счисления и

каждое положительное целое число N представляется в виде

многочлена

по

степеням

числа

k

с коэффициентами,

принимающими целые значения от 0 до

k

1,

т.е. в виде

N a

n

k n

a

n 1

k n 1

... a k

a

0

, 0

a

i

k

1, i 0,1,...n

(1.1)

1

Для обозначения коэффициентов разложения ai используются цифры или символы 0,1,2,…, k 1, которые называются базисными. Число N сокращенно записывают в виде N (an an 1...a1a0 )k . Для

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

Запись произвольного положительного числа x в системе счисления с основанием k определяется разложением по степеням

k

x a

n

k n

a

n 1

k n 1

... a k a

0

a

1

k 1

a

2

k 2 ...

( 1.2)

1

и имеет вид x

(an an 1...a1a0 .a 1a 2 ...)k , при этом целая и дробная

части числа разделены с помощью точки (или запятой).

В настоящее время наиболее употребительными являются десятичная, двоичная, 8-ричная и 16-ричная системы. В этих системах

счисления используются следующие цифры:
1). В десятичной системе счисления: цифры 0,1,2,3,4,5,6,7,8,9.
2)	В двоичной системе счисления: цифры 0,1.
3)	В восьмеричной системе счисления: цифры 0,1,2,3,4,5,6,7
4)	В шестнадцатеричной системе счисления: цифры
0,1, 2,3, 4,5,6,7,8,9, a, b, c, d, e, f .

В таблице 1.1 показан перевод 16 чисел из одной системы счисления

в другую для наиболее часто используемых оснований k =2, 10, 8, 16.
		Таблица 1.1.
Основание k
Числа	10		2	8	16
	0		0	0	0
	1		1	1	1
	2		10	2	2
	3		11	3	3
	4		100	4	4
	5		101	5	5
	6		110	6	6
	7		111	7	7
	8		1000	10	8
	9		1001	11	9
	10		1010	12	a
	11		1011	13	b
	12		1100	14	c
	13		1101	15	d
	14		1110	16	e
	15		1111	17	f

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

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

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

1.1.2. Перевод положительных чисел из k –ричной в

десятичную систему

Чтобы перевести число x																(an an 1...a1a0 .a 1a 2 ...)k , заданное в
k -ричной в системе,												в десятичную систему, нужно представить это
число в виде разложения (1.2)
x a		n	k n				a	n 1		k n 1		...	a k			a	0			a	1	k	1	a	2	k 2 ...
															1
и сосчитать результат. Например,
1101001 2							1 26				1 25			0		24	1 23						0	22		0	21	1 20
64				32			8			1	10510																			.
(0.11101)								1 2 1				1 2 2			1 2 3					0		2 4		1 2 5				29
						2
																												32 10
2568					2 82					5 8		6 80			128			40				6	17410
36.28					3 81					6	80	2	8 1			30.2510
fe14	16				f		163				e	162		1 16			4 160
15 163							14 162					1 16			4	65044					10
12af					1 163						2 162		10 16				15				4096			2 256				160		15	4683
16
ba.8					11 161						10 160				8 16		1			186.5
16																							10
1.1.3. Перевод целых положительных чисел из десятичной в																															k -
														ричную систему.
Чтобы							найти				представление						целого						положительного							числа	N ,
заданного							в		десятичной						системе					в			k -ричную систему нужно
представить это число в виде многочлена (1.1)
N		a		n	k n			a	n 1		k n 1 ...				a k		a	0	.
															1
Для этого							нужно найти коэффициенты																an , an 1 ,...,a1 , a0 . Разделим
число N на k										(в целых числах), остаток от деления будет равен a0 .

Далее частное от деления

N на k

разделим на k , при этом остаток

будет равен a1

a

n

k n

a

n 1

k n 1 ...

a k

a

0

k n 1

k n 2

a

0

1

a

a

...

a

n

n 1

k

1

k

a

n

k n 1

a

n

1

k n 1 ...

a

2

k

a

k n

2

k n 3

a

1

a

a

...

a

1

k

n

n 1

2

k

Продолжая

этот

процесс,

найдем

все

коэффициенты

an , an 1 ,...,a1 , a0 .

Пример 1.1.

1)

Записать число 3287 10

в восьмеричной системе

3287 | 8

[7]410 | 8

[2]51 | 8

[3][6]

3287 10		6	83	3 82		2	81	7	80
6	512	3	64	16	7		6327 8

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

2) Записать число 100 в двоичной системе

100| 2

[0]50 | 2

[0]25 | 2

[1] 12 | 2		10010 1100100 2

[0]6 | 2

[0]3 | 2

[1][1]

1.1.4.Перевод дробных чисел из десятичной в k - ричную

систему.

Пусть

x –

правильная

дробь,

заданная

в

десятичной

системе

x

0.a 1a 2 ...a n .

В

k -ричной

системе

она будет

иметь вид

x

0.b b

2

...b

m

...

,

т.е. .

x b

1

k 1 b

2

k

2

... b

m

k m

... , где

1

bi - коэффициенты, которые нужно определить. Для того чтобы найти

эти коэффициенты, нужно вначале умножить						x на	k .	Тогда целая
часть этого произведения			будет	равна	b 1 ;	дробную		часть этого
произведения	нужно	умножить		на k , целая часть полученного
произведения	определит		b 2 ,	дробную		часть		полученного
произведения	нужно	умножить		на	k и	т.д.	Этот процесс

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

требуемая точность изображения числа x в k -ричной системе. Пример 1.2. Перевести число x 0.110 в двоичную систему.

Будем обозначать целую часть числа с помощью скобок [ ], а дробную часть числа с помощью скобок { }. Тогда

b 1	[0.1 2]		0, {0.1 2}		0.2 ,	b 2	[0.2	2]	0, {0.2	2}	0.4 ,
b 3	[0.4	2]	0, {0.4	2} 0.8 ,		b 4	[0.8	2]	1, {0.8	2}	0.6
b 5	[0.6	2]	1, {0.8	2}	0.2 …Дальше			результаты			будут
повторяться. Поэтому x					(0.0001100110 011...)2 .

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

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

000, 1– 001,	2 – 010, 3 – 011, 4 –100 ,		5 –101 , 6 –110, 7 – 111.
Пример	1.3.	Записать числа	1001101 2 , 1101110110 0112 ,

заданные в двоичной системе счисления, в восьмеричной системе. Разобьем число 1001101 2 на триады, начиная с низшего разряда.

В результате получим 1001101	115	8	. Действительно,
	2

1001101				1 2	6	0	2	5		0	2		4	1 2	3	1 2		2	0	2	1 2	0
3	2	1	2	3							2									1
	1 8	2	(0	22		0 21			1 20 ) 81					(1 22			0		2	1 20 ) 80			115
																								8
	3						2												1
	Аналогично 11011101100011											2		33543		8

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

Например, 351	11101001		.
8		2

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

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

Пример 1.3. Перевести число 1001101 2 из двоичной системы

счисления в шестнадцатеричную.

Разобьем заданное число на

Тогда получим 100 11012 4d16

Действительно,

тетрады, начиная с низшего разряда.

.

1001101	2	(0	27	1 26			0	25	0	24 )
(1 23		1 22	0 21			1 20 ) (0 23 1 22 0 21 0 20 ) 161
13 160		4	16	d	16		160	4d	16
		16

Обратный переход из 16-ричной системы в двоичную осуществляется путем замены каждого шестнадцатеричного символа

соответствующей тетрадой. Например, 1d 6a16 1110101101010 2 .

1.1.7. Перевод произвольных положительных двоичных чисел в восьмеричную (шестнадцатеричную) систему и обратно.

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

цифр имеют вид: 0– 000, 1– 001, 2 – 010, 3 – 011, 4 –100 ,	5 –101 ,
6 –110, 7 – 111.

Для перевода произвольных положительных двоичных чисел в шестнадцатеричную систему необходимо целую и дробную части разбить на тетрады (группы по четыре двоичных разряда) соответственно влево и вправо от запятой, при этом недостающие разряды в тетрадах заполняются незначащими нулями. Обратный перевод числа из шестнадцатеричной в двоичную систему счисления заключается в представлении соответствующих символов шестнадцатиричной системы в виде двоичных тетрад. Двоичные тетрады шестнадцатеричных символов, используемых для обозначения базисных цифр, имеют вид: 0 – 0000, 1 – 0001, 2 – 0010, 3 – 0011, 4 – 0100, 5 – 0101, 6 – 0110, 7 – 0111, 8 – 1000, 9 – 1001, a – 1010, b – 1011, c – 1100, d – 1011, e – 1110, f – 1111.

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

Для перевода чисел, заданных в k-ричной (k 2,8,16) системе счисления, в десятичную систему с помощью Mathcad нужно ввести заданные числа в соответствующей системе. Для этого нужно после

последней цифры числа ввести соответственно буквы: b			(первую
букву слова	binary) для двоичного числа,	o (первую букву слова
octal ) для	восьмеричного числа, h	(первую букву	слова

hexadecimal ) для шестнадцатеричного числа. Тогда вывод этих чисел произойдет в десятичной системе счисления. Например,

a1	110110110.11001b		a1	438.78125		a1	4.3878125	102
a2	3745.6432o	a2	2021.81885		a2	2.0218188477		103
a3	19acde.3678h	a3	1682654.21277				a3 1.6826542128 106

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

1)General (Общий). Тогда числа будут отображаться с порядком. Количество знаков перед запятой определяется в пункте Exponential threshold (Порог экспоненты). Этот формат принят по умолчанию.

2)Decimal (Десятичный). В этом случае числа будут изображаться десятичной дробью с плавающей запятой.

3)Scientific (Научный). Тогда числа отображаются с порядком, перед запятой будет один знак.

4)Engeneering (Инженерный). В этом случае числа отображаются с порядком, кратным числу 3.

5)Fraction (Дробь). Число отображается в виде правильной или неправильной дроби.

Можно во всех форматах изменять количество знаков после запятой

(Number of decimal pieces) и порог экспоненты (Exponential threshold).

Для перевода чисел, заданных в десятичной системе счисления, в k-ричную (k 2,8,16) систему счисления с помощью Mathcad нужно

ввести заданные числа в десятичной системе. Затем с помощью пункта Format меню выбрать в раскрывающемся списке Result. В результате откроется окно Result Format. Затем нужно выбрать DisplayOptions, в котором нужно выбрать пункт Radix и в раскрывающемся списке указать нужную систему счисления (binary, octal, hexadecimal). После этого нужно нажать знак равенства. В результате будет выведено число в соответствующей системе счисления. Затем можно выбрать формат вывода этого числа.

Пример 1.5. Записать числа 2022 и 20.22 в двоичной, восьмеричной и шестнадцатеричной системах счисления с помощью

Mathcad.

2022	10b	10b1010b		2022	11111100110b
2022	3.746o		10o3o	2022	3746o

2022 7e6h

20.22

10100.01b

20.22

24.161o

20.22

14.385h

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

Перевод числа A из десятичной системы счисления соответственно в двоичную, восьмеричную и шестнадцатеричную системы осуществляется в пакете Mathematica встроенными

функциями BaseForm[A,2] , BaseForm[A,8] , BaseForm[A,16] , где

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

Shift Enter . В результате будет выведено число в соответствующей системе счисления.

Для перевода чисел K2 , L8 , M16 , заданных соответственно в двоичной, восьмеричной и шестнадцатеричной системах счисления, в десятичную систему нужно ввести эти числа в виде 2^ ^ K , 8^ ^ L , 16^ ^ M , затем нажать клавиши Shift Enter . В результате будут выведены числа в десятичной системе счисления.

Перечисленные команды можно использовать для перевода чисел из одной системы счисления в другую при обращении к www.wolframalpha.com. С помощью этой версии перевод числа A из десятичной системы счисления соответственно в двоичную, восьмеричную и шестнадцатеричную системы можно осуществить также с помощью команд A to binary, A to octal, A to hexydecimal.

Пример 1.6. Перевести числа 2022 и 20.22 в двоичную, восьмеричную, шестнадцатеричную системы счисления и числа, полученные в этих системах, перевести обратно в десятичную систему счисления с помощью пакета Mathematica.

I n [ 1 ] : = BaseForm 2022, 2

O u t [ 1 ] / / B a s e F o rm =

111111001102

I n [ 2 ] : = BaseForm 20.22, 2

O u t [ 2 ] / / B a s e F o rm =

10100.0011100001010012

Можно перевести совокупность чисел из одной системы счисления в другую:

I n [ 3 ] : =	BaseForm	2022, 20.22	, 8
O u t [ 3 ] / / B a s e F o rm =
	37468 , 24.160518
I n [ 4 ] : =	BaseForm	2022, 20.22	, 16
O u t [ 4 ] / / B a s e F o rm =

7e616 , 14.38516