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

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

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

1.8. Логические основы вычислительной техники.
Алгебра логики. Логические функции. Базовые логические операции

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

Употребляемые в обычной речи логические связки «и», «или», «если…,то», «эквивалентность» и частица «не» позволяют из уже заданных высказываний строить новые, более «сложные» высказывания. Так, из высказываний «х > 2», «x ≤ 3» при помощи связки «и» можно получить «х > 2 и х ≤ 3», при помощи связки «или» – «х > 2 или х ≤ 3».

Истинность или ложность получаемых таким образом высказываний зависит от истинности или ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями. Для обозначения истинности вводится символ П (Правда; или 1), а для обозначения ложности – Л (Ложь; или 0). Связки «и», «или», «если…,то», «эквивалентность» и частица «не» обозначаются соответственно знаками Ù (или “логическое И”, или & – амперсанд), Ú (или “логическое ИЛИ”),→, ~ и чёрточка сверху над .

Производимые с их помощью операции над высказываниями, имеющими значения только П(1) или Л(0), называют соответственно логическими умножением (конъюнкцией), сложением (дизъюнкцией), следование (импликацией), эквивалентностью и отрицанием. Связки и частицу «не» можно рассматривать, как операции над величинами, принимающими значения «0» или «1», и результатом применения этих операций (значением перечисленных логических функций) также являются числа «0» и «1».

Введённые операции позволяют каждой формуле при заданных значениях входящих в неё высказываний приписать одно из двух значений – «0» или «1». Тем самым каждая формула может одновременно рассматриваться как некоторый способ задания или реализации функций алгебры логики, то есть таких функций, которые определены на наборах нулей и единиц и которые принимают значения тоже «0» или «1». При этом формулы называются эквивалентными, если они реализуют равные логические функции (подчеркнём, что не совпадающие, а равные по значениям). Для задания функций алгебры логики иногда используют таблицы, содержащие все наборы значений переменных и значения функций на этих наборах. Это так называемый табличный способ задания функций. Сами же таблицы в алгебре логики называют таблицами истинности. Так, например, сводная таблица истинности, задающая: логические отрицание , умножение (конъюнкцию) х Ù у, сложение (дизъюнкция) х Ú у, следование (импликацию) х → у, эквивалентность х ~ у, имеет следующий вид.

Рис. 1.8. Сводная таблицаистинности
логических операций

Поясним образование высказываний с помощью операций импликации и эквивалентности:

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

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

ТЕМА II. Технические средства реализации

информационных процессов