Системы счисления. Алгебра логики

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

Представление информации в двоичной системе счисления

Система счисления — это система записи чисел, в которой используется специальный алфавит или определенный набор цифр.

В зависимости от того, меняется ли значение цифры от ее положения в числе, выделяют две: позиционную и непозиционную системы счисления.

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

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

Римская, в которой вместо цифр использовались латинские буквы. Используя их, можно записать любое число. При этом его значение определялось с помощью суммы и разницы цифр, из которых состояло число. Если слева от цифры находилось меньшее число, то левая цифра вычиталась из правой, а если справа цифра была меньше или равна цифре слева, то их значения суммировались. Например, число 11 записывалось как XI, а 9 – IX.

В позиционных системах значение цифры меняется вместе с ее положением в числе. Так, если взять число 234, то цифра 4 в ней означает единицы, если же рассмотреть число 243, то тут она будет уже означать десятки, а не единицы. К позиционным относятся: двоичная, восьмеричная, десятичная, шестнадцатеричная и шестидесятеричная (используемая при счете времени, к примеру, в минуте - 60 секунд, в часе - 60 минут).

В двоичной системе счисления используются всего две цифры 0 и 1. Другими словами, двойка является основанием двоичной системы счисления (аналогично у десятичной системы основание 10)

Чтобы научиться понимать числа в двоичной системе счисления, сначала рассмотрим, как формируются числа в привычной для нас десятичной системе счисления.

В десятичной системе счисления мы располагаем десятью знаками-цифрами (от 0 до 9). Когда счет достигает 9, то вводится новый разряд (десятки), а единицы обнуляются и счет начинается снова. После 19 разряд десятков увеличивается на 1, а единицы снова обнуляются. И так далее. Когда десятки доходят до 9, то потом появляется третий разряд – сотни.

Двоичная система счисления аналогична десятичной за исключением того, что в формировании числа участвуют всего лишь две знака-цифры: 0 и 1. Как только разряд достигает своего предела (т.е. единицы), появляется новый разряд, а старый обнуляется.

Перевод в двоичного числа в десятичное

Не трудно заметить, что в двоичной системе счисления длины чисел с увеличением значения растут быстрыми темпами. Как определить, что значит вот это: 10001001? Непривычный к такой форме записи чисел человеческий мозг обычно не может понять сколько это. Неплохо бы уметь переводить двоичные числа в десятичные.

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

1476 = 1000 + 400 + 70 + 6

Можно пойти еще дальше и разложить так:

1476 = 1 * 10^3 + 4 * 10^2 + 7 * 10^1 + 6 * 10^0

Посмотрите на эту запись внимательно. Здесь цифры 1, 4, 7 и 6 - это набор цифр из которых состоит число 1476. Все эти цифры поочередно умножаются на десять возведенную в ту или иную степень. Десять – это основание десятичной системы счисления. Степень, в которую возводится десятка – это разряд цифры за минусом единицы.

Аналогично можно разложить и любое двоичное число. Только основание будет равно  2:

10001001 = 1*2^7 + 0*2^6 + 0*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0

Если посчитать сумму составляющих, то в итоге мы получим десятичное число, соответствующее 10001001:

128 + 0 + 0 + 0 + 8 + 0 + 0 + 1 = 137

Т.е. число 10001001 по основанию 2 равно числу 137 по основанию 10. 

Почему двоичная система счисления так распространена? Дело в том, что двоичная система счисления – это язык вычислительной техники. Каждая цифра должна быть как-то представлена на физическом носителе. Если это десятичная система, то придется создать такое устройство, которое может быть в десяти состояниях. Это сложно. Проще изготовить физический элемент, который может быть лишь в двух состояниях (например, есть ток или нет тока). Это одна из основных причин, почему двоичной системе счисления уделяется столько внимания.

Перевод десятичного числа в двоичное

Может потребоваться перевести десятичное число в двоичное. Один из способов – это деление на два и формирование двоичного числа из остатков. Например, нужно получить из числа 77 его двоичную запись:

77 / 2 = 38 (1 остаток)

38 / 2 = 19 (0 остаток)

