МАТЕМАТИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРНОЙ ТЕХНИКИ

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

Компьютер предназначен для ввода, обработки, хранения и вывода информации. Любая информация в компьютерах представляется с помощью чисел. Для записи чисел используются системы счисления (десятичная, двоичная, шестнадцатеричная).

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

В непозиционной системе счисления значение каждой цифры в любом месте последовательности цифр, означающей запись числа, не изменяется. Примером непозиционной системы счисления является так называемая римская система счисления. Здесь знак I всегда означает единицу, знак V — пять, знак X — десять. Действительно, в числе XXX, записанном в римской системе счисления, цифра X в любом месте означает десять. Запись чисел в непозиционной системе счисления громоздка и неудобна. Например, число 278 в римской системе счисления запишется в виде CCLXXVIII. В особенности неудобны и сложны в таких системах арифметические действия.

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

Примером позиционной системы счисления является десятичная система счисления, которой мы пользуемся. Например, в числе 555 значение цифры 5 зависит от позиции, в которой она находится. Значение цифры 5 в разряде десятков в десять раз больше ее значения в разряде единиц и в десять раз меньше ее значения в разряде сотен.

В вычислительной технике широкое применение нашли также двоичная и шестнадцатеричная системы счисления. В двоичной системесчисления используются два символа: 0 и 1, основание системы равно 2. Двоичная система используется в компьютерах потому, что электрическими сигналами очень просто обозначить двоичные цифры: 0 - нет сигнала и 1 - есть сигнал. В десятичной системе счисления — 10 символов: от 0 до 9. В шестнадцатеричной системе счисления — 16 символов: цифры от 0 до 9 и первые шесть букв латинского алфавита (от A до F). Шестнадцатеричная система счисления просто соотносится с двоичной системой: одна шестнадцатеричная цифра соответствует четырем двоичным разрядам.

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

Задача перевода из одной системы счисления в другую часто встречается при программировании. Отдельные стандартные процедуры языков программирования Паскаль, Бейсик, HTML, Си требуют задания параметров в шестнадцатеричной системе счисления. Для непосредственного редактирования данных, записанных на жесткий диск, также необходимо умение работать с шестнадцатеричными числами. Отыскать неисправность в ЭВМ практически невозможно без представления о двоичной системе счисления.

Для обозначения используемой системы счисления нижним индексом указывают ее основание: 1510, 10112, 1EF9016 .

В общем случае в позиционной системе счисления с основанием Q любое число может быть представлено в виде полинома:

X=A_nQⁿ + … +A₁Q¹ + A₀Q⁰ + A_-1Q^-1 + A_-2Q^-2 + … + A_-mQ^-m , (*)

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

X = A_{n An - 1} … A₁ A₀, A_-1 A_-2 … A_-m

запятая отделяет целую часть числа от дробной.

В таблице приведены двоичные эквиваленты (тетрады) шестнадцатеричных символов:

Перевод чисел из одной системы счисления в другую

Рассмотрим правила перевода чисел из одной системы счисления в другую.

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

Контрольный пример 1.1. Перевести число 7D2,E₁₆ из шестнадцатеричной системы счисления в двоичную.

Решение.

Ответ: 7D2,E₁₆ = 11111010010,111₂.

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

Контрольный пример 1.2. Перевести число 10111110001,001₂ из двоичной системы счисления в шестнадцатеричную.

Решение.

Ответ: 10111110001,001₂ = 5F1,2₁₆.

Для перевода двоичного или шестнадцатеричного числа в десятичную систему счисления достаточно представить число в виде полинома (*), подставив в него известные коэффициенты, и вычислить сумму.

Контрольный пример 1.3. Перевести число 11011,11₂ из двоичной системы счисления в десятичную.

Решение.

11011,11 = 1*2⁴ + 1*2³ + 0*2² + 1*2¹ + 1*2⁰ + 1*2^-1 +1*2^-2 =

= 16+8+0+2+1+0,5+0,25 = 27,75

Ответ: 11011,11₂ = 27,75₁₀.

Контрольный пример 1.4. Перевести число 4A,1₁₆ из шестнадцатеричной системы счисления в десятичную.

Решение:

4А,1 = 4*16¹ + 10*16⁰ + 1*16^-1 = 64+10+0,0625 = 74,0625.

Ответ: 4А,1₁₆ = 74,0625₁₀.

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

Контрольный пример 1.5. Перевести число 25₁₀ из десятичной системы счисления в двоичную:

Решение.

Ответ: 25₁₀ = 11001₂.

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

Контрольный пример 1.6. Перевести число 177₁₀ из десятичной системы счисления в шестнадцатеричную:

Решение.

Ответ: 177₁₀ = В1₁₆.

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

Контрольный пример 1.7. Перевести правильную десятичную дробь 0,1875₁₀ в двоичную систему счисления.

Решение.

Ответ: 0,1875₁₀ = 0,0011₂

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

Контрольный пример 1.8. Перевести правильную десятичную дробь 0,47₁₀ из десятичной системы счисления в шестнадцатеричную с точностью до пяти знаков.

