Множества, отображения, логика (стр. 7 )

.

Для десятичной системы р = 10; например,

5092 = .

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

0 = 02, 1 = 12,

2 = 102, 3 = 112,

4 = 1002, 5 = 1102, 6 = 1102, 7 = 1112,

8 =10002, 9 = 10012, 10 = 10102, 11 = 10112,

12 = 11002, 13 = 11012, 14 = 11102, 15 = 11112,

16 = 100002, и т.д.

Алгоритм перехода от десятичной записи натурального числа х к двоичной х = (х1х2 … хn)2 основан на вычислении остатков при многократном делении на 2. Действительно, пусть , или, равносильно, . Тогда при делении числа х на 2 частное будет равно у, а остаток — хn. При делении же числа у на 2 получится остаток  и т.д. Таким образом, полученные остатки, записанные в обратном порядке их получения, дают искомую двоичную запись числа х. Например:

 

_26 | 2

26 _13 | 2

12 _6 | 2

6 _3 | 2 2610 = 110102.

2 _1 | 2

0 0

 

Действительно, проверяя полученный результат, получаем:

110102 = 1 × 24 + 1 × 23 + 0 × 22 + 1 × 21 + 0 × 20 = 16 + 8 + 2 = 26.

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

Пример 6. Двоичное представление числа 0,312510 получается следующим образом:

´

0,3125

0

´

2

0,6250

1

´

2

0,2500 0,312510 = 0,01012.

0

´

2

0,5000

1

2

0,0000

Проверка полученного результата дает:

0,01012 = 0 × 2–1 + 1 × 2–2 + 0 × 2–3 + 1 × 2–4 =  = 0,3125.■

Если число х является смешанным, т.е. его целая часть [х] и дробная часть {x} = х – [х] отличны от нуля, то оно переводится в двоичную систему раздельно: целая часть — последовательным делением, а дробная — последовательным умножением.

Арифметические операции над числами сводятся к операциям сложения и умножения одноразрядных чисел. В двоичной системе счисления умножение задается по правилу: 0 × 0 = 0, 0 × 1 = 0, 1 × 0 = 0, 1 × 1 = 1, а сложение — по правилу: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 102. Операции над двоичными числами выполняются по правилам, аналогичным для десятичных чисел, но эти правила предельно упрощаются (особенно для умножения).

Пример 7. Десятичные операции 41 + 27 = 68 и 41 × 5 = 205 выглядят следующим образом:

 

101001

101001 101

11011 101001 .■

1000100 101001

11001101

 

Задание 3. Даны (см. табл. 2) десятичные числа a, b, c, d:

 

1) Выполните в двоичной системе вычисление по формуле:

.

2) Переведите в двоичную систему счисления с точностью до пяти знаков после запятой число: .■

Таблица 2
№	a	b	c	d	№	a	b	c	d	№	a	b	c	d	№	a	b	c	d	№	a	b	c	d
1	3	7	3	2	7	1	3	3	9	13	3	9	7	5	19	3	9	3	7	25	3	3	9	8
2	1	6	4	3	8	2	7	4	8	14	4	3	9	7	20	4	6	2	6	26	2	7	4	9
3	4	3	7	4	9	3	6	5	7	15	5	7	3	6	21	1	3	3	8	27	1	6	7	7
4	1	7	3	2	10	4	9	3	8	16	3	6	4	5	22	3	7	7	5	28	4	9	2	3
5	2	3	5	7	11	5	3	5	5	17	1	9	5	8	23	5	7	2	4	29	5	7	3	7
6	4	6	7	8	12	4	9	2	4	18	2	7	6	9	24	1	9	4	6	30	6	9	3	4

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

Соглашение. Условимся знак конъюнкции не писать, т.е. вместо  записывать просто АВ.

Данная формула приводится к ДНФ посредством: 1) законов де Моргана (отрицание должно быть только у отдельных переменных); 2) первого закона дистрибутивности; 3) тождеств: ХХ = Х, .

Пример 8.

.■

Члены ДНФ, представляющие собой элементарные конъюнкции k букв, называются минитермами k-го ранга. Так, в примере 8 член ху — минитерм второго ранга,  — минитерм третьего ранга.