19 / 2 = 9 (1 остаток)

9 / 2 = 4 (1 остаток)

4 / 2 = 2 (0 остаток)

2 / 2 = 1 (0 остаток)

1 / 2 = 0 (1 остаток)

Собираем остатки вместе, начиная с конца: 1001101. Это и есть число 77 в двоичном представлении. Проверим:

1001101 = 1*2^6 + 0*2^5 + 0*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 64 + 0 + 0 + 8 + 4 + 0 + 1 = 77

Арифметические действия в двоичной системе счисления

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

Сложение двоичных чисел

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

0 + 0 = 0

0 + 1 = 1           

1 + 0 = 1            

1 + 1 = 10

1 + 1 + 1 = 11

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

Вычитание двоичных чисел

Вычитание выполняется поразрядно столбиком, начиная с младшего разряда и используя таблицы двоичного вычитания:

0 – 0 = 0

1 – 0 = 1

1 – 1 = 0

10 – 1 = 1

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

Для быстрого счета можно записать себе следующее правило, что если мы занимали у 1 (обязательно ставить точки или другие обозначения над цифрами), то остался 0, и наоборот, если занимали у 0, то теперь осталась 1. 

Умножение двоичных чисел

Умножение в двоичной системе производится по тому же принципу что и в десятичной системе счисления, при этом используется таблица двоичного умножения:

0 * 0 = 0              

0 * 1 = 0              

1 * 0 = 0              

1 * 1 = 1

Деление двоичных чисел

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

Перевод из 2-ой системы счисления в 8-ую и 16-ую

Для того, что осуществить перевод из 2 в 8-ую и 16-ую систему счисления достаточно знать таблицу триад и тетрад.

Рассмотрим способ без запоминания таблицы. 

Триада состоит из трех цифр. Максимальное число из трех цифр в 2-ой СС это 111. Переведем данное число в 10-ую систему счисления: 111 = 1*2^2+1*2^1+1*2^0 = 4 + 2 + 1. Максимальное число при сложении трех цифр может быть только 7, поскольку в 8-ой СС используются цифры от 0 до 7 (всего 8 цифр)

Теперь, учитывая, что 111 = 4+2+1, можно с легкостью сказать, что 101 это 4+0+1 и равно 5, а 110 это 4+2+0 и равно 6.

Аналогичный перевод и в 16-ую СС, только в данном случае идет разложение на тетрады. Тетрады состоят из 4 знаков и полная тетрада это 1111

Разложим 1111 = 1*2^3+1*2^2+1*2^1+1*2^0 = 8+ 4 + 2 + 1 = 15 (максимальная цифра в 16-ой СС)

В 16-ой СС используются следующие значения 0, 1 ... 9, A, B, C, D, E, F. Следовательно, 10 заменяется на A, 11 на B и т.д.

Если 1111 = 8+4+2+1, то 1100 это 8+4+0+0= 12 или С, 1010 это 8+0+2+0= 10 или А

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

Например число 11011101 необходимо перевести в 8-ую СС. Разбиваем на триады 011 011 101 (в первую триаду был добавлен 0 в начало). Получим, что 11011101 это 335 в 8-ой СС

Задания для самостоятельной работы

Вариант выбирается в зависимости от номера в списке (нечетные - 1 вариант, четные - 2 вариант)

Внимание! Переводить число нужно не последовательно, а отдельными операциями (например, в задании 1 перевод числа из 2-ой в 10-ую, из 2-ой в 8-ую, из 2-ой в 16-ую)

1 вариант

2 вариант

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

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

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

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

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

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

Например, высказывание «сумма углов треугольника равна 180 градусам» истинно, а высказывание «Рим – столица Греции» ложно. Не всякое повествовательное предложение является логическим высказыванием. Определить, истинны или ложны предложения «ученик восьмого класса» и «очень жаркое лето» нельзя. Вопросительные предложения, предложения в повелительной форме также не являются высказываниями.