Решение.

Ответ: 0,47₁₀ = 0,7851Е₁₆.

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

Контрольный пример 1.9. Перевести число 9,625₁₀ из десятичной системы счисления в двоичную.

Решение.

Переведем целую часть десятичного числа в двоичную систему счисления (см. пример 5):

9₁₀ = 1001₂.

Затем переведем правильную дробь (см. пример 7):

0,625₁₀ = 0,101₂.

Ответ: 9,625₁₀ = 1001,101₂.

Контрольный пример 1.10. Перевести число 399,125₁₀ из десятичной системы счисления в шестнадцатеричную.

Решение.

Переведем целую часть десятичного числа в шестнадцатеричную систему счисления (см. пример 6):

399₁₀ = 18F₁₆.

Затем переведем правильную дробь (см. пример 8):

0,125₁₀=0,2₁₆.

Ответ: 399,125₁₀ = 18F,2₁₆

При переводе чисел из десятичной системы счисления в шестнадцатеричную и наоборот иногда применяют так называемый «двойной перевод», когда в качестве промежуточного используют двоичное число. Перевод осуществляют по схеме 10→2→ 16 или 16→2→10.

Контрольный пример 1.11. Перевести число 741,625₁₀ из десятичной системы счисления в шестнадцатеричную.

Решение.

Переведем десятичное число в двоичную систему счисления (см. пример 9):

741,625₁₀ = 1011100101,101₂.

Затем переведем полученное двоичное число в шестнадцатеричную систему счисления (см. пример 2):

1011100101,101₂ = 2Е5,А₁₆.

Ответ: 741,625₁₀ = 2E5,A₁₆.

Контрольный пример 1.12. Перевести число DC,2₁₆ из шестнадцатеричной системы счисления в десятичную.

Решение.

Переведем шестнадцатеричное число в двоичную систему счисления (см. пример 1):

DC,2₁₆ = 11011100,001₂.

Затем полученное двоичное число переведем в десятичную систему счисления (см. пример 3):

11011100,001₂ = 200,125₁₀.

Ответ: DC,2₁₆ = 200,125₁₀.

Арифметические основы работы ЭВМ

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

Правила выполнения арифметических действий над двоичными числами можно свести в таблицу:

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

В реальных ЭВМ чаще всего используются 16-, 32- и 64-разрядные числа. Однако для учебных целей при рассмотрении методов выполнения арифметических операций не будем обращать внимание на разрядность операндов (т. е. будем использовать разрядность, отличающуюся от разрядности реальных ЭВМ).

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

Контрольный пример 1.13. Выполнить операцию арифметического сложения двоичных чисел 110111,01₂ и 10011,1₂.

Решение.

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

Умножение двоичных чисел производится путем образования частичных произведений и последующего их суммирования. Каждое частичное произведение равно 0, если в соответствующем разряде множителя стоит 0, или равно множимому, сдвинутому на соответствующее число разрядов влево, если в разряде множителя стоит 1.

Контрольный пример 1.14. Перемножить двоичные числа 111,1₂ и 101₂.

Решение.

Как и в предыдущем случае, в качестве проверки используем десятичные числа, соответствующие исходным двоичным.

В рассмотренном примере второй разряд множителя равен 0, поэтому второе частичное произведение также равно 0.

Логические основы работы ЭВМ

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

Булева алгебра оперирует логическими переменными, которые могут принимать только два значения: истина или ложь, обозначаемые соответственно 1 и 0.

Основной системой счисления ЭВМ является двоичная система счисления, в которой также используются только две цифры: 1 и 0. Таким образом, одни и те же цифровые устройства ЭВМ могут применяться для обработки как числовой информации в двоичной системе счисления, так и логических переменных. Это обуславливает универсальность схемной реализации процесса обработки информации в ЭВМ.

Широкое распространение имеют следующие логические операции: И (логическое умножение), ИЛИ (логическое сложение), НЕ(отрицание). В вычислительной технике они обозначаются соответственно AND (или ˄ ), OR (или ˅ ), NOT (или ˉ ). С помощью этих трех операций можно представить сколь угодно сложную логическую операцию (логическую функцию). Числа, участвующие в логической операции, называются операндами. Операции И, ИЛИ — двухоперандовые. Операция НЕ — однооперандовая.

Рассмотрим пять основных операций алгебры логики.

1. Операция отрицания. Отрицанием утверждения А называется утверждение, которое ложно, если А истинно, и истинно, если А ложно. Отрицание обозначается Ᾱ (читается «не А»). Связь между значением истинности для утверждений А и Ᾱ можно выразить с помощью следующей таблицы истинности для отрицания:

Из первой строки таблицы видно, что Ᾱ ложно, если А истинно. Вторая строка устанавливает, что Ᾱ истинно, если А ложно.

Контрольный пример 1.15. Рассмотрим высказывание:

А= {Город Нью-Йорк — столица США}.

Отрицанием этого высказывания будет высказывание

Ᾱ ={Город Нью-Йорк не является столицей США}.

