- •Системы счисления.
- •I. Алгоритм перевода целого числа Aq из q-ичной системы счисления в число Bd d-ичной системы.
- •II Алгоритм перевода целого числа Ad из d-ичной системы счисления в число Bq q-ичной системы.
- •III Алгоритм перевода правильных дробей из q-ичной системы счисления в d -ичную.
- •IV Алгоритм перевода правильных дробей из d-ичной системы счисления в q-ичную.
- •Переключательные функции.
- •Булевы формулы.
- •Полнота систем булевых функций
- •Алгебра Жигалкина
- •Формальная логика. Исчисление высказываний и предикатов.
- •Теория категорических суждений.
- •Формальная аксиоматическая теория - ив и ип.
Системы счисления.
Непозиционные системы счисления. Римская система счисления.
1 – I; 5 – V; 10 – X; 50 – L; 100 – C; 500 – D; 1000 – M.
Правило получения значения числа в современной Римской системе: если меньшая цифра стоит перед большей, то ее надо вычитать из общего значения числа, в противном случае прибавлять к общему значению числа.
Позиционная система счисления. Цифровая и многочленная формы представления числа.
d-ичные системы счисления, основание d, а цифры от 0 до d-1.
Записать число в d-ичной системе счисления означает: представить это число либо в цифровой:
Ad = (anan-1an-2...a1a0,a-1a-2…a-k)d
Либо в многочленной:
Ad = andn + an-1dn-1 + an-2dn-2 + … a1d1 + a0 + a-1d-1 + a-2d-2 + … a-kd-k.
Формах.
Взаимосвязь систем счисления. Алгоритмы перевода целых чисел и правильных дробей из одной системы счисления в другую. Алгоритм перевода чисел из d – ичной в dn –ую систему и из dn –ичной в d-ую систему.
I. Алгоритм перевода целого числа Aq из q-ичной системы счисления в число Bd d-ичной системы.
1) Присвоить результату цифру старшего разряда.
2) Если цифры закончились – stop.
3) Умножить текущее значение результата на «старое» основание q по правилам d-арифметики.
4) Прибавить цифру следующего разряда и перейти на шаг 2.
II Алгоритм перевода целого числа Ad из d-ичной системы счисления в число Bq q-ичной системы.
1) Разделить «с остатком» по правилам d-ичной арифметики число Ad на число q, записанное в d-ичной системе.
2) Если результат ≥ q, то повторить пункт 1.
3) Цифрами искомого числа Bq являются остатки от деления, выписанные так, чтобы последний остаток являлся цифрой старшего разряда.
III Алгоритм перевода правильных дробей из q-ичной системы счисления в d -ичную.
1) Цифру младшего разряда числа 0,Aq разделить на «старое» основание q по правилам d-арифметики.
2) Если цифры закончились – stop.
3) Прибавить следующую цифру исходной дроби.
4) Текущее значение результата разделить на «старое» основание q по правилам d-арифметики и перейти на шаг 2).
IV Алгоритм перевода правильных дробей из d-ичной системы счисления в q-ичную.
1) Умножить по правилам d-арифметики исходную дробь 0,Ad на «новое» ос-нование q, записанное в d-ичной системе.
2) Целую часть полученного произведения считать цифрой старшего разряда искомой дроби.
3) Если дробная часть равна 0 или достигнута требуемая точность, то stop. Иначе, дробную часть полученного произведения умножить по правилам d- арифметики на «новое» основание q, записанное в d-ичной системе и перейти на шаг 2).
Двоичная система счисления. Арифметика двоичных чисел: произведение как сложение со сдвигом, вычитание с использованием двоичного дополнения.
Таблица сложения Таблица умножения
Х |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
+ |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
10 |
Десятичным дополнением n-разрядного числа A10 называется разность 10n – A10 . Например, десятичное дополнение числа 7 – 3, числа 342 – 658.
Идея использования десятичного дополнения при вычитании основана на следующих рассуждениях. Пусть необходимо найти разность 10A− 10B. Возможны случаи:
а) A10> B10
В этом случае рассмотрим тождество
A10 -B10 =A10 + (10n – B10)- 10n,
откуда следует правило нахождения разности:
– найти десятичное дополнение к вычитаемому;
– сложить найденное дополнение и уменьшаемое;
– зачеркнуть единицу старшего разряда и вместо нее поставить знак «+»
б) A10< B10.
В этом случае используем тождество
A10 – A10 = - (10n – A10 – (10n – B10)), или, если через C10 обозначить сумму A10 + (10n - B10), получим
A10 - B10 = -(10n – C10).
Отсюда следует что искомая разность есть десятичное дополнение к числу C10 взятое со знаком «-».
Алгоритм вычитания целых десятичных чисел
Шаг 1. Уравнять число разрядов в числах A10 и B10 , приписав впереди требуемое число нулей.
Шаг2. Найти десятичное дополнение вычитаемого C10=(10n – B10)
Шаг3. Найти сумму A10 + C10= D10.
Шаг 4. Если появилась единица в дополнительном старшем разряде числа D10, то заменить ее знаком «+».В противном случае найти десятичное дополнение числа D10 и поставить перед ним знак «–».
Шаг 5. Полученное число считать искомой разностью A10− B10.
Алгоритм отыскания двоичного дополнения числа B2
Шаг 1. Все единицы числа B2 заменить на нули, а все нули – на единицы.
Шаг 2. К полученному числу по правилам двоичной арифметики прибавить 1. Чтобы получить алгоритм вычитания двоичных чисел, достаточно в приведенном выше алгоритме заменить слово «десятичный» словом «двоичный», а индекс «10» заменить индексом «2».