Алгебра логики позволяет определять истинность или ложность составных высказываний, не вникая в их содержание. В алгебре логики для формализации работы с высказываниями их обозначают символическими именами, например, А, В, С. Тогда, если обозначить простые высказывания «Денис сделал уроки» именем А, «Денис пошел в кино» именем В, то составное высказывание «Денис сделал уроки и пошел в кино» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать логические значения «истина» или «ложь».

Базовые логические элементы реализуют три основные логические операции: «И», «ИЛИ», «НЕ».

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

Логический элемент «НЕ» (инвертор)

Простейшим логическим элементом является инвертор, выполняющий функцию отрицания. «НЕ» инвертирует значение входной двоичной переменной. Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот. У этого элемента один вход и один выход. 

Логический элемент «И» (конъюнктор)

Логический элемент «И» (конъюнктор) выдает на выходе значение логического произведения входных сигналов. Он имеет один выход и не менее двух входов. 

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

Пример. «2*2 =4 И 3*3 =10» по таблице определяем (А = 1), (В = 0), значит F = 0 – данное высказывание ложно

 Логический элемент «ИЛИ» (дизъюнктор)

Логический элемент «ИЛИ» (дизъюнктор) выдает на выходе значение логической суммы входных сигналов. Он имеет один выход и не менее двух входов. 

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

Пример: «2*2 = 4 ИЛИ 3*3 = 10» по таблице определяем (А = 1), (В = 0), значит F = 1 – данное высказывание истинно

Функциональные схемы логических элементов 

НЕ

И

ИЛИ

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

Данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.

«A → B» истинно, если из А может следовать B.

Обозначение: F = A → B

А – На улице дождь

Б – Асфальт мокрый

A → B – если на улице дождь, то асфальт мокрый = 1

A → B – если на улице дождь, то асфальт сухой = 0

Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

«A ↔ B» истинно тогда и только тогда, когда А и B равны.

Обозначение: F = A ↔ B.

Порядок выполнения действий при решении задач:

Пример задания. Для какого из значений числа X истинно выражение  (X * 2 > 10) ∧ ¬(X + 3 < 8) ∨ ¬(X  > 0) 

Решение: 

Преобразуем неравенства так, чтобы слева оставалась только переменная X.
Получим (X > 5) ∧ ¬(X < 5) ∨ ¬(X = > 0).
Далее выполним операции отрицания, получим (X > 5) ∧ (X  >= 5) ∨ (X < 0). После применения отрицания знаки меняются на противоположные и нестрогое неравенство меняется на на строгое и наоборот.  

Затем выполняется операция конъюнкции (X > 5) ∧ (X  >= 5), результатом которой будет истина только в том случае, если оба неравенства будут выполняться (истина). Это возможно только при X > 5 (общее решение для двух неравенств).  

Последней выполняется операция дизъюнкции. Для получения истины необходимо, чтобы хотя бы один из операндов был истинным: Х > 5 или X < 0. В предложенных ответах все числа положительные, но только 7>5, значит, ответ Х = 7.

Самостоятельная работа

1. Создать таблицу истинности и схему для выражения:

1, 5, 9, 13, 17, 21, 25   A^Bv-B^A

2, 6, 10, 14, 18, 22      BvA^Bv-A

3, 7, 11, 15, 19, 23      BvAv-A^B

4, 8, 12, 16, 20, 24      -BvA^(BvA) 

2. Создать таблицу истинности и по ней определить значение результата при указанных значениях:

1, 5, 9, 13, 17, 21, 25   A^BvAv-C при A=1, B=0, C=1

2, 6, 10, 14, 18, 22      -(NvC)^-B при N=1, B=0, C=1

3, 7, 11, 15, 19, 23      M^Kv(-M^C) при M=1, K=0, С=0

4, 8, 12, 16, 20, 24      MvAv-B^M при M=1, B=1, A=1

3. Упростить выражение и вычислить результат:

1, 5, 9, 13, 17, 21, 25   A^-Av1=

2, 6, 10, 14, 18, 22      AvBv-Av-B=

3, 7, 11, 15, 19, 23      A^-A^1=

4, 8, 12, 16, 20, 24      --Av-A=

4. Упростить выражение (общее для всех)