1)«Компьютер может производить вычисления тогда и только тогда, когда компьютер не включен».

2)«Компьютер не может производить вычисления тогда и только тогда, когда компьютер включен».

1.4.4. Основные законы логики

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

Закон тождества. Всякое высказывание тождественно самому себе: А = А.

Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно, т. е. A & ¬A = 0.

Закон исключенного третьего. Высказывание может быть ли-

бо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения и его отрицания всегда принимает значение истина, т. е. A v ¬A = 1.

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

т. е. ¬ ¬ A = A.

1.5. Позиционные системы счисления. Основные определения

Определение 1. Система счисления или нумерация – это способ записи (обозначения) чисел.

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

Определение 3. Система счисления называется позиционной, если количественный эквивалент цифры зависит от ее положения в записи числа.

14

Вдесятичной системе значение числа образуется следующим образом: значения цифр умножаются на «веса» соответствующих разрядов и все полученные значения складываются.

Например, 4945 = 4 × 1000 + 9 × 100 + 4 × 10 + 5 × 1. Такой способ образования значения числа называется аддитивномультипликативным.

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

Основное достоинство любой позиционной системы счисления

–возможность записи произвольного числа ограниченным количеством символов.

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

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

10, 2 и 8 соответственно. В общем виде базис традиционной системы счисления можно записать так: … p-2, p-1, p0, p1, p2, …pn .

Определение 6. Знаменатель p геометрической прогрессии, члены которой образуют базис традиционной системы счисления, называется основанием этой системы. Традиционные системы счисленияс основанием p иначе называют p-ичными. В p-ичных системах счисления размерность алфавита равна основанию системы счисления.

Так, алфавит десятичной системы составляют цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Алфавитом произвольной системы счисления с основанием p служат числа 0, 1, …, p-1, каждое из которых должно быть записано с помощью одного уникального символа, младшей цифрой всегда является 0.

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

15

К первым можно отнести факториальную и фибоначчиеву сис-

темы счисления, ко вторым – уравновешенные системы счисления. Такие системы называются нетрадиционными. Алфавитом фибоначчиевой системы являются цифры 0 и 1, а ее базисом последовательность чисел Фибоначчи 1, 2, 3, 8, 13, 21, 34, 55, … .

Базисом факториальной системы счисления является последовательность 1!, 2!, 3!, …, n!, … . В отношении алфавита этой системы можно сделать замечание: количество цифр, используемых

вразряде, увеличивается с ростом разряда.

Вобщем случае, если система счисления устроена таким образом, что основание как таковое в ней отсутствует, а базис

представляет собой последовательность чисел … p0, p1, … pn, …, то количество Nk цифр, используемых в k-м разряде, определяется так:

		pk −1	, если pk-1 mod pk; в противном случае Nk =	p
				k	−1
	N k = pk					+1.
				p
				k

Операция «mod» здесь означает целочисленное деление.

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

Система	Основание	Размерность		Цифры
счисления		алфавита
Двоичная	2	2		0, 1
Троичная	3	3		0, 1, 2
Восьмеричная	8	8	0, 1, 2, 3, 4, 5,
				6, 7
Шестнадцатеричная	16	16	0, 1, 2, 3, 4, 5,
			6, 7, 8, 9, A, B,
				C, D, E, F
Факториальная	Нет	Увеличивается	1	разр.: 0, 1
		с ростом но-	2	разр.: 0, 1, 2
		мера разряда	3	разр.: 0, 1, 2,
			3…
Фибоначчиева	Нет	2		0, 1

Основанием p-ичной системы счисления может быть любое натуральное число, большее единицы. Системой счисления с минимальным основанием является двоичная система, все числа в которой записываются с помощью цифр 0 и 1.

16

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

Десятичная	Факториальная	Фибоначчиева
10	120	10010
25	1001	1000101
100	4020	1000010100

1.5.1. Некоторые понятия, вопросы и ответы

1) Какое множество понятий однозначно определяет позиционную систему счисления?

•базис, алфавит, основание

•базис, алфавит

•базис.

Ответ: базис.

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

2) Какая последовательность может быть использована в качестве базиса позиционной системы счисления?

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

3) Какие символы могут использоваться в качестве цифр системы счисления?

Ответ: Любые символы.

Если основание системы счисления p меньше 10, то для символьного представления в ней, как правило, используются первые p десятичных цифр (от 0 до p-1). Например, в пятеричной системе счисления будут использоваться пять цифр: 0, 1, 2, 3, 4.

Для 10 < p < 37 в качестве первых десяти цифр также используют их десятичное представление, а для остальных цифр буквы латинского алфавита.

Для систем счисления с основаниями, большими 36, единых правил для формы записи цифр не существует.

17