Было бы ошибкой считать отрицанием высказывания А высказывание

В = {Город Вашингтон — столица США}.

Контрольный пример 1.16. Записать результат выполнения логической операции .

Ответ: .

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

2. Операция дизъюнкции. Дизъюнкцией утверждений A и B называется утверждение, которое истинно, если истинно хотя бы одно из утверждений A и B, и ложно, когда A и B ложны одновременно. Дизъюнкция обозначается символом A ˅ B (читается «A или B») и определяется следующей таблицей истинности:

Контрольный пример 1.17. Даны два высказывания:

А = {Завтра первый урок литература} и

В= {Завтра первый урок математика}.

Дизъюнкция этих высказываний:

A ˅ B = {Завтра первый урок литература или математика}

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

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

Контрольный пример 1.18. Логически сложить два двоичных числа 10100010₂ и 1111₂.

Решение.

Ответ: 10100010 ˅ 1111=10101111.

3. Операция конъюнкции. Конъюнкцией утверждений A и B называется утверждение, которое истинно, если истинны оба утверждения A и B, и ложно – в противном случае, т.е. когда хотя бы одно из утверждений ложно. Конъюнкция обозначается символом A ˄ B (читается «A и B») и определяется следующей таблицей истинности:

Контрольный пример 1.19. Пусть даны высказывания:

А = {Петя не любит математику} и

В = {Петя любит физику}.

Конъюнкция A ˄ B = {Петя не любит математику и любит физику} истинна только тогда, когда Петя любит физику, а математику не любит. В остальных трех случаях, т. е. когда Петя:

а) не любит математику и не любит физику,

б) любит математику и физику,

в) любит математику, но не любит физику высказывание A ˄ B ложно.

Для образования конъюнкции в русском языке используются союзы и, а, но, хотя, однако.

Контрольный пример 1.20. Логически перемножить два двоичных числа 11110011₂ и 111111₂.

Решение.

Ответ: 11110011 ˄ 111111 = 110011.

4. Операция эквиваленции. Эквивалентность двух утверждений A и B истинна тогда и только тогда, когда A и B оба истинны или ложны и обозначается А ~ В.

Контрольный пример 1.21. Рассмотрим два высказывания:

А = {На Марсе будут обнаружены бактерии} и

В = {Сочи станет олимпийской столицей}.

Эквиваленцией этих двух высказываний является высказывание

А ~ В = {На Марсе будут обнаружены бактерии в том и только в том случае, если Сочи станет олимпийской столицей}.

Это высказывание истинно, если:

а) на Марсе будут обнаружены бактерии, и Сочи действительно станет олимпийской столицей;

б) на Марсе не будут обнаружены бактерии, а Сочи не станет олимпийской столицей,

и ложно, если:

в) на Марсе будут найдены бактерии, но олимпийской столицей Сочи не станет;

г) на Марсе не найдут бактерий, а Сочи будет олимпийской столицей.

Для образования эквиваленции используются слова «в том и только в том случае», «тогда и только тогда» и другие.

5. Операция импликации. Импликацией от утверждения А к утверждению В называется утверждение, которое ложно, когда А истинно, а В ложно, и истинно во всех других случаях. Утверждение А называют посылкой, а утверждение B – заключением импликации. Импликация обозначается символом (читается: «из А следует В», « А влечет В», «если А, то В»,) и определяемое следующей таблицей истинности:

	А	В

Контрольный пример 1.22.Даны два ложных высказывания:

A = {Число 3 является делителем числа 17} и

B = {Число 6 – простое число}.

Высказывание ={Если число 3 – делитель 17, то 6 – простое число} истинно (согласно строке 4 таблицы истинности для импликации).

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

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

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

Контрольный пример 1.23. Составить таблицу истинности для высказывания:

.

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

А	В

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

.

Наряду с тождественно-истинными высказываниями существуют высказывания тождественно-ложные, т.е. ложные всегда, независимо от того, истинны или ложны составляющие их высказывания. Тождественно-ложные высказывания обозначают латинской буквой L.

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

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

Наиболее важными «тождествами» алгебры высказываний являются следующие:

1. Закон двойного отрицания

;

2. Коммутативность дизъюнкции

;

3. Коммутативность конъюнкции

;

4. Ассоциативность дизъюнкции

;

5. Ассоциативность конъюнкции

;

6. Первый дистрибутивный закон

;

7. Второй дистрибутивный закон

;

8. Законы де Моргана

, ;

9. Законы идемпотентности

, .

10. Законы, включающие тождественно-истинные (I) и тождественно-ложные (L) высказывания

,

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

Контрольный пример 1.23. Доказать равносильность

Используя законы де Моргана, можем записать

Согласно закону двойного отрицания, получаем

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

Ассоциативность дизъюнкции позволяет опустить две пары скобок

учитывая законы пункта 10: и окончательно получаем

Контрольный пример 1.24. Упростить высказывание

Так как

, , ,

то предложенное высказывание равносильно высказыванию , т.е. является тождественно-ложным.