Арифметические операции в позиционных системах счисления

Рассмотрим основные арифметические операции: сложение, вычитание, умножение и деление. Правила выполнения этих операций в десятичной системе хорошо известны — это сложение, вычитание, умножение столбиком и деление углом. Эти правила применимы и ко всем другим позиционным системам счисления. Только таблицами сложения и умножения надо пользоваться особыми для каждой системы.

С л о ж е н и е

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

Пример. Сложим числа 15 и 6 в различных системах счисления.

Шестнадцатеричная: F16+616

Ответ: 15+6 = 2110 = 101012 = 258 = 1516. Проверка. Преобразуем полученные суммы к десятичному виду: 101012 = 24 + 22 + 20 = 16+4+1=21, 258 = 2. 81 + 5. 80 = 16 + 5 = 21, 1516 = 1. 161 + 5. 160 = 16+5 = 21.

В ы ч и т а н и е

Пример. Вычтем единицу из чисел 10₂, 10₈ и 10₁₆

У м н о ж е н и е

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

Умножение в двоичной системе

Умножение в восьмеричной системе

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

Пример. Перемножим числа 5 и 6.

Ответ: 5^. 6 = 30₁₀ = 11110₂ = 36₈.
Проверка. Преобразуем полученные произведения к десятичному виду:
11110₂ = 2⁴ + 2³ + 2² + 2¹ = 30;
36₈ = 38¹ + 68⁰ = 30.

Д е л е н и е

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

Пример. Разделим число 30 на число 6.

Ответ: 30: 6 = 5₁₀ = 101₂ = 5₈.

88888888888888888888888888888888888888888888888888888888888888888888888888888888

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

Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Логическое высказывание — это любoе повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истиннo oнo или лoжнo.

Так, например, предложение " 6 — четное число" следует считать высказыванием, так как оно истинное. Предложение " Рим — столица Франции" тоже высказывание, так как оно ложное.

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения " ученик десятого класса" и " информатика — интересный предмет". Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие " интересный предмет". Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла. Предложения типа " в городе A более миллиона жителей", " у него голубые глаза" не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь.

Алгебра логики рассматривает любое высказывание только с одной точки зрения — является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание " площадь поверхности Индийского океана равна 75 млн кв. км" в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

Так, например, из элементарных высказываний " Петров — врач", " Петров — шахматист" при помощи связки " и" можно получить составное высказывание " Петров — врач и шахматист", понимаемое как " Петров — врач, хорошо играющий в шахматы".

При помощи связки " или" из этих же высказываний можно получить составное высказывание " Петров — врач или шахматист", понимаемое в алгебре логики как " Петров или врач, или шахматист, или и врач и шахматист одновременно".

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание " Тимур поедет летом на море", а через В — высказывание " Тимур летом отправится в горы". Тогда составное высказывание " Тимур летом побывает и на море, и в горах" можно кратко записать как А и В. Здесь " и" — логическая связка, А, В — логические переменные, которые мoгут принимать только два значения — " истина" или " ложь", обозначаемые, соответственно, " 1" и " 0".

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

НЕ Операция, выражаемая словом " не", называется отрицанием и обозначается чертой над высказыванием (или знаком ). Высказывание истинно, когда A ложно, и ложно, когда A истинно. Пример. " Луна — спутник Земли" (А); " Луна — не спутник Земли" ( ).

И Операция, выражаемая связкой " и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой " ^. " (может также обозначаться знаками или & ). Высказывание А ^. В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание " 10 делится на 2 и 5 больше 3" истинно, а высказывания " 10 делится на 2 и 5 не больше 3", " 10 не делится на 2 и 5 больше 3", " 10 не делится на 2 и 5 не больше 3" — ложны.

ИЛИ Операция, выражаемая связкой " или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание " 10 не делится на 2 или 5 не больше 3" ложно, а высказывания " 10 делится на 2 или 5 больше 3", " 10 делится на 2 или 5 не больше 3", " 10 не делится на 2 или 5 больше 3" — истинны.

ЕСЛИ-ТО Операция, выражаемая связками " если..., то", " из... следует", "... влечет...", называется импликацией (лат. implico — тесно связаны) и обозначается знаком . Высказывание ложно тогда и только тогда, когда А истинно, а В ложно.

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: " данный четырёхугольник — квадрат" ( А ) и " около данного четырёхугольника можно описать окружность" ( В ). Рассмотрим составное высказывание , понимаемое как " если данный четырёхугольник квадрат, то около него можно описать окружность". Есть три варианта, когда высказывание истинно:

1. А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;

2. А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);

3. A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.

Ложен только один вариант, когда А истинно, а В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

В обычной речи связка " если..., то" описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться " бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: " если президент США — демократ, то в Африке водятся жирафы", " если арбуз — ягода, то в бензоколонке есть бензин".

РАВНОСИЛЬНО Операция, выражаемая связками " тогда и только тогда", " необходимо и достаточно", "... равносильно...", называется эквиваленцией или двойной импликацией и обозначается знаком или ~. Высказывание истинно тогда и только тогда, когда значения А и В совпадают. Например, высказывания " 24 делится на 6 тогда и только тогда, когда 24 делится на 3", " 23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны, а высказывания " 24 делится на 6 тогда и только тогда, когда 24 делится на 5", " 21 делится на 6 тогда и только тогда, когда 21 делится на 3" ложны.

Высказывания А и В, образующие составное высказывание , могут быть совершенно не связаны по содержанию, например: " три больше двух" ( А ), " пингвины живут в Антарктиде" ( В ). Отрицаниями этих высказываний являются высказывания " три не больше двух" ( ), " пингвины не живут в Антарктиде" ( ). Образованные из высказываний А и В составные высказывания A B и истинны, а высказывания A и B — ложны.

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

Импликацию можно выразить через дизъюнкцию и отрицание:

А В = v В.

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А В = ( v В) ^. ( v А).

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания (" не" ), затем конъюнкция (" и" ), после конъюнкции — дизъюнкция (" или" ) и в последнюю очередь — импликация.

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

Определение логической формулы:

1. Всякая логическая переменная и символы " истина" (" 1" ) и " ложь" (" 0" ) — формулы.

2. Если А и В — формулы, то , А ^. В, А v В, А B, А В — формулы.

3. Никаких других формул в алгебре логики нет.

В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул.

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

Равносильность двух формул алгебры логики обозначается символом " =" или символом " " Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: